Теория графов:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Построение остовных деревьев)
м
Строка 1: Строка 1:
−
== 1. Основные определения теории графов ==
 
−
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
−
# [[Лемма о рукопожатиях]]
 
−
# [[Теорема о существовании простого пути в случае существования пути]]
 
−
# [[Теорема о существовании простого цикла в случае существования цикла]]
 
−
# [[Матрица смежности графа]]
 
−
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
 
−
## Добавить свойства матрицы инцидентности с доказательствами
 
−
## Источники -> Источники информации
 
−
## Добавить про списки смежности и их оформить тоже в таблички
 
−
# [[Циклическое пространство графа]]
 
−
# [[Фундаментальные циклы графа]]
 
−
# [[Дерево, эквивалентные определения]]
 
−
# [[Алгоритмы на деревьях]]
 
−
# [[Дополнительный, самодополнительный граф]]
 
−
# [[Теоретико-множественные операции над графами]]
 
−
# [[Рёберное ядро]] (2)
 
−
## Добавить больше интервики в конспект
 
−
## В конце теоремы в доказательстве какая-то лажа
 
−
## Источники информации
 
−
## Оформить следствия красиво
 
−
# [[Факторизация графов]]
 
−
 
−
== 2. Связность в графах ==
 
−
# [[Отношение связности, компоненты связности]]
 
−
# [[Отношение реберной двусвязности]]
 
−
# [[Отношение вершинной двусвязности]]
 
−
# [[Точка сочленения, эквивалентные определения]]
 
−
# [[Мост, эквивалентные определения]]
 
−
# [[Граф компонент реберной двусвязности]]
 
−
# [[Граф блоков-точек сочленения]]
 
−
# [[k-связность]]
 
−
# [[Теорема Менгера]]
 
−
# [[Теорема Менгера, альтернативное доказательство]]
 
−
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
 
−
## пункт "Определения" не нужен
 
−
## Изменить знаки неравенств в tex
 
−
## Не надо дублировать определения из другого конспекта
 
−
## Отформатировать псевдокод
 
−
## find_flow какой-то стрёмный
 
−
## Источники информации
 
−
## k-связность с маленькой буквы
 
−
## Добавить См. также на что-нибудь разумное
 
−
## Добавить см. также
 
  
 
== 3. Остовные деревья ==
 
== 3. Остовные деревья ==
Строка 66: Строка 22:
 
</ol>
 
</ol>
  
−
=== Свойства остовных деревьев ===
+
== Обходы графов ==
−
<ol>
+
=== Эйлеровы графы ==
−
<li value="7">[[Матрица Кирхгофа]]</li>
 
−
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
 
−
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
 
−
<li> [[Количество помеченных деревьев]] </li>
 
−
<li> [[Коды Прюфера]] </li>
 
−
</ol>
 
  
−
== 4. Обходы графов ==
+
# [[Алгоритм построения Эйлерова цикла]] (2)
−
=== Эйлеровы графы ===
+
## Какое-то мутное доказательство леммы про корректность алгоритма
−
<ol>
 
−
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
 
−
<li> [[Покрытие ребер графа путями]] (3)</li>
 
−
# Какое-то мутное доказательства
 
−
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
 
−
# Какое-то мутное доказательство леммы про корректность алгоритма
 
−
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
 
−
</ol>
 
  
−
=== Гамильтоновы графы ===
+
=== Гамильтовы графы  
−
<ol>
+
<ol value="2">
−
<li value="5"> [[Гамильтоновы графы]] </li>
 
−
<li> [[Теорема Хватала]] </li>
 
−
<li> [[Теорема Дирака]] </li>
 
−
<li> [[Теорема Оре]] </li>
 
−
<li> [[Теорема Поша]]</li>
 
−
<li> [[Теорема Гуйя-Ури]] </li>
 
 
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
 
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
−
<li> '''!!!''' [[Теорема Гринберга]] (5) </li>
 
−
# Пояснить переходы в теореме
 
−
# Внести пояснение в определение бонда
 
−
# И зачем нужно доказывать отсутствие гамильтонова бонда в графе?
 
−
# Картинку сделать красивой
 
−
<li> [[Турниры]] </li>
 
−
<li> [[Теорема Редеи-Камиона]] </li>
 
 
</ol>
 
</ol>
−
 
−
== 5. Укладки графов ==
 
−
# [[Укладка графа на плоскости]]
 
−
# [[Формула Эйлера]]
 
−
# [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
 
−
# [[Укладка дерева]]
 
−
# [[Укладка графа с планарными компонентами реберной двусвязности]]
 
−
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
 
−
# [[Теорема Понтрягина-Куратовского]]
 
−
# [[Род, толщина, крупность, число скрещиваний]]
 
−
# [[Двойственный граф планарного графа]]
 
−
# [[Теорема Фари]]
 
−
# [[Гамма-алгоритм]]
 
−
 
−
== 6. Раскраски графов ==
 
−
# [[Раскраска графа]]
 
−
# [[Двудольные графы и раскраска в 2 цвета]]
 
−
# [[Хроматический многочлен]]
 
−
# [[Формула Зыкова]]
 
−
# [[Формула Уитни]]
 
−
# [[Теорема Брукса]]
 
−
# [[Верхние и нижние оценки хроматического числа]]
 
−
# [[Хроматическое число планарного графа]]
 
−
# [[Многочлен Татта]]
 
−
# [[Теория Рамсея]] ('''10''')
 
−
## Тут вообще ад какой-то
 
  
 
