マッチング(グラフ理論)
概要
マッチング(グラフ理論)（matching）とは、グラフの辺の部分集合であって、どの 2 辺も端点を共有しないもののことである。大きさ最大のものを最大マッチング、すべての頂点を覆うものを完全マッチングという。有限グラフのマッチングが最大であることは、飽和されない 2 頂点を結ぶ交互道（増加道）がないことと同値である（Berge の定理）。有限二部グラフでは、一方の部集合 $A$ を覆うマッチングが存在することは、すべての $S\subset A$ について $S$ の頂点に隣接する頂点が $|S|$ 個以上あることと同値であり（Hall の結婚定理）、最大マッチングの大きさは最小頂点被覆の大きさに等しい（König の定理）。後者は二部でないグラフでは一般には成り立たず（三角形では $\nu=1<2=\tau$）、成り立つ場合もある（三角形に新しい頂点を 1 辺で付けたグラフ）。
定義
本記事の「マッチング」は グラフ の辺の集合についての概念である。文字列の照合（パターンマッチング）や、経済学の安定マッチング問題とは別の用語であるが、後者はここでの二部グラフのマッチングを土台にしている。以下、グラフは単純無向グラフ $G=(V,E)$ とし、とくに断らない限り有限とする（グラフ の記事の定義「グラフの定義」）。頂点 $v$ の近傍を $N_G(v)$、頂点の集合 $S\subset V$ の近傍を $N_G(S):=\bigcup_{v\in S}N_G(v)$ と書き、$G$ が明らかなときは $N(S)$ と略す。
グラフ $G=(V,E)$ の辺の部分集合 $M\subset E$ が マッチング（matching）であるとは、$M$ の相異なる 2 辺が端点を共有しないことをいう。辺 $e\in M$ の端点である頂点を $M$ で飽和される（$M$ に覆われる）といい、そうでない頂点を $M$ で飽和されない頂点という。$|M|$ をマッチングの大きさという。
- 他のどの辺を加えてもマッチングでなくなるマッチングを 極大マッチング（maximal matching）という。
- 大きさが最大のマッチングを 最大マッチング（maximum matching）といい、その大きさを $\nu(G)$ と書いて $G$ の マッチング数 という。
- すべての頂点を飽和するマッチングを 完全マッチング（perfect matching）という。
- $S\subset V$ のすべての頂点を飽和するマッチングを、$S$ を飽和するマッチングという。二部グラフの二部分割 $(A,B)$ について $A$ を飽和するマッチングを、$A$ から $B$ への（$A$ の）マッチングともいう。
空集合 $\emptyset\subset E$ はつねにマッチングであり、頂点をもたないグラフでは完全マッチングでもある。$M$ がマッチングなら、飽和される頂点はちょうど $2|M|$ 個である。とくに完全マッチングをもつ有限グラフの頂点数は偶数であり、$\nu(G)\le\lfloor|V|/2\rfloor$ である。最大マッチングは極大マッチングであるが、逆は成り立たない（ex-matching-graph-theory-maximal）。
$M$ をグラフ $G$ のマッチングとする。$G$ の 道 $v_0,v_1,\dots,v_\ell$ が $M$ 交互道 であるとは、その辺 $v_0v_1,v_1v_2,\dots,v_{\ell-1}v_\ell$ が $M$ に属さない辺と $M$ に属する辺を交互にたどることをいう。$M$ 交互道のうち、長さが $1$ 以上で、両端点 $v_0,v_\ell$ がともに $M$ で飽和されないものを $M$ 増加道（augmenting path）という。
$M$ 増加道では、最初と最後の辺は $M$ に属さない（端点が飽和されないので）。したがって辺は「$M$ に属さない、属する、…、属さない」と並び、長さは奇数で、$M$ に属さない辺が $M$ に属する辺より 1 本多い。
マッチングと対になる概念として、頂点の部分集合 $C\subset V$ で、すべての辺が少なくとも 1 つの端点を $C$ にもつものを 頂点被覆（vertex cover、頂点被覆）という。頂点被覆の大きさの最小値を $\tau(G)$ と書く。
直感
マッチングは「辺で結ばれた 2 頂点をペアにする組み方」であり、各頂点は高々 1 つのペアにしか入れない。二部グラフでは、一方の部集合を人、他方を仕事、辺を「その人がその仕事をできる」関係と読めば、マッチングは重複のない割り当てにあたる。できるだけ多くのペアを作るのが最大マッチングの問題である。
欲張りにペアを作っていくと、それ以上ペアを足せない極大マッチングに行き着くが、それが最大とは限らない。そのとき、すでにあるペアを組み替えればペアを 1 つ増やせる。組み替え方を表すのが増加道であり、増加道の $M$ の辺と $M$ でない辺を入れ替えると大きさが 1 つ増える。Berge の定理（thm-matching-graph-theory-berge）は、増加道がなくなったときが最大であることを保証する。二部グラフでは、全員に仕事を割り当てられるための条件が「どの $k$ 人を選んでも、その誰かができる仕事が $k$ 種類以上ある」という Hall の条件で与えられ（thm-matching-graph-theory-hall）、最大マッチングの大きさは全辺を覆うのに必要な頂点の最小個数に等しい（thm-matching-graph-theory-konig）。
例と反例
- 道グラフ $P_n$（頂点 $1,\dots,n$、辺 $\{i,i+1\}$）では、辺 $\{1,2\},\{3,4\},\dots$ を 1 つおきにとると大きさ $\lfloor n/2\rfloor$ のマッチングになり、上の上界 $\nu\le\lfloor n/2\rfloor$ に達するので $\nu(P_n)=\lfloor n/2\rfloor$ である。$P_n$ が完全マッチングをもつのは $n$ が偶数のときに限る。
- 閉路グラフ $C_n$（$n\ge3$）も同様に $\nu(C_n)=\lfloor n/2\rfloor$ で、完全マッチングをもつのは $n$ が偶数のときに限る。
- 完全グラフ $K_n$ では任意の相異なる頂点の対が辺なので $\nu(K_n)=\lfloor n/2\rfloor$ である。
- 完全二部グラフ $K_{m,n}$（部集合 $A,B$、$|A|=m\le n=|B|$）では、$A$ の頂点を $B$ の相異なる頂点と 1 つずつ結べば $A$ を飽和するマッチングになる。どのマッチングも $A$ の各頂点を高々 1 回しか使わず、すべての辺は $A$ の頂点を端点にもつので大きさは $m$ 以下であり、$\nu(K_{m,n})=\min(m,n)$ である。
道グラフ $P_4$（頂点 $1,2,3,4$）で $M=\{\{2,3\}\}$ をとる。残りの辺 $\{1,2\}$、$\{3,4\}$ はどちらも $M$ の辺と端点を共有するので、$M$ は極大マッチングである。しかし $M'=\{\{1,2\},\{3,4\}\}$ は大きさ $2$ のマッチングで、$M$ は最大でない。道 $1,2,3,4$ は $M$ 増加道であり（両端点 $1,4$ は飽和されず、辺は $M$ に属さない、属する、属さないの順）、$M$ とこの道の辺の入れ替えで $M'$ が得られる。この例は「極大マッチングは最大マッチングである」という含意を破る。極大マッチングの大きさは最大の半分以上ではある（prop-matching-graph-theory-maximal-bound）が、この例でちょうど半分になる。
部集合 $A=\{a_1,a_2,a_3\}$、$B=\{b_1,b_2,b_3\}$ をもち、辺が $a_1b_1,a_2b_1,a_3b_1,a_3b_2,a_3b_3$ である二部グラフを考える。$S=\{a_1,a_2\}$ について $N(S)=\{b_1\}$ であり $|N(S)|=1<2=|S|$ なので、Hall の条件が破れている。実際、$a_1$ と $a_2$ はどちらも $b_1$ としか隣接しないので同時には飽和されず、$A$ を飽和するマッチングは存在しない。最大マッチングは $\{a_1b_1,a_3b_2\}$ などで、大きさは $2$ である。このグラフは頂点数が偶数 $6$ で、$|A|=|B|$ であるが完全マッチングをもたないので、「部集合の大きさが等しい二部グラフは完全マッチングをもつ」という含意を破る。
- （二部性を破る）三角形 $K_3$ では $\nu(K_3)=1$ であるが、3 辺を覆うには頂点が 2 個必要である（1 個の頂点は 2 辺しか覆わない）。したがって $K_3$ では最大マッチングの大きさと最小頂点被覆の大きさが一致せず、thm-matching-graph-theory-konig の結論は二部グラフでないグラフでは破れることがある。ただし、いつも破れるわけではない。三角形 $abc$ に頂点 $d$ と辺 $cd$ を付け加えたグラフは二部グラフでないが、$\{ab,cd\}$ は大きさ $2$ のマッチング、$\{a,c\}$ は大きさ $2$ の頂点被覆なので、$\nu=\tau=2$ である。
- （頂点数が偶数でも完全マッチングがない）星グラフ $K_{1,3}$ は頂点数 $4$ であるが、どの 2 辺も中心を共有するので $\nu(K_{1,3})=1$ であり、完全マッチングをもたない。中心 $c$ を除くと奇数個（$1$ 個）の頂点からなる 連結成分 が 3 つ残り、これが rem-matching-graph-theory-tutte の Tutte の条件 $o(G-S)\le|S|$ を $S=\{c\}$ で破っている。
- （有限性を破る）部集合 $A=\{a_0,a_1,a_2,\dots\}$、$B=\{b_1,b_2,\dots\}$ をもち、$a_0$ はすべての $b_i$ と、$a_i$（$i\ge1$）は $b_i$ だけと隣接する無限二部グラフを考える。$A$ の有限部分集合 $S$ について、$a_0\in S$ なら $N(S)=B$ は無限集合、$a_0\notin S$ なら $N(S)=\{b_i\mid a_i\in S\}$ は $S$ と同じ個数なので、Hall の条件はすべての有限部分集合で成り立つ（無限部分集合 $S$ についても $N(S)$ は可算無限集合で、濃度の意味で $|N(S)|\ge|S|$ である）。しかし $A$ を飽和するマッチングがあれば $a_i$（$i\ge1$）は $b_i$ と組むしかなく、$a_0$ と組める頂点が残らない。したがって thm-matching-graph-theory-hall の十分性は、$A$ が無限の場合には一般には成り立たない（この例では $a_0$ の次数が無限である）。
性質
$G$ を有限グラフとする。
- 任意のマッチング $M$ と任意の頂点被覆 $C$ について $|M|\le|C|$ である。とくに $\nu(G)\le\tau(G)$ である。
- $M$ が極大マッチングなら、$M$ の辺の端点全体 $V(M)$ は頂点被覆である。したがって $\tau(G)\le2|M|$ であり、$|M|\ge\nu(G)/2$ である。
- $M$ の各辺は少なくとも 1 つの端点を $C$ にもつ。$M$ の相異なる辺は端点を共有しないので、各辺にその端点のうち $C$ に属するものを 1 つ選ぶ対応は $M$ から $C$ への 単射 である。ゆえに $|M|\le|C|$ である。
- 辺 $e\in E$ が $V(M)$ に端点をもたないとすると、$e$ は $M$ のどの辺とも端点を共有しないので $M\cup\{e\}$ はマッチングであり、$e\notin M$ だから $M$ の極大性に反する。よって $V(M)$ は頂点被覆で、$|V(M)|=2|M|$ だから $\tau(G)\le2|M|$ である。1 とあわせて $\nu(G)\le\tau(G)\le2|M|$ である。$\square$
次の定理は、最大マッチングを増加道の有無で判定する。二部グラフに限らず任意のグラフで成り立つ。
有限グラフ $G$ のマッチング $M$ が最大マッチングであることと、$M$ 増加道が存在しないことは同値である。
$M$ 増加道 $P=v_0,v_1,\dots,v_\ell$ があるとし、その辺集合を $E(P)$ とする。$M':=M\triangle E(P)$（対称差）が大きさ $|M|+1$ のマッチングであることを示す。$E(P)$ のうち $M$ に属さない辺は $M$ に属する辺より 1 本多いので $|M'|=|M|+1$ である。$M'$ がマッチングであること：$P$ の内部の頂点 $v_i$（$0< i<\ell$）には $P$ の辺が 2 本接続し、交互性によりそのちょうど 1 本が $M$ に属する。$M$ はマッチングなので $v_i$ に接続する $M$ の辺はその 1 本だけであり、入れ替え後に $v_i$ に接続する $M'$ の辺は $P$ のもう 1 本だけである。端点 $v_0,v_\ell$ は $M$ で飽和されないので、入れ替え後に接続する $M'$ の辺は $P$ の最初または最後の辺だけである（$\ell\ge1$ で $v_0\neq v_\ell$）。$P$ に属さない頂点に接続する辺は変わらない。よって $M'$ はマッチングであり、$M$ は最大でない。
逆に $M$ が最大でないとし、$|M'|>|M|$ となるマッチング $M'$ をとる。辺集合 $M\triangle M'$ と頂点集合 $V$ からなるグラフ $H$ を考える。$H$ の各頂点には $M$ の辺と $M'$ の辺が高々 1 本ずつしか接続しないので、$H$ の各頂点の次数は $2$ 以下であり、次数 $2$ の頂点では $M\setminus M'$ の辺と $M'\setminus M$ の辺が 1 本ずつ接続する。したがって $H$ の各連結成分は、孤立点、辺が $M\setminus M'$ と $M'\setminus M$ を交互にたどる道、または同じく交互な閉路である。交互な閉路では両方の辺の本数が等しい。$|M'\setminus M|>|M\setminus M'|$ だから、$M'\setminus M$ の辺を $M\setminus M'$ の辺より多く含む成分があり、それは最初と最後の辺が $M'\setminus M$ に属する交互な道 $P$ である。
$P$ の端点 $v$ が $M$ で飽和されないことを示す。$v$ は $H$ で次数 $1$ で、$P$ の辺 $e'\in M'\setminus M$ に接続する。$v$ に接続する $M$ の辺 $e$ があったとすると、$e\notin M'$ なら $e\in M\triangle M'$ となって $v$ の $H$ での次数が $2$ になり矛盾し、$e\in M'$ なら $v$ に $M'$ の相異なる 2 辺 $e,e'$（$e\in M$、$e'\notin M$）が接続して矛盾する。よって $P$ の両端点は $M$ で飽和されず、$P$ の辺は $M$ に属さない辺（$M'\setminus M$）と属する辺（$M\setminus M'$）を交互にたどるので、$P$ は $M$ 増加道である。$\square$
二部グラフでは、一方の部集合を飽和するマッチングの存在が近傍の大きさだけで判定できる。以下、二部グラフ $G$ の二部分割を $(A,B)$ とし、$S\subset A$ について $N(S)\subset B$ である。条件
$$|N(S)|\ge|S|\qquad(\text{すべての }S\subset A)$$
を Hall の条件 という。
有限二部グラフ $G$ の二部分割を $(A,B)$ とする。$A$ を飽和するマッチングが存在することと、Hall の条件が成り立つことは同値である。
必要性：$A$ を飽和するマッチング $M$ があれば、$S\subset A$ の各頂点に $M$ で組む相手を対応させる写像は $S$ から $N(S)$ への単射なので $|N(S)|\ge|S|$ である。
十分性：$|A|$ についての帰納法で示す。$|A|=0$ なら空のマッチングでよい。$|A|\ge1$ とし、$|A|$ より小さい場合には主張が成り立つとする。
場合 1：$A$ の空でない真部分集合 $S$ がすべて $|N(S)|\ge|S|+1$ を満たすとき。$a\in A$ をとると Hall の条件により $|N(\{a\})|\ge1$ なので、$a$ に隣接する $b\in B$ がある。$G$ から頂点 $a,b$ を除いたグラフ $G'$ は二部分割 $(A\setminus\{a\},B\setminus\{b\})$ をもつ。$S\subset A\setminus\{a\}$ が空でなければ $S$ は $A$ の空でない真部分集合なので、$|N_{G'}(S)|\ge|N_G(S)|-1\ge|S|$ である（$S=\emptyset$ では自明）。帰納法の仮定により $G'$ に $A\setminus\{a\}$ を飽和するマッチング $M'$ があり、$M'\cup\{ab\}$ は $G$ で $A$ を飽和するマッチングである。
場合 2：$A$ の空でない真部分集合 $S_0$ で $|N(S_0)|=|S_0|$ となるものがあるとき。$G_1$ を頂点集合 $S_0\cup N(S_0)$ 上の $G$ の誘導部分グラフ（部分グラフ）とする。$S\subset S_0$ なら $N_{G_1}(S)=N_G(S)$ なので $G_1$ は Hall の条件を満たし、$|S_0|<|A|$ だから帰納法の仮定により $S_0$ を飽和するマッチング $M_1$ が $G_1$ にある。次に $G_2$ を頂点集合 $(A\setminus S_0)\cup(B\setminus N(S_0))$ 上の誘導部分グラフとする。$T\subset A\setminus S_0$ について $N_{G_2}(T)=N_G(T)\setminus N(S_0)$ であり、$N_G(T\cup S_0)$ は $N_G(T)\setminus N(S_0)$ と $N(S_0)$ の交わらない和集合だから、
$$|N_{G_2}(T)|=|N_G(T\cup S_0)|-|N(S_0)|\ge|T|+|S_0|-|S_0|=|T|$$
である。$|A\setminus S_0|<|A|$ なので帰納法の仮定により $A\setminus S_0$ を飽和するマッチング $M_2$ が $G_2$ にある。$G_1$ と $G_2$ の頂点集合は交わらないので $M_1\cup M_2$ は $G$ のマッチングであり、$A$ を飽和する。$\square$
この定理は、$A$ を人の集合、$b\in N(a)$ を「$a$ と $b$ は結婚してよい」と読んで、Hall の結婚定理（Hallの結婚定理）とも呼ばれる。$|A|=|B|$ なら、$A$ を飽和するマッチングは完全マッチングである。
$k\ge1$ とし、有限二部グラフ $G$ のすべての頂点の次数が $k$ である（$k$ 正則、正則グラフ）とする。このとき $G$ は完全マッチングをもつ。
二部分割を $(A,B)$ とすると、すべての辺は $A$ の頂点をちょうど 1 つ端点にもつので $|E|=k|A|$、同様に $|E|=k|B|$ であり、$k\ge1$ より $|A|=|B|$ である。$S\subset A$ に接続する辺はちょうど $k|S|$ 本あり、それらの $B$ 側の端点は $N(S)$ に属する。$N(S)$ の各頂点に接続する辺は $k$ 本なので $k|S|\le k|N(S)|$、すなわち $|N(S)|\ge|S|$ である。thm-matching-graph-theory-hall により $A$ を飽和するマッチングがあり、$|A|=|B|$ だからそれは完全マッチングである。$\square$
$k=0$ の場合は、辺がないので頂点が 1 つでもあれば完全マッチングはなく、仮定 $k\ge1$ は外せない。
有限二部グラフ $G$ について $\nu(G)=\tau(G)$ である。
prop-matching-graph-theory-maximal-bound の 1 により $\nu(G)\le\tau(G)$ なので、大きさ $\tau(G)$ のマッチングを作ればよい。二部分割を $(A,B)$ とし、最小の頂点被覆 $C$ をとって $C_A:=C\cap A$、$C_B:=C\cap B$ とおく。
$C_A$ と $B\setminus C_B$ の間の $G$ の辺だけからなる二部グラフ $H_1$ を考え、$H_1$ が $C_A$ について Hall の条件を満たすことを示す。$S\subset C_A$ について $N_{H_1}(S)=N_G(S)\setminus C_B$ である。$|N_G(S)\setminus C_B|<|S|$ と仮定し、$C':=(C\setminus S)\cup(N_G(S)\setminus C_B)$ とおく。$S$ の頂点に接続する辺の $B$ 側の端点は $N_G(S)\subset C_B\cup(N_G(S)\setminus C_B)$ に属するので $C'$ に覆われ、その他の辺は $C\setminus S$ の頂点で覆われる。よって $C'$ は頂点被覆で $|C'|<|C|$ となり、$C$ の最小性に反する。したがって thm-matching-graph-theory-hall により、$H_1$ に $C_A$ を飽和するマッチング $M_1$ がある。
同様に、$C_B$ と $A\setminus C_A$ の間の辺からなる二部グラフで $C_B$ を飽和するマッチング $M_2$ がある。$M_1$ の辺の端点は $C_A\cup(B\setminus C_B)$ に、$M_2$ の辺の端点は $C_B\cup(A\setminus C_A)$ に属し、この 2 つの集合は交わらないので、$M_1\cup M_2$ は $G$ のマッチングであり、大きさは $|C_A|+|C_B|=|C|=\tau(G)$ である。$\square$
この等式は König の定理（Königの定理）と呼ばれる。二部グラフでないグラフでは一般に $\nu(G)<\tau(G)$ となりうる（ex-matching-graph-theory-counterexamples の 1）。
一般の有限グラフ $G=(V,E)$ と $S\subset V$ について、$G$ から $S$ の頂点を除いたグラフ $G-S$ の連結成分のうち頂点数が奇数のものの個数を $o(G-S)$ と書く。$G$ が完全マッチングをもつことと、すべての $S\subset V$ について $o(G-S)\le|S|$ であることは同値である（Tutte の定理、Die17 §2.2）。必要性は、完全マッチングでは奇数個の頂点からなる各成分から少なくとも 1 本の辺が $S$ に出て行き、それらの $S$ 側の端点が相異なることから分かる。この定理から、橋（除くと連結成分が増える辺）をもたない 3 正則グラフは完全マッチングをもつこと（Petersen の定理）が従う（同 §2.2）。
補足
- アルゴリズム：Berge の定理により、空のマッチングから始めて増加道を探し、見つかれば入れ替えることを繰り返せば最大マッチングが得られる。二部グラフでは増加道は交互道の探索で見つけられ、thm-matching-graph-theory-konig の最小頂点被覆も同時に得られる。一般のグラフでは奇閉路が探索を妨げるが、Edmonds の花（blossom）アルゴリズムにより多項式時間で最大マッチングが求まる（LP09 第 9 章）。
- 重み付きの問題と応用：重みのない二部グラフの最大マッチングは、各辺の容量を $1$ とした ネットワークフロー の最大流問題として求められる（LP09 第 2 章）。辺に重みがある二部グラフで重みの和が最大（または最小）の完全マッチングを求める割当問題は、最大流問題ではなく最小費用流問題（あるいは線形計画問題）として定式化され、ハンガリー法（Hungarian method）で解ける（LP09 第 7 章・第 9 章）。thm-matching-graph-theory-konig は最大流最小カット定理や線形計画法の双対定理の特別な場合とみることもできる（LP09 第 2 章・第 7 章）。
- 用語：マッチングの基本的な記述は Die17 第 2 章、BM08 第 16 章、Wes01 §3.1 にある。二部グラフの定義と二部分割の流儀は 二部グラフ の記事に従う。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
