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

Description

Титульный лист Предисловие. От автора Благодарности Оглавление 1 Введение 1.1 Вершины и рёбра 1.2 Подграфы 1.3 Некоторые операции над графами 1.4 Маршруты, пути и циклы 1.5 Связность 1.5.1 Компоненты связности 1.5.2 Дерево 1.5.3 Разделяющие множества 1.5.4 Части разбиения 1.5.5 Точки сочленения и блоки в связном графе 1.6 Двудольные и k-дольные графы 1.7 Орграфы и ориентации 1.7.1 Стрелки 1.7.2 Подграфы, степени и окрестности 1.7.3 Пути и циклы в орграфе 1.7.4 Некоторые операции над орграфами 1.7.5 Ориентация графа 1.8 Корневые деревья 1.8.1 Дерево поиска в ширину 1.8.2 Нормальное дерево 1.9 Эйлеров цикл и покрытие рёбер путями 1.10 Гиперграф 1.11 Изоморфизм графов 1.12 Рёберный граф 2 Паросочетания 2.1 Чередующиеся и дополняющие пути 2.2 Паросочетания в двудольном графе 2.3 Соотношения между α, β, α' и β' 2.4 Паросочетания с предпочтениями 2.5 Паросочетания в произвольном графе 2.5.1 Теорема Татта о совершенном паросочетании 2.5.2 Совершенное паросочетание в регулярном графе 2.5.3 Факторы регулярного графа 2.5.4 Дефицит графа. Формула Бержа 2.5.5 Фактор-критические графы 2.5.6 Структурная теорема Галлаи-Эдмондса 2.5.7 Барьеры 2.5.8 Критерии существования совершенного паросочетания 2.6 Факторы 2.6.1 Факторы и паросочетания 2.6.2 Нормальные множества 2.6.3 f-дефицит. Теорема Татта о факторе 2.6.4 Еще раз про факторы регулярного графа 2.6.5 Жесткость и k-факторы 2.7 Графы с единственным паросочетанием 2.8 Комментарии 3 Пути и циклы 3.1 Гамильтонов путь и цикл 3.1.1 Классические критерии Дирака и Оре 3.1.2 Замыкание. Метод Хватала 3.1.3 Связность и гамильтоновы циклы 3.1.4 Гамильтоновы последовательности 3.1.5 Гамильтонов цикл в степени графа 3.2 Панциклические графы 3.3 Окружение графа 3.4 Циклы четной длины 3.5 Обхват 3.6 Комментарии 4 Раскраски 4.1 Хроматическое число 4.2 Теорема Брукса 4.3 Критические графы 4.4 Гипотеза Хайоша 4.5 Конструируемые графы 4.6 Обхват и хроматическое число 4.7 Совершенные графы 4.8 Раскраски рёбер 4.8.1 Оптимальные раскраски 4.8.2 Теорема Визинга 4.8.3 Покрывающие раскраски рёбер 4.9 Списочные раскраски 4.10 Раскраски гиперграфов 4.10.1 Аналог теоремы Брукса 4.10.2 Правильные раскраски гиперграфов в два цвета 4.11 Теорема о раскраске без чередующегося цикла 4.12 Комментарии 5 Связность 5.1 Теорема Менгера 5.2 Разделяющие множества в k-связном графе 5.2.1 Части разбиения, граница и внутренность 5.2.2 Зависимые и независимые разделяющие множества 5.3 Удаление вершин с сохранением k-связности 5.4 Удаление ребер с сохранением k-связности 5.5 Деревья разбиения 5.5.1 Точки сочленения и блоки в связном графе 5.5.2 Дерево разбиения 5.5.3 Дерево разбиения двусвязного графа 5.5.4 Применение дерева разбиения двусвязного графа 5.6 Стягивание рёбер в k-связном графе 5.6.1 Двусвязные и трёхсвязные графы 5.6.2 Минимальные по стягиванию 4-связные графы 5.6.3 Трёхсвязные графы: происхождение от колеса 5.7 Разбиение вершин на связные множества 5.8 Комментарии 6 Планарные графы 6.1 Плоские и планарные графы 6.1.1 Теорема Жордана для замкнутой ломаной 6.1.2 Грань и её граница 6.1.3 Разные изображения одного графа 6.1.4 Плоскость и сфера 6.2 Формула Эйлера 6.3 Теорема Куратовского 6.3.1 Части разбиения и планарность 6.4 Изображения трёхсвязного графа 6.5 Двойственный граф 6.6 Триангуляции 6.7 Изображение с прямыми рёбрами 6.8 Вокруг 4СС 6.9 Списочные раскраски планарных графов 6.10 Пути и циклы в планарном графе 6.10.1 Негамильтоновы планарные графы 6.10.2 Теорема Томассена о пути в планарном графе 6.10.3 Теорема Татта о цикле в планарном графе 6.11 K-планарные графы 6.11.1 Оценка количества рёбер при k ≤ 4 6.12 1-планарные графы 6.12.1 Изображение 1-планарного графа 6.12.2 Оценка числа рёбер в двудольном 1-планарном графe 6.12.3 О 1-планарных графах K_n и K_m,n 6.12.4 Теорема о 6 красках 6.13 Комментарии 7 Циклическое пространство графа 7.1 Пространство разрезов 7.2 Бонды 7.3 Циклическое пространство трёхсвязного графа 7.4 Циклическое пространство и планарность 7.5 Циклическое пространство и двойственность 7.6 Комментарии 8 Ориентированные графы 8.1 Сильная связность 8.2 Входящее и исходящее дерево 8.3 Сильная k-связность 8.4 Гамильтоновы циклы в орграфе 8.5 Турниры 8.5.1 Циклы в сильно связных турнирах 8.5.2 Гамильтоновы пути в турнирном графе 8.6 Независимые множества вершин в орграфе 8.6.1 Теорема Хватала-Ловаса 8.6.2 Покрытие вершин путями 8.7 Ориентации графа и его раскраски 8.7.1 Теорема Роя-Галлаи 8.7.2 Ядро орграфа и списочные раскраски рёбер 8.8 Орграфы исходящей степени не менее 2 8.9 Циклический базис орграфа 8.10 Четные орграфы 8.10.1 Циклический базис орграфа и четные циклы 8.10.2 Редукция 8.10.3 Основная теорема 8.10.4 Условия существования слабого двойного треугольника 8.10.5 Критерии четности орграфа 8.11 Снова о раскрасках гиперграфа в два цвета 8.12 Комментарии 9 Остовные деревья 9.1 Количество остовных деревьев 9.2 Матричная теорема о деревьях 9.3 Количество висячих вершин 9.3.1 Теорема о промежуточных значениях 9.3.2 Минимальная степень и количество висячих вершин 9.3.3 Остовные деревья в графах с вершинами степеней 1 и 2 9.3.4 Экстремальные примеры 9.4 Непересекающиеся остовные деревья 9.5 Комментарии 10 Потоки 10.1 Поток в сети 10.1.1 Теорема Форда-Фалкерсона 10.1.2 Целочисленные сети 10.1.3 Рёберная теорема Менгера 10.1.4 Максимальный поток в произвольной сети 10.2 Поток в графе 10.2.1 K-поток и Z_k-поток 10.2.2 2, Z_2, 3 и Z_3-потоки 10.2.3 Существование 6-потока 10.3 Комментарии 11 Теория Рамсея 11.1 Числа Рамсея 11.1.1 Существование. Оценки сверху 11.1.2 Экстремальные примеры и оценки снизу 11.1.3 Числа Рамсея для раскрасок в несколько цветов 11.2 Числа Рамсея больших размерностей 11.3 Числа Рамсея для произвольных графов 11.4 Индуцированная теорема Рамсея 11.4.1 Случай двудольного графа 11.4.2 Случай произвольного графа 11.5 Комментарии 12 Экстремальные графы 12.1 Наследственное свойство 12.2 Задача о запрещенном подграфе 12.2.1 Теорема Турана 12.2.2 Графы без K_m,n: оценка 12.2.3 Проективная плоскость и графы без K_2,2 12.2.4 Корни из единицы в F_q и графы без K_2,n+1 12.2.5 Графы без K_3,3 12.3 Комментарии 13 Графы и многочлены 13.1 Хроматический многочлен 13.1.1 Хроматический многочлен и компоненты 13.1.2 Хроматический многочлен и блоки 13.2 Потоковый многочлен 13.2.1 Существование потокового многочлена 13.2.2 4 и Z_2 × Z_2-потоки 13.2.3 Двойственность потоков и раскрасок 13.2.4 Вычисление хроматического многочлена через потоковый 13.3 Многочлен Татта 13.3.1 Многочлен Татта и ранговый многочлен 13.3.2 Многочлен Татта и компоненты графа 13.3.3 Универсальное свойство многочлена Татта 13.3.4 Многочлен Татта двойственного графа 13.4 Многочлен Эрхарта и количество k-потоков 13.4.1 Многогранники и симплексы 13.4.2 Триангуляция 13.4.3 Многочлен Эрхарта 13.4.4 Количество k-циркуляций и k-потоков 13.5 Дискриминант графа 13.5.1 Дискриминант плоской триангуляции 13.6 Комментарии