0

私は現在、大学でフロー ネットワークを研究しており、私の教授はこの定理を私たちに提示しました。B(e) の ∑(e:u→v) - B(e') の ∑(e':v→u) | ≤ε。

注: この方程式は、すべての v (ネットワーク内のソースでもシンクでもない頂点) に対するものです。e:u→v は、カットセット内の u のセットから v のセットまでのすべてのエッジの B(e) の合計が必要であることを意味します。次に、e':v→u は次のことを意味します。 v のセットから u のセットまで、同じカットセット内にあるすべてのエッジの B(e) の合計が必要です。

グラフのすべてのエッジに対して |F(e)-B(e)|<ε*N (N はグラフの頂点の数) という新しいフロー F が存在します。」</p>

彼は証拠が存在すると主張しましたが、私はその真相を突き止めることができません。イプシロンの下限はグラフの最小カットであるという事実について考えていましたが、私が持っていた他のすべてのアイデアは役に立ちません。助けていただければ幸いです。その証拠をネットで探したのですが、見つかりませんでした。

事前に感謝します, または

4

1 に答える 1

0

辺への量の反対称割り当てが与えられると、頂点の超過は、入る総量から出て行く総量を差し引いたものになります。負の超過 -c を持つ各頂点 v について、ソース s から v へのパスを選択し、c で乗算し、代入に追加します。正の超過 c を持つ各頂点 v について、v からシンク t へのパスを選択し、それに c を掛けて、代入に追加します。(1) s と t を除いて、すべての超過が現在ゼロであることを確認するのは簡単です (2) すべての超過は絶対値でイプシロンよりも小さいため、エッジの最悪の場合の変化は、エッジがすべてのパスに含まれている場合です。 、合計がイプシロン x n (頂点の数) 未満の場合。

于 2014-06-06T02:32:30.730 に答える