平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

グラフ理論から組合せ最適化へ
岩田 覚

1

Euler 閉路

グラフの一筆書きに関する Euler の定理を思い出してみましょう．グラフ中のすべての枝をちょうど 1 回ずつ通って元の点に戻るような閉路を Euler 閉路と言います．Euler閉路が存在するためには，グラフは連結でなければなりません．連結なグラフにおいて，すべての点での次数が偶数のとき，かつそのときに限って，Euler 閉路が存在するというのが，Euler の定理でした．この定理は，実に素晴らしい定理です．
どのように素晴らしいかを味わうために，目の前にグラフを見せられて，Euler 閉路があるかどうかを問われた状況を考えてみましょう．Euler 閉路が存在する場合に，そのことを納得してもらうには，実際に一筆書きをして見せればよいでしょう．では，Euler 閉路が存在しない場合はどうでしょうか？ あれこれ試してもできないというのでは，説得力がありません．Euler 閉路が存在しないことの簡潔な証拠が求められます．
もし Euler 閉路が存在するならば，Euler 閉路に沿って一周したときに各点に入る回数と出る回数が等しくなるので，各点での次数は偶数でなければなりません．ですから，次数が奇数の点があれば，Euler 閉路の存在しないことの証拠になります．実際，ケーニヒ
スベルグの 7 本の橋に関しては，陸地を点，橋を枝と見たグラフにおいて，奇数次数の点が存在することから，すべての橋を 1 回ずつ通って元の地点に戻る周遊ルートがないことが示されます．Euler の定理は，さらに踏み込んで，どんな連結グラフであっても，一筆書きが存在しないならば，奇数次数の点という簡潔な証拠が必ず存在することを保証しています．これは，「良い特徴付け」と呼ぶに相応しいものではないでしょうか．

2

良い特徴付け良い特徴付け (good characterization) というのは，単なる褒め言葉ではなく，厳密な意味の定義された専門用語なのです．答えが Yes か No で与えられる判定問題で，答えが Yes の場合に，そのことを保証する多項式時間で検証可能な証拠が存在する問題のクラスが NP と呼ばれています．同様に，答えが No の場合に，多項式時間で検証可能な証拠が存在する問題のクラスが co-NP です．

1

平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

Euler 閉路の存在判定問題では，答えが Yes の場合には，どうやって見付けるかは別にして，一筆書きの仕方，すなわち Euler 閉路中の枝の順番が証拠になります．本当にEuler 閉路になっているかどうかは，グラフ構造の入力に比例した程度の計算量で検証可能です．一方，答えが No の場合には，Euler の定理より，次数が奇数の点が存在します．
どうやって奇数次数の点を見付けるかは別として，証拠として提示された点が本当に奇数次数かどうかを検証するのは，きわめて簡単にできます．ですから，Euler 閉路の存在判定問題は，NP にも co-NP にも含まれることになります．Euler の定理のように，ある判定問題が NP ∩ co-NP に含まれることを明らかにする定理が「良い特徴付け」です．
離散数学の定理の中には，必要十分条件を示しているものがたくさんあります．しかし，単なる形式的な言い換えだけでも，必要十分条件の形をした正しい命題を作ることはできます．どのような必要十分条件ならば，定理の名に値するものかどうかを見極めるための有用な一つの規準が「良い特徴付け」であるかどうかなのです．

3マッチング

点集合 V , 枝集合 E からなるグラフ G = (V, E) におけるマッチングとは，どの二つの枝も端点を共有しない枝部分集合 M ⊆ E のことです．マッチング M の端点集合 ∂Mに対して，|∂M | = 2|M | となります．特に ∂M = V となるマッチング M を完全マッチングと言います (図 1)．
t
@@@tt
t
@@@tt

