Processing math: 100%

組合せとグラフの理論（塩田）　2020年度 第13回


今日のテーマ

  • 最大フロー・最小カット定理
  • Menger の定理
　ネットワークフローの勉強をしました、と言って知らないで済まされない「最大フロー・最小カット定理」を今日は勉強します。

1.　ネットワークのカット

　前回用いた次の記号・設定を今回も継承します。
  • D=(V,A) は有向グラフ
  • N=(D,Ψ) は D 上のネットワーク
  • N の入口は v ひとつだけ
  • N の出口は w ひとつだけ
Def.1
  • 頂点集合 V を 2 つの部分集合 S, ¯S に分けたとき、 D の弧のうち、 S の頂点から ¯S の頂点に至るもの全ての集合を (S,¯S) と表す。
  • 特に、S が入口 v を含み、¯S が出口 w を含むとき、 この形に書ける弧の集合 K=(S,¯S) を「( ネットワーク N の ) カット」と呼ぶ。
　K=(S,¯S) が N のカットであれば D−K は v-w 道を含まないことに注意してください。
Ex.2　次のネットワークではカットは 4 通りあります。
S={v}, ¯S={x,y,w} のとき、赤い辺たちがカット K=(S,¯S) です。
  →  
K=({v},{x,y,w}) D−K
S={v,x}, ¯S={y,w} のときは
  →  
K′=({v,x},{y,w}) D−K′
S={v,y}, ¯S={x,w} のときは D−K″ に弧 xy が残りますが、 向きが ¯S から S へ向かっているのでやはり v-w 道はありません。
  →  
K″=({v,y},{x,w}) D−K″
S={v,x,y}, ¯S={w} のとき
  →  
K‴=({v,x,y},{w}) D−K‴
Rem.3 　教科書 p.185 では
「 D−K が v-w 道を含まないこと」
を「カット」の定義としていますので、 「Def.1 のカット」は「教科書のカット」のうち極小なもの、 ということになります。
Def.4　
  • D 上の重み f と、弧の部分集合 B に対し、 B に属する弧の重みの総和を
    f(B)=∑a∈Bf(a)
    と表す。
  • 特にカット K=(S,¯S) に属する弧の容量の総和 Ψ(K) を「カット K の容量」と呼ぶ。
  • N のカットの中で容量が最小のものを「N の最小カット」と呼ぶ。
　Ex.2 では Ψ(K)=8+2=10Ψ(K′)=2+2+3=7Ψ(K″)=8+5=13Ψ(K‴)=3+5=8 であり、N の最小カットは K′ となります。

　フローにカットがどう関わっているかという最初の定理は
Th.5　N の任意のフロー φ と任意のカット K=(S,¯S) に対し、
( φ の値 ) ≦Ψ(K)
が成り立つ。しかも、ここで等号が成立するのは、
  • K=(S,¯S) の全ての弧 a に対して φ(a)=Ψ(a)
  • (¯S,S) の全ての弧 a に対して φ(a)=0
が成り立つときに限る。
　教科書では明らかなように書いてありますが、ちゃんと示しましょう。
Lemma 6　N の任意のフロー φ と任意のカット K=(S,¯S) に対し、
( φ の値 ) =φ((S,¯S))−φ((¯S,S))
が成り立つ。
証明　x∈S から出る弧は、S の頂点に至るものと ¯S の頂点に至るものに分けられます。従って
outdeg(φ,x)=∑a=xy,y∈Sφ(a)+∑a=xy,y∈¯Sφ(a)
この式を全ての x∈S について加えると
∑x∈Soutdeg(φ,x)=∑a=xy,x,y∈Sφ(a)+∑a=xy,x∈S,y∈¯Sφ(a)
右辺の第 2 項は φ((S,¯S)) のことですから
∑x∈Soutdeg(φ,x)=∑a=xy,x,y∈Sφ(a)+φ((S,¯S))
となります。向きを逆にして考えると
∑x∈Sindeg(φ,x)=∑a=yx,x,y∈Sφ(a)+φ((¯S,S))
この 2 つの式の右辺第 1 項は同じものですから、片々引くと
∑x∈S(outdeg(φ,x)−indeg(φ,x))=φ((S,¯S))−φ((¯S,S))
入口 v 以外の頂点では φ の出次数と入次数が釣り合っていますので
左辺 =outdeg(φ,v)−indeg(φ,v)= ( φ の値 )
(証明終)

