ALG2015-09

算法数理工学
第9回
定兼邦彦
残余容量と残余ネットワーク
• ネットワークにおいて，任意の2節点 i, j  V の間
に枝(i,j)と(j,i)の両方が存在することはないと仮定
• あるフロー x = (xij) が与えられているとする．ネット
x
u
ワーク G = (V,E) の各枝 (i,j)  E を容量 ij  uij  xij
x
を持つ枝 (i,j) と，容量 u ji  xij を持つ枝 (j,i) で
置き換える
x
x
• uij  0 なら枝 (j,i) のみ， u ji  0 なら枝 (i,j) のみ
uijx  uij  xij
i
xij / uij
j
i
j
u xji  xij
2
x
x
u
,
u
• ij ji をフロー x に対する枝 (i,j) の残余容量という
• ネットワーク G の各枝 (i,j) を上のように置き換え
たネットワークを，フロー x に対する残余ネットワー
クと言い，Gx = (V,Ex) と書く
元のネットワーク G
1
2
5
残余ネットワーク Gx
4
3
5
3
1
5
3
4
8
(3)
2
(1)
4
2
1
2
3
2
5
6
(1)
(2) (0)
5
3
4
5
1
3
4
1
(4)
2
2
1
フロー x
1
(6)
3
• 残余ネットワークにおいて，ソースからシンクへの
路が存在すれば，その路に沿ってフローを追加す
ることによって，元のネットワーク上での流量 f を
増やせることがわかる
• そのような路を，(現在のフロー x に対する) フロー
増加路と呼ぶ
• フロー増加路に沿って追加できるフローの量は，そ
の路に含まれる枝の残余容量の最小値に等しい
残余ネットワーク Gx
2
2
1
1
5
1
3
2
4
4
1
2
3
6
2
5
4
フロー x
(1)
2
(3)
4
(1)
(2) (0)
1
新しいフロー x
5
3
(4)
(6)
(4)
2
(1)
4
(2)
(3) (1)
1
(4)
残余ネットワーク Gx
フロー増加路 (流量1)
1
1
2
2
3
2
4
4
5
1
1
2
3
5
6
3
(6)
2
5
5
フロー増加法
(Ford-Fulkerson法)
•
最大流を求めるアルゴリズム
(正当性の証明は後)
(0) 適当な初期フロー x を求める
例えば，全ての枝 (i,j) に対し xij = 0 とする
(1) 残余ネットワーク Gx においてソースからシ
ンクへの路 (フロー増加路) を見つける
存在しなければ計算終了
(2) フロー増加路に沿って可能な限りフローを
追加し，新しいフロー x を得る．ステップ(1)
に戻る
6
初期フロー
(0)
2
残余ネットワーク
(0)
(0)
4
(0)
(0)
1
5
(0)
3
2
5
4
3
5
3
1
5
3
4
(0)
フロー
(0)
1
8
残余ネットワーク
2
(0)
(0)
4
(0)
(0)
1
5
(4)
3
(4)
1
2
5
4
3
5
3
1
4
4
3
5
4
7
フロー
(3)
残余ネットワーク
2
(0)
(3)
4
(0)
(0)
1
5
(4)
3
3
4
3
5
3
1
3
4
(7)
フロー
(4)
2
2
1
1
5
7
残余ネットワーク
2
(1)
(3)
4
(1)
(0)
1
5
(4)
3
(7)
2
1
1
1
4
4
4
5
3
3
2
1
1
5
7
フロー増加路が存在しないので終了
フローの流量は 8
8
フロー増加法の正当性と
最大流最小カット定理
• 枝の容量が全て整数なら，初期フローを整数値と
してフロー増加法を用いると，ソースからシンクへ
の流量は1回の反復で少なくとも1は増える
• よって有限回の反復の後にアルゴリズムは終了
• 終了した時点でのフローが最大流になっていること
を示す
9
• 頂点集合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) で表す．つまり
C (S , T ) 
u
ij
( i , j )( S ,T )
10
• x を任意のフロー，f をその流量，(S,T) を任意のカ
ットとする
• f   xij   x ji が成立する
( i , j )( S ,T )
( j ,i )(T , S )
• 全ての枝 (i,j) E に対して 0  xij  uij であるから，
カット容量の定義より，f  C(S,T) を得る
f 

x

x

ij
( i , j )( S ,T )
ij
( i , j )( S ,T )
x
ji
( j ,i )(T , S )
u
ij
( i , j )( S ,T )
 C (S , T )
