chap4

4. Matching
松山
4.0
• マッチングとはグラフGで全ての v  V (G ) に対し
て  G (v)  S  1 をみたすような枝集合 S  E (G )
• つまり、全ての点に接する赤線が一本か零本
○
×
• また、全てのvで  (v)  S  1 のとき完全マッチン
G
グという
• この章では（完全）二部グラフでの最大重みを求める
直接アルゴリズムを扱う
• 二部グラフでない一般的なグラフでのマッチ
ングを求めるアルゴリズム
• 一般的なグラフでのマッチングの特徴ベクト
ルのconvex hullの不等式記述
• その最小重みマッチングへの適用
4.1 Augmenting Paths and
Matroids
Definitions
• S: Gのマッチング
• P: Gのpath or cycle
• PがSについてalternating(交互)とは
– Pの要素がpath, cycleにそってSの要素と E (G ) \ S の
要素と交互になっていること
赤線: P
緑線: S
←PはSについてalternating
Definitions
• 頂点 v  V (G ) がexposedとは  G (v)  S  0
• not exposed = covered
• alternating pathがaugmenting(増大)とはpathの
両端がSによってexposedであるということ
exposed
水色線: alternating path
両端（左上,左下）がexposedなので
このpathはaugmenting
covered
Berge’s Theorem
• SがGの最大マッチング ⇔ Sに対してGが
augmenting pathを持たない
• Proof（→, 対偶を示す）
–
–
–
–
PをSに対するaugmenting pathとする
S’ = SΔPとする
S’は|S’| > |S|となるGのマッチング
つまりSは最大マッチングではない
augmenting path
・・・
S
S’
• Proof（←, 対偶を示す）
– SがGの最大マッチングでないとする
– S’を|S’| > |S|となるGのマッチングとする
– C = S’ΔSとすると、G.Cの最大次数は２
補足）F ⊆ E(G) に対し，グラフ G.F を，節点集合 V(G.F) := V(G),
枝集合 E(G.F) := F のグラフとする
どの接点vでも
S
S’
– G.Cはいくつかのコンポーネントに分かれ、それら一つ一
つがalternating pathもしくはcycleになっています
– |S’| > |S|なのでいくつかの部品はS’からの枝を多く含み
ます。それがaugmenting pathになります。
G.C
alternating cycleなので
赤と緑の線の数は一緒
cycle
・・・
これが求めたいaugmenting pathになります
S
S’
G.C
Theorem (Matching Matroid)
• Gを任意のグラフとし、W⊂V(G)とする
• MをE(M) := Wで定義（グラフGのいくつかの
頂点集合）
• I(M) := {X⊂W : GはXをカバーするマッチン
グを持つ（あるマッチングにおいて全ての頂
点がcovered）}
→ I(M)はマトロイドになる
例
Graph G
v3
v1
v6
v2
v5
v4
W = {v1, v2, v3, v5, v6} とする
E(M) = W = {v1, v2, v3, v5, v6}
I(M) = {(v1), (v2), (v3), (v5), (v6), (v1, v2), (v1, v3),
....}
(v1, v3, v6)はI(M)に含まれない
I1.   I ( M )
I2. X  Y  I ( M )  X  I ( M )
I3. X , Y  I ( M ), Y  X
 X  e  I (M ) となる
