# マッチング ## 定義 グラフ `G` における**マッチング(matching)**とは、端点を共有しない辺の集合 `M ⊆ E(G)`(どの頂点も `M` に属する辺の端点として高々1回しか現れない)である。マッチングが頂点集合 `S` を**覆う(cover)**とは、`S` の各頂点が `M` のいずれかの辺の端点になっていることをいう。`V(G)` 全体を覆うマッチングを**完全マッチング(perfect matching)**と呼ぶ。二部グラフ `G`(頂点集合が `L(G)`, `R(G)` に分割され全辺が両側に1端点ずつ持つ)において、集合 `S ⊆ V(G)` の**近傍(neighbor set)**を `N(S) := {r | ⟨s—r⟩∈E(G) for some s∈S}` とし、`|S| > |N(S)|` となる `S` を**ボトルネック(bottleneck)**と呼ぶ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.5) **Hall の定理(Hall's Matching Theorem)**は、二部グラフ `G` において `L(G)` を覆うマッチングが存在するための必要十分条件を与える: `L(G)` のどの部分集合もボトルネックでないこと(=どの部分集合の男性集合も、それが好む女性集合以上には大きくないこと、マッチング条件)。証明の一方向(存在→条件)は自明な数え上げで、逆方向(条件→存在)は男性の人数に関する強帰納法で構成的に与えられる。**次数制約グラフ(degree-constrained graph)**(`L(G)` 側の頂点次数が `R(G)` 側の頂点次数以上であるグラフ)は自動的にHallの条件を満たし、`L(G)` を覆うマッチングを持つ。特に**正則グラフ(regular graph、全頂点が同じ次数を持つグラフ)**である二部グラフは常に完全マッチングを持つ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.5) ## 横断的知見 （2ソース目以降に積み増す。現時点では第11章単独の導入のため、複数ソース間の横断的な観察はまだ記録できていない。） ## 未解決の問い - Hall の定理の強帰納法による証明はマッチングを構成的に与えるが非効率(演習ベース)である。本章は「効率的なマッチングアルゴリズムは存在する」とだけ述べて詳細を省いており、具体的な多項式時間アルゴリズム(増加道法など)は後続章・別ソースで確認する必要がある。 - 正則二部グラフの完全マッチング定理(定理11.5.8)は、通信ネットワーク(第10章のバタフライネット・Beneš ネットなど)のルーティング設計とどう関係するのか、章をまたいだ突き合わせがまだ行われていない。 ## 関連 - 概念: [[単純グラフ]] / [[安定結婚問題]] / [[二項関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 11.