算法数理工学 第8回 定兼 邦彦.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
算法数理工学 第 7 回 定兼 邦彦 1. グラフ グラフ G = (V, E) –V: 頂点 ( 節点 ) 集合 {1,2,…,n} –E: 枝集合, E  V  V = {(u,v) | u, v  V} 無向グラフ – 枝は両方向にたどれる 有向グラフ – 枝 (u,v) は u から.
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
算法数理工学 第9回 定兼 邦彦.
    有限幾何学        第8回.
On the Enumeration of Colored Trees
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
An Algorithm for Enumerating Maximal Matchings of a Graph
    有限幾何学        第5回.
Extremal Combinatrics Chapter 4
Approximation of k-Set Cover by Semi-Local Optimization
算法数理工学 第10回 定兼 邦彦.
JAG Regional Practice Contest 2012 問題C: Median Tree
    有限幾何学        第12回.
Natural Semantics 実行過程の、最初と最後の状態(state)の関係を考える。
情報工学概論 (アルゴリズムとデータ構造)
9.NP完全問題とNP困難問題.
宇野 毅明 国立情報学研究所 2002年3月 東北大大学院 情報科学研究科ワークショップ
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
Selfish Routing and the Price of Anarchy 第2回
情報学研究科 通信情報システム専攻 小野寺研究室 M1 奥村 佳弘
シャノンのスイッチングゲームにおけるペアリング戦略について
アルゴリズムとデータ構造 2011年7月4日
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
アルゴリズムイントロダクション 第24章 単一始点最短路問題
離散数学 08. グラフの探索 五島.
7.4 Two General Settings D3 杉原堅也.
25. Randomized Algorithms
Selfish Routing and the Price of Anarchy 4.3
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
計算量理論輪講 chap5-3 M1 高井唯史.
First Course in Combinatorial Optimization
A Simple Algorithm for Generating Unordered Rooted Trees
離散数学 07. 木 五島.
情報生命科学特別講義III (13) 固定パラメータアルゴリズムと 部分k木
算法数理工学 第8回 定兼 邦彦.
九州大学大学院 情報学専攻特別講義 (6) 固定パラメータアルゴリズムと 部分k木
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
算法数理工学 第7回 定兼 邦彦.
    有限幾何学        第5回.
離散数学 06. グラフ 序論 五島.
Max Cut and the Smallest Eigenvalue 論文紹介
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月8日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
4.プッシュダウンオートマトンと 文脈自由文法の等価性
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
生命情報学特論 (6) 固定パラメータアルゴリズムと 部分k木
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
グラフの列挙 中野 眞一    (群馬大学) 2019/9/14 列挙学校.
生物情報ソフトウェア特論 (10)固定パラメータアルゴリズムと 部分k木
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
アルゴリズムとデータ構造 2012年7月9日
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

算法数理工学 第8回 定兼 邦彦

深さ優先探索,幅優先探索 木やグラフの探索法 深さ優先探索 (depth-first search, DFS) 行き止まりになるまで先に進む 幅優先探索 (breadth-first search, BFS) 全体を同時に探索する DFSはスタック(再帰),BFSはキューで実現できる 1 3 4 2 5 6 1 4 5 2 3 6 DFS BFS

DFS(G) for each u  V[G] color[u]  白 [u]  NIL time  0 if color[u] = 白 DFS-Visit(u) DFS-Visit(u) color[u]  灰 time  time + 1 d[u]  time for each v  Adj[u] if color[v] = 白 [v]  u DFS-Visit(v) color[u]  黒 f[u]  time

白:未訪問 灰:探索中 黒:探索終了 u v w 1/ x y z

u v w 1/ 2/ x y z

u v w 1/ 2/ 3/ x y z

u v w 1/ 2/ 4/ 3/ x y z

辺 (x, v) をたどる v は既に訪問しているので行かない u v w 1/ 2/ 4/ 3/ x y z

白:未訪問 灰:探索中 黒:探索終了 u v w 1/ 2/ 4/5 3/ x y z