図 1: 完全マッチングの例.
グラフ G = (V, E) に完全マッチングが存在するためには，点の個数 |V | が偶数でなければなりません．しかし，点の個数が偶数であっても，完全マッチングが存在しないこともあります (図 2)．それでは，完全マッチングが存在するのは，どんなときなのでしょうか？
各点での次数が d であるようなグラフを d 正則グラフと言います．また，任意の k 本の枝を削除しても連結であるグラフを k 枝連結グラフと言います．図 1 のような 2 連結
3 正則グラフに完全マッチングが存在することは，19 世紀に Petersen によって示されています．これは，興味深い十分条件ですが，特徴付けを与えている訳ではありません．
この疑問に完全な解答を与えているのが，Tutte の定理です．点部分集合 U ⊆ V に対して，G から U の点と, U に接続している枝をすべて削除して得られるグラフを G − U2平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)t@@tt@tttHHt@@ttt

図 2: 完全マッチングが存在しないグラフの例.と書くことにします．さらに，G − U の連結成分の中で，点の数が奇数であるものの個数を odd(G − U ) と書くことにしましょう．グラフ G に完全マッチング M が存在するならば，M の枝のうち，少なくとも odd(G − U ) 本が，U の点に接続しなくてはなりません．したがって，odd(G − U ) ≤ |U | が成立します．Tutte は，この逆も成立することを示しました．
定理 1 (Tutte [7]) グラフ G = (V, E) において，任意の点部分集合 U ⊆ V に対してodd(G − U ) ≤ |U | のとき，かつそのときに限って，完全マッチングが存在する．

Tutte の定理によって，完全マッチングが存在しないときには，odd(G − U ) > |U | となる U ⊆ V が存在することが保証されます．そのような U は，完全マッチングが存在しないことの多項式時間で検証可能な証拠となっています．Tutte の定理も，Euler の定理と同様に，「良い特徴付け」になっているのです．
完全マッチングが存在しないとなると，枝数最大のマッチングが気になります．実際，Tutte の定理を用いて，最大マッチングの枝数 µ(G) に関して，µ(G) =1min{|V | − odd(G − U ) + |U | : U ⊆ V }2となることが示せます．この等式は，Tutte-Berge 公式と呼ばれています．Tutte-Berge 公式は，指定された枝数のマッチングの存在に関する良い特徴付けを与えています．
枝集合の部分集合 H ⊆ E は，∂H = V となるとき，枝被覆と呼ばれます．完全マッチングは枝被覆となります．完全マッチングの大きさは |V |/2 なので，これよりも小さい枝被覆はあり得ません．すなわち，完全マッチングが枝数最小の枝被覆になります．それでは，完全マッチングが存在しないときも含めて，枝被覆の枝数の最小値 η(G) は，一般にどうなるのでしょうか?
最大マッチング M の枝が接続していない点の集合を X ⊆ V として，X の各点から出る枝を勝手に 1 本ずつ選んで，M に加えた結果として得られる集合を H とします．
このとき，H は枝被覆であり，その枝数は |H| = |V | − |M | となります．このことは，
η(G) ≤ |V | − µ(G) となることを意味します．

3

平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

一方，最小枝被覆 H の各枝について，両端点のうち少なくとも一方は，この枝以外にH の枝とは接続していません．すなわち，H の各連結成分は，1 点に接続している数本の枝からなる形になります．各連結成分から 1 本ずつ枝を集めて得られる枝集合 M はマッチングであり，その枝数は，|M | = |V | − |H| です．これは，µ(G) ≥ |V | − η(G) を意味します．
以上の結果，µ(G) + η(G) = |V | が成立します．この等式は，Gallai の補題と呼ばれています．Gallai の補題は，最大マッチングと最小枝被覆を結び付けた公式になっていますが，良い特徴付けではありません．最大マッチングか最小枝被覆のどちらか一方が見付かれば，他方も見付けられると言っているに過ぎません．

4最大重みマッチング