11
• フロー増加法の計算が終了した時点で得られてい
るフローを x*，その流量を f * とする
• 残余ネットワークでs から到達できる点の集合をS*,
その補集合を T* とする
• s  S* かつ t  T* より，(S*,T*) はカットとなる
• 残余ネットワークの定義より
(i, j )  ( S *, T *)  xij*  uij
( j , i )  (T *, S *)  x*ji  0
12
• 従って，
f*
*
x
 ij 
( i , j )( S * ,T * )

*
x
 ji
( j ,i )(T *,S *)
u
ij
( i , j )( S* ,T * )
 C ( S *, T *)
• 任意のフローに対して f  C(S,T)が成り立つので，
上の式は x* が実行可能な全てのフローの中で
最大流量を与えるものであり，同時に，(S*,T*) が
全てのカットの中で最小の容量をもつものであるこ
とを示している (最大流最小カットの定理)
• 以上より，フロー増加法が終了したときのフローは
最大流になっている
13
フロー増加法の計算量とその改良
• 容量が整数値のとき，フロー増加法では1回の反
復で少なくとも1単位の流量が追加される
⇒ 全体の反復回数は最大流量の値を越えない
• 枝の容量の最大値を U = max{uij| (i,j)  E} とす
ると，最大流量の上限は mU
• 1つのフロー増加路を見つける計算量は O(m)
• 全体の計算量は O(m2U)
• 計算量に U が現れるので，理論的には多項式
時間アルゴリズムとは言えない
14
Edmonds-Karpアルゴリズム
• フロー増加法において，フロー増加路を求め
る際に辺数最小のものを求める
– 幅優先探索で路を求めればいい
• 反復回数が mn/2 以下になる (後述)
• 全体の時間計算量は O(m2n)
15
• i 回目の反復後のフローを fi とする
• i+1 回目の反復では，残余ネットワーク G f i で辺数
最小のフロー増加路 Pi を求め，フロー fi+1を流す
• 補題：フローの系列 f1, f2,... に対し
(a) 全ての k で |E(Pk)|  |E(Pk+1)|
(b) Pk  Pl が逆辺対を持つような全ての k < l に
対して， |E(Pk)| + 2  |E(Pl)|
16
• 証明：(a) Pk  Pk+1 から逆辺対を全て除去した
グラフを G1 とする
• Pk と Pk+1 の両方に現れる辺は多重辺とする
• G1 には2つの辺素な s-t パス Q1, Q2 が存在する
Q2
Pk+1
t
s
• E (G
t
s
Q1
Pk
f k 1
G1
fk
) \ E (G ) の任意の辺はPk の辺の逆辺となる
– E (G f k 1 ) \ E (G f k ) の辺は Pk にそってフローを流したとき
にできたので，それは流量が 0 のところにフロー Pk を
17
流したあとの残余ネットワークの辺であるから
• G1 の枝は Pk  Pk+1 に含まれるが，後者の枝の
中で E (G f k 1 ) \ E (G f k ) の枝は Pk の逆辺なので
削除されている．よって E (G1 )  E (G f k )
• Q1, Q2 の枝は G1 に含まれるので，Q1, Q2 は
f k での増加路である
G
• Pk は辺数最小の増加路なので，|E(Pk)|  |E(Q1)|
かつ |E(Pk)|  |E(Q2)|
2 E ( Pk )  E (Q1 )  E (Q2 )
 E (G1 )
(Q1とQ2はG1の辺素パス)
 E ( Pk )  E ( Pk 1 )
