Алгоритмы на графах и их приложения. Дорофеева В.И. - 11 стр.

     Матрицей пропускных способностей сети G=(Е,U) называется квадратная
матрица С размерности n×n, где n=Е, каждому элементу Сij которой соот-
ветствует величина пропускной способности дуги (Xi,Xj).
     Матрицей потоков сети G=(Е,Г) называется квадратная матрица F раз-
мерности n×n, где n=Е, каждому элементу Fij которой соответствует величи-
на потока, протекающего по дуге (Xi,Xj).
     Существенным моментом в решении многих задач является нахождение
пропускной способности графа. Например, в транспортной задаче, необходимо
найти, сколько единиц транспорта проследует через сеть дорог в некоторой об-
ласти.
     Таким образом, математически задача максимального потока формулиру-
ется следующим образом:
     Задача о максимальном потоке. Требуется определить такую функцию

ϕ(u), u∈U, что ϕ        принимает максимальное значение.
                   xN



    2.2 Алгоритм Форда-Фалкерсона нахождения максимального
потока в сети
     В качестве теоретической базы алгоритма для решения указанной задачи

использованы следующие теоремы. Для простоты записи положим ϕ = ϕ               .
                                                                           xN


     Теорема 1 . Пусть µ=(Х0, Х , …, Х            , Х N ) – путь, соединяющий вход
                                     i1      in

Х0 с выходом ХN. Если все дуги этого пути ненасыщенные, то можно увеличить
ϕ, не нарушая соотношения.
     Действительно, рассмотрим разности
                                     δ(u)=c(u)–ϕ(u)>0
и выберем среди них наименьшую δ*. Увеличивая на δ* поток в каждой дуге
приходим к потоку ϕ +δ*.


                                           11