u v w 1/ 2/ 4/5 3/6 x y z

u v w 1/ 2/7 4/5 3/6 x y z

辺 (u, x) をたどる x は既に訪問しているので行かない u v w 1/ 2/7 4/5 3/6 x y z

u v w 1/8 2/7 4/5 3/6 x y z

u v w 1/8 2/7 9/ 4/5 3/6 x y z

u v w 1/8 2/7 9/ 4/5 3/6 x y z

u v w 1/8 2/7 9/ 4/5 3/6 10/ x y z

u v w 1/8 2/7 9/ 4/5 3/6 10/ x y z

u v w 1/8 2/7 9/ 4/5 3/6 10/11 x y z

u v w 1/8 2/7 9/12 4/5 3/6 10/11 x y z

辺 (u, v) をたどったら,v の親を u にする ([v] = u) グラフ G = (V, E) を次のように定義する E = {([v], v)  E | v  V かつ [v]  NIL} G は深さ優先探索森 (depth-first forest) 連結ならば深さ優先探索木 (depth-first tree) 各点は探索前は白,探索中は灰,探索終了後は黒 各点 v は2つのタイムスタンプを持つ d[v] は v を最初に発見した (灰色にした) 時刻 f[v] は v の隣接リストを調べ終わった (黒にした) 時刻 タイムスタンプは 1 から 2n の整数 全ての u に対し d[u] < f[u] DFSの実行時間は (n+m)

定理 (括弧付け定理): グラフ G に対する任意の深さ優先探索を考える.任意の2つの頂点 u, v に対し,以下の3つの条件の中の1つだけが成立する. 区間 [d[u], f[u]] と区間 [d[v], f[v]] には共通部分が無く,深さ優先森において u と v はどちらも他方の子孫ではない. 区間 [d[u], f[u]] は区間 [d[v], f[v]] に完全に含まれ, u が v の子孫となる深さ優先探索木が存在する 区間 [d[v], f[v]] は区間 [d[u], f[u]] に完全に含まれ, v が u の子孫となる深さ優先探索木が存在する 注:2つの区間が部分的に重なることは無い

証明: まず d[u] < d[v] の場合を考える d[v] < f[u] のとき u がまだ灰色のときに v が発見されている.つまり v は u の子孫. v は u よりも後に発見されたので,u の探索が終わる前に v の探索は終わる.つまり f[v] < f[u]. このとき区間 [d[v], f[v]] は区間 [d[u], f[u]]に含まれる. f[u] < d[v] のとき d[u] < f[u] < d[v] < f[v] なので区間に共通部分は無い. つまり一方が探索中に他方が発見されない. よってどちらも他方の子孫では無い d[v] < d[u] の場合も同様に証明できる.

系:有向または無向グラフに対する深さ優先探索森において頂点 v が 頂点 u ( v) の子孫であるための必要十分条件は d[u] < d[v] < f[v] < f[u] 定理 (白頂点経路定理): グラフ G の深さ優先探 索森において,頂点 v が 頂点 u の子孫であるため の必要十分条件は,探索が u を発見する時刻 d[u] に u から v に至る白頂点だけからなるパスが 存在することである. 証明:⇒) v が u の子孫であると仮定する.uv間のパス上の任意の頂点を w とする.w は u の子孫なので,d[u] < d[w].つまり時刻 d[u] では w は白.

←) 時刻 d[u] に u から v に至る白頂点だけからなるパスが存在するが,深さ優先探索木において v が u の子孫にならないと仮定する.一般性を失うことなく,このパス上の v 以外の全ての頂点は u の子孫になると仮定できる. このパス上で v の直前の点を w とする. w は u の子孫 (uを含む) なので f[w]  f[u]. v の発見は u の後で,w の終了の前なので, d[u] < d[v] < f[w]  f[u]. 区間は部分的には重ならないので f[v] < f[u]. つまり v は u の子孫.

