0.1. 目的

sourceとsinkが複数ある場合でもフロー分解が成立することを証明する.

0.2. 定義

source集合を$S$,sink集合を$T$とする.
今後考えるグラフ$G:=(V,E)$はsource->sourceもしくはsink->sinkを繋ぐ有効枝は存在しないとする.つまり, $$(s_1,s_2)\notin E(\forall s_1,s_2\in S)(t_1,t_2)\notin E(\forall t_1,t_2\in T)$$

またフロー$x:E\to R_{\ge 0}$が与えられたとき, 任意の頂点$v$に対して,正味の流出量$b\left(v\right)$を以下のように定める. $$b\left(v\right)=\sum _{e\in E(v,V)}x\left(e\right)-\sum _{e\in E(V,v)}x\left(e\right)$$ また,フロー$x$のフロー値$f\left(x\right)$を以下で定める.
$$f\left(x\right)=\sum _{s\in S}\sum _{e\in E(s,V)}x\left(e\right)-\sum _{s\in S}\sum _{e\in E(V,s)}x\left(e\right)=\sum _{s\in S}b\left(s\right)$$ さらにフロー$x$が以下の条件を満たすとき,$S$-$T$フローと呼ぶ.
$$b\left(s\right)\ge 0(\forall s\in S)b\left(t\right)\le 0(\forall t\in T)$$

0.2.1. 補題2.1 フロー分解のためのcutに関する補題

頂点集合の部分集合$A\subseteq V$に対して$A$からの流出量$x^{out}\left(A\right)$と$A$への流入量$x^{in}\left(A\right)$を以下のように定める. $$x^{out}\left(A\right):=\sum _{e=(v,w)\in E,v\in A,w\in V\setminus A}x\left(e\right)x^{in}\left(A\right):=\sum _{e=(v,w)\in E,v\in V\setminus A,w\in A}x\left(e\right)$$

$S\subseteq A$かつ$T\subseteq B$を満たす頂点集合$V$の分割$V=A\bigsqcup B$を$S$-$T$カットと呼び,$S$-$T$カットの容量$c(A,B)$を $$c(A,B):=\sum _{(v,w)\in E,v\in A,w\in B}x\left(e\right)$$ と定義する.
このとき以下が成立

$x$を任意の$S$-$T$フローとし,($A$,$B$)を任意の$S$-$T$カットとする.
このとき$f\left(x\right)=x^{out}\left(A\right)-x^{in}\left(A\right)$

(Proof)
$$\begin{array}{cc}f\left(x\right)& =\sum _{s\in S}b\left(s\right)\\ & =\sum _{v\in A}b\left(v\right)(\because \text{flow conservation})\\ & =\sum _{v\in A}\left(\sum _{e\in E(v,V)}x\right(e)-\sum _{e\in E(V,v)}x(e\left)\right)\\ & =\sum _{v\in A}\left(\sum _{e\in E(v,A)}x\right(e)+\sum _{e\in E(v,B)}x(e\left)\right)-\sum _{v\in A}\left(\sum _{e\in E(A,v)}x\right(e)+\sum _{e\in E(B,v)}x(e\left)\right)\\ & =\left(\sum _{v\in A}\sum _{e\in E(v,B)}x\right(e)-\sum _{v\in A}\sum _{e\in E(B,v)}x(e\left)\right)+\left(\sum _{v\in A}\sum _{e\in E(v,A)}x\right(e)-\sum _{v\in A}\sum _{e\in E(A,v)}x(e\left)\right)\\ & =x^{out}\left(A\right)-x^{in}\left(A\right)\end{array}$$

0.2.2. 補題2.1 フロー分解

> $x$をネットワーク $N=[G=(V,E);S,T,u]$上の($S$-$T$)フローとする.
このとき$x$は流量が正であるsourceからsinkへの有限個のパスと流量が正である有限個の閉路に分解することができる.
さらに閉路の個数は最大で|E|個で,パスと閉路の個数の総和は最大で$|E|+|V|$になるようにできる.

