第4章　Matching(後半) 情報学研究科 湯浅研究室M1 藤川浩光

4.4 Kuhn’s Algorithm for the Assignment Problem 頂点が V1(G) と V2(G) で分かれており、どちらの頂点数も n である(下の図は n=3 の場合) c を E(G) の重み関数とする もっとも重みが大きくなるようなマッチングを探す V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem 割り当て問題を解くために線形計画法の双対定理を使う

4.4 Kuhn’s Algorithm for the Assignment Problem 割り当て問題を以下のような式に変形する c はコスト関数 xe は枝 e を選ぶかどうか 変数 xe は整数だが特に制限しない 双対定理の形にはめるため 答えは必ず整数になる

4.4 Kuhn’s Algorithm for the Assignment Problem 主問題より双対問題を導く 全ての　　　　　　の組み合わせに対し以下のような変形重み関数　　を定義する 双対定理より y が実行可能解であることは　　が非正である事と等しい

4.4 Kuhn’s Algorithm for the Assignment Problem Example V1(G) := {1,2,3,4}, V2(G) := {a,b,c,d} 辺の重み関数 c の行列 1 a 2 b 3 c 4 d V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example (y1, y2, y3, y4) = (15, 18,17, 18) (ya, yb, yc, yd) = (0, 0, 0, -2) 変形重み関数　　の行列 1 a 2 b 3 c 4 d V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem マッチングFの重みが　　に関して最大であるならば c に関しても最大であり、逆も言える よって　 を最大にするようなマッチングを考えればよい 　　は非正なのでできるだけ 0 に近い方がよい

4.4 Kuhn’s Algorithm for the Assignment Problem ここで紹介するアルゴリズムは常に双対実行可能解を持つ この解は十分に最適である 最適解がいくつかあるかもしれないが、そのうちの一つになる 同等部分グラフ(equality subgraph) G= を定義する V(G=) := V(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example 変形重み行列の0の枝のみ 　　残したグラフになる G= 1 a 2 b 3 c 4 d V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem y が双対実行可能解であり、Fが任意の辺の集合とすると　　　　　　であることは明白 y が双対実行可能解ならば、G=の任意の完全マッチングはGの最大重み完全マッチングである よってG= の最大マッチング F を探す

4.4 Kuhn’s Algorithm for the Assignment Problem Example 例の場合は右の実線が 　　最大マッチング F G= 1 a 2 b 3 c 4 d V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem F が完全マッチングでなければ F に入らなかった頂点集合のうち、V1 (G)に入っているものを起点とした最大の alternating forest を H とする

4.4 Kuhn’s Algorithm for the Assignment Problem Example この場合起点は4のみ G= 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) H

4.4 Kuhn’s Algorithm for the Assignment Problem Example 起点からたどれるものを全て H とする G= H 1 a 1 a 2 b 2 b H 3 c 3 c 4 d 4 d V1(G) V2(G) H

4.4 Kuhn’s Algorithm for the Assignment Problem 次に以下を定義をする △は必ず 0 より大きいことに注意する そうでなければ H はまだ拡張できる

4.4 Kuhn’s Algorithm for the Assignment Problem Example H 1 a 1 a 2 w b 2 b v w H 3 c 3 c 4 d w 4 d v H

4.4 Kuhn’s Algorithm for the Assignment Problem 最後に双対解を更新する 再び G= を作るところからスタートし、アルゴリズムが停止するまで繰り返す

4.4 Kuhn’s Algorithm for the Assignment Problem Example △の更新により変形重み関数の行列が変わる 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example △の更新により変形重み関数の行列が変わる 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem 次のことがらは必ず満たされる ある枝の変形重みが非負ならば y を更新した後も非負 変形重みの更新は以下のとおり 　　　　　　　　　　　　　　　　　　　　　　　　　　　のような枝は△だけ減少する しかし△の選び方より、前の変形重みが非負ならば、更新後も非負である

4.4 Kuhn’s Algorithm for the Assignment Problem 次の条件も満たされる アルゴリズムはあるステップ数で必ず停止する マッチングの増加の回数は n (= V(G1) = V(G2)) 1から出る枝のマッチングが決まる、2から出る枝のマッチングが決まる…… n から出る枝のマッチングが決まる マッチングを1つ増やすのに alternating forest H を成長させる回数は最大で n よって y は最大 n^2 回変化する