Th.5 の証明　フローの条件から、各弧 a について φ(a)≦Ψ(a) が成り立つので
φ((S,¯S))=φ(K)≦Ψ(K)
また φ(a)≧0 が成り立つので
φ((¯S,S))≧0
従って L'a 6 により
( フロー φ の値 ) =φ((S,¯S))−φ((¯S,S))≦Ψ(K)
等号成立条件は以上の議論よりわかります。(証明終)
Th.7　N の或るフロー φ と或るカット K=(S,¯S) が
( φ の値 ) =Ψ(K)
を満たせば、φ は最大フロー、K は最小カットである。
証明　最大フローのひとつを φ∗ 、最小カットのひとつを K∗ とすると、
  • φ∗ は最大フローゆえ ( φ の値 ) ≦ ( φ∗ の値 )
  • K∗ は最小カットゆえ Ψ(K∗)≦Ψ(K)
  • Th.5 より ( φ∗ の値 ) ≦Ψ(K∗)
これらと仮定をつなぐと、
( φ の値 ) ≦ ( φ∗ の値 ) ≦Ψ(K∗)≦Ψ(K)= ( φ の値 )
従って全て等号が成り立って、φ は最大フロー、K は最小カットとなります。(証明終)

2.　最大フロー・最小カット定理

　そしていよいよ、驚くべき定理です。
Th.8（最大フロー・最小カット定理）　N の最大フロー φ と最小カット K=(S,¯S) は必ず
( φ の値 ) =Ψ(K)
を満たす。すなわち
( 最大フローの値 ) = ( 最小カットの容量 )
が成り立つ。
　N′ を 前回の「残りを表すネットワーク」とし、次の定理と一緒に証明しましょう。
Th.9（前回の Th.11）　ネットワーク N=(D,Ψ) のフロー φ が最大フローであることと、 N′ が増加道を持たないことが同値である。
Th.9 の証明　⇒) は前回示しました。逆に、N′ が増加道を含まないと仮定して、φ が最大フローであることを導きましょう。
  1. N′ において入口 v から到達可能な頂点全ての集合を S と置きます。 もちろん v∈S であり、また N′ には増加道が無いので w∉S ですから K=(S,¯S) は N のカットになります。
  2. a=xy∈K=(S,¯S) を任意に取ります。 もし Ψ′(a)>0 であれば、N′ の中の v-x 道と a=xy をつなげば v-y 道が作れるので y∈¯S であることに矛盾します。 従って Ψ′(a)=0 でなければなりません。
  3. N′ の作り方から
    Ψ′(a)=Ψ(a)−φ(a)+φ(a−1)
    ですが、フローの条件より φ(a)≦Ψ(a), φ(a−1)≧0 ですから、2° により φ(a)=Ψ(a) かつ φ(a−1)=0 が言えます。 a−1 は (¯S,S) の弧ですから、結局
    • K=(S,¯S) の全ての弧 a に対して φ(a)=Ψ(a)
    • (¯S,S) の全ての弧 a に対して φ(a)=0
    であることがわかりました。
  4. 3° と Th.5 より ( φ の値 ) =Ψ(K) となり、 Th.7 より φ は最大フローです。同時に Th.8 も証明できました。(証明終)
