Изменения

# ''fixed'' [[Укладка графа на плоскости]]

# ''fixed'' [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]

# ''fixed'' [[Теорема Понтрягина-Куратовского]]

# ''fixed'' [[Двойственный граф планарного графа]]

# ''fixed'' [[Раскраска графа]]

# '''!!!''' [[Алгоритм Куна для поиска максимального паросочетания]]

* # ''fixed'' [[Определение сети, потока]]* ## ссылки на русскую и английскую википедию# ''fixed'' [[Разрез, лемма о потоке через разрез]]* ## англоязычные термины## добавить определение минимального разреза## ссылки на русскую и английскую википедию# ''fixed'' [[Дополняющая сеть, дополняющий путь]]* ## Дополняющую сеть также называют остаточной, указать это## ссылки на русскую и английскую википедию# ''fixed'' [[Лемма о сложении потоков]]* ## добавить внутренних ссылок# [[Теорема Форда-Фалкерсона]]* # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]* ## гм, и зачем "дельта" русским словом в псевдокоде?## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.# [[Алоритм Эдмондса-Карпа]]* ## а описание алгоритма где?## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?## ссылки на русскую/английскую википедию# [[Алгоритм масштабирования потока]]* ## ссылки на русскую/английскую википедию## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.# [[Блокирующий поток]]* ## англоязычные термины## ссылки на русскую и английскую википедию# [[Схема алгоритма Диница]]* ## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте## "makeGl" назвать как-нибудь нормально## "algorithmDinica" тоже назвать нормально# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]* ## может, назвать остаточную сеть $G_f$, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоли?## В лемме в утверждении фигурирует поток $f$, но дальше про него ничего нет. Зачем он?## "Мы можем применить Лемму(2" — лемму 3, наверное?# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]]* ## "Жадный Алгоритм" — зачем с большой буквы алгоритм?## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то херовый, переписать псевдокод для этого алгоритма польностью, чтобы было приближено к реальной реализации## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# [[Метод проталкивания предпотока]]* ## зачем какие-то кванторы в for?## initialaze -> initialize## названия функций в тексте оборачиваются в \mathrm# [[Алгоритм "поднять-в-начало"]]* ## названия функций в тексте оборачиваются в \mathrm## relable -> relabel# [[Теорема о декомпозиции]]* ## кванторы в псевдокоде не нужну, написать просто not exists# [[Теорема о декомпозиционном барьере]]* # [[Циркуляция потока]]* ## англоязычные термины## ссылки на русскую и английскую википедию## раздел постановка задачи не нужен, перенести в заголовок## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами# [[Алгоритм Каргера для нахождения минимального разреза]]## внутреннюю ссылку на мультиграф## названия функций в тексте оборачиваются в \mathrm

* # [[Поток минимальной стоимости]]* ## "Найти любой поток величины..." -- а почему так получится поток минимальной стоимости? (видимо, надо сослаться на лемму)# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]* # [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]* # [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* # [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]* # [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]* # '''!!!''' [[Венгерский алгоритм решения задачи о назначениях]]## написать более подробный псевдокод