Теорема Форда - Фалкерсона. Алгоритм нахождения максимального потока

Теорема: На любой сети максимальная величина потока из истока S в сток t равна минимальной пропускной способности разреза, отделяющего S от t. Т.е. существует такой поток по сети:M*G =max∑Mi = minC(A/B).

Алгоритм нахождения максимального потока: 1) Построить некоторый начальный поток X0 = {X0ij}. В примере это потоки М1 и М2. 2) Организовать процедуру составления подмножества А вершин, достижимых из истока S по ненасыщенным ребрам. А={s, 3, 2, t}. Если в этом процессе сток t не попадает в подмножество А, то построенный поток максимальный и задача решена, если же сток t попал в А, то перейти к пункту 3 алгоритма. 3) Выделить путь из истока s в сток t, состоящий из ненасыщенных ребер и увеличить поток Хij по каждому ребру этого пути на величину ∆=min(Cij-Xij), где min берется по i-тым j-тым ребрам этого пути. Тем самым будет построен поток и затем следует вернуться к пункту 2 алгоритма. (Мы построили М3). А={1}, В={2, 3, 4, 5}. R*(A/B)=6.