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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Построение остовных деревьев)
(→‎2 Связность в графах)
 
(не показано 37 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== 1. Основные определения теории графов ==
+
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)
−
# [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
 
−
# [[Лемма о рукопожатиях]]
 
−
# [[Теорема о существовании простого пути в случае существования пути]]
 
−
# [[Теорема о существовании простого цикла в случае существования цикла]]
 
−
# [[Матрица смежности графа]]
 
−
# [[Матрица инцидентности графа]] (4 ''или больше, зависит от свойств'')
 
−
## Добавить свойства матрицы инцидентности с доказательствами
 
−
## Источники -> Источники информации
 
−
## Добавить про списки смежности и их оформить тоже в таблички
 
−
# [[Циклическое пространство графа]]
 
−
# [[Фундаментальные циклы графа]]
 
−
# [[Дерево, эквивалентные определения]]
 
−
# [[Алгоритмы на деревьях]]
 
−
# [[Дополнительный, самодополнительный граф]]
 
−
# [[Теоретико-множественные операции над графами]]
 
−
# [[Рёберное ядро]] (2)
 
−
## Добавить больше интервики в конспект
 
−
## В конце теоремы в доказательстве какая-то лажа
 
−
## Источники информации
 
−
## Оформить следствия красиво
 
−
# [[Факторизация графов]]
 
−
 
 
−
== 2. Связность в графах ==
 
−
# [[Отношение связности, компоненты связности]]
 
−
# [[Отношение реберной двусвязности]]
 
−
# [[Отношение вершинной двусвязности]]
 
−
# [[Точка сочленения, эквивалентные определения]]
 
−
# [[Мост, эквивалентные определения]]
 
−
# [[Граф компонент реберной двусвязности]]
 
−
# [[Граф блоков-точек сочленения]]
 
−
# [[k-связность]]
 
−
# [[Теорема Менгера]]
 
−
# [[Теорема Менгера, альтернативное доказательство]]
 
−
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] (1.5)
 
−
## пункт "Определения" не нужен
 
−
## Изменить знаки неравенств в tex
 
−
## Не надо дублировать определения из другого конспекта
 
−
## Отформатировать псевдокод
 
−
## find_flow какой-то стрёмный
 
−
## Источники информации
 
−
## k-связность с маленькой буквы
 
−
## Добавить См. также на что-нибудь разумное
 
−
## Добавить см. также
 
  
−
== 3. Остовные деревья ==
+
== 1. Остовные деревья ==
 
=== Построение остовных деревьев ===
 
=== Построение остовных деревьев ===
 
<ol>
 
<ol>
Строка 51: Строка 8:
 
<li> [[Алгоритм Краскала]] </li>
 
<li> [[Алгоритм Краскала]] </li>
 
<li> [[Алгоритм Борувки]] </li>
 
<li> [[Алгоритм Борувки]] </li>
−
<li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]] (5) </li>
+
<li> [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]</li>
−
# Доказательство красиво оформить
 
−
# Заменить дефис на шаблон
 
−
# Зачем там написано про Краскала? Если алгоритм доказывается через критерий, то надо в отдельный пункт
 
−
# Почему ребро uv {{---}} единственное ребро, пересекающее разрез?
 
−
# Источники информации
 
−
# Знаки неравенств
 
−
# Категория
 
 
<li> [[Алгоритм двух китайцев]] (7) </li>
 
<li> [[Алгоритм двух китайцев]] (7) </li>
 
# Англоязычные термины оформить правильно
 
# Англоязычные термины оформить правильно
Строка 73: Строка 23:
 
</ol>
 
</ol>
  
−
=== Свойства остовных деревьев ===
+
== 2 Связность в графах ==
−
<ol>
+
# [[Отношение связности, компоненты связности]]
−
<li value="7">[[Матрица Кирхгофа]]</li>
+
# [[Отношение реберной двусвязности]]
−
<li> [[Связь матрицы Кирхгофа и матрицы инцидентности]] </li>
+
# [[Отношение вершинной двусвязности]]
−
<li> [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]] </li>
+
# [[Точка сочленения, эквивалентные определения]] 4
−
<li> [[Количество помеченных деревьев]] </li>
+
## разобраться с доказательством теоремы из 7 пунктов
−
<li> [[Коды Прюфера]] </li>
+
# [[Мост, эквивалентные определения]]
−
</ol>
+
# [[Граф компонент реберной двусвязности]]
 +