(G1は逆辺を削除)
以上より |E(Pk)|  |E(Pk+1)|
18
• (b) の証明： k < i < l である全ての i に対しPi  Pl
が逆辺を持たないようなk, l に対して証明できれば,
(a) より全ての k < l に対しても成り立つ
• Pk  Pl から逆辺対を全て除去したグラフを
G1 とする
• E ( Pk )  E (G f k ), E ( Pl )  E (G f l ) であり，
fl
fk
E (G ) \ E (G ) の任意の辺は Pk, Pk+1,...,Pl-1 の
いずれかに含まれる辺の逆辺である
• よって，Pl の辺で Pk の逆辺でないものは，
E (G f k ) の辺か Pk+1,...,Pl-1 の辺の逆辺である
• k と l の定め方より，Pl は Pk+1,...,Pl-1 の辺の逆辺を
持たない．
19
• よって，Pl の辺で Pk の逆辺でないものは E (G )
の辺となり， E (G1 )  E (G f k ) が得られる
• G1 には2つの辺素な s-t パス Q1, Q2 が存在し，
それらは G f k での増加路である
• Pk は辺数最小の増加路なので，|E(Pk)|  |E(Q1)|
かつ |E(Pk)|  |E(Q2)|
• 2 E( Pk )  E(Q1 )  E(Q2 )  E( Pk )  E( Pl )  2
(少なくとも2辺を除去しているので)
より，命題が成り立つ
fk
20
• 定理：辺数 m, 点数 n のネットワークに対して，
Edmonds-Karpアルゴリズムは辺の容量に関わら
ず，高々 mn/2 回の反復で終了する
• 証明：アルゴリズムの実行中に選ばれた増加路を
P1, P2,... とする
• 増加路で可能な限りフローを追加するので，各増
加路には残余ネットワークでの容量いっぱいまで
流す枝が存在する．それをボトルネック辺と呼ぶ
• 任意の辺 e に対して，e をボトルネック辺にもつ増
加パスを Pi , Pi ,... とする
• Pi と Pi の間に，e の逆辺を含む増加路 Pk
が存在する (ij < k < ij+1)
1
j
2
j 1
21
• 補題 (b) より，全ての j に対し
E ( Pi j )  4  E ( Pk )  2  E ( Pi j1 )
• e が端点として s と t を含まなければ，全ての j で
3  E ( Pi )  n  1 となり，e をボトルネック辺としても
つ増加路は高々 n/4 個
• e が端点として s と t のいずれかを含むときは，
e またはその逆辺をボトルネック辺として持つ増加
路は高々1つ
• 任意の増加路は G の辺かその逆辺を少なくとも
1本含むので，高々 2m  n/4 = mn/2 個の増加路し
か選ばれない
j
22
Dinicアルゴリズム
• フロー増加法の各反復において，1本のフロー増加
路だけを用いてフローを追加するのではなく，複数
のフロー増加路を求めてそれらに同時にフローを
追加するアルゴリズム
• Edmonds-Karpアルゴリズムでは各反復で最短の
増加路を求めているが，補題 (a) より路の長さは
単調増加
• 路の長さが等しい増加路の系列をアルゴリズムの
フェイズと呼ぶ
• 1つのフェイズの全ての増加路を同時に求めて
23
加える
• 命題：あるフェイズの始まりのフローを f とする．
そのフェイズの増加路は全て Gf の増加路になる．
• 証明：補題 (b) より，ある増加路 Pk と Pl に対して，
Pk  Pl が逆辺対を持つならば |E(Pk)| + 2  |E(Pl)|
なので，同じフェイズに属する増加路の共通部分
は逆辺対を持たない
fl
fk
• E (G ) \ E (G ) の任意の辺は Pk, Pk+1,...,Pl-1 の
いずれかに含まれる辺の逆辺であるが，今は逆辺
は存在しないので， E (G fl )  E (G f k ) となる
• つまり，あるフェイズの増加路は全て Gf の増加路
24
初期フロー
(0)
2
残余ネットワーク
(0)
(0)
4
(0)
(0)
1
5
(0)
3
2
5
4
3
5
3
1
5
3
4
(0)
フロー
(0)
1
8
残余ネットワーク
2
(0)
(0)
4
(0)
(0)
1
5
(4)
3
(4)
1
2
5
4
3
5
3
1
4
4
3
5
4
25
フロー
(3)
残余ネットワーク
2
(0)
(3)
4
(0)
(0)
1
5
(4)
3
(7)
2
2
1
1
3
4
3
5
3
1
4
3
5
7
この増加路は1つ前の
残余ネットワークにも存在
(長さ3の増加路全てで成立)
26
• 残余ネットワークから，路長最小の路の集合を求
める必要がある．
• 定義：ネットワークの s-t フロー f に対して，Gf の
f
G
レベルグラフ L は
V (G), e  ( x, y)  E(G
f

) | dist G f (s, x)  1  dist G f (s, y)
2
フロー
(0)
2
5
(0)
(0)
4
(0)
(0)
3
4
1
(4)
3
4
3
5
(4)
残余ネットワーク
5
3
4
1
1
2
5
4
レベルグラフ
4
1
5
3
27
• 定義：ネットワークの s-t フロー f は，
V (G), e  E (G f ) | f (e)  u(e) が s-t パスを含まない
とき，ブロックフロー (blocking flow) と呼ぶ
s-t フローが存在 ⇒
左はブロックフローではない
残余ネットワーク
のレベルグラフ
3/5
2
1
4
3/3
1
3/4
2
3
5
3
4/5
2
1/1
4
3/4
3
1
4
3
1
5
3
s-t フローが存在しない ⇒
左はブロックフロー
3/3
1
2
1
1/3
5
1
2
4
1
2
1
3
5
28
Dinicのアルゴリズム
1. 全ての e  E(G) で f(e) = 0 とする
2. Gf のレベルグラフを作る
3. レベルグラフでのブロックフロー f’ を求める．
f’ = 0 ならば終了
4. f を f’ だけ増加させる．2. へ行く
注：f を増加させるときは，逆辺に対しては
f(e) := f(e)  f’(e) とする
29
初期フロー
2
(0)
残余ネットワーク
(0)
4
(0)
(0)
1
5
3
(0)
4
3
5
3
1
5
4
(0)
3
8
ブロックフロー
レベルグラフ
2
2
4
1
5
4
2
5
(0)
1
3
8
4
1
5
4/4
3
4/8
30
フロー
(0)
残余ネットワーク
(0)
2
(0)
4
1
3
3
5
3
4
3
4
(4)
5
4
ブロックフロー
レベルグラフ
5
4
1
5
(4)
2
5
(0)
(0)
1
1
2
4
3
3
1
4
3
4/5
5
2
1/1
4
3/3
1
3/4
1/3
5
3
31
フロー
(4)
残余ネットワーク
2
(1)
(3)
4
(1)
(0)
1
5
(4)
3
2
1
1
4
4
(7)
1
4
5
3
3
2
1
1
5
7
レベルグラフ
1
2
4
1
5
3
レベルグラフに s-t フローが存在しないので終了
フローの流量は 8
32
Dinicアルゴリズムの計算量
• 辺数最小の増加路の辺数はフェイズごとに厳密に
増加する．よってDinicアルゴリズムは高々 n1 回
のフェイズ後終了する．
• 各フェイズではブロックフローは O(mn) 時間で
求まる
– レベルグラフは幅優先探索で O(m) 時間
– レベルグラフ上で1つのs-tパスは O(n) 時間
– 1つのs-tパス上には少なくとも1つの飽和辺が存在する
それを削除してさらにs-tパスを探す．高々 m 回で終了
• 全体の計算量は O(mn2)
• 動的木というデータ構造を用いるとブロックフロー
33
は O(m log n) 時間．全体で O(mn log n) 時間．
プリフロープッシュ法
• フロー増加法では，各節点における流れ保存則を
常に保ちつつ，ソースからシンクへのフロー増加路
に沿ってフローを追加していく
• フロー増加路を求めるためにネットワーク全体を探
索する必要があり，遅い
• GoldbergとTarjanによって提案されたプリフロープ
ッシュ法では，流れ保存則を緩和した条件
(3.13)