y z s t 3/6 2/9 1/10 11/16 4/5 7/8 12/13 14/15 x w v u s t z v u y w x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)

辺の分類 グラフ G の深さ優先探索森 G を1つ固定する. G の辺を4種類に分類する tree edge (木辺) back edge (後退辺) 辺 (u, v) で,u と v がある深さ優先探索木の頂点とその先祖の場合.セルフループも後退辺とみなす. forward edge (前進辺) 辺 (u, v) で,木辺でなく,u と v がある深さ優先探索木の頂点とその子孫の場合. cross edge (横断辺) 上の3つ以外

定理: 無向グラフ G を深さ優先探索するとき,G の任 意の辺は木辺または後退辺である. 証明: (u, v) を G の任意の辺とし,一般性を失うこと なく d[u] < d[v] と仮定する. v は u の隣接リストに含まれるので,u に対する処理 が終わる前に v に対する処理が終わる. 辺 (u, v) が最初に u から v に向かって探索されたな ら,v はその時点では白である.すると (u, v) は木辺. 辺 (u, v) が最初に v から u に向かって探索されたな ら,u はその時点では灰である.すると (u, v) は 後退辺.

定理: ・辺 (u,v) が木辺または前進辺 ⇔ d[u] < d[v] < f[v] < f[u] ・辺 (u,v) が後退辺 ⇔ d[v] < d[u] < f[u] < f[v] ・辺 (u,v) が横断辺 ⇔ d[v] < f[v] < d[u] < f[u]

トポロジカルソート 入力:閉路のない有向グラフ G = (V, E) 出力: Gの全頂点の線形順序で, G が辺 (u, v) を含む ⇔ この線形順序で u が v より先に現れる 注:グラフに閉路があればそのような線形順序は存在しない 半順序しか定義されていない集合に,それと矛盾しない全順序を1つ与えることに相当する. (n+m) 時間で求まる. 閉路を持たない有向グラフは DAG (directed acyclic graph) と呼ばれる

全ての有向辺が左から右の向きになっている 注:トポロジカルソートは1通りでは無い socks 17/18 11/16 undershorts shoes 13/14 12/15 pants shirt 1/8 watch 9/10 6/7 belt tie 2/5 jacket 3/4 socks undershorts pants shoes watch shirt belt tie jacket 17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4 全ての有向辺が左から右の向きになっている 注:トポロジカルソートは1通りでは無い

TOPOLOGICAL-SORT(G) L   (空リスト) for each u  V[G] color[u]  白 if color[u] = 白 Visit(u) Visit(u) if color[u] = 灰 stop (DAGでは無い) if color[u] = 黒 return color[u]  灰 for each v  Adj[u] Visit(v) color[u]  黒 L の先頭に u を入れる 時間計算量: (n+m)

補題1: 有向グラフ G に閉路が存在しない ⇔ G を深さ優先探索した時に後退辺を生成しない 証明: →) 後退辺 (u, v) が存在すると仮定する. つまり深さ優先探索木において v は u の祖先. v から u のパスに後退辺(u, v)を加えると閉路になる. ←) G が閉路 c を含むと仮定する.c の中で最初に 訪れられる点を v とし,c において v に入る辺を(u, v) とする.時刻 d[v] では,c 内の頂点は全て白である. よって v から u まで白頂点のみからなるパスが存在 するため,vは uの先祖であり,(u, v)は後退辺となる.

補題: トポロジカルソートのアルゴリズム実行時に 辺 (u, v) が探索されたとする.グラフに閉路が無い ⇔ v は灰色ではない. (つまり,v が灰色なら解は存在しない) 証明: v が灰色なら,v は u の先祖であり, (u, v) が 後退辺となる.前の補題からグラフは閉路を持つ. グラフに閉路があるなら,後退辺 (u, v) が存在し, v は灰色である.

