ネットワークには複数の最小カットが存在する場合があります。例えば：
には 4 つの最小カットがあり、Ford-Fulkerson は s (ソース) に「近い」ものを見つけます。すべてのネットワークについて同じことが言えますか? つまり、Ford-Fulkerson はソースに最も近いカットを見つけますか? もしそうなら、フローネットワークで「ソースに最も近い」という概念をどのように形式化しますか?
1723 次
2 に答える
6
ソースを含むがシンクを含まない一連の頂点としてカットを表現してみましょう。最小カットには、2 つの最小カットの交点が最小カットであるという性質があります (これは和集合にも当てはまります)。したがって、すべての最小カットの交差は、他のすべての最小カットのサブセットであるため、ある意味でソースに「最も近い」最小カットです。
于 2015-04-02T17:13:08.850 に答える
0
（交差点の下で最小カットが閉じていると仮定します。）
最小カット (最も近いカット) の交点は、まさに FF によって返されるカットであると主張します。証明の大まかなスケッチを次に示します。
MaxFlow MinCut 定理から、次の結果が確立されます。
カットは、それを出るすべてのエッジが完全に飽和している場合、つまり f(e) = c(e) が最小です。
したがって、矛盾するため、FF によって返されるものよりもソースに近い最小カット C = Ca、Cb があると仮定します。これを F = Fa、Fb と呼びます。
次に、エッジ e = (v, w) を取って、Fa にあったが、現在は Ca にないようにします (Ca の出力エッジです)。このエッジは完全に飽和している必要があります。したがって、残差グラフの定義により、残差グラフには後方エッジ (w, v) のみが存在し、そのノード w は到達不能になります - それでも w は Fa にあったため、到達可能であったに違いありません。
于 2021-10-19T05:33:17.650 に答える