グラフ G = (V, E) の各枝 e ∈ E に非負重み w(e) ≥ 0 が与えられているときに，∑w(M ) = e∈M w(e) が最大となるマッチングを求める問題を考えてみましょう．各枝e ∈ E に対する変数 x(e) を集めて，全部で |E| 個の変数を用意します．ここで，x は，|E| 次元線形空間 RE の中のベクトルと見ることができます．
任意の部分集合 F ⊆ E に対して，e ∈ F のときには x(e) = 1 で，e ̸∈ F のときにはx(e) = 0 となるベクトル x ∈ RE を対応させます．このようにして得られるベクトル xを F の特性ベクトルと呼びます．マッチング M ⊆ E の特性ベクトルは，どのような条件を満たすのでしょうか? 各点 v ∈ V に接続する枝の集合を δv と書くことにすると，v∑に接続する枝を高々1 本しか含まないという条件は， e∈δv x(e) ≤ 1 と表現できます．逆に，この条件を満たす 0-1 ベクトルは，マッチングの特性ベクトルになります．さらに，∑x がマッチング M の特性ベクトルのとき，その重みは w(M ) = e∈E w(e)x(e) で得られます．その結果，最大重みマッチングを求める問題は，以下のように定式化できます．

Maximize∑w(e)x(e)e∈Esubject to∑x(e) ≤ 1(v ∈ V ),x(e) ∈ {0, 1}(e ∈ E).

e∈δv

このように変数が整数値を取るという条件の入った最適化問題を整数計画問題と言います．特に，線形不等式制約と整数条件を満たしつつ線形目的関数を最小化/最大化する問題は整数線形計画問題と呼ばれています．整数線形計画問題は，一般には NP 困難で，解くのが難しいとされています．それに対して，整数条件を含まない線形計画問題には，効率的な解法が開発され，広く使われています．整数線形計画法を解くための第一歩は，整数条件を緩和して得られる線形計画問題を解くことです．緩和問題の最適解は，必ずしも整数条件を満たしません．しかし，得られた最適解が運よく整数性条件も満たすな

4

平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

らば，間違いなく元の問題の最適解にもなっています．そして，整数条件を満たさない場合でも，最適値の上界を与えることになります．
マッチング問題を定式化した整数線形計画問題の場合，緩和問題の最適解は整数条件を満たすとは限りません．実際，グラフ G として，3 点の完全グラフ K3 を考えてみましょう. 各枝の重みを全て 1 にした場合の問題，すなわち最大マッチングを求める問題の場合，緩和問題の最適解は，各枝 e ∈ E に x(e) = 1/2 を割り当てたものになり，目的関数値は 3/2 となります．実際，K3 のマッチングは，高々1 本の枝しか含みません．このように，緩和問題と元の問題には本質的な差が生じてしまいます．
実は，この緩和問題の線形不等式制約と非負条件から定まる多面体の頂点は，各成分x(e) が 1/2 の整数倍になる半整数ベクトルであることが知られています．この事実は，線形不等式系の係数行列が，各列に 1 が高々 2 回だけ現れる 0-1 行列であることに由来しています．その結果，緩和問題の最適解に半整数解が存在することが保証されます．
さて，緩和問題の最適解と最大重みマッチングの間に本質的な差が生じてしまうのはどうしてなのでしょうか．上で挙げた K3 は，そのヒントを与えています．グラフの中の 3 点の間を結ぶ枝から高々1 本の枝しかマッチングに参加できないという事実が，線形不等式制約の中に反映されていないのです．さらに，一般に，3 以上の奇数個の点の集合
S に対して，S の中の点を結ぶ枝からは，高々 (|S| − 1)/2 本の枝しかマッチングに参加できません．このことを表す不等式制約を加えた線形計画問題を考えてみましょう．

Maximize∑w(e)x(e)e∈Esubject to∑x(e) ≤ 1(v ∈ V ),(1)e∈δv∑

x(e) ≤e∈E[S]x(e) ≥ 0|S| − 12(S ∈ Q),(e ∈ E).

