正接の非晶系グラフでフローがノード要求を満たすことができるかどうかを判断する

Question

私は私が解決しようとしなかった次の問題があります：

私はノード要求を持つ有向グラフを持っています。要求を伴う循環とは異なり、これらのノード要求はフローから「減算」しません。ノードは単にそれらを通って流れる強度の流れがあることを要求します。グラフは非公式ですが、ツリーではありません - より高いノードから下位ノードへの複数のルートが存在します。

問題は、強度 R の流れが全てのノード要求を満たすことができるかどうかということである。もちろん、 K 以上の強度を有する流れは、需要 k を有するノードを通って流れることができる。また、入力グラフには容量制限はありません。

この問題を最大流動問題に縮小する必要があります。私は、必要に応じて、需要を満足させながらノード内のフローを制限する方法についての良い方法を見つけることができないので、私はそれを下限と循環させて循環させようとしています同時に。

Answer 1

新しいソースを追加する $ s '$ 、およびエッジ $（s'、s）$ 最大および最小容量 $ R $ 。

$ v $ の場合 $ d $ 次のようにします。

• $ v $ を2つの頂点に置き換えます $ v_1 $ 、 $ v_2 $ 。
• $（u、v_1）$ $（u、v）$ をすべて置き換えます。 >
• $（v_2、u）$ $（v、u）$ を置き換えます。 >。
• 最小容量 $ d $ を持つEdge $（v_1、v_2）$ を追加します。

問題は、最小および最大エッジ容量を有するネットワーク内に実現可能な流れがあるかどうかをチェックすることと同等である。

この問題はよく知られており、マックスフローに縮小することができます（例えば、「バランスと擬似フロー」= https://jeffe.cs.illinois.edu/teaching/algorithms/を参照してください。 "REL=" NOFOLLOW NOREFERRER ">アルゴリズムによってJeff Ericksonによって。

本質的に、 $ d $ の場合は、すべてのエッジの最小容量の合計です：

• 新しいソース頂点 $ s ^ * $ と新しいターゲット頂点 $ t ^ * $ 。
• EDGE $（s ^ *、s '）$ を追加 $ + \ infty $ 。

• 各エッジ $（u、v）$ 最小容量 $ c \ neq 0 $ < / SPAN>と最大容量 $ c $ 、edend $（u、t ^ *）$ 容量 $ c $ 、Edge $（s ^ *、v）$ の容量 $ c $ 、 $（u、v）$ から最小容量を削除し、 $（u、v）$ $ cc $ （ $ c $ は $ + \ infty $ でした。その場合、新しい容量も $ + \ infty $ ）

• $ s ^ * $ から $ t ^ * $ $ d $ 。