Алгоритм Форда-Фалкерсона поиска максимального потока в сети.

Метод решения Алгоритмом Форда-Фалкерсона.

Дан несимметричный ор-граф с выходом и входом, числа на матрице инцидентности задают пропускные способности трубопроводов между пунктами. Надо найти максимальный поток, который можно дать через сеть трубопроводов.

1. Ищется цепочка с ненулевыми пропускными способностями через которую можно дать сквозной поток.

2. По узкому звену находится пото

1. (Код: Алгоритм Форда)(2 задачи на пару 90 мин). Алгоритмом Форда-Фалкерсона найти максимальный поток в сети

(Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ)

При решении только САМ граф перерисовывается 5-6 раз. Кроме этого в ответе даётся граф потоков.

При выполнении каждой итерации необходимо нарисовать новый граф и произвести его разметку в соответствии с алгоритмом, найти новый элементарный (не разветвлённый) поток и, пересчитав веса нарисовать новый граф, повторяя итерации пока возможно проводить потоки.

В условии на каждом ребре стоит две пропускных способности – это соответствует наличию двух трубопроводов ведущих в прямую и обратную сторону (то, что трубопроводы односторонние, может быть связано, с направлением ориентации турбин в них).

Итерации основаны на том, что когда по цепочке даётся поток частично заполненные потоком трубопроводы теряют пропускную способность на размер потока в направлении движения потока и встречный участок трубопровода формально «как бы» приобретает пропускную способность ровно на туже величину (сумма прямой и обратной пропускной способности остаётся постоянной), т.к. прежде чем загрузить этот встречный участок во избежание встречной транспортировки можно полностью выключить поток в прямом направлении.

В ответе.

1)Восстановить граф потоков по разности пропускных способностей на старом и новом графе

2)построить матрицу потоков

3) дать СУММУ потоков,

а) как сумму прямолинейных потоков на каждой итерации

б) проверить совпадение с суммой выходящих из Sи

в) входящих в Fпо матрице потоков.