все записи автора Пусть задан неориентированный взвешенный граф G. Вершины A, B принадлежат G. Pxy - вес ребра между вершинами X и Y. Необходимо найти max(∑ CAi).
∀X,Y: |Cxy| ≤ Pxy
∀X,Y: Cxy = -Cyx
∀X, X≠A,X≠B: ∑ CXi = 0

Упрощенный метод Флойда-Фалкерсона:
1. Найти произвольный путь из A в B: S=(A, i, j... k, B)
2. Найти его пропускную способность: C1= min( PAi, Pij..., PkB )
3. Запомнить данный поток (Q - путь, набор C1 для ребер).
4. Построить новый граф G'= G: P'Ai= PAi - C1, P'ij= Pij - C1... P'kB= PkB - C1. У одного ребра в рассматриваемом пути после пересчета P'=0. Считать, что через это ребро пути не образуются.
5. Повторять процедуру для новых графов, пока существует хотя бы один путь из A в B.
6. Общий макс. поток будет суперпозицией Q, полученных на всех итерациях цикла.

Попытки доказательства:
Пусть L - максимальная величина потока в G'. Допустим, L1 - максимальная величина потока в G, L1 > L+C1. Тогда при вычитании из G пути потока Q в соответствии с шагом 4 алгоритма величина L1 уменьшаться на C1 (поскольку именно на столько уменьшаются пропускные способности сотавляющих путь ребер, исходя из предположения, что либо 1.: в L1 через эти ребра проходит поток, и его величина уменьшится на C1, если он равен C1 - больше быть не может из-за наименшего ребра, либо 2.: величина потока Cx меньше, чем C1, если его ограничивала пропускная способность другого ребра пути, нагруженного дополнительными потоками, и как раз уменьшение того ребра на C1 сократило как величину рассматриваемого потока на Cx, так и суммарную величину других потоков в том ребре на оставшуюся величину C1-Cx, либо на еще меньшую), то есть в G' будет существовать поток с величиной Lx = L1-C1, Lx > L. Следовательно, L1 ≤ L+C1. Далее, если из G' восстановить G, то к максимальному потоку G' можно будет добавить Q, так как будет существовать путь с необходимым запасом пропускной способности: ∀X,Y Pxy - Cxy ≤ C1, то есть в G существует поток с величиной Lx=L+C1. Так как L1 ≤ L+C1, Lx будет максимальной величиной.
Ошибка в том, что через ребра S может проходить несколько параллельных потоков, и в предельном случае величина L1 может уменьшится на C1*(|S|-1), где (|S|-1) - число ребер в пути S

На основании рассмотрения примера, в котором алгоритм не получит оптимальный результат, можно придти к выводу, что проблема заключается в неправильной ориентации потока в части ребер произвольно выбранного пути. В результате этого ребра теряют пропускную способность, которую можно было бы использовать для увеличения потока. Напрашивающийся вывод - не исключать ребра, а рассматривать возможность обращения потока в ребре при поиске очередного пути, то есть рассматривать граф как ориентированный, с парными противоположно направленными дугами между каждой парой вершин. Увеличение потока в одной из дуг повышает пропускную способность парной дуги на величину добавленного потока. Если в противоположной дуге уже есть поток, он уменьшается на величину добавляемого, при этом на ту же величину восстанавливается пропускная способность парной дуги, и уменьшается у текущей, если величина добавляемого потока больше имеющегося в парной дуге, парный поток обнуляется, пропускная способность парной дуги восстанавливается, после чего остаток потока применяется к текущему с соответствующим изменением пропускных способностей обеих дуг. Пропусная способность парных дуг в сумме всегда равна 2*P, где P - пропускная способность ребра в исходном неориентированном графе..

Еще вариант - перебрать все 2^|G| вариантов ориентации ребер в графе.. ::