Излагаются основы теории графов, обсуждаются некоторые известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов. Каждая глава сопровождается упражнениями. Для студентов вузов, обучающихся по специальностям «Математика» и «Прикладная математика».
Содержание
Глава I. Начальные понятия
§ 1. Определение графа
§ 2. Подграфы
§ 3. Операции над графами
§ 4. Цепи, циклы, компоненты
§ 5. Степени вершин графа
§ 6. Матрицы, ассоциированные с графом
§ 7. Регулярные графы
§ 8. Метрические характеристики графа
§ 9. Критерий двудольности графа
§ 10. Реберный граф
§ 11. Группа автоморфизмов графа
§ 12. «Почти все» графы
Упражнения
Глава II. Деревья
§ 13. Определение дерева
§ 14. Матричная теорема Кирхгофа
§ 15. Остов минимального веса
Упражнения
Глава III. Матроиды и трансверсали
§ 16. Азбука теории матроидов
§ 17. Двойственный матроид
§ 18. Примеры матроидов
§ 19. Изоморфизм матроидов
§ 20. Представление матроида
§ 21. Бинарные матроиды
§ 22. Трансверсали
§ 23. Жадный алгоритм
§ 24. Объединение и пересечение матроидов
Упражнения
Глава IV. Независимость и покрытия
§ 25. Независимые множества и покрытия
§ 26. Клика
§ 27. Проблемы клики, изоморфной вложимости и изоморфного подграфа
§ 28. Интерпретации независимых множеств
§ 29. Паросочетания
§ 30. Паросочетания в двудольном графе
§ 31. Двудольные графы и семейства подмножеств
§ 32. Паросочетания и покрытия
Упражнения
Глава V. Связность
§ 33. Вершинная связность и реберная связность
§ 34. Двусвязные графы
§ 35. Теорема Менгера
Упражнения
Глава VI Планарность
§ 36. Плоские и планарные графы
§ 37. Грани плоского графа. Формула Эйлера
§ 38. Плоские триангуляции
§ 39. Критерии планарности
§ 40. Двойственность и планарность
§ 41. Алгоритм укладки графа на плоскости
§ 42. Характеристики непланарных графов
Упражнения
Глава VII. Обходы
§ 43. Эйлеровы графы
§ 44. Гамильтоновы графы
Упражнения
Глава VIII Степенные последовательности
§ 45. Графическая последовательность
§ 46. Критерии графичности последовательности
§ 47. Реализация графической последовательности с максимальной связностью
§ 48. Гамильтонова реализация графической последовательности
§ 49. Расщепляемые графы
§ 50. Пороговые графы
§ 51. Пороговое разложение графа
§ 52. Степенное множество графа
Упражнения
Глава IX. Раскраски
§ 53. Правильная раскраска
§ 54. Оценки хроматического числа
§ 55. Хроматический полином
§ 56. Раскраска ребер
§ 57. Связь матроидных разложений графов с раскрасками
§ 58. Раскраска планарных графов
§ 59. Проблема четырех красок
§ 60. Другие подходы к раскраске графов
§ 61. Совершенные графы
§ 62. Триангулированные графы
Упражнения
Глава X. Ориентированные графы
§ 63. Основные определения
§ 64. Полустепени исхода и полустепени захода
§ 65. Обходы
§ 66. Пути
§ 67. База и ядро
Упражнения
Глава XI. Гиперграфы
§ 68. Основные определения и свойства
§ 69. Независимые множества
§ 70. Раскраски
§ 71. Реализации гиперграфа
Упражнения
Глава XII. Алгоритмы
§ 72. Предварительные сведения
§ 73. Поиск в глубину
§ 74. Отыскание двусвязных компонент
§ 75. Минимальный остов
§ 76. Кратчайшие пути
§ 77. Наибольшие паросочетания и задача о назначениях
§ 78. Труднорешаемые задачи
Упражнения
