Графы и сети. Харитонова Е.В. - 40 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

39
(
)
cd е
3 5,
⎯
⎯
→
⎯
⎯
⎯
⎯
←
)4,4(
на
(
)
(
)
cd е
5 5,2 4,
⎯
⎯
→
⎯
⎯
⎯
⎯
←
Поток из d в e уменьшен на ту же величину, на которую увеличен поток из d в
с. Поэтому чистый поток из вершины d остался неизменным.
Процесс увеличения потока в сети чрезвычайно прост. Формируем цепь
из
а в z. Если возможно, то увеличиваем поток, определяя наибольшую величи-
ну, которую можно добавить к каждому из ребер, имеющих то же самое на-
правление, что и цепь, чтобы поток не превысил пропускную способность, и
которую можно вычесть из каждого ребра, имеющего противоположное на-
правление, не создавая отрицательный поток. Поскольку последнее ребро, вхо-
дящее в z, имеет то же самое направление, что и цепь, то поток в z возрастает.
Аналогично, ребро, выходящее из
а, имеет то же самое направление, что и
цепь, поэтому, как и ожидалось, поток из
а возрастает. Так и должно было
быть, потому что
()
(
)
zпоток aпоток =
. Потому что пропускная способность –
конечная величина, а общая величина потока увеличивается, неизбежно насту-
пает момент, когда наращивать поток далее нельзя. Когда это происходит, по-
лучаем максимальный поток.
До сих пор рассматривался способ увеличения уже существующего пото-
ка. А с какого потока начинать? Ответ прост. Следует начинать с нулевого по-
тока,
т.е. когда поток через каждое ребро равен 0, а затем наращивать его. Те-
перь перейдем к изложению систематического алгоритма для нахождения мак-
симального потока. Каждой вершине поставим в соответствие упорядоченную
пару. Первый элемент пары – предшествующая вершина в рассматриваемой
цепи предназначена для того, чтобы можно было найти обратный путь. Второй
элемент пары
– резерв, т.е величина, на которую можно увеличить поток на ка-
ждом ребре вдоль пути, если ориентация ребра совпадает с направлением цепи
(такую ориентацию назовем правильной), или уменьшить поток, если ребро
ориентировано неправильно. Проще говоря, резерв заданной вершины равен
максимальной величине, на которую поток вдоль цепи до этой вершины можно
увеличить без нарушения самого потока. Рассмотрим также множество
S, со-
держащее все вершины, не задействованные при построении цепи в
z. Если S
окажется пустым, до того как будет достигнута вершина
z, то больше не будет
вершин, которые можно испытать на пути к
z, поэтому нет иного пути в z и нет
более возможности увеличить поток, значит поток максимален.
Алгоритм (Форда-Фалкерсона) нахождения максимального потока
(1) Установить предшественника каждой вершины и резерв равными сим-
волу – (непомечено). Вершина помечена, когда ее резерв не обозначен

Страницы