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