x

x

0
i

V

{
s
,
t
}
 ij  ji
{ j |( i , j )E }
{ j |( j ,i )E }
を保ちつつ，最終的に制約条件を満たすフローを
34
構成するアルゴリズム
• 定義：プリフローとは，各枝 (i,j) E において容量
制約 0  xij  uij を満たし，さらに各節点 i V{s,t}
において条件 (3.13) を満たす x = (xij)
• プリフロー x に対して，節点 i V{s,t} における
流入超過量を e(i )   x ji   xij と表す
{ j |( j ,i )E }
{ j |( i , j )E }
• プリフローの定義より，全ての節点 i V{s,t} に
おいて e(i)  0
• e(i) > 0 である節点 i を活性節点と呼ぶ
• 活性節点を持たないプリフローはフローである
35
• シンク t から各節点 i V への「近さ」を表す指標と
して，距離ラベルを導入する．
• プリフロー x に対する残余ネットワーク Gx = (V,Ex)
に対し，d(t) = 0 および
(i,j)  Ex ならば d(i)  d(j) + 1
を満たす距離ラベル d は x に対して有効という
• 有効な距離ラベルが与えられた残余ネットワーク
において，d(i) = d(j) + 1 を満たす枝 (i,j) Ex を
残余ネットワーク
可能枝と呼ぶ
d(2)=1
d(4)=1
プリフロー
(5)
2
(1)
(3)
1
5
4
()
1
(5)
5
(3)
3
(1)
d(1)=2
1
2
3
1
3
4
5
3 d(3)=1
2
7
1
d(5)=0
1
5
36
• 命題：距離ラベルが有効のとき，残余ネットワーク
において各節点 i からシンク t への最短路の長さ
は d(i) 以上
• 証明： t については d(t) = 0 なので成り立つ
t からの距離が l の点全てで成り立っていると仮定
する．距離が l+1 の点 i から距離が l の点 j への
残余ネットワークの辺 (i,j)  Ex が存在する．
d(i)  d(j) + 1  (j から t への距離)+1
= (i から t への距離)
より，距離が l+1 の点でも成り立つ．
よって全ての点において成り立つ．
• ある点から t への路が存在するときは，その長さは
37
n1 以下
プリフロープッシュ法
(0) 初期プリフロー x として，各枝 (s,j)  E に対して
xsj = usj，それ以外の枝の流量を 0 とする．
初期距離ラベルとして，d(s) = n, それ以外の節点
i で d(i) = 0 とする．
(1) 活性節点 i  V を1つ選ぶ．なければ終了．
(2) 残余ネットワーク Gx = (V,Ex) において，節点 i に
対する可能枝 (i,j) Ex が存在すれば (3) へ．
存在しなければ (4) へ．
38
(3) 節点 i から j に  = min{e(i), uxij} だけ流れを押し
出す．つまり，
(i,j)  E のときは xij := xij + 
(j,i)  E のときは xij := xij  
ステップ (1) へ戻る．
(4) 節点 i の距離ラベルを