Rem.10　最大フロー φ に対しては
( φ の値 ) =Ψ(K)
を満たすカット K が必ず存在します。 もしそのような K が上手く見つかれば、N′ を作らなくても φ が最大フローであることが言えます。 比較的小さいグラフで最大フローの手計算をするときにはしばしば有効な手段です。
Ex.11（教科書 p.183）
N :
の最大フローは
φ :  
でした。Th.5 の等号条件をヒントに対応する最小カット K を探すと次の赤い弧たちがそうです。
記号で書くと、S={v,x,y,z}, ¯S={w} として K=(S,¯S) になります。 また
も最小カットです。こちらは S={v,x,y}, ¯S={w,z} の場合です。
Rem.12　「Def.1 のカット」は「教科書のカット」のうち極小なものを指しますので、 Th.7, Th.8 は「教科書のカット」の意味でも成立しています。

3.　Menger の定理

　最大フロー・最小カット定理は 「どれだけたくさんデータを送れるか」と「どれだけ小さいカットでブロックできるか」が同じ、 という定理でした。 この現象を重みの無いグラフで考えた Menger の定理を紹介します。まず次の問を考えます。
問　G=(V,E) を連結グラフ、v, w ∈V とするとき、
  1. 辺を共有しない（辺素な、と言います） v-w 道は最大で何本あるか。
  2. 中間点を共有しない（点素な、と言います） v-w 道は最大で何本あるか。
  3. 有向グラフではどうか。
Ex.13　次のグラフで 問 を考えてみましょう。 （黒い記号が頂点、緑の記号が辺です。）
たまたま (1) も (2) も答えは 2 本で、例えば次の図の赤い道と青い道が取れます。
　次はブロックする側の定義です。
Def.14
  1. 辺の部分集合 F⊆E が「vw-非連結化集合」である、とは、任意の v-w 道が F の辺を含むこと。
  2. 頂点の部分集合 W⊆V が「vw-分離集合」である、とは、任意の v-w 道が W の頂点を中間点として含むこと。
言い換えると
  1. ⇔  G−F には v-w 道が無いこと。
  2. ⇔  G−W には v-w 道が無いこと。
Ex.13 のグラフ
では、例えば {h,i,j,k}, {h,f,g}, {g,ℓ} はいずれも vw-非連結化集合です。
   
G−{h,i,j,k} G−{h,f,g} G−{g,ℓ}

また、{s,t,u} や {u,x} は vw-分離集合です。
 
G−{s,t,u} G−{u,x}
　この例では、vw-非連結化集合の辺数の最小値も、 vw-分離集合の頂点数の最小値も 2 で 問 の答えに一致していますが、 これが一般にも成り立ちます。
Th.15（辺形の Menger の定理）　辺素な v-w 道の最大数は、vw-非連結化集合の辺数の最小値に等しい。
Th.16（Menger の定理）　点素な v-w 道の最大数は、vw-分離集合の頂点数の最小値に等しい。
Th.17（整数性定理）　Th.15 は有向グラフでも（辺を弧に読み替えて）成り立つ。
証明　Th.17 は全ての弧の容量が 1 の場合の最大フロー・最小カット定理です。 Th.15 は全ての辺 e=xy を 2 本の逆向きの弧 xy, yx に置き換えれば Th.17 に帰着します。 Th.16 も Th.17 の応用として証明されます（Bondy-Murty 11章を参照）。

　今日は最大フロー・最小カット定理から先に証明しましたが、 歴史的には 1927 年にまず Menger が Menger の定理を証明し、 最大フロー・最小カット定理と辺形の Menger の定理は 1956 年に Ford と Fulkerson によって証明されました。

宿題

  • ここから download
  • 提出期限：一応来週7月24日を目安に。
  • 提出方法：スキャンするか写メを撮るかして、shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。 上手く送信できない人は個別に相談してください。
  • 宿題を複数回分まとめて提出されると見落とす危険があります。 多少面倒でも１回分ずつ送信してください。

戻る