== 7. Обход в глубину ==
 
== 7. Обход в глубину ==
Строка 154: Строка 57:
  
 
== 9. Задача о паросочетании ==
 
== 9. Задача о паросочетании ==
−
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Куна для поиска максимального паросочетания]]
 
# [[Алгоритм Куна для поиска максимального паросочетания]]
−
# [[Теорема Холла]]
 
−
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
 
−
# [[Связь вершинного покрытия и независимого множества]]
 
−
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
−
# [[Теорема Татта о существовании полного паросочетания]]
 
 
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
−
# [[Декомпозиция Эдмондса-Галлаи]]
 
−
# [[Задача об устойчивом паросочетании]] (5)
 
−
## паросочетание в интервики
 
−
## пару оформить нормально
 
−
## Зачем-то списки в доказательствах лемм использованы
 
−
## Надо бы доказать все леммы
 
−
 
−
<!--
 
  
 
== 10. Задача о максимальном потоке ==
 
== 10. Задача о максимальном потоке ==
Строка 229: Строка 118:
 
## Оформить покрасивей и правильней
 
## Оформить покрасивей и правильней
 
# [[Венгерский алгоритм решения задачи о назначениях]]
 
# [[Венгерский алгоритм решения задачи о назначениях]]
−
-->
 

Версия 22:10, 22 сентября 2017

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

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

  1. Остовные деревья: определения, лемма о безопасном ребре
  2. Алгоритм Прима
  3. Алгоритм Краскала
  4. Алгоритм Борувки
  5. Теорема Тарьяна (критерий минимальности остовного дерева)
  6. Алгоритм двух китайцев (7)
    1. Англоязычные термины оформить правильно
    2. Добавить определение покрывающего дерева
    3. Описать реализацию красиво
    4. Дефис заменить на тире
    5. Отформатировать псевдокод
    6. Доказать, почему не более V конденсаций
    7. Источники информации оформить правильно
    8. Доказать второе замечание
    9. Добавить отступы в описании примера
    10. 5ый пункт в описании алгоритма расписать чуть понятней
    11. Категория

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

= Эйлеровы графы

  1. Алгоритм построения Эйлерова цикла (2)
    1. Какое-то мутное доказательство леммы про корректность алгоритма

=== Гамильтовы графы

  1. Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре

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

  1. Обход в глубину, цвета вершин
  2. Лемма о белых путях
  3. Использование обхода в глубину для проверки связности
  4. Использование обхода в глубину для поиска цикла в ориентированном графе
  5. Использование обхода в глубину для топологической сортировки
  6. Использование обхода в глубину для поиска компонент сильной связности
  7. Использование обхода в глубину для поиска точек сочленения
  8. Построение компонент вершинной двусвязности
  9. Использование обхода в глубину для поиска мостов
  10. Построение компонент реберной двусвязности

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

  1. Обход в ширину
  2. Алгоритм Форда-Беллмана
  3. Алгоритм Дейкстры
  4. Алгоритм Флойда
  5. Алгоритм Джонсона
  6. Алгоритм Левита
  7. Алгоритм A*
  8. Алгоритм D*
  9. Эвристики для поиска кратчайших путей

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

  1. Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
  2. Алгоритм Куна для поиска максимального паросочетания
  3. Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
    1. как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками

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

  1. Определение сети, потока
  2. Разрез, лемма о потоке через разрез
  3. Дополняющая сеть, дополняющий путь
  4. Лемма о сложении потоков
  5. Теорема Форда-Фалкерсона
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
  7. взяли Алоритм Эдмондса-Карпа (5)
    1. Полностью описать пример про грибок с картинками в конспекте
  8. Алгоритм масштабирования потока
  9. взяли Блокирующий поток (1)
    1. англоязычные термины
    2. ссылки на русскую и английскую википедию
    3. Добавить немного общей информации
    4. Расположить красиво картинки, чтобы не наезжали
  10. Схема алгоритма Диница
  11. fixed Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями (6)
    1. может, назвать остаточную сеть [math]G_f[/math], как в предыдущих конспектах?
    2. "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
    3. В лемме в утверждении фигурирует поток [math]f[/math], но дальше про него ничего нет. Зачем он?
    4. "Мы можем применить Лемму(2" — лемму 3, наверное?
    5. Дефисы на тире
    6. Знаки неравенств
    7. Источники информации
  12. Алгоритм поиска блокирующего потока в ациклической сети
    1. !!! (10) алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. !!! Метод проталкивания предпотока (7)
    1. Картиночки с резервуарами!
    2. Источники информации
    3. Добавить см. также
    4. Дефисы заменить на тире
    5. Отформатировать псевдокоды
  14. Алгоритм "поднять-в-начало"
  15. Теорема о декомпозиции
  16. fixed Теорема о декомпозиционном барьере (3)
    1. Источники информации
    2. Пояснить,почему такие константы используются
    3. Увеличить дроби
    4. А что из этой теоремы следует?
  17. Циркуляция потока
  18. Алгоритм Каргера для нахождения минимального разреза

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

  1. Поток минимальной стоимости
  2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
  3. fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
    1. Интервики на декомпозицию
    2. Знаки неравенств
    3. Источники информации
  4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
  5. !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
    1. Написать и оформить так, чтобы не было чуши
  6. взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
    1. Взять задачи в шаблон
    2. Оформить покрасивей и правильней
  7. Венгерский алгоритм решения задачи о назначениях
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_графов:Тикеты&oldid=61939»