ここで，E[S] は両端点が S に含まれる枝の集合，Q は点数が 3 以上の奇数である点部分集合の全体を表します．
この線形計画問題の制約条件を表す多面体は，頂点がすべて 0-1 ベクトルとなり，マッチングの特性ベクトルの凸包と一致します [3]．この多面体は，G のマッチング多面体と呼ばれています．マッチング多面体上の線形計画問題を解けば，最大重みマッチングが得られます．ただし，この線形計画問題が非常に多数の制約条件を含んでいることに注意しなくてはなりません．グラフの点数が n のときに，線形不等式制約の本数は 2n−1 ほどにもなります．これでは，線形計画問題を計算機の中に直接入力することすら覚束なくなります．そこで，線形計画法の双対理論が威力を発揮するのです．

5

平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

5

主双対アルゴリズム

最大重みマッチング問題を表す線形計画問題 (1) の双対問題は, 各点 v ∈ V における変数 y(v) と，各 S ∈ Q に対する変数 z(S) に関する以下のような最小化問題になります．

Minimize∑y(v) +v∈Vsubject to∑∑ |S| − 1S∈Qy(v) +v∈∂e∑2y(S)z(S) ≥ w(e)(e ∈ E),(2)S∈Q:e∈E[S]y(v) ≥ 0(v ∈ V ),z(S) ≥ 0(S ∈ Q).

主問題の実行可能解 x と双対問題の実行可能解 (y, z) の組は，相補性条件と呼ばれる次のような条件を満たすとき，かつそのときに限り，それぞれの両問題の最適解を与えます．

(i) 任意の e ∈ E に対して，x(e) = 0 または∑v∈∂e(ii) 任意の S ∈ Q に対して，∑∑

y(v) +z(S) = w(e).

S∈Q:e∈E[S]x(e) = (|S| − 1)/2 または z(S) = 0.

e∈E(S)(iii) 任意の v ∈ V に対して，∑x(e) = 1 または y(v) = 0.

e∈δv

相補性条件のうちで，(i) と (ii) を常に保持しつつ，マッチング M の特性ベクトル x と双対問題の実行可能解 (y, z) とを更新して行って，条件 (iii) が満たされた時点で終了するという形のアルゴリズムが設計できます．ここで，アルゴリズムの実行中の全ての段階において，z(S) > 0 となっている S ∈ Q の個数が無闇に増えないようすることがポイントになります．具体的には，S, T ∈ Q に関して，z(S) > 0, z(T ) > 0 ならば，S ⊆ T ,S ⊇ T , S ∩ T = ∅ のいずれかが成り立つようにできるのです．その結果，z(S) > 0 となる S ∈ Q の個数は高々 |V | となり，それ以外の z の値は全部 0 なので，陽に持つ必要さえなくなります．これが，一見して非常に多くの制約条件を持つ線形計画問題 (1) を効率的に解く仕組みです．
このように，相補性条件を達成することを指導原理として設計されたアルゴリズムは，一般に主双対アルゴリズムと呼ばれています．
各枝の重みが整数の場合には，主双対アルゴリズムを実行した結果，最終的に各点 v ∈ V
での y(v) は半整数で，各 S ∈ Q での z(S) が整数となる双対問題の最適解 (y, z) が得られます．さらに，実は y の値も整数となるような最適解が存在します [2]．この性質は，線形不等式系 (1) の完全双対整数性 (TDI) と呼ばれています．

6

平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

6完全マッチング多面体∑グラフ G = (V, E) の各枝に費用 c(e) が与えられているときに，費用 c(M ) = e∈M c(e)を最小にする完全マッチングを求める問題を考えてみましょう．この問題は，十分大きな値 θ を用いて，w(e) = θ − c(e) で定めた w に関する最大重みマッチング問題に帰着して解くことができます．あるいは，最大重みマッチングと同様に，以下のような線形計画問題とその双対問題を考えることで，直接的に最小費用完全マッチングを見出す主双対アルゴリズムを設計することもできます．

Minimize∑c(e)x(e)e∈Esubject to∑x(e) = 1(v ∈ V ),x(e) ≥ 1(S ∈ Q),(3)e∈δv∑e∈∆Sx(e) ≥ 0(e ∈ E).