d (i) : min d ( j )  1 | (i, j )  E
x

と更新する．ステップ (1) へ戻る．
39
ネットワーク
2
5
5
4
(0)
(0)
3
8
残余ネットワーク
4
5
3
(0)
(1) 活性節点2を選ぶ
(4) d(2)=1 とする
d(4)=0
e(4)=0
d(2)=0
e(2)=5
(0)
(0)
1
(4)
3
5
3
初期プリフロー
(5)
4
1
[反復1]
2
1
1
2
5
4
3
5
3
1
d(1)=5
5
4
3
8
d(5)=0
d(3)=0
e(3)=4
40
[反復 2]
(1) 活性節点2を選ぶ
(2) 可能枝 (2,4) が存在するので (3) へ
(3)  = min{e(2), u24} = 1 より，x24 = 1
残余ネットワーク
プリフロー
(5)
2
(1)
(0)
4
(0)
(0)
1
3
(0)
1
2
5
5
(4)
d(4)=0
e(4)=1
d(2)=1
e(2)=4
4
3
5
3
1
d(1)=5
5
4
3
8
d(5)=0
d(3)=0
e(3)=4
41
[反復 3]
(1) 活性節点2を選ぶ
(2) 可能枝 (2,3) が存在するので (3) へ
(3)  = min{e(2), u23} = 3 より，x23 = 3
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(0)
(0)
1
3
(0)
1
2
5
5
(4)
d(4)=0
e(4)=1
d(2)=1
e(2)=1
4
3
5
3
1
d(1)=5
5
4
3
8
d(5)=0
d(3)=0
e(3)=7
42
[反復 4]
(1) 活性節点3を選ぶ
(2) 可能枝が存在しないので (4) へ
(4) d(3)=1 とする
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(0)
(0)
1
3
(0)
1
2
5
5
(4)
d(4)=0
e(4)=1
d(2)=1
e(2)=1
4
3
5
3
1
d(1)=5
5
4
3
8
d(5)=0
d(3)=1
e(3)=7
43
[反復 5]
(1) 活性節点3を選ぶ
(2) 可能枝 (3,5) が存在するので (3) へ
(3)  = min{e(3), u35} = 7 より，x35 = 7
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(0)
(0)
1
3
(7)
1
2
5
5
(4)
d(4)=0
e(4)=1
d(2)=1
e(2)=1
4
3
5
3
1
d(1)=5
4
3
1
5
7
d(5)=0
d(3)=1
e(3)=0
44
[反復 6]
(1) 活性節点4を選ぶ
(2) 可能枝が存在しないので (4) へ
(3) d(4)=1 とする
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(0)
(0)
1
3
(7)
1
2
5
5
(4)
d(4)=1
e(4)=1
d(2)=1
e(2)=1
4
3
5
3
1
d(1)=5
4
3
1
5
7
d(5)=0
d(3)=1
e(3)=0
45
[反復 7]
(1) 活性節点4を選ぶ
(2) 可能枝 (4,5) が存在するので (3) へ
(3)  = min{e(4), u45} = 1 より，x45 = 1
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(1)
(0)
1
3
(7)
1
2
5
5
(4)
d(4)=1
e(4)=0
d(2)=1
e(2)=1
5
3
1
d(1)=5
4
2
1
5
1
4
3
7
d(5)=0
d(3)=1
e(3)=0
46
[反復 8]
(1) 活性節点2を選ぶ
(2) 可能枝が存在しないので (4) へ
(4) d(2) = 6 とする
残余ネットワーク
プリフロー
(5)
2
(1)
(3)
4
(1)
(0)
1
3
(7)
1
2
5
5
(4)
d(4)=1
e(4)=0
d(2)=6
e(2)=1
5
3
1
d(1)=5
4
2
1
5
1
4
3
7
d(5)=0
d(3)=1
e(3)=0
47
[反復 9]
(1) 活性節点2を選ぶ
(2) 可能枝 (2,1) が存在するので (3) へ
(3)  = min{e(2), u21} = 1 より，x12 = 51=4
残余ネットワーク
プリフロー
(4)
2
(1)
(3)
4
(1)
(0)
1
3
(7)
1
2
5
5
(4)
d(4)=1
e(4)=0
d(2)=6
e(2)=0
5
3
1
d(1)=5
4
2
1
5
1
4
3
7
d(5)=0
d(3)=1
e(3)=0
48
[反復 10]
(1) 活性節点はないので終了
プリフローはフローになっていて，流量は 8
残余ネットワーク
フロー
(4)
2
(1)
(3)
4
(1)
(0)
1
3
(7)
1
d(1)=5
1
2
1
5
(4)
d(4)=1
e(4)=0
d(2)=6
e(2)=0
4
4
5
3
2
1
5
1
4
3
7
d(5)=0
d(3)=1
e(3)=0
49
アルゴリズムの正当性の証明
• ステップ (0) で与えた x はプリフローであり，d は
有効な距離ラベルである．
• ステップ (3) (プッシュ操作) が実行された時，節点 i
から j に  = min{e(i), uxij} だけ流れを押し出す．
このとき e(i)  0 であり，0  xij  uxij なのでプリフロ
ーの条件を満たす．
• 辺 (i,j) に対してプッシュ操作を行ったとき，残余ネ
ットワークの新しい辺になりうるのは (j,i) のみであ
る． (i,j) は可能枝であったので，d(i) = d(j) + 1．
つまり d(j) = d(i)  1 < d(i) + 1 となり有効な距離
50
ラベルとなる．
• ステップ (4) (距離ラベル更新操作) では

