Максимальный поток
Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D. Максимальный поток всегда является полным (обратное, вообще говоря, неверно). Введем для заданной транспортной сети D и допустимого потока j в этой сети орграф приращений I(D,j), имеющий те же вершины, что и сеть D. Каждой дуге x = (v,w) Î X транспортной сети D в орграфе приращений I(D, j) соответствуют две дуги: x и x* = (w,v) – дуга, противоположная по направлению дуге x. Припишем дугам x и x* орграфа приращений I(D, j) длину l:
l(x) = ¥, если j(x) = c(x),
l(x*) = ¥, если j(x) = 0.
|
0, если j(x) < c(x),
0, если j(x) > 0,