# [[Граф блоков-точек сочленения]]
 +
# [[k-связность]]
 +
# [[Теорема Менгера]]
 +
# [[Теорема Менгера, альтернативное доказательство]]
 +
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
 +
# [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
 +
# [[Задача о динамической связности]]
 +
 
 +
== Обходы графов ==
 +
=== 3 Эйлеровы графы ===
  
−
== 4. Обходы графов ==
+
# [[Алгоритм построения Эйлерова цикла]] (2)
−
=== Эйлеровы графы ===
+
## Какое-то мутное доказательство леммы про корректность алгоритма
−
<ol>
 
−
<li value="1"> [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]</li>
 
−
<li> ''взяли'' [[Покрытие ребер графа путями]] (3)</li>
 
−
# Какое-то мутное доказательства
 
−
<li> [[Алгоритм построения Эйлерова цикла]] (2) </li>
 
−
# Какое-то мутное доказательство леммы про корректность алгоритма
 
−
<li> [[Произвольно вычерчиваемые из заданной вершины графы]] </li>
 
−
</ol>
 
  
−
=== Гамильтоновы графы ===
+
=== 4 Гамильтовы графы ===
−
<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> '''взяли''' [[Турниры]] (6) </li>
 
−
# Доказательства всех утверждений из конспекта (эквивалентность утверждений и конденсация)
 
−
<li> [[Теорема Редеи-Камиона]] </li>
 
 
</ol>
 
</ol>
  
−
== 5. Укладки графов ==
+
== 5. Обход в глубину ==
−
# [[Укладка графа на плоскости]]
+
# [[Обход в глубину, цвета вершин]] 1
−
# [[Формула Эйлера]]
+
## поправить тех (цифры и аргументы функций)
−
# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]] (0.5)
+
## разделить функции в псевдокоде
−
## Исправить знаки неравенств
+
## убрать из названия конспекта "цвета вершин"
−
## Источники информации
+
## Заменить "NILL" на что-то более подходящее
−
## Константы в Tex
+
# [[Лемма о белых путях]] 1
−
# [[Укладка дерева]]
+
## поправить тех (названия функций)
−
# [[Укладка графа с планарными компонентами реберной двусвязности]]
+
## добавить "см. также"
−
# [[Укладка графа с планарными компонентами вершинной двусвязности]]
+
## "...есть как белые, так и черные, и серые вершины" - бред
−
# [[Теорема Понтрягина-Куратовского]]
+
## источники информации
−
# [[Род, толщина, крупность, число скрещиваний]]
+
# [[Использование обхода в глубину для проверки связности]] 2
−
# [[Двойственный граф планарного графа]]
+
## СНМ не к месту
−
# [[Теорема Фари]]
+
## источники информации
−
# [[Гамма-алгоритм]]
+
# [[Использование обхода в глубину для поиска цикла]] 3
 +
## добавить реализацию для неориентированного графа
 +
# [[Использование обхода в глубину для топологической сортировки]] 3
 +
## поправить теорему в "постановке задачи"
 +
## поправить тех для dfs-ов
 +
## поправить тех в псевдокоде
 +
## описать в псевдокоде ans, visited
 +
## пример отнести к применениям
 +
# [[Использование обхода в глубину для поиска компонент сильной связности]] 2
 +
## тех для чисел
 +
## максимально перевести объяснения в коде на русском в псевдокод
 +
## "см. также"
 +
# [[Использование обхода в глубину для поиска точек сочленения]] 2
 +
## разделить функции в псевдокоде
 +
## добавить комментарии к псевдокоду
 +
# [[Построение компонент вершинной двусвязности]] 0.5
 +
## поправить тех (для "dfs", "paint")
 +
# [[Использование обхода в глубину для поиска мостов]] 1
 +
## шаблон "задача"
 +
