マッチングと被覆 ― 最適な組み合わせを見つける

増加路，Bergeの定理，Hallの結婚定理，Königの定理，安定マッチング（Gale-Shapley），重み付きマッチングを証明付きで扱う．

2026年2月27日

1 マッチングの基本概念

定義 1 (マッチング).

グラフ

G = (V, E)

の辺集合

M \subseteq E

がマッチングであるとは，

M

のどの

2

辺も端点を共有しないことをいう．

M

に接続する頂点を飽和されている（matched）という．

∣ M ∣

が最大のマッチングを最大マッチング，

V

のすべての頂点を飽和するマッチングを完全マッチングという．

定義 2 (増加路).

マッチング

M

に関する交互路（alternating path）とは，

M

に属する辺と属さない辺が交互に現れる路のことである．交互路であって，両端点がともに

M

で飽和されていないものを増加路（augmenting path）という．

2 Berge の定理

定理 3 (Berge の定理).

マッチング

M

が最大マッチングであるための必要十分条件は，

M

に関する増加路が存在しないことである．

証明.

(\Rightarrow)

：増加路

P

が存在すれば，

P

上の

M

に属する辺と属さない辺を入れ替えた

M^{'} = M \oplus E (P)

（対称差）は

∣ M^{'} ∣ = ∣ M ∣ + 1

を満たすマッチングであり，

M

の最大性に矛盾する．

(\Leftarrow)

：

M

が最大でないとし，最大マッチング

M^{*}

（

∣ M^{*} ∣ > ∣ M ∣

）を取る．

H = M \oplus M^{*}

を考える．

H

の各頂点の次数は高々

2

（

M

から高々

1

辺，

M^{*}

から高々

1

辺）なので，

H

の各連結成分は路または偶数長の閉路である．

∣ M^{*} ∣ > ∣ M ∣

であるから，

H

には

M^{*}

の辺が

M

の辺より多い成分が存在する．閉路は

M

と

M^{*}

の辺が交互に等しく現れるので，当該成分は路でなければならない．この路は

M^{*}

の辺で始まり

M^{*}

の辺で終わるので，両端点は

M

で飽和されておらず，

M

に関する増加路である． □

3 二部グラフのマッチング

定義 4 (二部グラフ).

グラフ

G = (V, E)

が二部グラフであるとは，

V = X ⊔ Y

と分割でき，

E

のすべての辺が

X

と

Y

を結ぶものであることをいう．

定理 5 (Hall の結婚定理).

二部グラフ

G = (X ⊔ Y, E)

が

X

を飽和するマッチングを持つための必要十分条件は，任意の

S \subseteq X

に対して

∣ N (S) ∣ \geq ∣ S ∣

が成り立つことである（

N (S)

は

S

の近傍集合）．

証明.

(\Rightarrow)

：

X

を飽和するマッチング

M

が存在すれば，任意の

S \subseteq X

に対し

M

は

S

の各頂点を

Y

の異なる頂点に対応させるので

∣ N (S) ∣ \geq ∣ S ∣

．

(\Leftarrow)

：対偶を示す．

X

を飽和するマッチングが存在しないとする．最大マッチング

M

は

∣ M ∣ < ∣ X ∣

を満たす．

M

で飽和されない頂点

u \in X

を取る．

u

から交互路で到達可能な頂点集合を

Z

とし，

S = Z \cap X

，

T = Z \cap Y

とおく．

u \in S

であり，

T

の各頂点は

M

で

S ∖ {u}

のある頂点と対応する（増加路がないので

T

の各頂点は

M

で飽和されており，その相手は交互路で到達可能ゆえ

S

に属する）．よって

∣ T ∣ = ∣ S ∣ - 1

．一方

N (S) \subseteq T

である（

S

の近傍で

T

に属さない頂点

y

があれば，

y

は

M

に属さない辺で

S

と接続し交互路が延びるので

y \in Z \cap Y = T

となり矛盾）．ゆえに

∣ N (S) ∣ \leq ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣

． □

4 König の定理

定義 6 (頂点被覆).

G = (V, E)

の頂点集合

C \subseteq V

が頂点被覆であるとは，すべての辺

e \in E

が

C

の少なくとも

1

つの頂点を端点に持つことをいう．

定理 7 (König の定理).

二部グラフにおいて，最大マッチングの辺数は最小頂点被覆の頂点数に等しい．

証明.

任意のマッチング

M

と頂点被覆

C

に対し，

M

の各辺を被覆するため

∣ C ∣ \geq ∣ M ∣

は明らかである．等号の達成を示す．最大マッチング

M

を取り，上の Hall の定理の証明と同様の到達可能性集合

Z

を構成する．

C = (X ∖ Z) \cup (Y \cap Z)

とおくと

∣ C ∣ = ∣ M ∣

であり，

C

が頂点被覆であることが確認できる． □

5 安定マッチング

定義 8 (安定マッチング).

n

人の男性集合

M

と

n

人の女性集合

W

が，それぞれ相手集団に対する厳密な選好順序を持つとする．完全マッチング

μ

が不安定であるとは，

μ

でペアになっていない男性

m

と女性

w

が存在し，

m

は

μ (m)

より

w

を好み，

w

は

μ (w)

より

m

を好む場合をいう．不安定なペアが存在しないマッチングを安定マッチングという．

定理 9 (Gale-Shapley).

Gale-Shapley アルゴリズム（男性プロポーズ版）は，有限ステップで終了し，安定マッチングを出力する．さらに，得られるマッチングはすべての安定マッチングの中で男性にとって最適（男性最適安定マッチング）である．

証明.

終了性：各男性は同じ女性に

2

度プロポーズしないので，高々

n^{2}

回のプロポーズで終了する．

安定性：不安定ペア

(m, w)

が存在すると仮定する．

m

は最終的に

w

にプロポーズしなかったか，プロポーズして断られたかのいずれかである．前者は

m

が

μ (m)

を

w

より好むことを意味し，

(m, w)

の不安定性に矛盾する．後者では

w

はその時点で

m

より好ましい相手を持っていたが，アルゴリズムで

w

の相手は悪化しないので，最終結果でも

w

は

μ (w)

を

m

より好む．これも矛盾．

男性最適性は，「男性がアルゴリズムの過程で何らかの安定マッチングにおける相手から断られることはない」ことを帰納的に示すことで証明される． □

6 重み付きマッチング

注意 10.

辺に重み

w (e)

が与えられたとき，重みの和

\sum_{e \in M} w (e)

を最大化するマッチングを最大重みマッチングという．二部グラフの場合，ハンガリアン法（Kuhn-Munkres アルゴリズム）が

O (n^{3})

で最大重みマッチングを求める．これは双対性（LP 緩和の双対）に基づく手法であり，König の定理の重み付き拡張と見なせる．一般グラフの場合は Edmonds の花アルゴリズムが

O (n^{3})

で動作する．

マッチングと被覆 ― 最適な組み合わせを見つける

1 マッチングの基本概念

2 Berge の定理

3 二部グラフのマッチング

4 König の定理

5 安定マッチング

6 重み付きマッチング

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