4.4 Kuhn’s Algorithm for the Assignment Problem なぜマッチングを1つ増やすのに alternating forest H を成長させる回数は最大で n なのか？

4.4 Kuhn’s Algorithm for the Assignment Problem Example 最小コストマッチングは左図なのに、3つ目のマッチングまでで右図のようになってしまった場合 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example 1 a 1 a 2 b 2 b 3 c 3 c 4 H d 4 d V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d H V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d H V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example 1 a 1 a 2 b 2 b 3 c 3 c 4 d 4 d H V1(G) V2(G) V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem Example y を更新しても、前の H の枝は全て G= に残る 更新して新しく G= に入った全ての枝は F に適用される 1 a 2 b 3 c 4 d V1(G) V2(G)

4.4 Kuhn’s Algorithm for the Assignment Problem 1回の双対解の更新にかかる通常の計算機の計算量は O(n^2) よって全ての計算量は O(n^4)

4.4 Kuhn’s Algorithm for the Assignment Problem また、Hの要素は V1(G) のものが V2(G) のものより1つ多い よって これより　　　　　が1ステップごとに減少することがわかる 1回ごとに これはアルゴリズムが停止するという簡単な証明にもなっている

4.5 Application of Weighted Matching グラフの最適重みマッチングを見つけるアルゴリズムの応用について議論する シンプルな応用のひとつに最小重み偶数経路を探すものがある ただしグラフは無向グラフで、枝の重みは非負であるとする

4.5 Application of Weighted Matching 最小重み偶数経路問題 グラフ G を無向グラフで枝の重みが非負であるとする v、w を G の頂点のペアとする 目的は v から w までの経路のうち、枝の数が偶数で重みが最小のものを探すこと

4.5 Application of Weighted Matching 最小重み偶数経路問題 H := G[V(G) – v] H’ は G[V(G) – w] のコピーであり V(H’) :={u’ : u∈V(G) - w} M は V(H) - w の要素 u と コピーのV(H’) – v の要素u’ との枝の集合 新しいグラフ G’ を構成する G’の枝 E(H)∪E(H’) の重みはGのものと同じ G’の枝 M の重みは0

4.5 Application of Weighted Matching v v H’ G H w G’

4.5 Application of Weighted Matching Q1)　 G’の最小重み完全マッチングが分かると、v-w 経路の中から枝の数が偶数であるようなもののうち、重みが最小である経路を見つけることが出来ることを証明せよ Q2)　G の重みが負の場合どのような不都合が生じるか？

4.5 Application of Weighted Matching v H’ H u1’ u1 u2’ u2 u3’ u3 u4’ u4 u5’ u5 w

4.5 Application of Weighted Matching v H’ H u2’ u2 u3’ u3 u5’ u5 w

4.5 Application of Weighted Matching v H’ H u2 u3 u5 w

4.5 Application of Weighted Matching v H’ H u2 u3 u5 w

4.5 Application of Weighted Matching さらに重みつきマッチングを応用する グラフ G において T を V(G) の部分集合とし、F をE(G) の部分集合とする |T| は偶数とする F が以下の条件を満たす時、F を G の T-join と呼ぶ 右図を G とし v1、v2 を T とすると 　 G の T-join は{{v1, v2}} 　 または {{v1, v2}, {v2, v3}, {v2, v4}, {v3, v4}} v1 v3 v2 v4

4.5 Application of Weighted Matching 節点-枝変換行列をA(G)、 F ⊂ E(G) の特徴ベクトルを ｘ(F)、集合 T ⊂ V(G)の特徴ベクトルを x(T) とする |T| は偶数とする F が T-join であることは GF(2) における A(G)x(F)=x(T) であることの必要十分条件である GF(2) は元の数が2つなので1足す1を0とする

4.5 Application of Weighted Matching 以下のような F の場合は A(G)x(F)=x(T) を満たし、この F はG の T-join である v1 v3 v2 v4

