4. Matching 松山

4.0 マッチングとはグラフGで全ての に対して をみたすような枝集合 つまり、全ての点に接する赤線が一本か零本 ○ × 　　　○　　　　　　　　　　　　× また、全てのvで　　　　　　　　　　　のとき完全マッチングという この章では（完全）二部グラフでの最大重みを求める直接アルゴリズムを扱う

二部グラフでない一般的なグラフでのマッチングを求めるアルゴリズム 一般的なグラフでのマッチングの特徴ベクトルのconvex hullの不等式記述 その最小重みマッチングへの適用

4.1 Augmenting Paths and Matroids

Definitions S: Gのマッチング P: Gのpath or cycle PがSについてalternating(交互)とは Pの要素がpath, cycleにそってSの要素と の要素と交互になっていること 赤線: P 緑線: S ←PはSについてalternating

Definitions 頂点 がexposedとは 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の最大次数は２ 　どの接点vでも G.Cはいくつかのコンポーネントに分かれ、それら一つ一つがalternating pathもしくはcycleになっています |S’| > |S|なのでいくつかの部品はS’からの枝を多く含みます。それがaugmenting pathになります。 補足）F ⊆ E(G) に対し，グラフ G.F を，節点集合 V(G.F) := V(G), 　 　　 枝集合 E(G.F) := F のグラフとする S S’

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 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)に含まれない

Proof 条件I1, I2は明らか I3についてここで示す X∈I(M), Y∈I(M), |X| < |Y|を考える となる が存在 Proof 条件I1, I2は明らか I3についてここで示す X∈I(M), Y∈I(M), |X| < |Y|を考える Sx, SyをX, Yをカバーするマッチングとする Sxは　　　　の要素を全てカバーしないか一つ以上カバー ある点vをカバーすれば、 　→X+vはSxによってカバー 　→X+v∈I(M)となるv∈　　　　が存在

続き Sxは を一つもカバーしない（仮定）とする C := SxΔSyを考える Berge’s Theoremの証明の時のようにG.Cは部品としてalternating path, or cycleを持つ。 次数が２の頂点はXに含まれるときに限りYに含まれるという特徴を持つ（仮定より） ゆえにG.Cのalternating cycleに含まれるXの点の数は少なくともYの点の数以上|X in cycle| ≧ |Y in cycle| X∧￢Yは○ Y∧￢Xは×(SxはY∧￢Xを含まない) X∧Yは○ ￢X∧￢Yは○ Sx Sy ・・・

alternating pathの内部の点も同様の事がいえる 続き alternating pathの内部の点も同様の事がいえる 以上を踏まえると、|Y| > |X|より、いくつかのalternating pathで両端の点がYであるものの方が多いpathが存在 今まで数えてきた点のみカウントすると|x| ≧|y| Sx Δ Syで打ち消しあったところ(Sx and Sy)の点に関しては次数２の点と同じことが言える その他の点はpathの両端のみ マッチングSxを、そのパスに関するところ以外はそのまま、パスの部分に関してはSx→Syと変更すると、I3を満たすことができる 　（次ページで図解） ・・ ここ Sx∧Sy

両端の点のうち、X<Yであるpath ・・ ・・ Y ・・ ・・ Y 両端の点が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 e2 e3 e4 e5

Characterization マッチングの特徴ベクトルをpolytopeのextreme pointsとして定式化 (0, 0, ..., 0)も含む 全てのマッチングに対してベクトルを取ってpolytopeを構成 イメージ polytope matching

用語 M(G)：Gのマッチングの集合 PM(G)：conv(M(G)の特徴ベクトル集合)

Matching-Polytope Theorem Gのマッチング特徴ベクトルのconvex hullは以下の解集合で表される Xeとは、convex hull内のベクトルxの枝eに対する要素

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) (1, 0, 0) (0, 0, 0)

示すべき目的はPM(G)の「全てのfacetが(i),(ii),(iii)の不等式によって記述されること」 ・・・(*) 　　　　　　　　　　・・・(*) 上式をPM(G)のfacetを描く式とする。もしマッチングSが 　を満たすならばSは式(*)を「tightに満たす」という Image (*)の表す（n-1次元）平面 これらのマッチングは(*)をtight マッチングベクトルがfacet上 n次元多面体

場合分け 必ずこのPolytopeはfacetの組で表される 一つfacetを取ってきたときにその条件で場合分け Case 1 Case 2 facet (*)の係数α(e)があるeで負の時 Case 2 facet (*)を満たす全てのマッチングで必要な共通頂点がある時 Case 3 それ以外

Example 1 G M1 M2 polytope (0, 1) facet (1, 0) (1, 0) この場合、facetは-e1≦0, -e2≦0, e1+e2≦1 黒線のfacetはCase 1に相当 赤線はCase 2に相当（共通頂点は左下の点）

