完璧なマッチング

グラフ理論では、グラフ内の完全マッチングはグラフのすべての頂点をカバーするマッチングです。より正式には、グラフG = ( V、E )が与えられた場合、 G内の完全マッチングは辺集合EのサブセットMであり、頂点集合V内のすべての頂点はM内の 1 つの辺に隣接しています。

完全マッチングは1 因子とも呼ばれます。この用語の説明については、グラフ因数分解を参照してください。一部の文献では、完全マッチングという用語が使用されています。

すべての完全マッチングは最大濃度マッチングであるが、その逆は真ではない。例えば、次のグラフを考えてみよう: ^[1]

グラフ (b) では、6 つの頂点すべてが一致しているため、完全マッチング (サイズ 3) が存在します。グラフ (a) と (c) では、最大基数マッチング (サイズ 2) が存在します。これは、一部の頂点が一致していないため、完全ではありません。

完全マッチングは最小サイズのエッジカバーでもあります。完全マッチングがある場合、マッチング数とエッジカバー数はどちらも | V | / 2に等しくなります。

完全マッチングは、グラフの頂点数が偶数の場合のみ発生します。ほぼ完全なマッチングとは、正確に 1 つの頂点が一致しないマッチングです。これは、グラフの頂点数が奇数の場合のみ発生し、このようなマッチングは最大でなければなりません。上の図の (c) は、ほぼ完全なマッチングを示しています。グラフ内のすべての頂点に対して、その頂点のみを省略したほぼ完全なマッチングがある場合、そのグラフは因子臨界とも呼ばれます。

ホールの結婚定理は、完全マッチングを持つ二部グラフの特徴付けを提供します。

Tutteの定理は任意のグラフの特性を示します。

完全マッチングは、全域1 正則サブグラフ、つまり1 因子です。一般に、全域k正則サブグラフはk因子です。

グラフが完全マッチングを持つためのスペクトル特性は、Hassani Monfared と Mallik によって次のように与えられています。 が偶数頂点のグラフで、がそれぞれ異なる非ゼロの純虚数であるとします。このとき、グラフと 固有値を持つ実対称歪行列が存在する場合のみ、 が完全マッチングを持ちます。^[2]次数 の実対称または非対称歪行列の (単純な) グラフには、の非ゼロの非対角要素によって与えられる頂点と辺があることに注意してください。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{\frac {n}{2}}>0}$${\displaystyle {\frac {n}{2}}}$${\displaystyle G}$ ${\displaystyle A}$${\displaystyle G}$ ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{\frac {n}{2}}}$${\displaystyle A}$${\displaystyle n}$${\displaystyle n}$${\displaystyle A}$

グラフが完全マッチングを許容するかどうかの決定は、最大基数マッチングを見つけるための任意のアルゴリズムを使用して、多項式時間で行うことができます。

しかし、たとえ二部グラフであっても、完全マッチングの数を数えることは#P 完全です。これは、任意の 0–1 行列のパーマネントを計算すること(別の #P 完全問題) が、与えられた行列をその双方向隣接行列として持つ二部グラフの完全マッチングの数を計算することと同じであるためです。

Kasteleynの注目すべき定理によれば、平面グラフ内の完全マッチングの数はFKT アルゴリズムによって多項式時間で正確に計算できるとされています。

完全グラフ K _n（nは偶数）における完全マッチングの数は二重階乗で与えられる：^[3]${\displaystyle (n-1)!!}$

辺色グラフは、各マッチングで各頂点が正確に1回カバーされるため、完全マッチングの数に等しい数の（必ずしも適切ではない）頂点彩色を誘導することができる。この特性は量子物理学^[4]と計算複雑性理論^[5]で研究されてきた。

グラフの完全マッチング多面体とは、各コーナーが完全マッチングの接続ベクトルである R ^{|E|内の多面体です。}

• 嫉妬のないマッチング
• 最大基数マッチング
• 高次ハイパーグラフにおける完全マッチング
• ハイパーグラフのホール型定理
• 唯一の完全マッチング問題^{[6] [7] [8]}