Теория графов

Ф. Харари

В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника химии, она проникла и в науки считавшиеся раньше далекими от нее - экономику, социологию лингвистику и др. Давно известны тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов исследованием операций, теорией кодирования, теорией игр).

Широко используется теория графов при решении различных задач на вычислительных машинах. За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций. Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениями дискретной математики.

Год издания: 1973

ISBN 978-5-397-00622-4

Количество страниц: 301.

Содержание книги «Теория графов»:

6 Предисловие редактора перевода
9 Введение
13 Глава 1. Открытие!
- 13 Задача о кёнигсбергских мостах
- 14 Электрические цепи
- 15 Химические изомеры
- 16 «Вокруг света»
- 17 Гипотеза четырех красок
- 18 Теория графов в двадцатом веке
21 Глава 2. Графы
- 21 Типы графов
- 26 Маршруты и связность
- 27 Степени
- 28 Задача Рамсея
- 30 Экстремальные графы
- 33 Графы пересечений
- 35 Операции над графами
- 38 Упражнения
41 Глава 3. Блоки
- 41 Точки сочленения, мосты и блоки
- 45 Графы блоков и графы точек сочленения
- 46 Упражнения
48 Глава 4. Деревья
- 48 Описание деревьев
- 51 Центры и центроиды
- 53 Деревья блоков и точек сочленения
- 54 Независимые циклы и коциклы
- 57 Матроиды
- 59 Упражнения
60 Глава 5. Связность
- 60 Связность и реберная связность
- 64 Графические варианты теоремы Менгера
- 70 Другие варианты теоремы Менгера
- 74 Упражнения
76 Глава 6. Разбиения
- 81 Упражнения
83 Глава 7. Обходы графов
- 83 Эйлеровы графы
- 85 Гамильтоновы графы
- 88 Упражнения
91 Глава 8. Реберные графы
- 91 Некоторые свойства реберных графов
- 94 Характеризация реберных графов
- 99 Специальные реберные графы
- 101 Реберные графы и обходы
- 103 Тотальные графы
- 104 Упражнения
106 Глава 9. Факторизация
- 106 1-факторизация
- 111 2-факторизация
- 113 Древесность
- 116 Упражнения
117 Глава 10. Покрытия
- 117 Покрытия и независимость
- 120 Критические вершины и ребра
- 122 Реберное ядро
- 124 Упражнения
126 Глава 11. Планарность
- 126 Плоские и планарные графы
- 131 Внешнепланарные графы
- 133 Теорема Поптрягина-Куратовского
- 138 Другие характеризации планарных графов
- 141 Род, толщина, крупность, число скрещиваний
- 148 Упражнения
151 Глава 12. Раскраски
- 152 Хроматическое число
- 155 Теорема о пяти красках
- 156 Гипотеза четырех красок
- 162 Теорема Хидвуда о раскраске карт
- 164 Однозначно раскрашиваемые графы
- 167 Критические графы
- 169 Гомоморфизмы
- 172 Хроматический многочлен
- 175 Упражнения
178 Глава 13. Матрицы
- 178 Матрица смежностей
- 180 Матрица инциденций
- 183 Матрица циклов
- 186 Обзор дополнительных свойств матроидов
- 187 Упражнения
189 Глава 14. Группы
- 193 Группа автоморфизмов графа
- 194 Операции на группах подстановок
- 195 Группа графа-композиции
- 198 Графы с данной группой
- 201 Симметричные графы
- 204 Графы с более сильной симметрией
- 206 Упражнения
209 Глава 15. Перечисления
- 209 Помеченные графы
- 211 Теорема перечисления Пойа
- 216 Перечисление графов
- 219 Перечисление деревьев
- 224 Теорема перечисления степенной группы
- 225 Решенные и нерешенные задачи перечисления графов
- 230 Упражнения
232 Глава 16. Орграфы
- 232 Орграфы и соединимость
- 234 Ориентированная двойственность и бесконтурные орграфы
- 237 Орграфы и матрицы
- 244 Обзор по проблеме восстановления турниров
- 244 Упражнения
248 Приложение I. Диаграммы графов
260 Приложение II. Диаграммы орграфов
266 Приложение III. Диаграммы деревьев
268 Список литературы и именной указатель
291 Указатель обозначений
293 Предметный указатель