748
правок
Изменения
→2 Связность в графах
# Категория
</ol>
== 2 Связность в графах ==
# [[Отношение связности, компоненты связности]]
# [[Отношение реберной двусвязности]]
# [[Отношение вершинной двусвязности]]
# [[Точка сочленения, эквивалентные определения]] 4
## разобраться с доказательством теоремы из 7 пунктов
# [[Мост, эквивалентные определения]]
# [[Граф компонент реберной двусвязности]]
# [[Граф блоков-точек сочленения]]
# [[k-связность]]
# [[Теорема Менгера]]
# [[Теорема Менгера, альтернативное доказательство]]
# [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]
# [[Задача о динамической связности оффлайн]]<tex>^\star</tex>
# [[Задача о динамической связности]]
== Обходы графов ==
=== 2 3 Эйлеровы графы ===
# [[Алгоритм построения Эйлерова цикла]] (2)
## Какое-то мутное доказательство леммы про корректность алгоритма
=== 3 4 Гамильтовы графы ===
<ol value="2">
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li>
</ol>
== 45. Обход в глубину ==# [[Обход в глубину, цвета вершин]] 1
## поправить тех (цифры и аргументы функций)
## разделить функции в псевдокоде
## убрать из названия конспекта "цвета вершин"
## Заменить "NILL" на что-то более подходящее
# [[Лемма о белых путях]]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"
== 56. Кратчайшие пути в графах ==# [[Обход в ширину]]5
## исправить речевые ошибки в описании
## поправить тех
## поправить псевдокод ("in", "=="(хотя уже есть <tex>\ne</tex>), "Q = <tex>\varnothing</tex>")
## добавить "см. также"
# [[Алгоритм Форда-Беллмана]]6
## поправить тех для чисел
## из s достижимы циклы отрицательного веса <tex>\nRightarrow</tex> не существует кратчайших путей
## в таблице из оценки сложности поиск минимума не правильно указан для двоичной кучи и для фибоначчиевой кучи
## добавить "см. также"
# [[Алгоритм Флойда]]1.5
## поправить нерабочий тех
## переписать, чтобы индексация d была везде через "[]"
## комментарии в псевдокоде несодержательны
# [[Алгоритм Джонсона]]0.5
## поправить псевдокод
# [[Алгоритм Левита]]3
## избавиться от тернарного оператора
## поправить тех min
## про реализацию через дек внести ясность
## утверждение о сложности обернуть в соответствующих шаблон
# [[Алгоритм A*]]5
## теорема доказана не полностью
# [[Алгоритм D*]]4
## ссылки на доказательства заменить на доказательства
## использование g(s) до ее определения
## описание сделать более информативным - что за что отвечает и когда предполагается, что будет изменятся
## добавить "см. также"
# [[Эвристики для поиска кратчайших путей]]0.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
