問題タブ [max-flow]

最小コスト フロー問題の修正されたインスタンスを有向グラフで解こうとしています。具体的には、送信元と送信先のペアは固定されており、各エッジには単位コストがありますが、容量は有限です。合計（フロー）/エッジを最小限に抑えたい。これに関連する 2 つのクエリがあります。

1. 各フローがソースから宛先まで 1 つのパスを取る場合、どのように進めればよいですか? 1 つの解決策は、最短パス アルゴリズム (Dijkstra など) を使用することですが、フローを完全に収容できるパスのみを考慮します。これは、フローごとに繰り返し解決し、エッジ容量を毎回更新することで実行できます。最小コスト問題と最大フロー問題に関連する文献を確認しましたが、それらはすべて、任意の商品が任意のソースから任意の宛先に流れることができると仮定しています (同じタイプの商品の需要と供給を考えてください)。私の問題は、固定の送信元と送信先のペアが含まれていることです。この特定のケースのアルゴリズムはありますか?
2. フローを分割することを検討している場合、つまり、各フローが複数のパスを取ることができる場合、どのような解決策がありますか?

下限（需要ではない）でネットワーク内の循環フローを見つける方法がわかりません。問題の説明と解決策が記載された次のドキュメントを見つけました。

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

次のエッジ (l - 下限、c - 容量) を持つネットワークを考えてみましょう。

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

問題を解決するために私が理解しているように、次のステップを実行する必要があります。

1. この問題を「需要のある循環問題」に変換します。これは、次の式 dv' = dv - (Lin - Lout) で実行できます。ここで、'dv' は元の頂点要求 (この場合はゼロに等しい)、'Lin' - 頂点入力エッジの下限の合計、および ' Lout' - 頂点出力エッジの下限の合計。
2. 辺の容量を c' = c - l として更新
3. 容量 '-dv' で dv < 0 の各頂点にエッジを持つソース頂点 S を追加します
4. 容量 'dv' で dv > 0 の各頂点からのエッジを持つシンク頂点 T を追加します
5. Edmonds-Karp アルゴリズムなどの任意のアルゴリズムを使用して、新しいネットワークで max-flow を見つけます。
6. 最大フローの値が、T への接続を持つ頂点のすべての需要の合計に等しい場合、ネットワーク内に循環があります。

これらの手順を実行すると、新しいネットワークは次のようになります。

S -> 2 : c = 1

2 -> 3 : c = 2

3 -> T : c = 1

1 -> 2 : c = 2

3 -> 1 : c = 1

頂点の要求:

d1 = 0

d2 = -1

d3 = 1

最大フローは 1 に等しく、これも 1 である T へのエッジの合計に等しいことがわかります。また、エッジ A->2->3->T をカバーします。

問題は、元の境界を持つ元のネットワークで循環フローをどのように取得するかです。

元のネットワークの循環フローが存在します。すべてのエッジに 2 に等しいフローを割り当てるだけで済みます。