Сетью называется ориентированный граф G=(V,E), каждому ребру (u,v) Î E которого поставлено в соответствие число c(u,v)³0, называемое пропускной способностью ребра..
Если (u,v) Ï E мы полагаем c(u,v)=0
В графе выделены две вершину: исток s и сток t .
Предполагаем, что в графе нет «бесполезных» вершин (каждая вершина лежит на каком-то пути из истока в сток)
Потоком в сети G называется функция f:V´V ¬R, обладающая следующими тремя свойствами.
Ограничение, связанное с пропускной способностью:
f (u,v) £ c(u,v) для всех u,v из V.
Кососимметричность:
f (u,v) = - f (v,u) для всех u,v из V.
Сохранение потока:
для всех u из V – {s,t}
Величина потока f определяется как сумма
Задача о максимальном потоке состоит в следующем: для данной сети G с истоком s и стоком t найти поток максимальной величины.
Разделим вещество, поступающее в данную вершину v и вещество, из нее выходящее.
Входящим потоком называется сумма
. Аналогично определяется выходящий поток.
Закон сохранения потока можно сформулировать так; для любой вершины, кроме истока и стока, входящий поток равен исходящему.
Пример сети