Case 1 : facet(*)の係数がいくつかのeで負の時 そのようなeにおいて、S – eは(*)を超えてしまう よって(*)を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の一意性, 0.4参照) ちなみに二つ以上負になることはない Sはmatchingより、S – eもmatching α(e) < 0より　(*)の値はS→S － eで増大 　Σ～(S)＝β → Σ～(S – e)＞β より、S – eがマッチングにもかかわらずpolytope から飛び出る S tight (*) S - e 有効であるとは、PM(G)に属する全ての点が 不等式を満たすということ

Case 2 : (*)をtightに満たす全てのマッチングで共通して必要な頂点を含むとき そのとき(*)にtightな全てのマッチングSに対して なぜなら、(*)をtightなマッチングベクトルで、↑でいうところの共通頂点に繋がる枝のベクトル成分を足したら1 x(S)は(ii)を等式として満たす PM(G)はfull dimensionalかつ、(ii)はPM(G)にとって有効であるので、(*)は(ii)の正の定数倍でなくてはならない（解集合が一致） e1 マッチングなので一本だけ赤 e2 x e1(s) = 0 x e2(s) = 0 x e3(s) = 0 x e4(s) = 1 x e5(s) = 0 真ん中の点が上記の共通頂点 e3 e4 e5

Case 3 : それ以外 1. 全てのe∈E(G)でα(e)≧0 2. 全てのv∈V(G)で、vがexposedである、(*)をtightに満たすマッチングが存在 G+を次のように定義 Case 3をいくつかのClaimを順に示しながら解析

Claim 1 : G+は連結している G+が空でなく、互いに連結しないG1, G2で出来ているとする、i = 1, 2で とするとそのとき、全てのeでα(e) = α1(e) + α2(e)がいえる i = 1, 2でSiを　　　　　　　　を最大にするマッチングとする βiをその最適値とする Si⊂E(Gi)と仮定すると　　　　　　　　 はPM(G)で有効(i = 1, 2) さらに、(*)は二つの不等式の和→有効な二つの不等式の和が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は境界線を飛び出すのでおかしい

ゆえに、u-v間の最短パスの間にはu, vと異なる頂点wが存在 v (exposed) ゆえに、u-v間の最短パスの間にはu, vと異なる頂点wが存在 exposedな点同士の中でu-vが距離最短であったので、wはexposedではない S’をwがexposedな(*)をtightなマッチングとする Case 3仮定2よりそのようなS’は存在 SΔS’を考えるとwを一つの端としたalternating path Qを含む（図参照） u (exposed) S u, vはSでexposed S→S’としてこの線を 増やすことが出来る tight (*) S + e w u ・・ ・・・ v

左と同様に考えてここにSΔS’取った時に alternating path SΔS’ ・・・ S S w ・・・ u v u v ・・・ S’ u ・・・ v 左と同様に考えてここにSΔS’取った時に alternating path SΔS’ ここに長さ1以上の alternating path w u

SΔQ, S’ΔQはマッチングより、facetの内側なので β= β= SとS’は(*)をtightなので、 より、 SΔQ, S’ΔQはマッチングより、facetの内側なので よって よってSΔQは(*)をtight しかし、SΔQはwをexposed 少なくともuかvが一つexposed 最初の、距離最小に矛盾

最低でもuとwがSΔQでは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は( 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+)としたとき、( 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)の解集合

4.3 Duality and a Maximum-Cardinality Matching Algorithm

Definitions グラフGのodd-set coverとは次の集合を指す odd-set Wのcapacityとは ここで、Wi, vjは以下の条件を満たすとする vj∈V(G), Wi⊂V(G) |Wi| ≧3, odd Gの枝は全て片端にvjを持つか、両端に同じWiに含まれる点を持つ odd-set Wのcapacityとは 片方だけvj どちらもWiに含まれる

Example W = {{v3, v4, v5}}; {v1, v2}とすると capacity = 2 + (3 - 1) / 2 = 3 v1 v2 v3 v4 v5

odd-set coverって何？ このodd-set coverの考えはPM(G)の不等式記述と線形計画の双対性に刺激されることで登場 Gの最大マッチングは不等式(i)~(iii)を満たす　　　　　　　の最大値を求める問題と一致 この線形計画 の双対問題は→

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 で、 はCとvertex-disjointとする Cを縮小して一つの点とみなして出来たグラフをG’とする S’ := がG’の最大マッチングとなる⇔SがGの最大マッチングになる A set of paths between two vertices is called vertex-disjoint if they share no vertices.

Example S S’ Shrink cycle S’が最大マッチング⇔Sが最大マッチング この場合は違う