4.5 Application of Weighted Matching T-join が最小とはその集合の中にそれより小さな　 T-join が含まれていないということとする 全ての最小 T-join は forest である forest でない T-join からサイクルを繰り返し削除できる 下の例では{{v1, v2}, {v2, v3}, {v2, v4}, {v3, v4}}からサイクルを削除した{{v1, v2}}が T-join v1 v3 v2 v4

4.5 Application of Weighted Matching この書では最小 T-join に注目する 枝には正の重みがついているならば、最小重み T-join は最小 T-join になる 非負の重みがついているならば、最小重み T-join は「最小 T-join」と「重みが0の枝で構成された 0-join」との枝を共有しない集合 「重みが0の枝で構成された 0-join」とは重みが0の枝のみで出来たサイクル

4.5 Application of Weighted Matching |V(G)|/2 の要素を持つ V(G)-join は G の完全マッチングの集合 V(G)-join はV(G)の全ての頂点から奇数の枝が伸びている 枝の数が |V(G)|/2 ならばすべての頂点は1本ずつ枝を持つ よって V(G)-joinは Gの完全マッチング

4.5 Application of Weighted Matching 大きな正の定数の重みをそれぞれの枝に加えると　新しい重みについての最小重み V(G)-join はもとの重みについての最小重み完全マッチング もし重みが0以下の枝があれば最小重み V(G)-join の頂点のうちひとつの頂点から複数本の枝が出る可能性がある 大きな正の定数を加えて上げ底をすることで、ひとつの頂点から出る枝の数を1本にして、完全マッチングを作ることが出来る これらのように T-join は完全マッチングに一般化される

4.5 Application of Weighted Matching 無効グラフの最小重み経路 v-w を探す問題を考える d を E(G) の重み関数とする もし d が非負ならば G の枝を有効グラフ Hの別の向きの枝のペアに置き換えることが出来る 新しい枝を e’、e’’とする 重み関数を c とし 　　c(e’) := c(e’’) := d(e)とする c に関して最小重み経路 v-w を 　 H から探す問題を考えればよい i i e’ e e’’ j j

4.5 Application of Weighted Matching T := {v, w} とすると最小 T-join の枝集合は G の(無向の) {v, w} の経路の枝集合 Gが負の重みの枝のサイクルを含んでいないならば　G の最小重み T-joinは v-w 経路と重みが0の枝で構成された 0-joinとの枝を共有しない枝集合 よって最小重み T-join を見つける効果的なアルゴリズムは無向グラフの最小重み v-w 経路を見つける効果的なアルゴリズム

4.5 Application of Weighted Matching 二つの補題を使って、最小重み T-join を探す問題は、非負の重みの場合のみを考えればよいことを示す

4.5 Application of Weighted Matching 補題[T-joinの排他的論理和] F’を G の T’-join とし、F⊂E(G) 、T⊂V(G) とする F が G のT-join であることはFΔF’がGのTΔT’-joinであることの必要十分条件である

4.5 Application of Weighted Matching 証明 F’が T’-join ということは A(G)x(F’)=x(T’) であると言うことと同等であった FとFΔF’も同じ FΔF’がGのTΔT’-joinであるとする x(FΔF’) = x(F) + x（F’）、 x(TΔT’) = x(T) + x（T’）なのでA(G)x(FΔF’) = x(TΔT’) ということは 　　A(G)x(F)+ A(G)x(F’) = x(T) + x(T’) ということと同等　　よって A(G)x(F) = x(T) なので F は G の T-joinである 　　逆も同様にして証明できる

4.5 Application of Weighted Matching 補題[T-joinの目的関数のシフト] F’をGのT’-join とし c を E(G) の重み関数とする E(G) の新しい重み関数を d とし全ての F⊂E(G)に対して d(F) := c(FΔF’) – c(F’) とする F が d(F) を最大にする T-join ということは FΔF’が　　　　　 c（FΔF’) を最大にする TΔT’-join であるということの必要十分条件である 証明 先の補題より、F が T-join ということは FΔF’が TΔT’-joinであるということの必要十分条件であった さらに目的関数 d(F) が c(FΔF’) から定数 c(F’)だけシフトしている