定理: TOPOLOGICAL-SORT(G)は有向グラフGが 閉路を持たないなら G をトポロジカルソートし,閉路 を持つならその1つを発見する. 証明: グラフが閉路を持つなら後退辺 (u, v) が存在 し,v の色は灰となる.アルゴリズムは全ての辺を 調べるので,閉路があるなら必ず発見する. 以下ではグラフが閉路を持たない場合を考える. 頂点はその探索の終了時にLの先頭に挿入される. つまり L には頂点は終了時刻 f[] の降順に入って いる.よって,G の中に辺 (u, v) があるときに f[v] < f[u] となっていることを示せばいい.

アルゴリズムが辺 (u, v) を探索する時点を考える. v の色は白か黒である.v が白なら v は u の子孫に なり, f[v] < f[u] が成立する. v が黒なら v の処理 は既に終了しているので,f[v] は既に決定されてい る.u は探索中なので f[u] は未決定である. よって f[v] < f[u] となる.

強連結成分分解 定義: 有向グラフ G = (V, E) の強連結成分 (strongly connected component) とは,次の条件を満たす 頂点の集合 C  V で極大なものと定義する. C の全ての頂点対に対して u v かつ v u (u v はuからvへ有向パスが存在することを表す.) Cが極大とは,C  C’, C  C’ となる強連結成分 C’ は無いという意味 つまり,u と v は互いに到達可能である.

13/14 11/16 1/10 12/15 3/4 4つの強連結成分 (SCC) を持つ 注: 各SCCは1つの閉路とは限らない a b c d 13/14 11/16 1/10 8/9 12/15 3/4 2/7 5/6 e f g h 4つの強連結成分 (SCC) を持つ 注: 各SCCは1つの閉路とは限らない 1点でもSCCになる

各強連結成分を1点に縮約すると,DAGになる b c d 13/14 11/16 1/10 8/9 12/15 3/4 2/7 5/6 e f g h abe cd h fg 各強連結成分を1点に縮約すると,DAGになる

定義: グラフ G = (V, E) の転置とは,次のように 定義されるグラフ GT = (V, ET) である. ET = {(v, u) | (u, v)  E} GT の隣接行列は,G の隣接行列の転置になる. GT は線形時間 (n+m) で求まる. G の各頂点 u に対し,その隣接点 v  Adj[u] を  列挙し,辺 (v, u) を GT の v の隣接リストに挿入

SCC(G) // Strongly-Connected-Components DFS(G) を呼び出し,各頂点 u に対して終了時刻 f[u] を計算する GT を計算する DFS(GT) を呼び出す.ただし 1. で計算した f[u] の降順で頂点を探索する 3. で生成した深さ優先探索森の各木の頂点集合を1つの強連結成分として出力する (n+m) 時間

補題: 有向グラフ G=(V, E) の異なる2つの強連結 成分を C と C’, u, v  C, u’, v’  C’ とする. G に経路 u u’ が存在するとき,G には経路 v’ v は存在しない. 証明: G に経路 v’ v が存在すると仮定すると, 経路 u u’ v’ と v’ v u が存在する. 従って u と u’ は互いに到達可能であり,C と C’ が 異なる強連結成分であることに矛盾する. v v’ C’ C u’ u

定義: d(U) = minu  U {d[u]} f(U) = maxu  U {f[u]} つまり, d(U) と f(U) は U の頂点の発見時刻と終了 時刻の中で最も早い時刻と最も遅い終了時刻. 補題: 有向グラフ G=(V, E) の異なる2つの強連結 成分を C と C’ とする. u  C, v  C’ である辺 (u, v) が存在するなら,f(C) > f(C’) である. C’ C v u

時刻 d[x] では C と C’ の点は全て白で,x から u に 至る白頂点だけからなるパスが G に存在する. 証明: d(C) < d(C’) の場合 C の中で最初に発見される点を x とする. 時刻 d[x] では C と C’ の点は全て白で,x から u に 至る白頂点だけからなるパスが G に存在する. (u, v)  E なので,時刻 d[x] では x から任意の頂点 w  C’ に至る白頂点だけからなるパスが G に存在 する.つまり x u  v w である.白頂点経路 定理より C’ の全頂点はDFS木で x の子孫となり, f[x] = f(C) > f(C’). x w C’ C v u

