Лекции по теории графов

Содержание книги «Лекции по теории графов»:

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