e Y \ X が存在
• Proof
–
–
–
–
–
–
条件I1, I2は明らか
I3についてここで示す
X∈I(M), Y∈I(M), |X| < |Y|を考える
Sx, SyをX, Yをカバーするマッチングとする
SxはY \ X の要素を全てカバーしないか一つ以上カバー
ある点vをカバーすれば、
→X+vはSxによってカバー
→X+v∈I(M)となるv∈ Y \ X
が存在
• 続き
– SxはY \ X を一つもカバーしない（仮定）とする
– C := SxΔSyを考える
– Berge’s Theoremの証明の時のようにG.Cは部品として
alternating path, or cycleを持つ。
– 次数が２の頂点はXに含まれるときに限りYに含まれると
いう特徴を持つ（仮定より）
Sx
Sy
X∧￢Yは○
Y∧￢Xは×(SxはY∧￢Xを含まない)
X∧Yは○
￢X∧￢Yは○
– ゆえにG.Cのalternating cycleに含まれるXの点の数は
少なくともYの点の数以上|X in cycle| ≧ |Y in cycle|
・・・
• 続き
– alternating pathの内部の点も同様の事がいえる
・・
ここ
– 以上を踏まえると、|Y| > |X|より、いくつかの
alternating pathで両端の点がYであるものの方
が多いpathが存在
• 今まで数えてきた点のみカウントすると|x| ≧|y|
• Sx Δ Syで打ち消しあったところ(Sx and Sy)の点に関
しては次数２の点と同じことが言える
Sx∧Sy
• その他の点はpathの両端のみ
– マッチングSxを、そのパスに関するところ以外は
そのまま、パスの部分に関してはSx→Syと変更
すると、I3を満たすことができる
（次ページで図解）
両端の点のうち、X<Yであるpath
・・
・・
Y
Y\X
・・
・・
Y
Y\X
両端の点がYであるものの方が多いpath
であることをふまえるとこれはXではない
・・
そもそも両端の点がYであるものの方が多いpath
でない
4.2 The Matching Polytope
特徴ベクトル
• あるグラフGの枝の数がnであるとする
• それぞれの枝をe1~enとする
• グラフGにおいてS⊂E(G)をベクトルで表記
– x(S)とする
• x(S) = (xe1(S), xe2(S), ..., xen(S))
• xei(S) = 1(Sにeiがある) or 0（Sにeiがない）
e1
e3
e5
e2
e4
 xe1   1 
   
 xe 2   0 
 x    0
 e3   
 xe 4   0 
x   
 e5   1 
Characterization
• マッチングの特徴ベクトルをpolytopeのextreme
pointsとして定式化
– (0, 0, ..., 0)も含む
• 全てのマッチングに対してベクトルを取ってpolytope
を構成
イメージ
polytope
matching
用語
• M(G)：Gのマッチングの集合
• PM(G)：conv(M(G)の特徴ベクトル集合)
Matching-Polytope Theorem
• Gをループを含まないグラフとする
• Gのマッチング特徴ベクトルのconvex hullは以下の
解集合で表される
• Xeとは、convex hull内のベクトルxの枝eに対する
要素
(i )
(ii )
 xe  0,
e  E (G )
 1,
v  V (G )
x


e
(iii )
e
G (v)

eE ( G[W ])
xe 
W 1
2
,  W  V (G) with W  3 odd.
• Proof
– M(G)をGのマッチングの集合とする
– Gはループを含まないので全ての一本の枝の特徴ベクト
ルは空集合の特徴ベクトル（0, 0, ..., 0）とあわせて、
|E(G)|＋１個のaffinely independentな点集合を構成する
ループ
– つまりグラフGから枝を一本だけ取ってきたものはマッチ
ング
その集合はベクトルで表すと
(0, 0, ..., 0), (1, 0, ..., 0), ... , (0, 0, ..., 1)
– ゆえにpolytope PM(G)はfull dimensional(n次元空間にn
次元多面体があり、facetはn-1次元)
例) 3次元
G
e1
e1
e2
e2
これらは全てマッチング
e3
e3
e1
e1
マッチング特徴ベクトル(e1, e2, e3)
e2
e2
e3
他のマッチングもあるかもしれないけど、
今言いたいのは、
「少なくとも、三次元に三次元多面体がある」
e3
(0, 0, 1)
(0, 1, 0)
(0, 0, 0)
(1, 0, 0)
– 示すべき目的はPM(G)の「全てのfacetが(i),(ii),(iii)の不等
式によって記述されること」
 (e) xe   ・・・(*)

eE ( G )
– 上式をPM(G)のfacetを描く式とする。もしマッチングSが
  (e) x ( S )  
