| Предисловие ко второму изданию | 5
|
| Из предисловия к первому изданию | 7
|
| Введение | 9
|
| ГЛАВА I. Что такое граф? | 11
|
| § 1. Спортивные состязания | 11
|
| § 2. Нуль-граф и полный граф | 13
|
| § 3. Изоморфные графы | 15
|
| § 4. Плоские графы | 19
|
| § 5. Одна задача о плоских графах | 21
|
| § 6. Число ребер графа | 26
|
| § 7. Интервальные графы | 30
|
| ГЛАВА II. Связные графы | 33
|
| § 1. Компоненты | 33
|
| § 2. Задача о кенигсбергских мостах | 35
|
| § 3. Эйлеровы графы | 37
|
| § 4. Отыскание правильного пути | 41
|
| § 5. Гамильтоновы линии | 43
|
| § 6. Головоломки и графы | 46
|
| ГЛАВА III. Деревья | 50
|
| § 1. Деревья и леса | 50
|
| § 2. Циклы и деревья | 52
|
| § 3. Задача о соединении городов | 55
|
| § 4. Снова к проблеме коммивояжера | 58
|
| § 5. Системы соединений | 60
|
| § 6. Улицы и площади | 64
|
| Г Л А В А IV. Установление соответствий | 68
|
| § 1. Задача о назначении на должности | 68
|
| § 2. Другие формулировки | 72
|
| § 3. Круговые соответствия | 76
|
| ГЛАВА V. Ориентированные графы | 81
|
| § 1. Снова спортивные состязания | 81
|
| § 2. Одностороннее движение | 83
|
| § 3. Степени вершин | 90
|
| § 4. Генеалогические графы | 92
|
| § 5. Поиск кратчайшего пути | 100
|
| ГЛАВА VI. Игры и головоломки | 105
|
| § 1. Головоломки и ориентированные графы | 105
|
| § 2. Теория игр | 108
|
| § 3. Парадокс спортивных обозревателей | 116
|
| ГЛАВА VII. Отношения | 122
|
| § 1. Отношения н графы | 122
|
| § 2. Специальные условия | 125
|
| § 3. Отношения эквивалентности | 130
|
| § 4, Частичная упорядоченность | 135
|
| ГЛАВА VIII. Плоские графы | 141
|
| § 1. Условия для плоских графов | 141
|
| § 2. Формула Эйлера | 145
|
| § 3. Некоторые соотношения для графов. Двойственные графы | 149
|
| § 4. Правильные многогранники | 152
|
| § 5. Мозаики | 157
|
| ГЛАВА IX Раскрашивание карт | 160
|
| § 1. Проблема четырех красок | 160
|
| § 2. Теорема о пяти красках | 164
|
| § 3. Раскраска карт на других поверхностях | 170
|
| Решения упражнений | 173
|
| Литература | 183
|
| Словарь основных терминов, используемых в книге | 184
|
Оре Ойстин Известный норвежский математик, специалист в области алгебры, теории чисел и теории графов. Родился в Христиании (ныне Осло). В 1922 г. окончил университет Христиании, некоторое время учился в Геттингенском университете. С 1926 г. профессор университета Осло (город был переименован в 1925 г.). Через год переехал в США и начал работать в Йельском университете. В 1945 г. вернулся в Норвегию. Был действительным членом Норвежской академии наук, Американского математического общества и Американской академии искусств и наук.
Ойстин Оре — автор более сотни статей и около десятка книг в различных областях математики. Его исследования по алгебре и математическому анализу способствовали развитию многих отраслей знания, в том числе теории информации и кибернетики. Широкую известность получили написанные им биографии выдающихся математиков Абеля и Кардано, научно-популярная книга «Приглашение в теорию чисел», а также работы в области теории графов, к которым относится и книга «Графы и их применение», многократно переиздававшаяся на многих языках мира, в том числе и на русском.