(Proof)
$b\left(s_0\right)>0$となる$s_0\in S$が存在する限り以下の操作(操作1)を繰り返す.
(この操作が有限回で終了することは最後に示す)
$b\left(s_0\right)>0$より$e_0=(v_0,v_1)\in E$かつ$x\left(e_0\right)>0$を満たすアーク$e_0$が存在する.$v_1\in T$であるならsinkに到達する流量が正のパス$P$が得られたことになる.そうでない場合はフロー保存則($v_1\notin S\cup T$の場合)もしくは$b\left(v_1\right)\ge 0$($v_1\in S$の場合)という仮定から$e_1=(v_1,v_2)$かつ$x\left(e_1\right)>0$を満たすアーク$e_1$が存在する.この議論を繰り返し行うことで,頂点$V$が有限個であることから
(1) sinkに到達するパス$P$が得られる(終点を$t_0$とおく)
(2) 1度訪れたノードに到達するパスが得られる
かのいずれかが起こる.
(1)の場合
$\delta :=min\left\{b\right(s_0),-b(t_0),{min}_{e\in P}x(e\left)\right\}$とし,フロー$x$からパス$P$に流量$\delta$を流したフローを除く操作を行う.すなわち,新しいフローを$x^{\prime }$とすると $$x^{\prime }\left(e\right)=\{\begin{array}{cc}x\left(e\right)-\delta & \text{if}e\in P\\ x\left(e\right)& \text{otherwise}\end{array}$$ (注意)
$\delta :={min}_{e\in P}x\left(e\right)$でなく$\delta :=min\left\{b\right(s_0),-b(t_0),{min}_{e\in P}x(e\left)\right\}$とすることにより新しいフローも($S$-$T$)フローとなっていることに注意する.

(2)の場合
流量が正の閉路$C$が得られるので,$\delta :={min}_{e\in C}x\left(e\right)$と定義し,フロー$x$から閉路$C$に流量$\delta$を流したフローを除く操作を行う.すなわち $$x^{\prime }\left(e\right)=\{\begin{array}{cc}x\left(e\right)-\delta & \text{if}e\in C\\ x\left(e\right)& \text{otherwise}\end{array}$$

次に上記の操作1が終了した後の操作(操作2という)について述べる.
初めに操作1が終了した時点で全ての頂点$v\in V$に対して$b\left(v\right)=0$となっていることを示す.
$v\notin T$ならば,操作1とフロー保存則より$b\left(v\right)=0$であるので,$v\in T$である場合について考える.
上記のcutに関する補題より, $$\begin{array}{cc}f\left(x\right)& =\sum _{s\in S}b\left(s\right)\\ & =x^{out}(V\setminus T)-x^{in}(V\setminus T)\\ & =-\left(x^{out}\right(T)-x^{in}(T\left)\right)\\ & =-\sum _{t\in T}b\left(t\right)\end{array}$$ であり, $b\left(s\right)=0(\forall s\in S)$かつ$S$-$T$フローの条件より$b\left(t\right)\le 0(\forall t\in T)$であるので,$b\left(t\right)=0(\forall t\in T)$となる.
続いて操作2について述べる.
$x\left(e\right)>0$となるアークが存在する限り以下の操作(操作2)を繰り返す.
全ての頂点$v\in V$においてフロー保存則$b\left(v\right)=0$が成立していることを考慮すると,操作1と同じ議論から流量が正の閉路が得られるので,$\delta :={min}_{e\in C}x\left(e\right)$とおきフロー$x$から閉路$C$に流量$\delta$を流したフローを引く.

操作2が終了した時点で全てのアークの流量は0となるので,フローを分解出来たことになる.
最後に操作1と操作2は有限回で終わることを証明する.
操作1,2のいずれかの操作を1回行うことによって次の3つのうちいずれかが起こる.
(a)少なくとも1つのアークの流量が0となる.($\delta :={min}_{e\in C}x\left(e\right)$となるとき)
(b)少なくとも1つの$v\in S\cup T$について$b\left(v\right)=0$となる. ($\delta :=b\left(s_0\right)$ or $-b\left(t_0\right)$となるとき.)
操作1と操作2のいずれかの1回の操作によって,流量が正である$S$-$T$パスもしくは閉路が得られるのでパスと閉路の個数の総和は最大で$|E|+|V|$となるようにできる.また1回の操作によって,閉路が除かれる場合は(a)の場合のであるので,閉路の個数は最大で$|E|$個となるように分解できる.
(補足)

操作1が終わった段階で$x\left(e\right)>0$となるアークが存在した場合$e$を通る流量が正の閉路が存在する.

(Proof)
上記の証明より$x\left(e\right)>0$となるアークが存在した場合には流量が正の閉路が存在するがその閉路が$e$を含む場合は証明終了.含まない場合はフローを更新した後も$x\left(e\right)>0$となるので同様の操作を繰り返すことができる.もし,この操作を何回繰り返しても$e$を含む閉路が得られないとするとこの操作は有限回で終了しないことになり矛盾.