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
## поправить тех у "dfs"
# [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] (7)
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
== 78. Задача о максимальном потоке ==# [[Определение сети, потока]]0.5
## добавить "см. также"
# [[Разрез, лемма о потоке через разрез]]0.5
## добавить "см. также"
## поправить тех для чисел
# [[Дополняющая сеть, дополняющий путь]]0.5
## добавить "см. также"
# [[Лемма о сложении потоков]]0.5
## добавить "см. также"
# [[Теорема Форда-Фалкерсона]]0.5
## исправить "\text{in}"
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]0.5
## нормально расположить картинки
# [[Алгоритм Эдмондса-Карпа]] (0,25).5
## Добавить см также
# [[Алгоритм масштабирования потока]]
## Добавить немного общей информации
## Интервики
# [[Схема алгоритма Диница]]0.5
## добавить "см. также"
## поправить тех
## Дефисы заменить на тире
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]2
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
## поправить тех
# [[Теорема о декомпозиции]]0.5
## добавить "см. также"
## поправить "-" в псевдокоде
# [[Теорема о декомпозиционном барьере]]1
## оформить следствие
# [[Циркуляция потока]]0.5
## поправить тех
## добавить "см. также"
# [[Алгоритм Каргера для нахождения минимального разреза]]3
## поправить сигму в определении веса разреза и определение множества там же
## поправить псевдокод (если возможно)
## добавить "см. также"
== 89. Задача о потоке минимальной стоимости ==
# [[Поток минимальной стоимости]] 3
## исправить замечания из обсуждения статьи
<!-- # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] перенаправляется на "Поиск потока мин.стоимости...", который ниже есть -->
# [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]] 0.5
## добавить "см. также"
## поправить тех сигм
# [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]0.5
## поправить тех "G"
# взяли [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]] (5)
## Написать и оформить так, чтобы не было чуши
# [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]] (0,5)
## Добавить см также
## Источники информации оформить нормально
# [[Венгерский алгоритм решения задачи о назначениях]]0.5
## поправить тех
## сделать wikitable
