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

Предисловие
Глава 1. Основные понятия
§ 1. Основные понятия и определения теории
графов
§ 2. Маршруты, пути, циклы в графе. Связные
графы и орграфы
§3. Подграф графа G. Основные операции над
графами
§ 4. Изоморфизм и автоморфизм графов
Глава 2. Деревья и их перечисление
§ 1. Основные свойства деревьев
§ 2. Перечисление деревьев. Формула Кэли
§ 3. Подсчет остовных деревьев в графе.
Матричная теорема о деревьях
Глава 3. Циклы в графах
§ 1. Эйлеровы циклы
§ 2. Гамильтоновы циклы
§ 3. Линейное пространство ребер. Циклы и
разрезы
§ 4. Циркуляции и напряжения. Электрические
сети
Глава 4. Связность в графах
§ 1. Вершинная и реберная связность графа
§ 2. Двусвязные графы
§ 3. fc-связные графы. Теорема Менгера
§ 4. Теорема Форда-Фалкерсона
Глава 5. Паросочетания в графах
§1. Понятие паросочетания. Теорема Бержа.
Независимые множества и покрытия графа
§ 2. Паросочетания в двудольных графах.
Алгоритм Куна поиска максимального
паросочетания в двудольном графе
§ 3. Совершенные паросочетания в произвольном
графе. Теорема Татта
§ 4. Максимальные паросочетания в произвольном
графе. Структурная теорема Галлаи-Эдмондса.
Алгоритм Эдмондса
Глава 6. Раскраска графов
§ 1. k-раскрашиваемые графы. Теорема Брукса
§2. Нижние оценки на хроматическое число.
Теорема Турана. Совершенные графы
§ 3. Реберная раскраска графов
§ 4. Хроматический многочлен графа
Глава 7. Планарные графы
§ 1. Планарные графы и их основные свойства
§ 2. Формула Эйлера для плоских графов
§ 3. Карты на поверхностях
§ 4. Критерии планарности графов. Теорема
Куратовского
§ 5. Раскраска плоских графов
Литература
Предметный указатель