d (i) : min d ( j )  1 | (i, j )  E x

とするが，この操作のあとも距離ラベルの有効性
(i,j)  Ex ならば d(i)  d(j) + 1
も満たされている．
• 注： d(i) は単調増加
• 残余ネットワークにはソースからシンクへの路は
存在しない．よって活性節点がなくなったときは
プリフローはフローになっており，増加路もない
ため最大フローが求まっている．
51
プリフロープッシュ法の計算量
• 距離ラベル更新操作の回数
– 計算の途中に現れる任意の残余ネットワークにおいて
，どの活性節点からもソースへの路が存在する
– 距離ラベルの有効性より (i,j)  Ex ならば d(i)  d(j) + 1
d(s) = n より，全ての点の距離ラベルは 2n 以下．
– よって，アルゴリズム中での更新回数は 2n2 以下．
• プッシュ操作の回数は O(mn2)
• 全体の計算量は O(mn2)
• ステップ (1) で活性節点を選ぶときに，距離ラベル
が最大のものを選ぶようにすると，計算量は
52
On 2 m  になる．
最小費用流問題
• 複数のソースとシンクをもつネットワークにおいて，
流れ保存則と容量制約条件を満たすフローの中で
各枝の単位フロー辺りのコストの総和を最小にす
る問題
通過節点
10
ソース
供給量
1
2,10
3,5
15
4,7
2
8,15
0
3
コスト，容量
5,15
4
-25
シンク
需要量(負の値)
53
• 最小費用流問題は次の線形計画問題に定式化
できる
目的関数：  cij xij → 最小
( i , j )E
制約条件：
x
ij
{ j |( i , j )E }