4.5 Application of Weighted Matching 定理 [非負重み T-join への変形] E_ := {e∈E(G) : c(e) < 0} O_ := {v∈V(G) : |E_∩δG(v)| is odd} E(G) に対して非負重み関数 c+ を定義する 全ての e∈E(G) に対して c+(e) := |c(e)| c に対して FΔE_ が 最小重みTΔO_-join ということは c+ に対して F が最小重み T-join であることの必要十分条件

4.5 Application of Weighted Matching 証明 先の補題の T’を E_、F’をO_ とする F’は T’-join d(F) = c(FΔF’) - c(F’) 　　= c(F　F’) + c(F’　F) - c(F’) 　　= c(F　F’) - c(F’∩F) 　　= c+(F)

4.5 Application of Weighted Matching G の最小重み T-join を探す問題に戻る 重み関数 c は非負と考える 補題[Structure of repeated edges] P を G の最小重み T-join とする Pは次のようなパスの枝集合に分割される 端点を共有しない 端点が T に入っている

4.5 Application of Weighted Matching 証明 P の枝の数に関する帰納法で考える P の中のパス H を選ぶ H の枝はサイクルを持たない よってその枝は次数1の頂点を(少なくとも) 2つ含む これらの頂点は必ず T に入っている P の2つの頂点間の経路は一つだけ存在する この経路を P から削除する

4.5 Application of Weighted Matching 補題より次のアルゴリズムを導く事ができる Edmonds-Jonson 最小重み T-join アルゴリズム G をグラフ、T を V(G) の部分集合、c を E(G)の非負の重み関数とする Tの要素数は偶数とする i, j　が T の要素である時、P{i, j} を G の最小重み i-j 経路とする K を V(K) := T であるような完全グラフとする c’を次のように定義する

4.5 Application of Weighted Matching 重み関数c’に関して、S を K の最小重み完全マッチングとする この時 P を {i, j}∈S における P{i, j} の排他的論理和とするとP は G の最小重み T-join である 経路 {i, j} のうち最小重みのものが T = {{i, j}} の最小T-joinであることはすでに述べた さらにこれらのT-joinの排他的論理和を取る事で T と T-joinを増やしていっている

4.5 Application of Weighted Matching T-join はオイラーグラフと呼ばれる巡回問題にも応用される 無向グラフのオイラー閉路とは E(G) を1回ずつ通るようなグラフのたどり方の事を指す 無効グラフがオイラリアンであるということはグラフがオイラー閉路を持っている事の必要十分条件である

4.5 Application of Weighted Matching オイラーの定理 G がオイラリアンであることの必要十分条件は G がつながっており、E(G) が 0-join であることである 証明 「 G がオイラリアンである⇒ G がつながっており、E(G) が 0-join であることである 」 ということは明らか オイラー閉路は全ての枝を通り、そのたび頂点 v を通る v を通るときに2本の枝が使われる

4.5 Application of Weighted Matching 「 G がつながっており、E(G) が 0-join であることである ⇒ G がオイラリアンである」 　を示す 枝の数に関する帰納法で証明する G がつながっていて、 E(G) が 0-join だとする E(G) が サイクル C を持つ事はすぐわかる 枝が2本の場合、G は1つのサイクルなので明らかにオイラリアン 頂点の次数が2より大きいものがある場合、C とつながっているグラフを G1, G2, … , Gk とする E(G) から C を除いても、グラフの全ての頂点の次数は偶数である 帰納法の仮定より Gi は全てオイラー閉路を持つ サイクル C をたどりつつ、Gi に寄り道をすればオイラー閉路ができる

4.5 Application of Weighted Matching 全ての頂点の次数が2の場合 G はつながっているので1つのサイクルになる

4.5 Application of Weighted Matching 頂点の次数が２より大きいものがある場合 Gkはそれぞれ「つながっており枝が 0-join」であるので、帰納法の仮定よりオイラリアン G1 G4 G3 G2

4.5 Application of Weighted Matching グラフ G がつながっており E(G) の非負重み関数を c とする 郵便配達人経路 G の全ての枝を通る 同じ枝を何回通っても良い 最後はスタート地点に帰ってくる 郵便配達人グラフをオイラーグラフ G＾ とする V(G) = V(G^) E(G) ⊂ E(G^)

