マッチング

グラフ $G$ の辺集合 $M\subseteq E(G)$ で、どの 2 辺も端点を共有しないものをマッチングという。$M$ の辺の端点になっている頂点は $M$ で飽和されているといい、そうでない頂点は非飽和であるという。$uv\in M$ のとき、$v$ を $u$ の（$M$ での）相手という。辺の数が最大のマッチングを最大マッチング、その辺の数をマッチング数 $\nu(G)$ という。全頂点を飽和するマッチングを完全マッチングまたは 1-因子という。一般に、$k$-正則な全域部分グラフを $k$-因子という。