Теория графов: Пер. с англ.—М.: Мир, 1988.—424 с., ил. ISBN 5-03-001001-7
Монография крупного канадского математика, содержащая перспективные методы и конструкции современной теории графов (связность, факторизация, раскраска, планарность и др.). Многие результаты принадлежат автору, активно работающему в области комбинаторной теории. Книга вышла в известной серии «Энциклопедия математики и ее приложений», ряд томов которой издан на русском языке в издательствах «Мир» и «Наука».
Для математиков различных специальностей, инженеров-исследователей, аспирантов и студентов, специализирующихся в области дискретной математики.
ОТ ПЕРЕВОДЧИКА
Автора книги Уильяма Т. Татта представлять нет необходимости: его яркие, насыщенные своеобразными идеями исследования комбинаторных проблем известны многим математикам — геометрам, специалистам по дискретной математике, алгебраистам. Его известные монографии по связности графов и теории матроидов продолжают оказывать существенное влияние на молодых исследователей, занимающихся комбинаторной математикой.
Данная книга тоже создавалась с целью оказания действенной помощи начинающим самостоятельные изыскания математикам. В ней доходчиво и с высоким методическим мастерством освещается ряд важных направлений современной теории графов. Делается это с необходимой степенью детализации и строгости, но без стремления «объять необъятное». Тщательно отобраны и библиографические ссылки: указываются только те работы, которые либо являются непосредственными источниками излагаемых результатов, либо тесно переплетаются с излагаемым материалом. Мы не считали нужным пополнять библиографию, так как не хотели нарушать авторский замысел. Те из читателей, которых интересует более широкая панорама теории графов, могут обратиться к обзорам, появившимся за последние семь — восемь лет в «Итогах науки и техники» (см., например, т. 16, 18, 21, 23 в серии «Теория вероятностей. Математическая статистика. Теоретическая кибернетика» (М.: ВИНИТИ, 1979, 1981, 1983, 1985)).
Ряд сведений исторического характера содержится в «Предисловии» К- Нэш-Вильямса, во введении и в замечаниях автора, помещенных в конце глав. О содержании книги достаточно подробно говорится во введении, да и сама она находится в руках читателя, поэтому здесь нет необходимости останавливаться на ее содержании.
Книгу можно использовать (об этом говорится и во введении) как справочное руководство по современной теории графов. Она предназначена для математиков различных специализаций, а также для научных работников, инженеров-исследо-
Оглавление
От переводчика........ ...... . . 5
От редактора Энциклопедии .-..-•......... 7
Предисловие................ ..... 8
Введение ........ ..... .......... 13
Глава I. Графы и подграфы............... 1&
I. 1. Определения.................... 16
1.2. Изоморфизм.................... 20
1.3. Подграфы..................... 25
1.4. Соединяющие вершины................ 28
1.5. Компоненты и связность........... ... 32
I. 6. Удаление ребра.................. 36
I. 7. Перечни неизоморфных связных графов.........42
1.8. Мосты...................... 47
1.9. Замечания.................... 52
Упражнения................... 52
Литература..................... 53
Глава II. Сжатия и теорема Менгера.......... 54
II. 1. Сжатия.............. ....... 54
II. 2. Стягивание ребра................ 59
II. 3. Соединяющие вершины........ . ..... 64
II. 4. Числа разделения............ . .... 66
II. 5. Теорема Менгера................ .70
II.6. Теорема Холла................... 75
II. 7. Замечания................... 78
Упражнения.....................79
Литература.....................79
Глава III. Двусвязность • • . . •...........80
III. 1. Разделимые и двусвязные графы..........80
III. 2. Построение двусвязных графов............ 83
III. 3. Блоки......................87
III. 4. Ответвления..................92
II 1.5. Удаление и стягивание ребра............. 95
III. 6. Замечания.................... 97
Упражнения....................98
Литература....................98
Глава IV. Трехсвязность • • • • •.......-..- 99
IV. 1. m-связность............... .... 99
IV. 2. Некоторые конструкции для трехсвязных графов .... 104
IV. 3. 3-блоки...................... 115
IV. 4. Расслоения.................... 128
IV. 5. Удаление и стягивание ребер............. 141
IV. 6. Теорема о колесе................. 149
IV. 7. Замечания.................... I52
Упражнения.............. ...... 153
Литература.................... 153
Глава V. Восстановление ...-..••.......154
V. 1. Проблема восстановления............... 154
V. 2. Теория и практика.................157
V. 3. Лемма Келли....................159
V. 4. Реберное восстановление...............163
V. 5. Замечания.................... 164
Упражнения...................• 165
Литература....................165
Глава VI. Орграфы и пути.....• •........ 166
VI. 1. Орграфы.................... . 166
VI. 2. Пути......................171
VI. 3. Теорема BEST...................176
VI. 4. Матричная теорема о деревьях............182
VI. 5. Законы Кирхгофа..................188
VI. 6. Отождествление вершин...............196
VI. 7. Теория транспортных сетей............. 200
VI. 8. Замечания....................208
Упражнение....................209
Литература..................• • 209
Глава VII. Чередующиеся пути • . ........... 211
VII. 1. Курсальность дуг и ребер.............211
VII. 2. Бикурсальные подграфы..............213
VII. 3. Бикурсальные секции...............219
VII. 4. Чередующиеся барьеры.............. 221
VII. 5. f-факторы и f-барьеры............... 223
VII. 6. Теорема об f-факторе............... 227
VII. 7. Подграфы с наименьшим дефицитом.........233
VII. 8. Двудольный случай................ 235
VII. 9. Теорема Эрдёша — Галлаи...........• . 238
VII. 10. Замечания ...................239
Упражнения...................240
Литература................... 240
Глава VIII. Алгебраическая двойственность •.....242
VIII. 1. Группы цепей..................242
VIII. 2 Примитивные цепи ................ 246
VIII. 3. Регулярные группы цепей.............253
VIII. 4. Циклы..................... 257
VIII. 5. Кограницы.................. . 261
VIII. 6. Ограничения и сжатия ..............266
VIII. 7. Алгебраическая двойственность........... 268
VIII. 8. Связность................... 273
VIII. 9. О теории транспортных сетей............ 280
VIII. 10. Матрицы инцидентности . •.............282
VIII. 11. Матроиды...................284
VIII. 12. Замечания..................285
Упражнения................• . 285
Литература..................286
Глава IX. Графы и многочлены............. 287
IX. 1. У-функции....................287
IX. 2. Хроматический многочлен..............292
IX. 3. Раскраска графов..................300
IX. 4. Потоковый многочлен................3Ti
IX. 5. Реберная раскраска................309
IX. 6. Дихромат графа.................• 313
IX. 7. Несколько замечаний о восстановлении ......... 318
IX. 8, Замечания................... . 321
Упражнения...................321
Литература.................... 322
Глава X. Комбинаторные карты....... . . . 323
X. 1. Определения и предварительные теоремы ........ 323
X. 2. Ориентируемость.................327
X. 3. Двойственность..................330
X. 4. Изоморфизм...................332
X. 5. Изображение карт.................335
Х.6. Углы..................... . 340
X. 7. Операции над картами.............. 340
X. 8. Комбинаторные поверхности............. 348
X. 9. Циклы и кограницы.........•...... • 356
X. 10. Замечания....................359
Упражнения...................359
Литература........:........... 360
Глава XI. Планарность • • • • • • •......... 361
XI. 1. Пленарные графы................. 361
XI. 2. Остовные подграфы.............. . 364
XI. 3. Теорема Жордана................. 367
XI. 4. Связность в пленарных картах........... 374
XI. 5. Теорема о рассечении............... 385
XI. 6. Мосты..................... 391
XI. 7. Один алгоритм выявления планарности......... 395
XI. 8. Периферические циклы в трехсвязных графах...... 399
XI. 9. Теорема Куратовского......... . . . • 403
XI. 10. Замечания.............../ .... 408
Упражнения.................. 408
Литература................... 409
Предметный указатель.....••.......... 410
Цена: 150руб.
