セダーバウムの最大フロー定理

セダーバウムの定理^[1]は、最小s-tカット問題の解を自動的に生成する仮想アナログ電気ネットワークを定義します。あるいは、 そのようなネットワークのシミュレーションでも、最小s-tカット問題の解が生成されます。この記事では、基本的な定義、定理の記述、定理の証明を示します。この記事のプレゼンテーションは、元の出版物での定理のプレゼンテーションに厳密に従っています。

この記事の定義は、最大フロー最小カット定理の議論で与えられた定義とあらゆる点で一貫しています。

Cederbaum の定理は、特定の種類の有向グラフに適用されます: G = ( V , E )。V はノードの集合です。 は有向エッジの集合です: 。各エッジには正の重みが関連付けられています: w _ab : E → R ⁺。2 つのノードはsとtである必要があります:および。  ${\displaystyle E}$${\displaystyle E=(a,b)\in V\times V}$  ${\displaystyle s\in V}$${\displaystyle t\in V}$

フロー f  : E → R ^{+ は}、グラフ内の各辺に関連付けられた正の量です。フローは、関連付けられた辺の重みと、ここで説明されているように各頂点でのフローの保存によって制約されます。  

電流は、 各エッジ ペアを実数i _ab  : E ^p → Rにマップしたものとして定義されます。電流は、電圧から、それぞれの順方向エッジと逆方向エッジの重みによって決まる範囲にマップします。各エッジ ペアは、特定の頂点ペアの順方向エッジと逆方向エッジからなるタプルです。1 組のノード間の順方向と逆方向の電流は、互いに逆加算されます: i _ab = − i _ba。電流は、ネットワークの各内部ノードで保存されます。ノードとノードの正味電流はゼロではありません。ノードの正味電流は、入力電流として定義されます。ノードの近傍の集合については、次のようになります。    ${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle s}$${\displaystyle N_{s}}$

${\displaystyle I_{in}=\sum _{b\in N_{s}}i_{sb}}$

電圧は、エッジペアのセットから実数へのマッピングとして定義されます。 v _ab  : E ^p → R。電圧は、電気ネットワークの電圧に直接類似しています。一対のノード間の順方向および逆方向の電圧は、互いの加法逆数です。 v _ab = − v _ba 。入力電圧は、ノードとノード間のパスを形成するエッジのセット上の電圧の合計です。    ${\displaystyle P_{ab}}$${\displaystyle s}$${\displaystyle t}$

${\displaystyle V_{in}=\sum _{(a,b)\in P_{ab}}v_{ab}}$

s -t カットは、グラフをまたはのいずれかを含む 2 つの部分に分割することです 。、、 の場合、 s-t カットは です。s-t カット セットは、 で始まり で終わるエッジの集合です。最小 s-t カットは、カット セットの重みが最小になる s-t カットです。正式には、カット セットは次のように定義されます。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle S\cup T=V}$${\displaystyle \;\;s\in S}$${\displaystyle \;\;t\in T}$${\displaystyle (S,T)}$${\displaystyle S}$${\displaystyle T}$

${\displaystyle X_{C}=\{(a,b)\in E\mid a\in S,b\in T\}}$

電気ネットワークは、フロー グラフから派生したモデルです。電気ネットワーク内の各抵抗要素は、フロー グラフ内のエッジ ペアに対応します。電気ネットワークの正と負の端子は、それぞれグラフの端子と端子に対応するノードです。モデルの電圧状態は、入力電圧差が に近づくにつれて、極限で 2 進数になります。電気ネットワークの動作は、キルヒホッフの電圧法則と電流法則によって定義されます。電圧はすべての閉ループの周囲で 0 になり、電流はすべてのノードで 0 になります。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle \infty}$

この定理の文脈における抵抗要素は、フロー グラフ内のエッジ ペアに対応する電気ネットワークのコンポーネントです。

特性は電流と電圧の関係です。要件は次のとおりです。 ${\displaystyle iv}$

(i) 電流と電圧は互いに連続関数である。
(ii) 電流と電圧は互いに非減少関数である。
(iii) 電流の範囲は、抵抗要素に対応する順方向エッジと逆方向エッジの重みによって制限される。電流の範囲は、エンドポイントを含む場合と含まない場合があります。電圧のドメインは、最大電流と最小電流を除きます。

 i _ab  : R → [− w _ab , w _ba ] または (− w _ab , w _ba ] または [− w _ab , w _ba ) または (− w _ab , w _ba )

 v _ab  : (− w _ab , w _ba ) → R

入力電圧V _{in が に}近づくにつれて、電気ネットワークの入力端子間の_電流I in の限界は、最小カットセットの重みX _Cに等しくなります。   ${\displaystyle \infty}$

${\displaystyle \lim _{V_{in}\rightarrow \infty }(I_{in})=\min _{X_{C}}\sum _{(a,b)\in X_{C}}w_{ab}.}$

主張 1電気ネットワーク内のどの抵抗要素でも、どちらの方向の電流も、グラフ内の対応するエッジの最大フロー以下になります。したがって、電気ネットワークを流れる最大電流は、フロー グラフの最小カットの重みよりも小さくなります。

${\displaystyle \lim _{V_{in}\rightarrow \infty }(I_{in})\leq \min _{X_{C}}\sum _{(a,b)\in X_{C}}w_{ab}.}$

請求項 2 入力電圧が無限大に近づくと、カットセット間の電圧が無限大に近づくような カットセットが少なくとも 1 つ存在する。${\displaystyle V_{in}}$${\displaystyle X'_{C}}$

${\displaystyle \exists X'_{C}\;\;\forall \;(a,b)\in X'_{C}\;\;\lim _{V_{in}\rightarrow \infty }(v_{ab})=\infty }$

これは次のことを意味します:

${\displaystyle \lim _{V_{in}\rightarrow \infty }(I_{in})=\sum _{(a,b)\in X'_{C}}w_{ab}\;\geq \;\min _{X_{C}}\sum _{(a,b)\in X_{C}}w_{ab}.}$

上記の主張1と2を考慮すると、

${\displaystyle \lim _{V_{in}\rightarrow \infty }(I_{in})=\min _{X_{C}}\sum _{(a,b)\in X_{C}}w_{ab}.}$

単調な抵抗要素で構成される電気回路網の方程式の解の存在と一意性はダフィンによって確立された。^[2]

セダーバウムの最大フロー定理はSimcutアルゴリズムの基礎となっている。^{[3] [4]}