4.5 Application of Weighted Matching 補題 [繰り返し枝の forest] オイラー閉路 G^ が G の最小重み郵便配達人経路になりうるならばE(G^) 　E(G)はサイクルを持たない 証明(対偶) E(G^) 　E(G) からサイクルを除いてもオイラリアンの性質は失われない 全ての枝が非負なので G^ は最小重み郵便配達人経路にはなりえない

4.5 Application of Weighted Matching コストは6 E(G^) E(G) (曲線の枝集合)はサイクルではない B 1 B A A 1 1 G 1 G^ 1 C C D D 1 1

4.5 Application of Weighted Matching E(G^) E(G) (曲線の枝集合) はサイクル G の最小重み郵便配達人経路は 4 G^ のコストは8 1 1 B B A A 1 1 G 1 1 G^ C C D D 1 1

4.5 Application of Weighted Matching グラフ G の各枝を2本ずつにした重みつきグラフを G(2) と呼ぶことにする 特に次のようなグラフを G’と呼ぶことにする V(G’) := V(G) E(G’) := E(G(2)) E(G) 要するに G の複製 最小重み郵便配達人経路探索問題を最小重みを持つオイラーグラフ G^ を見つける問題とする E(G^) ⊆ E(G(2)) E(G) ⊆ E(G^) G G^ G(2)

4.5 Application of Weighted Matching 奇数の次数を持つ G の頂点集合を T とする (G^　G)⊂G’はG’の最小重み T-join これらより郵便配達人経路の探し方を導く グラフ G の中の奇数の次数を持つ頂点を見つける それらの頂点を通る G の最小重みグラフを見つける(最小重みT-join) それらの枝をそれぞれ二つに増やしグラフ G^ を作る G^ の最小重みオイラー閉路を探す 見つけたオイラー閉路のうち、途中で増やした枝を2回通るような道筋が G の郵便配達人経路

4.5 Application of Weighted Matching Exercise 4 4 3 3 1 1 1 1 2 1 3 4 4 3

4.5 Application of Weighted Matching Exercise 4 4 3 3 1 1 1 1 2 1 3 4 4 3

4.5 Application of Weighted Matching Exercise 4 4 3 3 1 1 1 1 2 1 3 4 4 3

4.5 Application of Weighted Matching Exercise 4 4 3 3 1 1 1 1 1 2 2 1 1 1 1 1 3 4 4 3

4.5 Application of Weighted Matching Exercise 9 10 1 18 4 17 19 16 20 2 3 11 15 12 14 13 6 8 7 5

4.5 Application of Weighted Matching Exercise 9 10 1 17 18 4 19 16 20 2 3 15 12 11 6 14 13 8 7 5

4.5 Application of Weighted Matching 同じ発想をハミルトン閉路の問題に適用できる ハミルトン閉路は全ての頂点を1度だけ通るような閉路 N を有限個の点の集合とする G を V(G) = N であるような完全グラフとする G の枝 e が存在するとき c(e) を e 間の距離とする G の最小重みハミルトン閉路を探す問題を巡回セールスマン問題と呼ぶ

4.5 Application of Weighted Matching オイラリアンであるようないかなる H⊂E(G(2)) に対しても、「圧縮」することにより H の重み以下の重みの ハミルトン閉路を探すことが出来る 重複する頂点に対して三角不等式を使う

4.5 Application of Weighted Matching 次に示す手法では、最小重みハミルトン閉路より50%未満だけ大きい重みのハミルトン閉路が見つかる(近似度1.5) クリストフィード・ヒューリスティック S を G の最小重み全域木とし、T を以下のような集合とする F をG’[T] の最小重み完全マッチングとする G(2) の部分グラフ H を V(H) := V(G) であり E(H) は S∪Fから構成されるようなグラフとし、H のオイラー閉路を探す オイラー閉路を圧縮してハミルトン閉路にする

4.5 Application of Weighted Matching 例：点集合が与えられる

4.5 Application of Weighted Matching 例：最小重み全域木Sを求める

4.5 Application of Weighted Matching 例：G’[T]の最小重み完全マッチングFを求める