eE ( G )
e
を満たすならばSは式(*)を「tightに満たす」という
Image
(*)の表す（n-1次元）平面
これらのマッチングは(*)をtight
マッチングベクトルがfacet上
n次元多面体
場合分け
• 必ずこのPolytopeはfacetの組で表される
• 一つfacetを取ってきたときにその条件で場合
分け
• Case 1
– facet (*)の係数α(e)があるeで負の時
• Case 2
– facet (*)を満たす全てのマッチングで必要な共通
頂点がある時
• Case 3
– それ以外
Example 1
G
1
 
0
M1
e1
M2
e2
polytope
(0, 1)
facet
0
(1, 0)
この場合、facetは-e1≦0, -e2≦0, e1+e2≦1
黒線のfacetはCase 1に相当
赤線はCase 2に相当（共通頂点は左下の点）
0
 
1
facetの式
  (e) x
eE ( G )
e

• Case 1 : facet(*)の係数がいくつかのeで負の時
– そのようなeにおいて、S – eは(*)を超えてしまう
S
tight
(*)
S-e
Sはmatchingより、S – eもmatching
α(e) < 0より (*)の値はS→S － eで増大
Σ～(S)＝β → Σ～(S – e)＞β
より、S – eがマッチングにもかかわらずpolytope
から飛び出る
– よって(*)をtightに満たすマッチングSはどれもeを含まな
い
– ゆえに、(*)をtightに満たす全てのマッチングSでxe（S）= 0
（マッチングのe成分が０）
– つまりこのfacetはxe(S) = 0 で表される(α(e) < 0 なe)
– PM(G)はfull dimensionalであり、(i)はPM(G)にとって有効で
あるので、(*)は(i)の正の定数倍でなくてはならない(facet
有効であるとは、PM(G)に属する全ての点が
の一意性, 0.4参照) 不等式を満たすということ
– ちなみに二つ以上負になることはない
• Case 2 : (*)をtightに満たす全てのマッチングで共通
して必要な頂点を含むとき
– そのとき(*)にtightな全てのマッチングSに対して
x (S )  1


e
e
G (v)
– なぜなら、(*)をtightなマッチングベクトルで、↑でいうところ
の共通頂点に繋がる枝のベクトル成分を足したら1
e1
e2
e3
e4
e5
x e1(s) = 0
x e2(s) = 0
x e3(s) = 0
x e4(s) = 1
x e5(s) = 0
マッチングなので一本だけ赤
真ん中の点が上記の共通頂点
– x(S)は(ii)を等式として満たす
– PM(G)はfull dimensionalかつ、(ii)はPM(G)にとって有効で
あるので、(*)は(ii)の正の定数倍でなくてはならない（解集
合が一致）
• Case 3 : それ以外
1. 全てのe∈E(G)でα(e)≧0
2. 全てのv∈V(G)で、vがexposedである、(*)をtightに満た
すマッチングが存在
– G+を次のように定義
E (G ) : {e  E (G) :  (e)  0}
V (G ) : {v V (G) : v is an endpoint of some e  E (G )}
– Case 3をいくつかのClaimを順に示しながら解析
• Claim 1 : G+は連結している
– G+が空でなく、互いに連結しないG1, G2で出来ているとす
る、i = 1, 2で
if e  E (Gi )
 (e)
i
 (e) : 
0 if e  E (G) \ E (Gi )
–
–
–
–
とするとそのとき、全てのeでα(e) = α1(e) + α2(e)がいえる
i = 1, 2でSiを
を最大にするマッチングとする
i
i
 (e) xe ( S )

