Johnon のアルゴリズム データ構造とアルゴリズム IⅠ 第 回最大フロー 疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている 隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra のアルゴリズムをすべての点について実行すれば最短路が得られる. 負辺があるが, 負閉路を持たない場合は, 再重み付けを行って, 全部非負にする. すなわち, 各頂点 v に関して h(v) を定義し, w (u, v)=w(u, v) + h(u) - h(v) とする. h( ) は新しい重みが必ず非負になるように選ぶ. Johnon のアルゴリズム : アイデア (II) 各頂点 v に関して h(v) を定義し, w (u, v)=w(u, v) + h(u) - h(v) とする. u から v の,( 再重み付け後の ) ある経路の長さは, 本来の辺の重みの和 + h(u) h(v) となる : 途中の頂点の分はキャンセルされる よって, 再重み付けによって最短路は変化しない 新しい重みの元での最短経路長 δ (u, v) から, 元の問題の最短経路長は以下で与えられる : δ(u, v)=δ (u, v) - h(u) + h(v). Johnon のアルゴリズム 各頂点 v に関して, ダミーの始点 ( 各頂点とは重み の辺で結ばれる ) からの距離を求める. これを h(v) とする. 三角不等式により, 任意の v, u に関して, h(v) h(u)+w(u,v), よって w(u,v)+h(u)-h(v), これを新しい辺の重みとする. 新しい辺の重みのもとで,Dikra のアルゴリズムを各頂点を始点として適用. 9 Johnon のアルゴリズム Johnon(G) { compue G, where V[G ]=V[G] {} and E[G ]=E[G] {(,v):v V[G]}.. w(,v)=. if Bellman-Ford(G,w,)=Fale hen prin a neg-weigh cycle ele for each verex v V[G ] e h(v)= (,v) compued by Bellman-Ford algo. for each edge (u,v) E[G ] w (u,v)=w(u,v)+h(u)-h(v) for each verex u V[G] run Dijkra(G,w,u) o compue (u,v) for each v V[G] d uv = (u,v)-h(u)+h(v) reurn D }
- - - - - 三角不等式より,u, vに関して, h(u) + w(u, v) h(v), よって, w(u, v) + h(u) h(v). - - - 再重み付け - / 赤が最短経路. / /- /- / - - / / /- /- / -
Johnon のアルゴリズムの計算量 Bellman-Ford の実行は O( V E ). Dijkra を V 回実行. 凝ったヒープ (Fibonacci heap) を使えば総計 O( V log V + V E ). 普通の Binary heap だと, 総計 O( V E log V ). E が少なければ ( V lg V ),Floyd-Warhall より良い. 右のグラフに関して Johnon のアルゴリズムを適用せよ ( 最短経路は, からの経路のみを求めるのみで良い ) - h: - h: - h:- h: - h: h:- h: h: 9 h: h: h: - d: d: h: h: h: d: d: h:- d: d=d : h: h:- h: - d: d: d :- d : h: h: d=d : d: d :- -
. 最大フロー フローネットワーク フローネットワーク :G V, E は有向グラフで, 各辺 u, v Eには容量 c u, v が定義される (uとvの間に辺がなければc u, v = と仮定 ) 始点, 終点 v v 9 v v フロー 最大流量問題 フロー / 流量は関数 f: V V Rで定義され, 任意の u, vに関して以下の条件を満たす : 容量制限 : f u, v c u, v フロー保存則 : すべてのu V, に関して, f v, u f u, v が成立. f f, v f v, をフロー f の値と呼ぶ ( 絶対値とは無関係 ). フローの値が最大となる f を求める. f u, v /c u, v / / / v v / 9/ /9 / v v / / フローネットワーク / / 残余ネットワーク v / v / / /9 / v v / / v v v v 最大流量問題の応用事例 最大マッチング : 後で説明 物流のネットワーク解析 : 工場から消費地に製品を配送. 経路は複数存在し, 配送できる個数に制約が存在 画像処理 ( セグメンテーション ): 画像から人物を切り出す, 最小カット 増加可能パス
Ford-Fulkeron 法 増加可能パスが存在する限り, 残余ネットワークにフローを加え続ける. 増加可能パスがなければ終了. Ford-Fulkeron(G,,) { for each edge (u,v) E[G] do f[u,v] f[v,u] while pah p from o on G f do c f (p) min{c f (u,v):(u,v) i in p} for each (u,v) in p if (u, v) E[G] f[u,v] f[u,v]+ c f (p) ele f[v,u] f[u,v]-c f (p) reurn f } 9 (a) v v v 9 v (b) v v v v / v / v / v / v / /9 / /9 v / v / / v / v / (c) v v v v (d) 9 v v 9 v v / / v v / v 9 / v / / / / v v / v 9 / / v / /
(e) v v (f) v v 9 9 9 v v v v / v / v 9/ 9 / / v / v / 演習 : Ford-Fulkeron 以下のグラフの最大フローを求めよ 演習 : Ford-Fulkeron 以下のグラフの最大フローを求めよ 9 最大フローと最小カット フローネットワークG V, E のカット (cu) S, T は, VのSとTの分割で S 及び T を満たすもの. カット S, T とフロー fに関して, カットと交差する純フロー f S, T は以下で与えられる : f u, v f v, u. Cu S, T の容量 (Capaciy),c S, T は以下で与えられる : c u, v. ネットワークの最小カットは, このネットワークのすべてのカット中で容量が最小のもの. 9 f u, v /c u, v / / S Cu の例 / v v / / /9 / v v / / T c S, T c v,v c v,v =+=
補題. 任意のカット S, T とフロー f に関して, S, T と交差する純フローは, フローの流量 f に等しい. 補題. の証明 f u, v S v v v v T 系. フローネットワークの流量は任意のカットの容量で上から抑えられる. 証明 : 容量制限から明らか 最大フロー = 最小カット 定理.: 最大フロー最小カット定理 以下の条件は等価. f は G における最大フローである.. 残余ネットワーク G は増加可能経路を含まない.. G のあるカット S, T に関して f c S,T である. 証明 : だか でない, すなわち, 最大フローであるのに, 増加可能パスがあるとすると, 明らかに矛盾. : 残余ネットワークでは, から への経路が存在しない. から到達可能な頂点集合を S, 残りを T とすると, これはカットになっている. u S,v T に関して, u, v E なら, この辺は容量一杯まで流れているはず ( そうでないと残余ネットワークで v が から到達可能 ). また, v, u E なら, この辺のフローは のはず ( そうでないと残余ネットワークで v が から到達可能 ). 補題. より, S, T と交差する純フローは, フローの流量に等しい. : 系. より, すべてのフローの流量はカットの容量で上から抑えられる. よって, カットの容量に等しいことは, フローが最大であることの十分条件である. Ford-Fulkeron 法の計算量 増加可能パスを求める方法に依存する. 良くない方法を使うと停止しないこともある ( 辺容量が無理数の場合 ). 容量が整数なら有限の繰り返しで停止する. 幅優先探索を用いて, 最短経路の増加可能パスを求めた方が良い (Edmond-Karpアルゴリズムと呼ばれる ). この場合のフロー増加操作の総数は高々 O V E となる.
最短でない増加可能パス a - a b b - 二分グラフの最大マッチング (.) 二分グラフは, 頂点集合 V が L と R の二つの集合に分割され, 任意の辺 u, v は,L と R の頂点を結ぶ (L 間,R 間の辺は存在しない ). - a - 回繰返 b - - a b 二分グラフの例 マッチング すべての頂点 vに関して, vに接続する辺が高々一つしかない辺集合をマッチングと呼ぶ. 最大マッチングは, 要素数が最大のマッチングである. L R 9 マッチングの例 最大マッチングの例 L R L R
最大フローとしての表現 最大フローとしての表現 新しい頂点 と を導入 から左側の頂点に容量 の辺を張る 右側の頂点から に容量 の辺を張る L R 最大フロー = 最大マッチング 定期試験に関して 月 日 ( 火 )::-: 内容は 題ぐらい 最小全域木, 最短路, 最大フロー等 L R 9