下限（需要ではない）でネットワーク内の循環フローを見つける方法がわかりません。問題の説明と解決策が記載された次のドキュメントを見つけました。
- https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
- http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
- 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
問題を解決するために私が理解しているように、次のステップを実行する必要があります。
- この問題を「需要のある循環問題」に変換します。これは、次の式 dv' = dv - (Lin - Lout) で実行できます。ここで、'dv' は元の頂点要求 (この場合はゼロに等しい)、'Lin' - 頂点入力エッジの下限の合計、および ' Lout' - 頂点出力エッジの下限の合計。
- 辺の容量を c' = c - l として更新
- 容量 '-dv' で dv < 0 の各頂点にエッジを持つソース頂点 S を追加します
- 容量 'dv' で dv > 0 の各頂点からのエッジを持つシンク頂点 T を追加します
- Edmonds-Karp アルゴリズムなどの任意のアルゴリズムを使用して、新しいネットワークで max-flow を見つけます。
- 最大フローの値が、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 に等しいフローを割り当てるだけで済みます。
