Теория графов:Тикеты

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)

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

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

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

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

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

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

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

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

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

1. Обход в глубину, цвета вершин
   1. поправить тех (цифры и аргументы функций)
   2. разделить функции в псевдокоде
   3. убрать из названия конспекта "цвета вершин"
   4. Заменить "NILL" на что-то более подходящее
2. Лемма о белых путях
   1. поправить тех (названия функций)
   2. добавить "см. также"
   3. "...есть как белые, так и черные, и серые вершины" - бред
   4. источники информации
3. Использование обхода в глубину для проверки связности
   1. СНМ не к месту
   2. источники информации
4. Использование обхода в глубину для поиска цикла
   1. добавить реализацию для неориентированного графа
5. Использование обхода в глубину для топологической сортировки
   1. поправить теорему в "постановке задачи"
   2. поправить тех для dfs-ов
   3. поправить тех в псевдокоде
   4. описать в псевдокоде ans, visited
   5. пример отнести к применениям
6. Использование обхода в глубину для поиска компонент сильной связности
   1. тех для чисел
   2. максимально перевести объяснения в коде на русском в псевдокод
   3. "см. также"
7. Использование обхода в глубину для поиска точек сочленения
   1. разделить функции в псевдокоде
   2. добавить комментарии к псевдокоду
8. Построение компонент вершинной двусвязности
   1. поправить тех (для "dfs", "paint")
9. Использование обхода в глубину для поиска мостов
   1. шаблон "задача"
   2. 2 одинаковых "enter(x)" в описании ret(v)
   3. "enter" и "ret" (как функции) - в \mathrm
10. Построение компонент реберной двусвязности
    1. поправить тех для "dfs", "paint"

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

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

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

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

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

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

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

1. Поток минимальной стоимости 3
   1. исправить замечания из обсуждения статьи
2. Теорема Форда-Фалкерсона о потоке минимальной стоимости
3. Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
4. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
5. взяли Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
   1. Написать и оформить так, чтобы не было чуши
6. Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0,5)
   1. Добавить см также
   2. Источники информации оформить нормально
7. Венгерский алгоритм решения задачи о назначениях