## 2 одинаковых "enter(x)" в описании ret(v)
 +
## "enter" и "ret" (как функции) - в \mathrm
 +
# [[Построение компонент реберной двусвязности]] 0.5
 +
## поправить тех для "dfs", "paint"
  
−
== 6. Раскраски графов ==
+
== 6. Кратчайшие пути в графах ==
−
# [[Раскраска графа]]
+
# [[Обход в ширину]] 5
−
# ''fixed'' [[Двудольные графы и раскраска в 2 цвета]] (3)
+
## исправить речевые ошибки в описании
−
## Англоязычные термины
+
## поправить тех
−
## Убрать определение двудольного графа и сделать интервики на основной конспект
+
## 0-1 bfs переписать
−
## Картинку двудольного графа перенести ниже, а то плохо смотрится
+
## нормально сформулировать доказательство 1ого утверждения
−
## Интервики
+
## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")
−
## Добавить, что можно ещё за проход в ширину проверить
+
## добавить "см. также"
−
## Оформить правильно источники информации и См. также
+
# [[Алгоритм Форда-Беллмана]] 6
−
## Перенести см. также до источников информации, а ссылку заменить на интервики
+
## поправить тех для чисел
−
# [[Хроматический многочлен]]
+
## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей
−
# [[Формула Зыкова]]
+
## весь конспект бессвязный - не ясно что к чему и как относится. Нормально структурировать
−
# [[Формула Уитни]]
+
## сделать доказательство первой леммы более содержательным
−
# [[Теорема Брукса]]
+
## пункт "Псевдокод" - бред почти полностью
−
# [[Верхние и нижние оценки хроматического числа]]
+
## иногда w(x, y), иногда w(xy) - исправить; обычно написано в неверном порядке
−
# [[Хроматическое число планарного графа]]
+
## систематизировать комментарии в псевдокоде (добавить, сделать содержательными)
−
# [[Многочлен Татта]]
+
## добавить "см. также"
−
# [[Теория Рамсея]] ('''10''')
+
# [[Алгоритм Дейкстры]] 0.5
−
## Тут вообще ад какой-то
+
## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи
 +
## добавить "см. также"
 +
# [[Алгоритм Флойда]] 1.5
 +
## поправить нерабочий тех
 +
## переписать, чтобы индексация d была везде через "[]"
 +
## комментарии в псевдокоде несодержательны
 +
# [[Алгоритм Джонсона]] 0.5
 +
## поправить псевдокод
 +
# [[Алгоритм Левита]] 3
 +
## избавиться от тернарного оператора
 +
## поправить тех min
 +
## формализовать (хотя бы частично) доказательство лемм (возможно, добавить еще)
 +
## про реализацию через дек внести ясность
 +
## утверждение о сложности обернуть в соответствующих шаблон
 +
# [[Алгоритм A*]] 5
 +
## теорема доказана не полностью
 +
# [[Алгоритм D*]] 4
 +
## ссылки на доказательства заменить на доказательства
 +
## использование g(s) до ее определения
 +
## описание g(s) очень мутное
 +
## "исходящие" и "входящие" вершины - правильно назвать
 +
## в определении rhs не хватает скобок
 +
## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
 +
## добавить "см. также"
 +
# [[Эвристики для поиска кратчайших путей]] 0.5
 +
## поправить тех
 +
## вряд ли 16MB памяти в таблице про Европу
  
−
== 7. Обход в глубину ==
+
== 7. Задача о паросочетании ==
−
# '''fixed''' [[Обход в глубину, цвета вершин]] (5)
 
−
## Англоязычные термины правильно оформить
 
−
## Отформатировать псевдокод
 
−
## Красивую картинку с цветными вершинами
 
−
# [[Лемма о белых путях]]
 
−
# [[Использование обхода в глубину для проверки связности]]
 
−
# [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
 
−
# [[Использование обхода в глубину для топологической сортировки]]
 
−
# [[Использование обхода в глубину для поиска компонент сильной связности]]
 
−
# ''fixed'' [[Использование обхода в глубину для поиска точек сочленения]] (4)
 
−
## Что-то картинки неудачно расположены
 
−
## Кривая структура у доказательства
 