Proof(→の対偶を証明) SがGの最大マッチングでないとする PをSに関するaugmenting pathとする もしPがどのCの頂点にもくっついていないならPはS’に関するaugmenting pathでもある augmenting path （両端がexposedな alternating path） cycle shrinking

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’の最大マッチングではない vertex disjoint なのでSではない 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のことである

Hのそれぞれの部品はちょうど一つのexposed な頂点(rootと呼ぶ)を持ち、exposedな頂点は全てHの部品のroot E(H) は森 Hのそれぞれの部品はちょうど一つのexposed な頂点(rootと呼ぶ)を持ち、exposedな頂点は全てHの部品のroot Hの頂点はrootからの距離に依存してodd もしくはevenと呼ばれ、それぞれのodd頂点の次数は2でどちらか片方の枝はSに含まれる 分かりにくいので次ページの図を参照 注. 次数とは、頂点に接続する枝の本数

Hにないマッチングの枝はHとは頂点を共有しない また、Hに現れない全ての頂点はcovered 赤色の枝はマッチングの枝 部品は一つの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を繰り返し可能な限り適用していく (Grow) もし枝eがe∈ でevenな端点x∈V(H)と、V(H)に含まれない端点yを持つとし、そのような枝が存在するならば、yはあるf∈ の端点.さらに、fのもう一つの端点zはV(H)にはない.Hを次のように再定義 E(H) ← E(H) + e + f V(H) ← V(H) + y + z

(Augment)もし、両方の端点がevenで、その端点同士はHの異なる部品であるような枝e∈ があれば、E(H) + eはそれぞれのrootからrootへeを含んだパスPができます. そのパスPはS’に対しaugmentingです. S’ΔPを新たなS’として、G’のマッチング濃度を上げます.繰り返しshrinkされたcycleをunshrinkします.もともとのグラフGをShrinking Lemmaを使い復元させ、マッチングSk+1を作ります.そしてStep 0に戻ります. (Shrink)もし、両方の端点がevenで、Hの同じ部品の中にその端点を持つような枝e∈ が存在する時、Pをeのどちらか一方の端点からrootへのパスとし、S’ΔPを新たなS’とする（S’の濃度は変わらない）.そして、E(H) + eにあるcycleをshrinkする.

(Optimality) もし、Step 1~3が適用できなくなったらSkはGの最大マッチング 例をみるとわかりやすい

Example 実際にアルゴリズムを適用 次のグラフを考える（マッチングは赤線） exposedな点は1, 11, 13, 14 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を作る 4 5 8 9 1 2 3 6 7 11 12 10 13 5, 7は連結してます 点線で表現 Growでalternating treeを作る 14

頂点5と7がevenかつ、同じ森部品の中で連結している ゆえにStep 3を適用 1, 2, 3, 4, 5の順のパスに属するマッチングを交換 14 4 5 8 9 11 1 2 3 10 12 6 7 (Shrink) Pをどちらか一方の端点からrootへのパスとし、 S’ΔPを新たなS’とする（S’の濃度は変わらない）. そして、E(H) + eにあるcycleをshrinkする. 13

3, 4, 5, 6, 7, 3のサイクルをshrinkします 14 8 9 11 3, 4, 5, 6, 7 1 2 10 12 13

またalternating forestを作ります 2 1 3, 4, 5, 6, 7 8 9 11 12 10 13 14

ゆえにStep 2を適用し、augmenting pathを得る((3, 4, 5, 6, 7), 10, 12, 11) (3, 4, 5, 6, 7)と10がevenで連結 またそれらは、森の中の異なる部品にある ゆえにStep 2を適用し、augmenting pathを得る((3, 4, 5, 6, 7), 10, 12, 11) augmentationを行う 14 8 9 11 3, 4, 5, 6, 7 1 2 10 12 (Augment) rootからrootへeを含んだパスPは S’に対しaugmentingなのでaugmentation. 繰り返しshrinkされたcycleをunshrink もともとのグラフGをShrinking Lemmaを使い 復元してStep 0に戻ります. 13

Shrinking Lemmaを適用し、unshrinkを行うと、もとより濃度の濃いマッチングが得られる 頂点10は4と6どっちにマッチングを持っていっても良い 結果、完全マッチングが得られる 14 4 5 8 9 11 1 2 3 10 12 6 7 13

またSeedを行い、Growで森を生成 Step 1~3のどれも適用できないのでStep 4に進み、 最大マッチングの濃度は6と分かる 2 1 13 8 9 14 Step 1~3のどれも適用できないのでStep 4に進み、 最大マッチングの濃度は6と分かる Odd-set coverのcapacityも6で、次のOdd-set coverが得られる

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なので Hの枝は全てOに触れている G‘[U]の全ての枝は両端がU-vに含まれており、vに接している 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より