Наверх

Ф.Харари, 1973 (Rus)
Теория графов


ОГЛАВЛЕНИЕ


ГЛАВА 1. Открытие
   1. Задача о кенигсбергских мостах
   2. Электрические цепи
   3. Химические изомеры
   4. "Вокруг света"
   5. Гипотеза четырех красок
   6. Теория графов в двадцатом веке

ГЛАВА 2. Графы
   1. Типы графов
   2. Маршруты и связность
   3. Степени
   4. Задача Рамсея
   5. Экстремальные графы
   6. Графы пересечений
   7. Операции над графами
   Упражнения

ГЛАВА 3. Блоки
   1. Точки сочленения, мосты и блоки
   2. Графы блоков и графы точек сочленения

ГЛАВА 4. Деревья
   1. Описание деревьев
   2. Центры и центроиды
   3. Деревья блоков и точек сочленения
   4. Независимые циклы и коциклы
   5. Матроиды
   Упражнения

ГЛАВА 5. Связность
   1. Связность и реберная связность
   2. Графические варианты теоремы Менгера
   3. Другие варианты теоремы Менгера
   Упражнение

ГЛАВА 6. Разбиения
  
Упражнения

ГЛАВА 7. Обходы графов
   1. Эйлеровы графы
   2. Гамильтоновы графы
   Упражнения

ГЛАВА 8. Реберные графы
   1. Некоторые свойства реберных графов
   2. Характеризация реберных графов
   3. Специальные реберные графы
   4. Реберные графы и обходы
   5. Тотальные графы
   Упражнения

ГЛАВА 9. Факторизация
   1. 1-факторизация
   2. 2-факторизация
   3. Древесность
   Упражнения

ГЛАВА 10. Покрытия
   1. Покрытия и независимость
   2. Критические вершины и ребра
   3. Реберное ядро
   Упражнения

ГЛАВА 11. Планарность
   1. Плоские и планарные графы
   2. Внешнепланарные графы
   3. Теорема Понтрягина-Куратовского
   4. Другие характеризации планарных графов
   5. Род, толщина, крупность, число скрещиваний
   Упражнения

ГЛАВА 12. Раскраски
   1. Хроматическое число
   2. Теорема о пяти красках
   3. Гипотеза четырех красок
   4. Теорема Хивуда о раскраске карт
   5. Однозначно раскрашиваемые графы
   6. Критические графы
   7. Гомоморфизмы
   8. Хроматический многочлен
   Упражнения

ГЛАВА 13. Матрицы
   1. Матрица смежности
   2. Матрица инциденций
   3. Матрица циклов
   4. Обзор дополнительных свойств матроидов
   Упражнения

ГЛАВА 14. Группы
   1. Группа автоморфизмов графа
   2. Операции на группах подстановок
   3. Группа графа-композиции
   4. Графы с данной группой
   5. Симметрические графы
   6. Графы с более сильной симметрией
   Упражнения

ГЛАВА 15. Перечисления
   1. Помеченные графы
   2. Теорема перечисления Пойя
   3. Перечисление графов
   4. Перечисление деревьев
   5. Теорема перечисления степенной группы
   6. Решенные и нерешенные задачи перечисления графов
   Упражнения

ГЛАВА 16. Орграфы
   1. Орграфы и соединимость
   2. Ориентированная двойственность
   3. Орграфы и матрицы
   4. Обзор по проблеме восстановления турниров
   Упражнения


ПРИЛОЖЕНИЕ 1. Диаграммы графов
ПРИЛОЖЕНИЕ 2. Диаграммы орграфов
ПРИЛОЖЕНИЕ 3. Диаграммы деревьев

Список литературы и именной указатель
Указатель обозначений
Предметный указатель