−
## Отформатировать псевдокод
 
−
## Источники информации красиво оформить
 
−
# [[Построение компонент вершинной двусвязности]]
 
−
# [[Использование обхода в глубину для поиска мостов]]
 
−
# [[Построение компонент реберной двусвязности]]
 
−
 
 
−
== 8. Кратчайшие пути в графах ==
 
−
# [[Обход в ширину]]
 
−
# [[Алгоритм Форда-Беллмана]]
 
−
# [[Алгоритм Дейкстры]]
 
−
# [[Алгоритм Флойда]]
 
−
# [[Алгоритм Джонсона]]
 
−
# [[Алгоритм Левита]]
 
−
# [[Алгоритм A*]]
 
−
# [[Алгоритм D*]]
 
−
# [[Эвристики для поиска кратчайших путей]]
 
−
 
 
−
== 9. Задача о паросочетании ==
 
−
# [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
 
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
−
# [[Алгоритм Куна для поиска максимального паросочетания]]
+
# [[Алгоритм Куна для поиска максимального паросочетания]] 0.5
−
# [[Теорема Холла]]
+
## поправить тех у "dfs"
−
# [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
+
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
−
# [[Связь вершинного покрытия и независимого множества]]
 
−
# [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
 
−
# [[Теорема Татта о существовании полного паросочетания]]
 
−
# '''!!!''' [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
 
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
 
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
−
# [[Декомпозиция Эдмондса-Галлаи]]
 
−
# '''взяли''' [[Задача об устойчивом паросочетании]] ''(все правки стоят 10 баллов)''
 
−
## Переменные и константы в Tex
 
−
## Добавить сначала постановку задачи
 
−
## Кривая ссылка на паросочетание
 
−
## Дефисы на тире
 
−
## Определения выделять жирным
 
−
## Отформатировать псевдокоды
 
−
## Зачем-то списки в доказательствах лемм использованы
 
−
## Битая ссылка на соседей
 
−
## Надо бы доказать все леммы
 
−
## Оформить правильно источники информации
 
−
## И вообще всё оформить надо
 
  
−
== 10. Задача о максимальном потоке ==
+
== 8. Задача о максимальном потоке ==
−
# [[Определение сети, потока]]
+
# [[Определение сети, потока]] 0.5
−
# [[Разрез, лемма о потоке через разрез]]  
+
## добавить "см. также"
−
# [[Дополняющая сеть, дополняющий путь]]
+
# [[Разрез, лемма о потоке через разрез]] 0.5
−
# [[Лемма о сложении потоков]]
+
## добавить "см. также"
−
# [[Теорема Форда-Фалкерсона]]
+
## поправить тех для чисел
−
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
+
# [[Дополняющая сеть, дополняющий путь]] 0.5
−
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (5)
+
## добавить "см. также"
−
## Полностью описать пример про грибок с картинками в конспекте
+
# [[Лемма о сложении потоков]] 0.5
 +
## добавить "см. также"
 +
# [[Теорема Форда-Фалкерсона]] 0.5
 +
## исправить "\text{in}"
 +
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] 0.5
 +
## нормально расположить картинки
 +
# [[Алгоритм Эдмондса-Карпа]] 0.5
 +
## Добавить см также
 
# [[Алгоритм масштабирования потока]]
 
# [[Алгоритм масштабирования потока]]
−
# ''взяли'' [[Блокирующий поток]] (1)
+
# [[Блокирующий поток]] (0,5)
−
## англоязычные термины
 
−
## ссылки на русскую и английскую википедию
 
 
## Добавить немного общей информации
 
## Добавить немного общей информации
−
## Расположить красиво картинки, чтобы не наезжали
+
## Интервики
−
# [[Схема алгоритма Диница]]
+
# [[Схема алгоритма Диница]] 0.5
−
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)
+
## добавить "см. также"
−
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
+
## поправить тех
−
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?
+
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]  
−
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
+
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
−
## "Мы можем применить Лемму(2" — лемму 3, наверное?
+
## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении  
−
## Дефисы на тире
+
# [[Метод проталкивания предпотока]] (7)
−
## Знаки неравенств
 
