Оpe О.ГРАФЫ И ИХ ПРИМЕНЕНИЕ. Пер. с англ. Л. И. Головиной/Под ред. И. М. Яглома. - М., 1965.
Графы — сети линий, соединяющих заданные точки, — широко используются в разных разделах математики и в приложениях.
Автором книги «Графы и их применение» является видный норвежский алгебраист Ойстин Оре. Для понимания книги вполне достаточны минимальные предварительные знания, практически не превышающие курса математики 7—8 классов средней школы.
Как при изучении любой книги по математике, овладение новыми понятиями, конечно, потребует от читателя некоторых усилий и известной настойчивости. Однако это лишь доставит удовольствие истинному любителю математики.
Оглавление
От редактора ........................................5
Введение.............................9
ГЛАВА I. Что такое граф?..............11
§ 1. Спортивные состязания ........11
§ 2. Нуль-граф и полный граф.......13
§ 3. Изоморфные графы ..........15
§ 4. Плоские графы .......... . . 19
§ 5. Одна задача о плоских графах.....21
§ 6. Число ребер графа...........26
ГЛАВА II. Связные графы...............30
§ 1. Компоненты ..............30
§ 2. Задача о кенигсбергскнх мостах .... 32
§ 3. Эйлеровы графы............31
§ 4. Отыскание правильного пути......33
§ 5. Гамильтоновы линии..........41
§ 6. Головоломки и графы .........43
ГЛАВА III. Деревья ..................47
§ 1. Деревья и леса............47
§ 2. Циклы и деревья...........49
§ 3. Задача о соединении городов.....52
§ 4. Улицы и площади...........55
ГЛАВА IV. Установление соответствий.........59
§ 1. Задача о назначении на должности . . 59
§ 2. Другие формулировки.........63
§ 3. Круговые соответствия.........67
ГЛАВА V. Ориентированные графы ..........72
§ 1. Снова спортивные состязания.....72
§ 2. Одностороннее движение .......74
§ 3. Степени вершин ........... . 81
§ 4. Генеалогические графы ........83
ГЛАВА VI. Игры и головоломки ............91
§ 1. Головоломки и ориентированные графы 91
§ 2. Теория игр ..............94
§ 3. Парадокс спортивных обозревателей . . 102
ГЛАВА VII. Отношения.................108
§ 1. Отношения и графы ..........108
§ 2. Специальные условия , . . ......111
§ 3. Отношения эквивалентности.....,116
§ 4. Частичная упорядоченность......121
ГЛАВА VIII. Плоские графы...............127
§ 1. Условия для плоских графов .... . .127
§ 2. Формула Эйлера............131
§ 3. Некоторые соотношения для графов.
Двойственные графы..........135
§ 4. Правильные многогранники ......138
§ 5. Мозаики................143
ГЛАВА IX. Раскрашивание карт............146
§ 1. Проблема четырех красок.......146
§ 2. Теорема о пяти красках........ 150
Решения упражнений ...................156
Литература ......................166
Словарь основных терминов, используемых в книге ... . . 168
