頂点セット間のフロー

Question

頂点セットのコンテキストでフローが何を意味するのか混乱します。

Say f(s,V)は、ソースであり、Vは頂点のセットです。平均/ v /はVでsに属する。

しかし、f(X,Y)ここで、XとYは両方ともセットです。どういう意味ですか？ 各ペアの合計はありますか？

この場合、f(X,X)=0,Xとは、なぜ{a,b}であるのですか。

Answer 1

複数のソース/シンクの場合のフローの定義は、単一のソース/シンクの場合と似ています。

各ソースには、入力フローが0である必要があります。各シンクは0の発信フローを持つ必要があります。他のすべてのノードは、等しいフローの着信および発信フローを持つ必要があります。興味深いことに、複数のソース/シンクノードの場合のフローは、シングルソース - シングルシンクケースに縮小することができます。

私たちは、グラフ G、 Xと表記ソースノードのセット、および Yと表記シンクノードのセットを持っていると仮定しましょう。

我々は、新しいグラフを作成し、それは以下の接続と、SとTとして示される2つの追加のノードを有することを除いて、Gとほぼ同一であるG」：

S

• はX内の各ノードに向かって発信エッジを有します。これらのエッジを無限の容量に設定します。

• TはX内の各ノードからの着信エッジを有します。また、これらのエッジを無限の容量に設定します。

そして、ソースからGの任意の流れとの間に直接的な1対1の対応がG」からの任意のフローにYを設定シンクにXを設定ありますソースsシンクへt。

また、当然の結果として、Sに対するTからG」における最大フローはまたXからYに、Gにおける最大フロー値を表しています。