ここで，∆S は，S と V \ S を結ぶ枝の集合を表しています．
グラフ G に完全マッチングがない場合には，この線形計画問題には実行可能解が存在しません．完全マッチングがある場合，線形計画問題 (3) の実行可能領域は，完全マッチング多面体と呼ばれ，完全マッチングの特性ベクトルの凸包を与えます．この事実に基づいて，Petersen の定理の別証を与えることもできます．2 連結 3 正則グラフの各枝e ∈ E に x(e) = 1/3 を割り当てて得られる x ∈ RE は，完全マッチング多面体の中に含まれます．したがって，G に完全マッチングが存在することが保証されるのです．

7郵便配達人問題

グラフ G = (V, E) の各枝 e ∈ E に長さ ℓ(e) ≥ 0 が与えられているときに，すべての枝を少なくとも 1 回通って出発点に戻ってくる最短経路を見つけるにはどうしたらよいでしょうか? すべての街路を通って郵便局に戻ってくる郵便配達人のための最短経路を求めたいという訳です．この問題は，中国の数学者 M.-G. Guan (管梅谷) によって提起されたため，中国郵便配達人問題と呼ばれることもあります．ここでは，マッチングを利用した解法を紹介します．
もし，G に Euler 閉路があるならば，話は簡単です．どのような Euler 閉路を採用して∑も，その長さは一定で，ℓ(E) = e∈E ℓ(e) に等しくなります．問題は，Euler 閉路の存在しない場合で，どこかの枝を 2 回通る必要が生じてきます．この場合，Euler の定理で保証されているように，次数が奇数となる点が存在します．これらの点の集合を W と書
b = (W, F ) とします．このとき，き，W のすべての点対間に枝を張った完全グラフを G
各枝 a ∈ F の費用 c(a) を a の両端点を結ぶ G 上の最短経路によって定めます．こう7平成22年度(第32回)数学入門公開講座テキスト(京都大学数理解析研究所，平成22年8月2日～8月5日開催)

b = (W, F ) には偶数個の点があり，完全マッチングが存在します．
して作られたグラフ G∑
これらの完全マッチングのうちで，費用 c(M ) = e∈M c(e) が最小になるものを見出し，マッチングの各枝に対応する最短路に沿って，並行枝を G に加えます．その結果として得られたグラフは，各点での次数が偶数になっているので，Euler 閉路の存在が保証されます．並行枝を通るところは同じ枝を 2 回通るのだと解釈することによって，G の中のすべての枝を 1 回以上通って出発点に戻る最短経路が得られます．
グラフ G = (V, E) の中で，点集合の空でない真部分集合 X を用いて D = ∆X と表すことのできる枝部分集合をカットといいます．各枝 e ∈ E に重み w(e) ≥ 0 が与えら∑れているときに，w(D) = e∈D w(e) が最大となるカット D を求める問題が最大カット問題です．最大カット問題は，一般のグラフ上では NP 困難であり，効率的な厳密解法は存在しないだろうと言われています．しかし，平面グラフ上の最大カット問題は，双対グラフ上の郵便配達人問題に帰着することで，効率的に解くことができます．
このように，マッチング問題の解法は，様々な組合せ最適化問題と関連しているため，その応用範囲も多岐に渡っています．より進んだ内容に関する専門書として，[1, 5, 6] を薦めます．また，「良い特徴付け」に関して，より詳しくは [4] の解説を参考にして下さい．

参考文献[1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver: CombinatorialOptimization, Wiley, 1998.
[2] W. H. Cunningham, A. B. Marsh, III: A primal algorithm for optimum matching,
Math. Programming Study, 8 (1978), pp. 50–72.
[3] J. Edmonds: Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat.
Bur. Stand., 69B (1965), pp. 125–130.
[4] 岩田: 良い特徴付け, 数学セミナー, 48 (2009), No. 12, pp. 36–40.
[5] L. Lovász, M. D. Plummer: Matching Theory, North-Holland, 1986.
[6] A. Schrijver: Combinatorial Optimization — Polyhedra and Eﬃciency, SpringerVerlag, 2003.
[7] W. T. Tutte: The factorization of linear graphs, J. London Math. Soc., 22 (1947),
pp. 107–111.

8