i
β をその最適値とする
eE ( G )
Si⊂E(Gi)と仮定すると
はP
M(G)で有効(i = 1,
i
i
 (e) xe  

2)
eE ( G )
– さらに、(*)は二つの不等式の和→有効な二つの不等式の
和がfacetになるのはありえない、仮定に矛盾
– よって、G+は連結
• Claim 2 : Sが(*)をtightに満たすとする時、S
は最高でもV(G+)でexposedな点は一つ
– (*)をtightに満たすSの中で二つ以上exposedな
ものがあるとします
– 二つ以上exposedな点のある全てのマッチングと
そのexposedな点の間で、距離が最小(G+におい
て)な頂点u, vを取ってきます
– まず、u-v間は距離１ではない（次ページ図参照）
•
•
•
•
•
1であるとして、その枝をeとする
Sは(*)をtight つまり境界線上(Σ～ = β)
S+eはα(e) > 0よりΣ～＞β となる
S+eはマッチング
上二つよりS+eは境界線を飛び出すのでおかしい
v (exposed)
S
u (exposed)
u, vはSでexposed
S→S’としてこの線を
増やすことが出来る
tight
(*)
S+e
– ゆえに、u-v間の最短パスの間にはu, vと異なる
w
u
v
頂点wが存在
・・
・・・
– exposedな点同士の中でu-vが距離最短であっ
たので、wはexposedではない
– S’をwがexposedな(*)をtightなマッチングとする
• Case 3仮定2よりそのようなS’は存在
– SΔS’を考えるとwを一つの端としたalternating
path Qを含む（図参照）
・・・
S
S
w
・・・
u
v
u
v
・・・
S’
u
・・・
v
SΔS’
w
u
左と同様に考えてここにSΔS’取った時に
alternating path
ここに長さ1以上の
alternating path
β=
β=
• SとS’は(*)をtightなので、  (e) x   (e) x  2
SQ  ( S \ Q)  ( S 'Q), S ' Q  ( S '\Q)  ( S  Q)
• より、   (e)    (e)  2
eS
eSQ
e
eS '
e
eS 'Q
• SΔQ, S’ΔQはマッチングより、facetの内側なので
  ( e)   ,   (e )  
eSQ
eS 'Q
 ( e)  
• よって e
SQ
• よってSΔQは(*)をtight
• しかし、SΔQはwをexposed 少なくともuかvが一つ
exposed
• 最初の、距離最小に矛盾
・・・
S
S
w
w
・・・
u
v
u
v
・・・
Q
Q
w
w
・・・
u
v
u
v
・・・
最低でもuとwがSΔQではexposed
• Claim 3 全てのv∈V(G+)で、G+からvを除いた
グラフには完全マッチングが存在
– Case 3の仮定2より(*)をtightなマッチングのうちv
がexposedなマッチングが(どのvでも)存在する
– そのようなマッチングSをS⊂E(G+)になるように選
ぶ(E(G+)にない枝を削ることにより)
S
v
S
G+
v
v
– Claim 2よりSには、vのそばにexposedなG+の頂
点は存在しない(元のSは(*)をtightだが、枝を
削ったため、Sがtightかどうかはわからない。しか
し少なくともG+の範囲ではClaim 2を満たす。ここ
で、Sはvをexposed→G+の範囲内でexposedな
頂点はもう存在しない)
– ゆえにSは完全マッチングをG+からvを消すことで
得ることが出来る（G+の範囲ではvのみが
exposedなので）
• Claim 4 W := V(G+)としたとき、(*)をtightする
全てのマッチングはG[W]の枝をちょうど(|W|
- 1) / 2本含む
– Sを(*)をtightするマッチングとする
– Claim 3のようにして、SはE(G[W])に含まれると
仮定できる
– Claim 2より、Sは最高でもWの要素を一つまでし
かexposedしない
– SはG[W]に少なくとも(|W| － 1) / 2本の枝を持つ
– Claim 3より、|W|は奇数
– よって|S| ≦ (|W| - 1) / 2
– よって|S| = (|W| - 1) / 2
まとめると
• Claim 1 G+は連結
• Claim 2 Sが(*)をtightなら、exposedな点は
一つまで
• Claim 3 全てのv∈V(G+)で、G+からvを除いた
グラフには完全マッチングが存在
• Claim 4 W:= V(G+)とするとき、(*)を満たす全
てのマッチングはちょうど(|W| - 1)/2本の
G[W]の枝を持つ
結論
• x(S)は(iii)を等式として満足
• PM(G)はfull dimensionalかつ(iii)はPM(G)に
とって有効であるので、(*)は(iii)の定数倍
• 全てのfacetは(i), (ii), (iii)の等号成立時のど
れかの定数倍
• よってconvex hullは(i), (ii), (iii)の解集合
(iii )

eE ( G[W ])
xe 
W 1
2
,
 W  V (G) with W  3 odd .
4.3 Duality and a MaximumCardinality Matching Algorithm
Definitions
• グラフGのodd-set coverとは次の集合を指す
W  ({W1 ,W2 ,,Wk };{v1 , v2 ,, vr })
–
–
–
–
ここで、Wi, vjは以下の条件を満たすとする
vj∈V(G), Wi⊂V(G)
|Wi| ≧3, odd
Gの枝は全て片端にvjを持つか、両端に同じWiに含まれる
点を持つ
片方だけvj
• odd-set Wのcapacityとは
k
Wi  1
i 1
2
r
どちらもWiに含まれる
Example
v1
v2
v3
v4
v5
W = {{v3, v4, v5}}; {v1, v2}とすると
capacity = 2 + (3 - 1) / 2 = 3
odd-set coverって何？
• このodd-set coverの考えはPM(G)の不等式記述と
線形計画の双対性に刺激されることで登場
• Gの最大マッチングは不等式(i)~(iii)を満たす eE (G ) xe
の最大値を求める問題と一致
W 1
• この線形計画
min  yv  
W
2
vV ( G )
W V ( G ) :
の双対問題は→
W 3, odd
subject to :
yv1  yv 2 

W
W V ( G ) : e W
W 3, odd
 1,  e  {v1 , v2 }  E (G );
yv  0,  v  V (G );
 W  0,  W  V (G ) : W  3, odd.
odd-set coverって何？
• odd-set coverの特徴ベクトルはこの双対線
形計画の実行可能解
• また、問題の解の目的値(最小にしたい式)は
そのcoverのcapacity
• ゆえにodd-set coverのcapacityの下限は
マッチング濃度の上限
• 実際、次の結果が論証される
Matching Duality Theorem
• ループを含まないグラフGの最大マッチング
はGのodd-set coverの最小capacityと同じ
• 証明はEdmonds’s Maximum-Cardinality
Matching Algorithm(後述)より従う
• Edomondsのアルゴリズムは次の結果
(Shrinking Lemma)に基づく
Shrinking Lemma
•
•
•
•
Gを無向グラフ、SをGのマッチングとする
Cを|C| = 2m + 1(mは正の整数)のサイクルとする
|S∩C| = m で、 S \ C はCとvertex-disjointとする
Cを縮小して一つの点とみなして出来たグラフをG’と
する
• S’ := S \ C がG’の最大マッチングとなる⇔SがGの最
大マッチングになる
A set of paths between two vertices is called vertex-disjoint
if they share no vertices.
Example
S’
S
cycle
Shrink
S’が最大マッチング⇔Sが最大マッチング
この場合は違う
• Proof(→の対偶を証明)
– SがGの最大マッチングでないとする
– PをSに関するaugmenting pathとする
– もしPがどのCの頂点にもくっついていないならP
はS’に関するaugmenting pathでもある
cycle
shrinking
augmenting path
（両端がexposedな
alternating path）
– PがCとvertex-disjointでないとすると、少なくとも
Pの一つの端点（vとする）がC上にはない
– Cからうまく頂点rを選ぶとv-r間がaugmenting
path
– wをvからたどって最初にCにぶつかる点とする
– subpath P’(vからwまでのパス)はS’(shrink済の
マッチング)に関してaugmenting
– このようにS’はG’の最大マッチングではない
S
vertex disjoint
なのでSではない
exposed
exposed
cycle
• Proof(←の対偶を示す)
– 逆に、S’がG’の最大マッチングでないとする
– T’をG’のマッチングとして、|T’| > |S’|とする
– Cを元に戻してGを復元
– そのとき、T’はGのマッチング（最高でもCの点は
一つしか含まないような）
– Cについている2m本の枝のうちm本（一つ飛ばし
で）をマッチングに追加（後の図で説明）
– |T| = |T’| + m > |S’| + m = |S|より、SはGの最大
マッチングでない
– 証明終
例に挙げると（オレンジ線はT（Sではない）です）
cycle
マッチングの順番が
違うことに注意
cycle
alternating forest
• augmenting pathを見つけるため、
alternating forestという考え方を使う
• サイクルがなければ探索で見つければよい
• GのマッチングSに関するalternating forestと
は、以下のようなsubgraph Hのことである
1. E(H) は森
2. Hのそれぞれの部品はちょうど一つの
exposed な頂点(rootと呼ぶ)を持ち、
exposedな頂点は全てHの部品のroot
3. Hの頂点はrootからの距離に依存してodd
もしくはevenと呼ばれ、それぞれのodd頂
点の次数は2でどちらか片方の枝はSに含
まれる
注. 次数とは、頂点に接続する枝の本数
•
分かりにくいので次ページの図を参照
•
•
•
•
次の図はHの部品の例
赤色の枝はマッチングの枝
部品は一つのrootから成る
Hにないマッチングの枝はHとは頂点を共有
しない
• また、Hに現れない全ての頂点はcovered
Even
Odd
Edmonds’s Maximum-Cardinality
Matching Algorithm
• SkをGの濃度kのマッチングとする(k=0でもよい)
0. (Seed) 森Hに種を撒く.グラフ内のexposedな頂点
を全てとってきてrootとする．G→G’, Sk→S’とする．
次にStep1~3を繰り返し可能な限り適用していく
1. (Grow) もし枝eがe∈ E (G ' ) \ E ( H )でevenな端点
x∈V(H)と、V(H)に含まれない端点yを持つとし、そ
のような枝が存在するならば、yはあるf∈ S ' \ E ( H )
の端点.さらに、fのもう一つの端点zはV(H)にはな
い.Hを次のように再定義
E(H) ← E(H) + e + f
V(H) ← V(H) + y + z
2. (Augment)もし、両方の端点がevenで、その端点
同士はHの異なる部品であるような枝e∈ E (G ' ) \ が
E(H )
あれば、E(H) + eはそれぞれのrootからrootへeを
含んだパスPができます. そのパスPはS’に対し
augmentingです. S’ΔPを新たなS’として、G’のマッ
チング濃度を上げます.繰り返しshrinkされたcycle
をunshrinkします.もともとのグラフGをShrinking
Lemmaを使い復元させ、マッチングSk+1を作ります.
そしてStep 0に戻ります.
3. (Shrink)もし、両方の端点がevenで、Hの同じ部品
)
の中にその端点を持つような枝e∈ E (G ' ) \ E ( Hが存
在する時、Pをeのどちらか一方の端点からrootへ
のパスとし、S’ΔPを新たなS’とする（S’の濃度は変
わらない）.そして、E(H) + eにあるcycleをshrinkす
る.
4. (Optimality) もし、Step 1~3が適用できなく
なったらSkはGの最大マッチング
•
例をみるとわかりやすい
Example
実際にアルゴリズムを適用
次のグラフを考える（マッチングは赤線）
14
4
5
8
9
11
1
2
3
10
12
6
7
exposedな点は1, 11, 13, 14
13
• まずはStep 0で、種まきをします
1
11
13
14
• まずはStep 1を繰り返し適用し、alternating
forestを作る
1
11
13
2
12
4
5
6
7
8
9
3
10
5, 7は連結してます
点線で表現
Growでalternating treeを作る
14
• 頂点5と7がevenかつ、同じ森部品の中で連
結している
• ゆえにStep 3を適用
• 1, 2, 3, 4, 5の順のパスに属するマッチングを
交換
14
4
5
8
11
1
2
3
10
12
6
(Shrink) Pをどちらか一方の端点からrootへのパスとし、
S’ΔPを新たなS’とする（S’の濃度は変わらない）.
そして、E(H) + eにあるcycleをshrinkする.
7
13
9
• 3, 4, 5, 6, 7, 3のサイクルをshrinkします
14
8
11
1
2
3, 4, 5, 6, 7
10
12
13
9
• またalternating forestを作ります
2
1
8
9
12
10
3, 4, 5, 6, 7
11
13
14
• (3, 4, 5, 6, 7)と10がevenで連結
• またそれらは、森の中の異なる部品にある
• ゆえにStep 2を適用し、augmenting pathを
得る((3, 4, 5, 6, 7), 10, 12, 11)
• augmentationを行う
14
8
9
11
1
2
3, 4, 5, 6, 7
10
12
13
(Augment) rootからrootへeを含んだパスPは
S’に対しaugmentingなのでaugmentation.
繰り返しshrinkされたcycleをunshrink
もともとのグラフGをShrinking Lemmaを使い
復元してStep 0に戻ります.
• Shrinking Lemmaを適用し、unshrinkを行う
と、もとより濃度の濃いマッチングが得られる
• 頂点10は4と6どっちにマッチングを持って
いっても良い
• 結果、完全マッチングが得られる
14
4
5
8
11
1
2
3
10
12
6
7
13
9
• またSeedを行い、Growで森を生成
2
1
8
9
13
14
Step 1~3のどれも適用できないのでStep 4に進み、
最大マッチングの濃度は6と分かる
Odd-set coverのcapacityも6で、次のOdd-set coverが得られる
W : ({{4, 5, 6, 7, 10, 11, 12}}; {2, 3, 8}) .
Fitness and efficiency of Edmonds’s
Cardinality Matching Algorithm
• EdmondのアルゴリズムはO(|V(G)|4)で終わる
• Proof
– まず、augmentation(増大)の回数は最高でも|V(G)|
/ 2回（マッチングなので）
– grow stepの回数は最高でも|V(G)| / 2回（森がいく
つ枝を持てるのかを考えよう！）
– shrink stepの回数は最高でも|V(G)| / 2回（shrinkし
たときの頂点の消える個数を考えよう！最小の
cycleの大きさは3）
– (grow + shrink) * augmentがステップ数
– ゆえに、このStep 1~3の繰り返し時間はO|V(G)|2
– とても単純なデータ構造を用いて、それぞれのStep
をO|V(G)|2時間で簡単に実行可能(詳細略)
– よって、計O(|V(G)|4)で実行可能
Lemma (Maximum-cardinality
matching in a shrunken graph)
• Edmondのアルゴリズムの結論として、S’
（matching of shrunken graph）はG’
（shrunken graph）の最大マッチング
• Proof
–
–
–
–
–
–
–
–
–
–
–
HをG’にアルゴリズムを適用後の森とする
EをHのevenな頂点集合とする
OをHのoddな頂点集合とする
UをHにはないG’の頂点集合とする
Hのroot以外の頂点は全てcoveredである
さらに、全てのrootでない頂点はS‘ ∩ E(H)の要素に使わ
れている
ゆえに、HとUの間にはもうマッチングの数を増やす余地は
ない（アルゴリズムが終わっているのでStep 2を適用でき
ない）
しかしながら、全てのUの要素はS’によりcovered
ゆえにS‘ ∩ E(G'[U])はG’[U]の完全マッチング
そして、|S‘ ∩ E(G'[U])| = |U| / 2
さらにHのalternating structure により、|S’ ∩ E(H)| = |O|
– もし、|U| > 2ならばv ∈ Uを選び、W := ({U - v}; O + v)
– WはG’のodd-set coverなので
1. Hの枝は全てOに触れている
2. G‘[U]の全ての枝は両端がU-vに含まれており、vに接して
いる
3. E(H) ∪ E(G'[U])にない唯一の枝は一つの端点Oに持つ。
(なぜなら、そうでなければgrow, shrink, augmentができ
るので)
– もし代わりに、|U| = 2とすると、odd-set coverはW :=
(Φ ; O + v)
– U = Φ ならW := (Φ ; O)
– どの場合もWのcapacityと濃度がどちらも|O|+|U|/2であ
ることは簡単にチェックできる。
Theorem (Correctness of Edmond’s
Cardinality Matching Algorithm)
• Edmondのアルゴリズムの結論として、Skは
Gの最大マッチング
• 前述のLemmaとShrinking Lemmaより

Download Report