748
правок
Изменения
→2 Связность в графах
# Категория
</ol>
== 2 Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]] 4
## разобраться с доказательством теоремы из 7 пунктов
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
# [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
# [[Задача о динамической связности]]
== Обходы графов ==
=== 2 3 Эйлеровы графы ===
# [[Алгоритм построения Эйлерова цикла]] (2)
## Какое-то мутное доказательство леммы про корректность алгоритма
=== 3 4 Гамильтовы графы ===
<ol value="2">
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
</ol>
== 45. Обход в глубину ==
# [[Обход в глубину, цвета вершин]] 1
## поправить тех (цифры и аргументы функций)
## поправить тех для "dfs", "paint"
== 56. Кратчайшие пути в графах ==# взяли [[Обход в ширину]] 5
## исправить речевые ошибки в описании
## поправить тех
## вряд ли 16MB памяти в таблице про Европу
== 67. Задача о паросочетании ==
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
# [[Алгоритм Куна для поиска максимального паросочетания]] 0.5
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 78. Задача о максимальном потоке ==
# [[Определение сети, потока]] 0.5
## добавить "см. также"
## добавить "см. также"
== 89. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи
<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] перенаправляется на "Поиск потока мин.стоимости...", который ниже есть -->
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5
## добавить "см. также"
## поправить тех сигм
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]0.5
## поправить тех "G"
# взяли [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]]0.5
## поправить тех
## сделать wikitable
