3622
правки
Изменения
→10. Задача о максимальном потоке (проверяется): проверена
## И вообще всё оформить надо
== 10. Задача о максимальном потоке (проверяется) ==# ''fixed'' [[Определение сети, потока]]## Оформить правильно источники информации## Правильно оформить англоязычные термины## Интервики## Исправить знаки неравенств## Дефисы на тире# '''!!!''' [[Разрез, лемма о потоке через разрез]](4)
## Оформить правильно англоязычные термины
## Списки кривые
## Источники информации
## Нарисовать красивую картинку вместо текущей
# '''fixed''' [[Дополняющая сеть, дополняющий путь]]#[[Лемма о сложении потоков]] (0.5)# Англоязычные термины правильно оформить# Переименовать конспект## Оформить правильно источники информацииУбрать "Также есть..."## Нарисовать примерВынести названия лемм в заголовки шаблонов# ''fixed'' [[Лемма о сложении потоковТеорема Форда-Фалкерсона]]## Дефисы на тире(0.5)
## Знаки неравенств
## Убрать "Аналогичная"# [[Теорема Форда-Фалкерсона]]## Знаки неравенств, источники Источники информации# '''!!!''' [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]](5)
## гм, и зачем "дельта" русским словом в псевдокоде?
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока и отрефакторить псевдокод
## Источники информации
## Знаки неравенств
## Подробней пояснить пример несходимости# '''!!!''' [[Алоритм Эдмондса-Карпа]](7)
## а описание алгоритма где?
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
## Знаки неравенств
## Добавить про грибок в конспект
# [[Алгоритм масштабирования потока]](3)
## ссылки на русскую/английскую википедию
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
## Отформатировать псевдокод
## Источники информации## См. также## Увеличить картинки# [[Блокирующий поток]](1)
## англоязычные термины
## ссылки на русскую и английскую википедию
## Добавить немного общей информации
## Расположить красиво картинки, чтобы не наезжали# '''взяли!!!''' [[Схема алгоритма Диница]](6)
## "динамические деревья Слетора и Тарьяна" — ссылку внешнюю хотя бы сделайте
## "makeGl" назвать как-нибудь нормально
## Интервики
## Написать более подробный псевдокод
# '''!!!''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]](6)
## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?
## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слистая слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, чтоличто ли?
## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?
## "Мы можем применить Лемму(2" — лемму 3, наверное?
## Дефисы на тире, знаки ## Знаки неравенств, источники ## Источники информации# '''!!!''' [[Алгоритм поиска блокирующего потока в ациклической сети]](5)
## "Жадный Алгоритм" — зачем с большой буквы алгоритм?
## Не нравится мне dfs без аргументов в удаляющем обходе, вообще он какой-то плохой, переписать псевдокод для этого алгоритма польностьюполностью, чтобы было приближено к реальной реализации## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, возможно, добавить картиночку, а может даже вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# '''!!!''' [[Метод проталкивания предпотока]](7)
## зачем какие-то кванторы в for?
## initialaze -> initialize
## Англоязычные термины
## Отформатировать псевдокоды
# # Больше неформальных описаний, чтобы было понятно## За картиночки с резервуарами {{---}} отдельные большие бонусы!# '''!!!''' [[Алгоритм "поднять-в-начало"]](5, но сначала лучше сделать предыдущий)
## названия функций в тексте оборачиваются в \mathrm или \mathtt
## relable -> relabel
## Англоязычные термины оформить правильно
## Отформатировать псевдокоды
# [[Теорема о декомпозиции]]## кванторы в псевдокоде не нужну, написать просто not exists, и вообще отформатировать псевдокод(3)
## Дефисы на тире
## Переписать формулировку теоремы
## Отформатировать псевдокод
## Оформить правильно источники информации
# [[Теорема о декомпозиционном барьере]](3)
## Источники информации
## Пояснить,почему такие константы используются
## Увеличить дроби## А что из этой теоремы следует?# [[Циркуляция потока]](3)
## англоязычные термины
## ссылки на русскую и английскую википедию
## сделать псевдокод чуть менее абстрактным и оформленным в соответствии с правилами
## Источники информации
# [[Алгоритм Каргера для нахождения минимального разреза]](2)
## внутреннюю ссылку на мультиграф
## названия функций в тексте оборачиваются в \mathrm или \mathtt
