エッジでの制約が与えられた最大流量

Question

3つのエッジがノードに入り、3つのエッジが出てくるようなグラフがありますが、特定の進行中のエッジに容量があった場合は、例えば、我々が持っている場合：

A - > N

B - > N

C - > N

N - > N '

N' - > A」

N ' - > B'

N ' - > C'

私だけエッジA、B、Cの上、基本的にその容量の制限

に「Aは流れがあったが、Bに流れる場合は、」Bは、などを流していた場合などを通って流れ、私は彼らを制限できませんでしたいです容量は当初。

この制約を最大フローに追加し、このシナリオが複数回発生すると仮定して、指定されたグラフの最大フローグラフの問題を解決するにはどうすればよいですか？

編集：A '、B'、C 'が後でグラフで使用されるため、最終的に容量を制限できません.NとN'を最後まで移動して結合容量を後で小さくすることはできませんに。

Answer 1

a、b、cをn> n 'の容量に制限した場合、nノードをグラフの反対側に移動するだけです。言い換えれば、a、b、cからの流れを取り出し、直接（または素数対を介して）nに、次にnから直接（またはn 'を介して）シンクに向けることで、問題をモデル化することができます。

編集：同じ効果のためにa/b/cの前にnを置くこともできます。

編集2：ford fulkersonの実装について話している場合は、論理的に、追加パスのリストを表示したくないパスを除外できます。例えば、あなたのプログラムが可能な増強経路を特定しているとき、フローa-> nがn ' - > a'等と等しくなければ、それに沿って補強しないでください。