4.5 Application of Weighted Matching 例：SとFを合わせてHとする

4.5 Application of Weighted Matching

4.5 Application of Weighted Matching 例：最小重みハミルトン閉路

4.5 Application of Weighted Matching クリストフィードの定理 クリストフィードの手法は最小重みハミルトン閉路の重みと近似度1.5の重みのハミルトン閉路を見つけることが出来る

4.5 Application of Weighted Matching 証明 ハミルトン閉路は全域木の一種なので、S の重みは G の最小重みハミルトン閉路の重みより大きくなることはない S は G の最小重み全域木 三角不等式より、G[T] の最小重みハミルトン閉路の重みは G の最小重みハミルトン閉路の重みより小さい 頂点数が少ないことから明らか G[T] のハミルトン閉路の枝集合は、2つのG[T] の完全マッチングに分けられる このうち重みが小さいマッチングが F になる よって F の重みは、 G[T] の最小重みハミルトン閉路の重みの半分未満

4.5 Application of Weighted Matching 証明続き よって E(H) の重みは V(G) の最小重みハミルトン閉路の重みの1.5倍未満 E(H) := E(S∪F) オイラーの定理より、H はオイラー閉路で、この道筋を圧縮して得られるハミルトン閉路の重みはオイラー閉路より小さくなる

4.5 Application of Weighted Matching 問： [クリストフィード･ヒューリスティックの最悪の場合] ε>0 が与えられたとき、次のような二次元のユークリッド空間における点集合が存在することを示せ 最小より少なくとも (50 -ε)% だけ大きい重みのハミルトン閉路がクリストフィードの手法によって見つかる つまり近似度が1.5に限りなく近くなる最悪の場合を考える

4.5 Application of Weighted Matching 答：次のような正三角形の集合を考える 辺の長さは1とする 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

4.5 Application of Weighted Matching 最小全域木は以下のようになる 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

4.5 Application of Weighted Matching 次数が奇数の頂点は 1 と m だけなので T := {{1,m}} とし、G[T]の最小重みマッチング F は以下のようになる 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

4.5 Application of Weighted Matching 次数が奇数の頂点はないのでこれがハミルトン閉路となる この閉路の重みは 3m-3 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

4.5 Application of Weighted Matching 最小重みハミルトン閉路は以下のようになる この閉路の重みは 2m-1 2m-1 2m-2 2m-3 m+3 m+2 m+1 1 2 3 m-2 m-1 m

4.5 Application of Weighted Matching

4.5 Application of Weighted Matching 最小重みハミルトン経路問題は最適重みマッチングにも利用できる S⊂E(G) が全ての v∈V(G) に対し |S∩δG(v)| = 2ならば S を 2-factor と呼ぶ 明らかにハミルトン閉路は 2-factor であり、最小重み2-factor は最小重みハミルトン閉路より重みが大きくなることはない

4.5 Application of Weighted Matching Gの最小重み 2-factor を探す問題を別のグラフ G’’の最小重み完全マッチング を探す問題に還元する 隣接した頂点に行くことの出来る枝の数を頂点要求と呼ぶ 2-factor の頂点要求は全て2 完全マッチングの頂点要求は全て１ よって頂点要求が2のグラフ G の問題を頂点要求が1のグラフG’’の問題に変換すればよい

4.5 Application of Weighted Matching

4.5 Application of Weighted Matching ステップ1 v w 間に頂点を増やす {v, w} ∈S ならば {v, w’}, {v’, w} ∈S’ {v, w} ∈S ならば {v’, w’} ∈S’ (2) (2) cvw G v w (2) (1) (1) (2) cvw/2 cvw/2 G’ v w’ v’ w

4.5 Application of Weighted Matching ステップ2 (1) (1) cvr/2 r’ cvr/2 cvr/2 r’ (2) (1) (1) cvs/2 (1) (1) cvs/2 cvs/2 s’ v s’ v v’’ cvt/2 (1) (1) cvt/2 cvt/2 t’ t’ G’ G’’

4.5 Application of Weighted Matching これらの操作により、最小重み 2-factor を探す問題を最小重み完全マッチング を探す問題に還元することができる