マッチング（グラフ理論）

ケーニッヒの定理は、二部グラフにおいて、最大マッチングのサイズは最小頂点被覆のサイズと等しいことを述べている。この定理により、二部グラフにおける最小頂点被覆、最大独立集合、および最大頂点二部グラフの問題を多項式時間で解くことができる。

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

グラフのマッチング数のスペクトル特性は、Hassani MonfaredとMallikによって次のように与えられています。${\displaystyle G}$グラフになる${\displaystyle n}$頂点、そして${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$なれ${\displaystyle k}$異なる非ゼロの純虚数${\displaystyle 2k\leq n}$.次に一致する数${\displaystyle G}$は${\displaystyle k}$（a）実数の歪対称行列が存在する場合に限る${\displaystyle A}$グラフ付き${\displaystyle G}$および 固有値${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$そして${\displaystyle n-2k}$ゼロ、および (b) グラフがゼロであるすべての実数歪対称行列${\displaystyle G}$最大で${\displaystyle 2k}$非ゼロ固有値。^{[ 7 ]}実対称行列または歪対称行列の（単純な）グラフは、${\displaystyle A}$順序の${\displaystyle n}$もっている${\displaystyle n}$非ゼロの非対角要素によって与えられる頂点と辺${\displaystyle A}$。

AとBが2つの極大マッチングである場合、 | A |  ≤  2| B |および| B |  ≤  2| A |が成り立つ。これを確認するには、Aはマッチングであるため、 B  \ Aの各辺は A  \ B の2つの辺に最大で隣接できることに注目する。さらに、Bの極大性により、 A \ Bの各辺はB \ Aの辺に隣接しているため、    

${\displaystyle |A\setminus B|\leq 2|B\setminus A|.}$

さらに我々は次のように推論する。

${\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}$

特に、これは任意の最大マッチングが最大マッチングの2近似であり、かつ最小最大マッチングの2近似でもあることを示しています。この不等式は厳密です。例えば、Gが3つの辺と4つの頂点を持つパスである場合、最小最大マッチングのサイズは1であり、最大マッチングのサイズは2です。

組み合わせ最適化における基本的な問題の一つは、最大マッチングを見つけることである。この問題には、グラフの種類に応じて様々なアルゴリズムが存在する。

重み付けされていない二部グラフでは、最適化問題は最大カーディナリティのマッチングを見つけることです。この問題は、ホップクロフト・カープアルゴリズムによってO(√VE)の時間で解決されますが、メイン記事で説明されているように、より効率的なランダム化アルゴリズム、近似アルゴリズム、および二部平面グラフなどの特殊なグラフクラス向けのアルゴリズムも存在します。

重み付き 二部グラフでは、最適化問題は最大重みマッチングを見つけることであり、双対問題は最小重みマッチングを見つけることです。この問題は、最大重み付き二部マッチング、または割り当て問題と呼ばれることがよくあります。ハンガリーアルゴリズムは割り当て問題を解決し、組み合わせ最適化アルゴリズムの初期のものの1つです。これは、増加パスアルゴリズムで修正された最短経路探索を使用します。このステップでベルマン・フォードアルゴリズムを使用すると、ハンガリーアルゴリズムの実行時間は${\displaystyle O(V^{2}E)}$または、エッジコストをシフトして達成できる可能性があります${\displaystyle O(V^{2}\log {V}+VE)}$ダイクストラ法とフィボナッチヒープを用いた実行時間。^{[ 8 ]}

非二部グラフの重み付きグラフでは、最大重みマッチングの問題は時間で解くことができる。 ${\displaystyle O(V^{2}E)}$エドモンズの開花アルゴリズムを使用する。

最大マッチングは単純な貪欲アルゴリズムで見つけることができます。最大マッチングは最大マッチングでもあるため、多項式時間で最大の最大マッチングを見つけることが可能です。また、高速行列乗算アルゴリズムを使用して最大マッチングを見つけることも可能で、その時間は${\displaystyle O({n^{\omega }})}$のために${\displaystyle ~2.37\leq \omega <3}$^{[ 9 ]}しかし、最小最大マッチング限り最小数のエッジを含む最大マッチングを見つけるための多項式時間アルゴリズムは知られていない。

k個のエッジを持つ最大マッチングは、 k個のエッジを持つエッジ支配集合です。逆に、 k個のエッジを持つ最小エッジ支配集合が与えられた場合、多項式時間でk個のエッジを持つ最大マッチングを構築できます。したがって、最小最大マッチングを見つける問題は、本質的に最小エッジ支配集合を見つける問題と同じです。^{[ 10 ]}これらの 2 つの最適化問題はどちらもNP 困難であることが知られています。これらの問題の決定バージョンは、NP 完全問題の古典的な例です。^{[ 11 ]}どちらの問題も、多項式時間で係数 2 以内で近似できます。任意の最大マッチングMを見つけるだけです。^{[ 12 ]}

グラフ内のマッチングの数は、グラフのホソヤ指数として知られています。この量を計算することは、二部グラフであっても#P 完全です。 ^{[ 13 ]}完全マッチングの数を数えることも、二部グラフであっても#P 完全です。これは、任意の 0-1 行列のパーマネントを計算すること(別の #P 完全問題) が、与えられた行列を二部隣接行列として持つ二部グラフ内の完全マッチングの数を計算することと同じであるためです。ただし、二部マッチングの数を数えるための完全多項式時間ランダム化近似スキームが存在します。^{[ 14 ]}カステレインの注目すべき定理は、平面グラフ内の完全マッチングの数は、 FKT アルゴリズムによって正確に多項式時間で計算できると述べています。

完全グラフK _n (n は偶数)における完全マッチングの数は、二重階乗( n − 1)!! で与えられる。^{[ 15 ]}マッチングを完全であるという制約なしに、完全グラフにおけるマッチングの数は、電話番号で与えられる。^{[ 16 ]}  

グラフにおける完全一致の数は、その隣接行列のハフニアンとしても知られています。

マッチング理論における基本的な問題の一つは、与えられたグラフにおいて、グラフ内で最大マッチングに拡張可能なすべてのエッジ（このようなエッジは最大マッチング可能なエッジ、または許容エッジと呼ばれる）を見つけることである。この問題に対するアルゴリズムには以下のようなものがある。

• 一般的なグラフの場合、時間で決定論的アルゴリズム${\displaystyle O(VE)}$そして時間におけるランダム化アルゴリズム${\displaystyle {\チルダ {O}}(V^{2.376})}$[ ^{17 ] [ 18 ]​}
• 二部グラフの場合、単一の最大マッチングが見つかった場合、決定論的アルゴリズムは時間で実行されます。${\displaystyle O(V+E)}$[ ^{19 ]​}

オンラインマッチングアルゴリズムの開発という問題は、1990年にリチャード・M・カープ、ウメシュ・ヴァジラニ、ヴィジャイ・ヴァジラニによって初めて検討された^{。[ 20 ]}

オンライン環境では、二部グラフの一方の側のノード（「クライアント」）は一度に 1 つずつ到着し、グラフのもう一方の側（「サーバー」）にすぐにマッチングされるか、破棄される必要があります。これは秘書問題の自然な一般化であり、オンライン広告オークションに応用できます。単純な貪欲アルゴリズムは 1/2 の競争率です。ランダム到着モデルによる重み付けなしの最大化の場合、Karp、Vazirani、および Vazirani は、競争率0.632を達成するランダム化アルゴリズムを提供しました。この上限は後に0.696に改善されました。^{[ 21 ]} この問題は、クライアントがマッチングを改善するためにサーバーを切り替えることができるモデルでも研究されており、目標は最大のマッチングを達成しながら切り替えの数を節約することです。^{[ 22 ]}

• 芳香族化合物のケクレ構造は、その炭素骨格の完全な一致から成り、化学構造中の二重結合の位置を示しています。これらの構造は、ベンゼン（グラフ理論の用語では6頂点サイクル）にそのような構造を与えることができることを示したフリードリヒ・アウグスト・ケクレ・フォン・ストラドニッツにちなんで名付けられました。^{[ 23 ]}
• 細谷指数は、空でないマッチングの数に1を加えた値であり、有機化合物の計算化学および数理化学の研究に用いられる。
• 中国の郵便配達員問題には、最小重みの完全マッチングを見つけるという部分問題が含まれる。

• 卒業問題とは、卒業に必要な要件の中から、最低限履修すべき科目を選択することである。
• ヒッチコック輸送問題には、部分問題として二部グラフマッチングが含まれる。
• 部分木同型性問題には、部分問題として二部グラフマッチングが含まれる。