Участник:Dgerasimov/Тикеты по конспектам year2012

Тикеты нумеруются как "X-Y", где X — номер темы, а Y — номер тикета внутри темы.

1. Основные определения теории графов

1. Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
2. Лемма о рукопожатиях
3. Теорема о существовании простого пути в случае существования пути
4. Теорема о существовании простого цикла в случае существования цикла
5. Матрица смежности графа
6. Связь степени матрицы смежности и количества путей
7. Матрица инцидентности графа
8. Циклическое пространство графа
9. Фундаментальные циклы графа
10. Дерево, эквивалентные определения
11. Дополнительный, самодополнительный граф

2. Связность в графах

1. Отношение связности, компоненты связности
2. Отношение реберной двусвязности
3. Отношение вершинной двусвязности
4. Граф компонент реберной двусвязности
5. Граф блоков-точек сочленения
6. Точка сочленения, эквивалентные определения
7. Мост, эквивалентные определения
8. k-связность
9. Теорема Менгера
10. Теорема Менгера, альтернативное доказательство
11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины

3. Остовные деревья

• Матрица Кирхгофа
• Связь матрицы Кирхгофа и матрицы инцидентности
• Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

4. Обходы графов

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Покрытие ребер графа путями
• Алгоритм построения Эйлерова цикла
• Произвольно вычерчиваемые из заданной вершины графы
• Гамильтоновы графы
• Теорема Хватала
• Теорема Дирака
• Теорема Оре
• Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
• Турниры
• Теорема Редеи-Камиона

5. Укладки графов

• Укладка графа на плоскости
• Формула Эйлера
• Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
• Укладка дерева
• Укладка графа с планарными компонентами реберной двусвязности
• Укладка графа с планарными компонентами вершинной двусвязности
• Теорема Понтрягина-Куратовского
• Двойственный граф планарного графа

6. Раскраски графов

• Раскраска графа
• Двудольные графы и раскраска в 2 цвета
• Хроматический многочлен
  • Хроматический многочлен полного графа
  • Хроматический многочлен пустого графа
  • Хроматический многочлен дерева
  • Рекуррентные формулы для хроматических многочленов
  • Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность
• Формула Зыкова
• Формула Уитни
• Теорема Брукса
• Верхние и нижние оценки хроматического числа

7. Обход в глубину

• Обход в глубину, цвета вершин
• Лемма о белых путях
• Использование обхода в глубину для проверки связности
• Использование обхода в глубину для поиска цикла в ориентированном графе
• Использование обхода в глубину для топологической сортировки
• Использование обхода в глубину для поиска компонент сильной связности
• Использование обхода в глубину для поиска точек сочленения
• Построение компонент вершинной двусвязности
• Использование обхода в глубину для поиска мостов
• Построение компонент реберной двусвязности

8. Кратчайшие пути в графах

• Обход в ширину
• Алгоритм Форда-Беллмана
• Алгоритм Дейкстры
• Алгоритм Флойда
• Алгоритм A*
• Алгоритм Джонсона

9. Построение остовных деревьев

• Лемма о безопасном ребре
• Алгоритм Прима
• Алгоритм Краскала
• Алгоритм Борувки
• Теорема Тарьяна (критерий минимальности остовного дерева)
• Алгоритм двух китайцев

10. Задача о паросочетании

• Теорема о максимальном паросочетании и дополняющих цепях
• Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
• Алгоритм Куна для поиска максимального паросочетания
• Теорема Холла
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
• Связь вершинного покрытия и независимого множества
• Матрица Татта и связь с размером максимального паросочетания в двудольном графе
• Паросочетания в недвудольных графах. Алгоритм вырезания соцветий

11. Задача о максимальном потоке

• Определение сети, потока
• Разрез, лемма о потоке через разрез
• Дополняющая сеть, дополняющий путь
• Лемма о сложении потоков
• Теорема Форда-Фалкерсона
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алоритм Эдмондса-Карпа
• Алгоритм масштабирования потока
• Блокирующий поток
• Схема алгоритма Диница
• Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
• Алгоритм поиска блокирующего потока в ациклической сети
• Метод проталкивания предпотока
• Алгоритм "поднять-в-начало"
• Теорема о декомпозиции
• Теорема о декомпозиционном барьере
• Циркуляция потока
• Алгоритм Каргера для нахождения минимального разреза

12. Задача о потоке минимальной стоимости

• Поток минимальной стоимости
• Теорема Форда-Фалкерсона о потоке минимальной стоимости
• Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
• Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
• Использование потенциалов Джонсона при поиске потока минимальной стоимости
• Сведение задачи о назначениях к задаче о потоке минимальной стоимости
• Венгерский алгоритм решения задачи о назначениях