−
## Источники информации
 
−
# [[Алгоритм поиска блокирующего потока в ациклической сети]]
 
−
## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
 
−
# '''!!!''' [[Метод проталкивания предпотока]] (7)
 
 
## Картиночки с резервуарами!
 
## Картиночки с резервуарами!
 
## Источники информации
 
## Источники информации
Строка 235: Строка 173:
 
## Дефисы заменить на тире
 
## Дефисы заменить на тире
 
## Отформатировать псевдокоды
 
## Отформатировать псевдокоды
−
# [[Алгоритм "поднять-в-начало"]]
+
# [[Алгоритм "поднять-в-начало"]] 2
−
# [[Теорема о декомпозиции]]
+
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
−
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)
+
## поправить тех
−
## Источники информации
+
# [[Теорема о декомпозиции]] 0.5
−
## Пояснить,почему такие константы используются
+
## добавить "см. также"
−
## Увеличить дроби
+
## поправить "-" в псевдокоде
−
## А что из этой теоремы следует?
+
# [[Теорема о декомпозиционном барьере]] 1
−
# [[Циркуляция потока]]
+
## оформить следствие
−
# [[Алгоритм Каргера для нахождения минимального разреза]]
+
# [[Циркуляция потока]] 0.5
 +
## поправить тех
 +
## добавить "см. также"
 +
# [[Алгоритм Каргера для нахождения минимального разреза]] 3
 +
## поправить сигму в определении веса разреза и определение множества там же
 +
## поправить псевдокод (если возможно)
 +
## поправить комментарий в псевдокоде
 +
## теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать
 +
## <tex>e^{count⋅(−\frac{2}{n^2})}=e^{−2ln(n)}</tex> - это как вообще?
 +
## <tex>\log</tex> можно использовать без базы только в оценках <tex>O(...)</tex>
 +
## заменить "/" на "\frac"
 +
## добавить "см. также"
  
−
== 11. Задача о потоке минимальной стоимости ==
+
== 9. Задача о потоке минимальной стоимости ==
−
# [[Поток минимальной стоимости]]
+
# [[Поток минимальной стоимости]] 3
−
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
+
## исправить замечания из обсуждения статьи
−
# ''fixed'' [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] (0.5)
+
<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] перенаправляется на "Поиск потока мин.стоимости...", который ниже есть -->
−
## Интервики на декомпозицию
+
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5
−
## Знаки неравенств
+
## добавить "см. также"
−
## Источники информации
+
## поправить тех сигм
−
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
+
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] 0.5
−
# '''!!!''' [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
+
## поправить тех "G"
 +
# [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
 
## Написать и оформить так, чтобы не было чуши
 
## Написать и оформить так, чтобы не было чуши
−
# ''взяли'' [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0.5)
+
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
−
## Взять задачи в шаблон
+
## Добавить см также
−
## Оформить покрасивей и правильней
+
## Источники информации оформить нормально
−
# [[Венгерский алгоритм решения задачи о назначениях]]
+
# [[Венгерский алгоритм решения задачи о назначениях]] 0.5
 +
## поправить тех
 +
## сделать wikitable

Текущая версия на 16:33, 5 сентября 2019

