グラフの最小カットを見つける必要があります。フロー ネットワークについて読んできましたが、Ford-Fulkerson、push-relabel などの最大フロー アルゴリズムしか見つかりませんでした。最大フローアルゴリズムを使用したグラフの最小カット? どのように？
これまでに見つけた最良の情報は、「飽和」エッジ、つまりフローが容量に等しいエッジを見つけた場合、それらのエッジは最小カットに対応するということです。本当？私には 100% 正しいとは思えません。最小カットのすべてのエッジが飽和するのは事実ですが、最小カットの「パス」から外れている飽和エッジもあると思います。
ソース頂点から、残差ネットワークのエッジ (つまり、飽和していないエッジとフローを持つエッジのバック エッジ) に沿って深さ優先検索を実行し、この方法で到達できるすべての頂点をマークします。カットは、マークされた頂点からマークされていない頂点までのすべてのエッジで構成されます。明らかに、これらのエッジは飽和しているため、横断されませんでした。ご指摘のとおり、最小カットの一部ではない飽和エッジが他にもある可能性があります。
理解するための 1 つの方法は、カットを 2 つのセット S と T として定義してみましょう。これには、それぞれ s と t が含まれます。
ここで、残差ネットワークの s から到達可能な S のすべての頂点を追加し、残りのエッジを T に配置します。これが 1 つのカットになります。
第 2 に、カットは、t から到達可能なすべての頂点を残差ネットワークに配置し、残りの頂点を S に配置することによって形成できます。
このビデオを見て、s と t から到達可能な頂点を見つける方法を確認してください。
https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma
注: Falk のアルゴリズムを使用して、頂点が最小のカットと頂点が最大のカットの両方を見つけることができます。後者の場合、アルゴリズムを逆にする必要があります。ソースではなくシンク頂点から検索します。関連する質問を参照してください:ネットワーク フロー: 新しいエッジの追加
最大フローが計算された後、残差グラフでからまで(u,v)の残差グラフにエッジがあり、[エッジが飽和していることを意味する]ようなエッジを検索できます。vuf(v,u) = c(u,v)
(u,v)そのようなエッジを候補リストに載せた後、残差グラフにuからシンクtへのパスが存在しないという基準を使用してそのようなエッジを選択できます。この条件が満たされると、そのようなエッジは(S,T)カットの一部を形成します
このアルゴリズムの実行時間はO(E) * O( V + E ) = O( E^2 )
他の方もおっしゃっていると思いますが、よく分からなかったので以下に説明します。
ソース ノードからグラフのフラッド フィルを実行し、残りのキャパシティを持つエッジに沿ってのみ移動し、訪問した各頂点をマークします。これには DFS を使用できます。頂点からのバック エッジには、フォワード エッジに沿ったフローに等しい残余容量があることを思い出してください (つまり、r(u, v) = エッジ (u, v) の残余容量、r(v, u) = フロー(u) 、v)))。
実際、これはグラフの ST カットの S 部分を決定します。
最小カットは、1 つの頂点が上のフラッド フィルからマークされ、他の頂点がマークされていないエッジのセットになります。これらは残余容量のないエッジになり (そうでなければ、DFS でそれらをトラバースしたことになります)、一緒になって最小カットを形成します。
これらのエッジを削除した後、マークされていない頂点のセットがカットの T セクションを形成します。