ji
{ j |( j ,i )E }
0  xij  uij
•
•
•
•
x
 bi
(i V )
((i, j )  E )
xij はグラフの枝 (i,j) 上の流れの大きさ
uij は枝 (i,j) の容量
cij は枝 (i,j) の1単位の流れに対するコスト
bi は節点 i における供給量 (負ならば需要量)
 bi  0 を仮定
iV
54
目的関数：
制約条件：
3x12
x12
 x12
 4 x13
 x13
 x13
 2 x23
 8 x24
 x23
 x23
 x24
 x24
 5 x34
 x34
 x34
 最小

10

15

0
  25
0  x12  5, 0  x13  7, 0  x23  10,
0  x24  15, 0  x34  15
10
1
2,10
3,5
15
4,7
2
8,15
0
3
5,15
4
-25
55
負閉路除去法
• あるフロー x が与えられたとき，残余ネットワーク
Gx = (V, Ex) を次のように定義する
• 容量 uij，コスト cij を持つ枝 (i,j) を，
残余容量 uxij = uij  xij，コスト cxij = cij を持つ枝 (i,j)
残余容量 uxji = xij，コスト cxji = cij を持つ枝 (j,i)
で置き換える
• 容量が 0 になるときは枝は作らない
56
10
1
ネットワーク
2,10
3,5
15
あるフロー
1
(5)
(10)
(5)
2
(10)
4,7
2
8,15
0
3
5,15
4
-25
残余ネットワーク
3
(15)
4
1
-3,5
2
4,2
-4,5
-2,10
8,5
3
-5,15
4
-8,10
57
• 残余ネットワークにおいて，ある節点から出発して
枝の向きに沿って次々に節点を経由し，元の節点
に戻る有向閉路を考える
• 閉路のコストとは，その上の枝のコスト cxij の合計
• 有向閉路 1  3  2  1 のコストは
4 + (-2) + (-3) = -1
• 有向閉路 2  4  3  2 のコストは
残余ネットワーク
8+ (-5) + (-2) = 1
4,2
• コストが負であるものを
1 -4,5 3
負閉路と呼ぶ
-3,5
-5,15
2
-2,10
8,5
-8,10
4
58
• 残余ネットワークにおいて，負閉路が1つ見つかっ
たとする
• その閉路に沿ってフローを追加すれば，流れ保存
則を保ったままコストの総和を減少できる
• 例：負閉路1  3  2  1 に沿って  追加する
• コストの総和は
4·+(-2)·+(-3)· = - 増える ( 減少する)
残余ネットワーク
• 追加できるフローの最大値は
フロー
 max  min{ u , u , u }
x
13
x
32
x
21
(5+)
1
2
(5-)
2
(10-)
(10)
3
1
(15) -3,5
4
2
4,2
-4,5
-2,10
8,5
-8,10
3
-5,15
459
残余ネットワーク
フロー
1
(3)
2
(7)
(8)
(10)
1
3
(15)
4
3,2
-4,7
2,2
-3,3
-2,8
8,5
2
3
-5,15
4
-8,10
• フロー変更後のコストは  = 2 減る
• 残余ネットワークに負閉路が存在するなら，その
閉路に沿ってフローを追加することでコストを減少
できる
• 負閉路が1つもなければ，そのときのフローは
最小費用流問題の最適解
60
負閉路除去法
(0) 適当な初期フロー x を求める
(1) 残余ネットワーク Gx = (V, Ex) において負閉
路を
見つける．なければ終了．
(2) 負閉路に沿って可能な限りフローを追加す
る．
ステップ (1) に戻る
61
• 各枝のコストと容量が整数なら，1回の反復におい
て総コストは少なくとも1単位減少する
• C  max cij : (i, j )  E ,U  max uij : (i, j )  Eとすれば，
初期フローのコストは mCU 以下，
最適解のコストは mCU 以上
• 負閉路除去法は最大でも 2mCU 回の反復で終了
• これは多項式時間ではない
• ステップ (1) において平均コスト (閉路のコストを閉
路の枝数で割ったもの) 最小の閉路を選べば，
反復回数は O(nm2log n) になる
• 平均コスト最小の閉路は O(mn) 時間で見つかる
62
• アルゴリズム全体の計算量は O(n2m3log n)



Download Report