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

                  ϕ х0 =       ∑ ϕ (u) − ∑ ϕ (u) = ∑ с(u) + 0 = c(U −А ).
                              u∈U −           u∈U +        u∈U −
                        N

                                  А               А            А
      Отсюда и из того, что общее количество вещества, входящего в А, не

превосходит c(U −А ) , заключаем, что все дуги u∈ U −А насыщенные, то есть ϕ х0
                                                                                N

– максимальный поток. Из теор. 1,2 и 3 вытекает следующая основная теорема.
      Теорема 4 (теорема Форда-Фалкерсона). Для заданной транспортной
сети максимальное значение потока равно минимальной пропускной способно-
сти разреза, т. е.

                             max ϕ x N =              min          c(U −
                                                                       A ).
                                              A I X 0 ∉ A, X N ∈ A

     2.3 Приложение алгоритма Форда-Фалкерсона к решению задачи
нахождения максимального потока
      Опишем алгоритм Форда-Фалкерсона в приложении к конкретной задаче.
      Пусть необходимо найти максимальный поток транспортной сети, графи-
ческое изображение которой представлено на Рисунке 6.
      Пусть узлом-источником является вершина 1, узлом-стоком – вершина 6.
Построим максимальный поток (F) между этими вершинами. Начальное значе-
ние F нулевое. Очевидно, что структурой данных для описания F является мат-
рица того же типа, что и матрица С, в которой определены пропускные способ-
ности дуг.

                             [1,2]                                        [2,2]
                                                   0(5)
                                      2                               5

                      2(2)                       2(3)
                                                               0(4)        0(7)
                                                                                              [4,2]
          [1,@]
                  1                                                                       6


                      0(6)                                                         2(3)
                                      [1,6]
                                                   0(2)
                                      3                               4    [2,2]


                                                  Рисунок 6
                                                          13