d(C) > d(C’) の場合. C’ の中で最初に発見される 点を y とする.時刻 d[y] では C’ の全頂点は白で, DFS木において y の子孫となり,f[y] = f(C’) となる. 時刻 d[y] では C の全頂点は白である.C から C’ に 辺 (u, v) が存在するので, C’ から C にはパスは 存在しない. y C’ C v u

C の任意の頂点は y から到達不可能なので, 時刻 f[y] には C の全頂点はまだ白のままである. 従って,任意の頂点 w  C に対して f[w] > f[y], すなわち f(C) > f(C’) が成立する. 系1: C と C’ を有向グラフ G=(V, E) の異なる2つの 強連結成分とする. u  C と v  C’ の間に 辺 (u, v)  ET があるとき,f(C) < f(C’) である. w y C’ C v u

定理: アルゴリズム SCC は有向グラフ G の強連結 成分を正しく求める. 証明: 帰納法で示す.アルゴリズムの3行目で求めた 最初の k 個の木が強連結成分のときに,k+1 個目も 強連結成分であることを示す.k=0のときは成り立つ. (k+1) 番目の木の根を u とし,u の属する強連結成分 を C とする.この後で訪問する C 以外の任意の強連 結成分 C’ に対して f[u] = f(C) > f(C’) が成立する. 帰納法の仮定(最初の k 個の木が強連結成分)から, C の一部の頂点が既に訪れられていることはない.

白頂点経路定理より,u からの深さ優先探索木に おいて C の他のすべての頂点は u の子孫になる. さらに,帰納法の仮定と系1から,GTの C から出る 任意の辺は既に訪問された強連結成分への辺で ある.従って,C 以外の任意の強連結成分に属する どの頂点も,u からの深さ優先探索によって u の 子孫になることはない.よって,u を根とする深さ優先 探索木の全頂点は1つの強連結成分に対応する.

最大流問題とフロー増加法 各枝に容量が与えられたネットワーク G = (V,E) において,ソース s  V からシンク t  V に向かってできるだけ多くのものを送ることを考える 枝 (i,j) 上の流れの大きさを xij,枝 (i,j) の容量,つまり流れ xij の上限値を uij,ソースからシンクへの総流量を f とすると,問題は次のような線形計画問題として定式化できる 1 2 3 4 5 8 ソース シンク

流れ保存則 容量制約条件 制約条件1: s からの正味の流出量が f 制約条件3: t への正味の流入量が f 制約条件: 流れ保存則 制約条件1: s からの正味の流出量が f 制約条件3: t への正味の流入量が f 制約条件2: s と t 以外の節点では流入量 = 流出量 容量制約条件 制約条件4: 各枝の流量が非負かつ枝の容量以下

流れ保存則と容量制約条件を満たす x = (xij) を フローと呼びそれに対する f をフローの流量と呼ぶ 最大流問題は,流量が最大になるフローを求める問題 最大流問題は線形計画問題なので単体法などで解くことができるが,ここではネットワーク問題の特性を利用したアルゴリズムを考える 1 2 3 4 5 8 ソース シンク

残余容量と残余ネットワーク ネットワークにおいて,任意の2節点 i, j  V の間に枝(i,j)と(j,i)の両方が存在することはないと仮定 あるフロー x = (xij) が与えられているとする.ネットワーク G = (V,E) の各枝 (i,j)  E を容量 を持つ枝 (i,j) と,容量 を持つ枝 (j,i) で 置き換える なら枝 (j,i) のみ, なら枝 (i,j) のみ i j

