|
Оглавление
Предисловие.............. Введение............... Глава 1. НАЧАЛЬНЫЕ ПОНЯТИЯ........ § 1. Определение графа......... § 2. Подграфы............ § 3. Операции над графами........ § 4. Цепи, циклы, компоненты....... § 5. Степени вершин графа........ § 6. Матрицы, ассоциированные с графом.... § 7. Регулярные графы......... § 8. Метрические характеристики графа.... § 9. Критерий двудольности графа...... § 10. Реберный граф.......... § 11. Группа автоморфизмов графа...... § 12. «Почти все» графы...... Упражнения............. Глава П. ДЕРЕВЬЯ............ § 13. Определение дерева......... § 14. Матричная теорема Кирхгофа...... § 15. Остов минимального веса....... Упражнения............. Глава III. МАТРОИДЫ И ТРАНСВЕРСАЛИ..... § 16. Азбука теории матроидов....... § 17. Двойственный матроид........ § 18. Примеры матроидов........ § 19. Изоморфизм матроидов........ § 20. Представление матроида....... § 21. Бинарные матроиды......... § 22. Трансверсали........... § 23. Жадный алгоритм......... § 24. Объединение и пересечение матроидов Упражнения.,........... Глава IV. НЕЗАВИСИМОСТЬ И ПОКРЫТИЯ.... § 25. Независимые множества и покрытия. § 26. Клика............. § 27. Проблемы клики, изоморфной вложимости и изоморфного подграфа......... § 28. Интерпретации независимых множеств § 29. Паросочетания........ § 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
§ 65. Обходы............. 286
§ 66. Пути............. 290
§ 67. База и ядро...........293
Упражнения............. 296
Глава XI. ГИПЕРГРАФЫ.......... 298
§ 68. Основные определения и свойства..... 298
§ 69. Независимые множества........ 304
§ 70. Раскраски............ 306
§ 71. Реализации гиперграфа........ 310
Упражнения............. 315
Глава XII. АЛГОРИТМЫ.......... 317
§ 72. Предварительные сведения....... 317
§ 73. Поиск в глубину.......... 323
§ 74. Отыскание двусвязных компонент..... 327
§ 75. Минимальный остов......... 334
§ 76. Кратчайшие пути......... 342
§ 77. Наибольшие паросочетания и задача о назначениях 354
§ 78. Труднорешаемые задачи....... 364
Упражнения............. 373
СПИСОК ЛИТЕРАТУРЫ.......... 375
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ.........377
|
