Изменения

Перейти к: навигация, поиск

Метод проталкивания предпотока

7 байт добавлено, 22:32, 5 марта 2018
Описание
== Описание ==
Пусть дан граф <tex>G</tex>, в котором выделены две вершины: исток <tex>S</tex> и сток <tex>T</tex>, а у каждого ребра определена пропускная способность <tex>C(u,v)</tex>. Поток <tex>F</tex> можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. Т.е. То есть поток {{---}} функция <tex>F(u,v)</tex>, определённая на множестве рёбер графа.
Задача заключается в нахождении максимального потока.
693
правки

Навигация