をフロー x に対する枝 (i,j) の残余容量という ネットワーク G の各枝 (i,j) を上のように置き換えたネットワークを,フロー x に対する残余ネットワークと言い,Gx = (V,Ex) と書く 元のネットワーク G 1 2 3 4 5 8 残余ネットワーク Gx 1 2 3 4 5 6 フロー x 1 2 3 4 5 (3) (4) (2) (1) (0) (6)

そのような路を,(現在のフロー x に対する) フロー増加路と呼ぶ 残余ネットワークにおいて,ソースからシンクへの路が存在すれば,その路に沿ってフローを追加することによって,元のネットワーク上での流量 f を 増やせることがわかる そのような路を,(現在のフロー x に対する) フロー増加路と呼ぶ フロー増加路に沿って追加できるフローの量は,その路に含まれる枝の残余容量の最小値に等しい 残余ネットワーク Gx 1 2 3 4 5 6

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 (1) (3) (0) (2) (1) (4) (6) (4) (2) (3) フロー x 1 2 3 4 5 (3) (4) (2) (1) (0) (6) 新しいフロー x 1 2 3 4 5 (4) (3) (1) (2) (6) 残余ネットワーク Gx フロー増加路 (流量1) 1 2 3 4 5 6

フロー増加法 (Ford-Fulkerson法) 最大流を求めるアルゴリズム (正当性の証明は後) (0) 適当な初期フロー x を求める 例えば,全ての枝 (i,j) に対し xij = 0 とする 残余ネットワーク Gx においてソースからシンクへの路 (フロー増加路) を見つける 存在しなければ計算終了 フロー増加路に沿って可能な限りフローを追加し,新しいフロー x を得る.ステップ(1)に戻る

初期フロー 残余ネットワーク 1 2 3 4 5 (0) 1 2 4 5 3 3 5 1 5 4 3 8 フロー 残余ネットワーク 1 2 3 4 5 (0) (4) 1 2 4 5 3 3 5 1 4 5 4 3 4

フロー 残余ネットワーク 1 2 3 4 5 (3) (4) (0) (7) 1 2 4 2 3 3 3 5 1 1 5 4 3 7 フロー 残余ネットワーク 1 2 3 4 5 (4) (3) (1) (0) (7) 1 2 4 1 2 3 5 4 1 1 1 5 4 3 7 フロー増加路が存在しないので終了 フローの流量は 8

フロー増加法の正当性と 最大流最小カット定理 枝の容量が全て整数なら,初期フローを整数値としてフロー増加法を用いると,ソースからシンクへの流量は1回の反復で少なくとも1は増える よって有限回の反復の後にアルゴリズムは終了 終了した時点でのフローが最大流になっていることを示す

頂点集合V をソースs を含む集合Sとシンクt を含む集合T に分割したものをカットと言い,(S,T) と表す 任意のカット (S,T) に対して,S の節点を始点とし, T の節点を終点とする枝を (i,j)  (S,T),逆に, T の節点を始点とし,S の節点を終点とする枝を (j,i)  (T,S) と書く 全ての枝 (i,j)  (S,T) の容量 uij の合計を カット (S,T) の容量と呼び,C(S,T) で表す.つまり

x を任意のフロー,f をその流量,(S,T) を任意のカットとする が成立する 全ての枝 (i,j) E に対して 0  xij  uij であるから, カット容量の定義より,f  C(S,T) を得る

フロー増加法の計算が終了した時点で得られているフローを x*,その流量を f * とする 残余ネットワークでs から到達できる点の集合をS*, その補集合を T* とする s  S* かつ t  T* より,(S*,T*) はカットとなる 残余ネットワークの定義より

従って, 任意のフローに対して f  C(S,T)が成り立つので, 上の式は x* が実行可能な全てのフローの中で 最大流量を与えるものであり,同時に,(S*,T*) が 全てのカットの中で最小の容量をもつものであることを示している (最大流最小カットの定理) 以上より,フロー増加法が終了したときのフローは最大流になっている

