47
правок
Изменения
→7. Задача о максимальном потоке
== 7. Задача о максимальном потоке ==
# [[Определение сети, потока]]
## добавить "см. также"# [[Разрез, лемма о потоке через разрез]] ## добавить "см. также"## поправить тех для чисел
# [[Дополняющая сеть, дополняющий путь]]
## добавить "см. также"
# [[Лемма о сложении потоков]]
## добавить "см. также"
# [[Теорема Форда-Фалкерсона]]
## исправить "\text{in}"
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## нормально расположить картинки# [[Алоритм Алгоритм Эдмондса-Карпа]] (0,25)
## Добавить см также
# [[Алгоритм масштабирования потока]]
## Интервики
# [[Схема алгоритма Диница]]
## добавить "см. также"
## поправить тех
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
# [[Алгоритм поиска блокирующего потока в ациклической сети]] (10)
## Отформатировать псевдокоды
# [[Алгоритм "поднять-в-начало"]]
## <tex>O(V^3)</tex> не сравнимо с <tex>O(V^2E)</tex>
## поправить тех
# [[Теорема о декомпозиции]]
## добавить "см. также"
## поправить "-" в псевдокоде
# [[Теорема о декомпозиционном барьере]]
## оформить следствие
# [[Циркуляция потока]]
## поправить тех
## добавить "см. также"
# [[Алгоритм Каргера для нахождения минимального разреза]]
## поправить сигму в определении веса разреза и определение множества там же
## поправить псевдокод (если возможно)
## поправить комментарий в псевдокоде
## теорема не утверждает "что вероятность получить правильный ответ ... очень мала". Нормально сформулировать
## <tex>e^{count⋅(−\frac{2}{n^2})}=e^{−2ln(n)}</tex> - это как вообще?
## <tex>\log</tex> можно использовать без базы только в оценках <tex>O(...)</tex>
## заменить "/" на "\frac"
## добавить "см. также"
== 8. Задача о потоке минимальной стоимости ==