Тикеты индексируются как "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. Отношение реберной двусвязности
  3. Отношение вершинной двусвязности
  4. Точка сочленения, эквивалентные определения 4
    1. разобраться с доказательством теоремы из 7 пунктов
  5. Мост, эквивалентные определения
  6. Граф компонент реберной двусвязности
  7. Граф блоков-точек сочленения
  8. k-связность
  9. Теорема Менгера
  10. Теорема Менгера, альтернативное доказательство
  11. Вершинная, реберная связность, связь между ними и минимальной степенью вершины
  12. Задача о динамической связности оффлайн[math]^\star[/math]
  13. Задача о динамической связности

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

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

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

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

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

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

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

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

  1. Обход в ширину 5
    1. исправить речевые ошибки в описании
    2. поправить тех
    3. 0-1 bfs переписать
    4. нормально сформулировать доказательство 1ого утверждения
    5. поправить псевдокод ("in", "=="(хотя уже есть [math]\ne[/math]), "Q = [math]\varnothing[/math]")
    6. добавить "см. также"
  2. Алгоритм Форда-Беллмана 6
    1. поправить тех для чисел
    2. из s достижимы циклы отрицательного веса [math]\nRightarrow[/math] не существует кратчайших путей
    3. весь конспект бессвязный - не ясно что к чему и как относится. Нормально структурировать
    4. сделать доказательство первой леммы более содержательным
    5. пункт "Псевдокод" - бред почти полностью
    6. иногда w(x, y), иногда w(xy) - исправить; обычно написано в неверном порядке
    7. систематизировать комментарии в псевдокоде (добавить, сделать содержательными)
    8. добавить "см. также"
  3. Алгоритм Дейкстры 0.5
    1. в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи
    2. добавить "см. также"
  4. Алгоритм Флойда 1.5
    1. поправить нерабочий тех
    2. переписать, чтобы индексация d была везде через "[]"
    3. комментарии в псевдокоде несодержательны
  5. Алгоритм Джонсона 0.5
    1. поправить псевдокод
  6. Алгоритм Левита 3
    1. избавиться от тернарного оператора
    2. поправить тех min
    3. формализовать (хотя бы частично) доказательство лемм (возможно, добавить еще)
    4. про реализацию через дек внести ясность
    5. утверждение о сложности обернуть в соответствующих шаблон
  7. Алгоритм A* 5
    1. теорема доказана не полностью
  8. Алгоритм D* 4
    1. ссылки на доказательства заменить на доказательства
    2. использование g(s) до ее определения
    3. описание g(s) очень мутное
    4. "исходящие" и "входящие" вершины - правильно назвать
    5. в определении rhs не хватает скобок
    6. описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
    7. добавить "см. также"
  9. Эвристики для поиска кратчайших путей 0.5
    1. поправить тех
    2. вряд ли 16MB памяти в таблице про Европу

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

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

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

  1. Определение сети, потока 0.5
    1. добавить "см. также"
  2. Разрез, лемма о потоке через разрез 0.5
    1. добавить "см. также"
    2. поправить тех для чисел
  3. Дополняющая сеть, дополняющий путь 0.5
    1. добавить "см. также"
  4. Лемма о сложении потоков 0.5
    1. добавить "см. также"
  5. Теорема Форда-Фалкерсона 0.5
    1. исправить "\text{in}"
  6. Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину 0.5
    1. нормально расположить картинки
  7. Алгоритм Эдмондса-Карпа 0.5
    1. Добавить см также
  8. Алгоритм масштабирования потока
  9. Блокирующий поток (0,5)
    1. Добавить немного общей информации
    2. Интервики
  10. Схема алгоритма Диница 0.5
    1. добавить "см. также"
    2. поправить тех
  11. Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
  12. Алгоритм поиска блокирующего потока в ациклической сети (10)
    1. алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
  13. Метод проталкивания предпотока (7)
    1. Картиночки с резервуарами!
    2. Источники информации
    3. Добавить см. также
    4. Дефисы заменить на тире
    5. Отформатировать псевдокоды
  14. Алгоритм "поднять-в-начало" 2
    1. [math]O(V^3)[/math] не сравнимо с [math]O(V^2E)[/math]
    2. поправить тех
  15. Теорема о декомпозиции 0.5
    1. добавить "см. также"
    2. поправить "-" в псевдокоде
  16. Теорема о декомпозиционном барьере 1
    1. оформить следствие
  17. Циркуляция потока 0.5
    1. поправить тех
    2. добавить "см. также"
  18. Алгоритм Каргера для нахождения минимального разреза 3
    1. поправить сигму в определении веса разреза и определение множества там же
    2. поправить псевдокод (если возможно)
    3. поправить комментарий в псевдокоде
    4. теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать
    5. [math]e^{count⋅(−\frac{2}{n^2})}=e^{−2ln(n)}[/math] - это как вообще?
    6. [math]\log[/math] можно использовать без базы только в оценках [math]O(...)[/math]
    7. заменить "/" на "\frac"
    8. добавить "см. также"

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

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