フロー増加法の計算量とその改良 容量が整数値のとき,フロー増加法では1回の反復で少なくとも1単位の流量が追加される  ⇒ 全体の反復回数は最大流量の値を越えない 枝の容量の最大値を U = max{uij| (i,j)  E} とすると,最大流量の上限は mU 1つのフロー増加路を見つける計算量は O(m) 全体の計算量は O(m2U) 計算量に U が現れるので,理論的には多項式時間アルゴリズムとは言えない

Edmonds-Karpアルゴリズム フロー増加法において,フロー増加路を求める際に辺数最小のものを求める 幅優先探索で路を求めればいい 反復回数が mn/2 以下になる (後述) 全体の時間計算量は O(m2n)

i 回目の反復後のフローを fi とする i+1 回目の反復では,残余ネットワーク で辺数 最小のフロー増加路 Pi を求め,フロー fi+1を流す 補題:フローの系列 f1, f2,... に対し (a) 全ての k で |E(Pk)|  |E(Pk+1)| (b) Pk  Pl が逆辺対を持つような全ての k < l に対して, |E(Pk)| + 2  |E(Pl)|

証明:(a) Pk  Pk+1 から逆辺対を全て除去した グラフを G1 とする Pk と Pk+1 の両方に現れる辺は多重辺とする G1 には2つの辺素な s-t パス Q1, Q2 が存在する の任意の辺はPk の辺の逆辺となる の辺は Pk にそってフローを流したときにできたので,それは流量が 0 のところにフロー Pk を流したあとの残余ネットワークの辺であるから s t Pk Pk+1 s t Q1 Q2 G1

G1 の枝は Pk  Pk+1 に含まれるが,後者の枝の 中で の枝は Pk の逆辺なので 削除されている.よって Q1, Q2 の枝は G1 に含まれるので,Q1, Q2 は での増加路である Pk は辺数最小の増加路なので,|E(Pk)|  |E(Q1)| かつ |E(Pk)|  |E(Q2)| 以上より |E(Pk)|  |E(Pk+1)| (Q1とQ2はG1の辺素パス) (G1は逆辺を削除)

(b) の証明: k < i < l である全ての i に対しPi  Pl が逆辺を持たないようなk, l に対して証明できれば, (a) より全ての k < l に対しても成り立つ Pk  Pl から逆辺対を全て除去したグラフを G1 とする であり, の任意の辺は Pk, Pk+1,...,Pl-1 の いずれかに含まれる辺の逆辺である よって,Pl の辺で Pk の逆辺でないものは, の辺か Pk+1,...,Pl-1 の辺の逆辺である k と l の定め方より,Pl は Pk+1,...,Pl-1 の辺の逆辺を持たない.

よって,Pl の辺で Pk の逆辺でないものは の辺となり, が得られる G1 には2つの辺素な s-t パス Q1, Q2 が存在し, それらは での増加路である Pk は辺数最小の増加路なので,|E(Pk)|  |E(Q1)| かつ |E(Pk)|  |E(Q2)|   (少なくとも2辺を除去しているので) より,命題が成り立つ

定理: 辺数 m, 点数 n のネットワークに対して, Edmonds-Karpアルゴリズムは辺の容量に関わらず,高々 mn/2 回の反復で終了する 証明:アルゴリズムの実行中に選ばれた増加路を P1, P2,... とする 増加路で可能な限りフローを追加するので,各増加路には残余ネットワークでの容量いっぱいまで流す枝が存在する.それをボトルネック辺と呼ぶ 任意の辺 e に対して,e をボトルネック辺にもつ増加パスを とする と の間に,e の逆辺を含む増加路 が存在する (ij < k < ij+1)

補題 (b) より,全ての j に対し e が端点として s と t を含まなければ,全ての j で となり,e をボトルネック辺としてもつ増加路は高々 n/4 個 e が端点として s と t のいずれかを含むときは, e またはその逆辺をボトルネック辺として持つ増加路は高々1つ 任意の増加路は G の辺かその逆辺を少なくとも 1本含むので,高々 2m  n/4 = mn/2 個の増加路しか選ばれない