Излагаются основы теории графов, обсуждаются некоторые-известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов. Каждая глава сопровождается упражнениями.
Для студентов вузов, обучающихся по специальностям «Математика» и «Прикладная математика».
Табл. 1. Ил. 211. Библиогр. 32 назв.
Посвящается Дмитрию Алексеевичу СУПРУНЕНКО
Предисловие
В основу настоящего учебного пособия положены курсы лекций, которые читались авторами в Белорусском государственном университете им. В. И. Ленина для студентов-математиков и в Белорусском политехническом институте для студентов, обучающихся по специальности «Прикладная математика». Изложение материала в книге ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и к .другим чисто абстрактным дисциплинам. Основной задачей этого учебного пособия является ознакомление студентов с теоретическими основами теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и в связи с этим,— построению эффективных алгоритмов.
Книга состоит из двенадцати глав.
В главе I даны основные понятия теории графов. Обсуждается гипотеза Келли — Улама о реконструируемо-сти, вводятся регулярные, двудольные и реберные графы, изучается группа автоморфизмов графа. Глава заканчивается результатами, характеризующими свойства графов при большом числе вершин. Эти свойства отражают в некотором смысле типичный случай и потому формулируются в терминах «почти всех» графов.
Глава II посвящена деревьям и остовам. Она содержит матричную теорему Кирхгофа о деревьях и теорему Кэли о числе помеченных деревьев. В этой нее главе излагаются и обосновываются алгоритмы Краскала и Прима для решения задачи об остове минимального веса.
Глава III содержит элементарное замкнутое изложение основ теории матроидов и трансверсалей, специально приспособленное к нуждам теории графов.
Глава IV касается понятий независимости и покрытия. При этом понятия вершинного и реберного покрытий в идейном плане объединены.
Оглавление
Предисловие .............. 3
Введение............... 7
Глава I. НАЧАЛЬНЫЕ ПОНЯТИЯ........ 9
§ 1. Определение графа . ....... 9
§ 2. Подграфы............ 17
§ 3. Операции над графами........ 19
§ 4. Цепи, циклы, компоненты....... 22
§ 5. Степени вершин графа........ 26
§ 6. Матрицы, ассоциированные с графом .... 27
§ 7. Регулярные графы......... 32
§ 8, Метрические характеристики графа .... 34
§ 9. Критерий двудольности графа...... 36
§ 10. Реберный граф.......... 38
§ И. Группа автоморфизмов графа...... 42
§ 12. «Почти все» графы......... 47
Упражнения............. 51
Глава II. ДЕРЕВЬЯ............ 53
§ 13. Определение дерева......... 53
§ 14. Матричная теорема Кирхгофа...... 57
§ 15. Остов минимального веса....... 60
Упражнения............. 63
Глава III. МАТРОИДЫ И ТРАНСВЕРСАЛИ..... 64
§ 16. Азбука теории матроидов....... 64
§ 17. Двойственный матроид ........ 68
§ 18. Примеры матроидов......... 70
§ 19. Изоморфизм матроидов....... . 73
§ 20. Представление матроида ....... 75
§ 21. Бинарные иатроиды......... 79
§ 22. Трансверсалл........... 87
§ 23. Жадный алгоритм......... 92
§ 24. Объединение и пересечение матроидов ... 95
Упражнения............. 100
Глава IV. НЕЗАВИСИМОСТЬ И ПОКРЫТИЯ .... 102
§ 25. Независимые множества и покрытия .... 102
§ 26. Клика............. 111
§ 27. Проблемы клики, изоморфной вложимости и изоморфного подграфа......... 115
§ 28. Интерпретации независимых множеств , . . 117
§ 29. Паросочетания.......... 122
381
§ 30. Паросочетания в двудольном графе .... 124
§ 31. Двудольные графы и семейства подмножеств . 128
§ 32. Паросочетания и покрытия....... 130
Упражнения ............. 132
Глава V. СВЯЗНОСТЬ........... 133
§ 33. Вершинная связность и реберная связность . . 133
§ 34. Двусвязные графы......... 137
§ 35. Теорема Менгера.......... 145
Упражнения............. 148
Глава VI. ПЛАНАРНОСТЬ......... 150
§ 36. Плоские и пленарные графы...... 150
§ 37. Грани плоского графа. Формула Эйлера . . . 153
§ 38. Плоские триангуляции......... 157
§ 39. Критерии планарности........ 159
§ 40. Двойственность и плапарность...... 169
§ 41. Алгоритм укладки графа на плоскости . . . 175
§ 42. Характеристики пепланарных графов .... 183
Упражнения............. 187
Глава VII. ОБХОДЫ........... 191
§ 43. Эйлеровы графы.......... 191
§ 44. Гамильтоновы графы........ 196
Упражнения............. 207
Глава VIII. СТЕПЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ . . 208
§ 45. Графическая последовательность..... 209
§ 46. Критерии графичности последовательности . . 211 § 47. Реализация графической последовательности с максимальной связностью........ 217
§ 48. Гамильтонова реализация графической последовательности ............ 220
§ 49. Расщепляемые графы........ 222
§ 50. Пороговые графы.......... 223
§ 51. Пороговое разложение графа...... 228
§ 52. Степенное множество графа....... 232
Упражнения............. 234
Глава IX. РАСКРАСКИ.......... 235
§ 53. Правильная раскраска........ 235
§ 54. Оценки хроматического числа...... 238
§ 55. Хроматический полином........ 245
§ 56. Раскраска ребер.......... 248
§ 57. Связь матроидных разложений графов с раскрасками .............. 252
§ 58. Раскраска пленарных графов...... 255
§ 59. Проблема четырех красок....... 260
§ 60. Другие подходы к раскраске графов .... 264
§ 61. Совершенные графы......... 267
§ 62. Триангулированные графы....... 272
Упражнения............. 277
Глава X. ОРИЕНТИРОВАННЫЕ ГРАФЫ..... 279
§ 63. Основные определения........ 279
§ 64. Полустепени исхода и полустепени захода . , 283
382
§ 65. Обходы............. ?™
1 § 66. Пути............. 593
§ 67. База и ядро........... ?jjj
Упражнения .............
Глава XI. ГИПЕРГРАФЫ.......... 298
§ 68. Основные определения и свойства..... яаа
§ 69. Независимые множества........ ;>У*
§ 70. Раскраски . ........... |>"°
§ 71. Реализации гиперграфа........ ;""
Упражнения............. d °
Глава XII. АЛГОРИТМЫ.......... 317
§ 72. Предварительные сведения....... ^'
§ 73. Поиск в глубину.......... %?>
§ 74. Отыскание двусвязных компонент..... ««/
§ 75. Минимальный остов......... «**
§ 76. Кратчайшие пути......... ^2
§ 77. Наибольшие Паросочетания и задача о назначениях о54
§ 78. Труднорешаемые задачи....... 364
Упражнения............. 373
СПИСОК ЛИТЕРАТУРЫ.......... 375
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ........,377
Цена: 300руб.
