7

グラフ G = (V,E) で Ford-Fulkerson アルゴリズムを実行し、その結果が最小カット Xmin に関連付けられた最大フロー f maxであるとします。グラフ内のいずれかのエッジの容量を増やすことで、フローを可能な限り増やすことに興味があります。このエッジを特定するにはどうすればよいですか?

最初の頂点sと最後の頂点tが与えられた場合、 sからtまでのすべてのパスを考慮し、容量が小さいエッジを検証します。たとえば、1/1 のエッジがある場合、これは容量を増やす必要がある頂点です。

この問題を解決するための一般的なアルゴリズムはありますか?

4

1 に答える 1

8

グラフで最大フローを見つけたら、残差グラフに s から u および v から t への正の容量パスがある場合にのみ、エッジ (u, v) の容量を増やしても最大フローが増えます。そうでない場合、増加を行った後に残差グラフに増加パスが存在しないため、最大フローは最大のままになります。

このプロパティを持つエッジ (u, v) のうち、(u, v) の容量を増やした後に s から t にプッシュできる余分なフローの最大量は制限されます。このエッジを越えてフローをプッシュできる場合は、s から u へのパスと v から t へのパスを見つける必要があります。その場合、2 つのパスのそれぞれに常にボトルネック エッジが存在し、これ以上フローを増やすことはできません。したがって、問題を解決するための 1 つのオプションは、次の手順を実行することです。

  • 残差グラフで、s から s から到達可能な他の各ノードへの最大ボトルネック パスを見つけます。
  • 残差グラフで t に到達できる各ノードから t への最大ボトルネック パスを見つけます。
  • パスを横切る各エッジ (u, v) について、エッジを横切って押し込める余分なフローの最大量は、s から u への最大ボトルネック パスと v から t への最大ボトルネック パスの最小値によって与えられます。 .

つまり、グラフ内の最大ボトルネック パスを計算できれば、時間 O(B(m, n) + m) で増加させる必要があるエッジを見つけることができます。ここで、B(m, n) は次のコストです。グラフ内の最大ボトルネック パスを計算します。

幸いなことに、これは十分に研究された問題であり、各ノードへの最小コスト パスを保存する代わりに、各ノードへの最大ボトルネック パスを保存するダイクストラのアルゴリズムの変形を使用して解決できます。Google で簡単に検索すると、これに関する追加情報が表示されるはずです。フィボナッチ ヒープを使用すると、この検索を O(m + n log n) の時間で実装できるため、容量を増やす必要があるエッジを特定するための全体的な実行時間も O(m + n log n) になります。

お役に立てれば！

于 2013-06-10T02:31:55.737 に答える