Maximum-cardinality matchingEdit
組み合わせ最適化の基本的な問題は、最大マッチングを見つけることである。 この問題にはグラフのクラスごとに様々なアルゴリズムがある。
重みのない2-部グラフでは、最適化問題は最大カーディナリティ・マッチングを見つけることである。 この問題はHopcroft-Karpアルゴリズムによって時間O(√VE)で解かれるが、より効率のよいランダム化アルゴリズム、近似アルゴリズム、2部平面グラフのような特殊なクラスのグラフに対するアルゴリズムがあり、主論文で述べられている。
Maximum-weight matchingEdit
重みつき2-部グラフにおいて、最適化問題は最大荷重マッチングを見つけることであり、双対問題は最小荷重マッチングを見つけることである。 この問題はしばしば最大重み付き2部マッチング、あるいは割り当て問題と呼ばれる。 この問題を解くのがハンガリー法であり、組合せ最適化アルゴリズムの始まりの一つであった。 これは、オーグメンテーション・パス・アルゴリズムの修正された最短経路探索を用いるものである。 このステップにBellman-Fordアルゴリズムを用いると、Hungarianアルゴリズムの実行時間はO ( V 2 E ) {displaystyle O(V^{2}E)} となる。
, またはエッジコストをポテンシャルでシフトしてO ( V 2 log V + V E ) {displaystyle O(V^{2}log {V}+VE)}} を達成することが可能である。
実行時間は、ダイクストラアルゴリズムとフィボナッチヒープを使用した場合。
非2分割の重み付きグラフにおいて、最大重みマッチングの問題は時間O ( V 2 E ) {displaystyle O(V^{2}E)} で解くことができる。
Edmondsのblossomアルゴリズムを用いている。
Maximal matchingEdit
A maximal matching can be found with a simple greedy algorithm.これは単純な貪欲アルゴリズムである。 最大マッチングは最大マッチングでもあり、それゆえ多項式時間で最大の最大マッチングを見つけることが可能である。 しかし、最小の最大マッチング、すなわち可能な限り少ない数のエッジを含む最大マッチングを求める多項式時間アルゴリズムは知られていない。 逆に言えば、k個の辺を持つ最小の辺支配集合が与えられれば、k個の辺を持つ最大マッチングを多項式時間で構成することができる。 したがって、最小の最大マッチングを求める問題は、最小の辺支配集合を求める問題と本質的に等しい。 この二つの最適化問題はともにNP困難であることが知られており、これらの問題の決定版はNP完全問題の古典的な例である。 両問題とも多項式時間で係数2の範囲内で近似できる。任意の最大マッチングMを見つけるだけでよい。
Counting problemsEdit
グラフのマッチング数は細谷指数と呼ばれる。 この量を計算するのは，2部グラフでも#P-completeである． また、任意の0-1行列のpermanentを計算すること（これも#P-completeな問題）は、与えられた行列をbiadjacency行列とする2部グラフのpermaningの数を計算することと同じなので、2部グラフであってもpermaningを数えることは#P-completeである。 しかし、2部マッチングの数を数えるための完全多項式時間ランダム化近似スキームが存在します。 Kasteleynの驚くべき定理によれば、平面グラフの完全一致数はFKTアルゴリズムによって多項式時間で正確に計算できる。
完全グラフKn（偶数n）の完全一致数は、二階乗（n – 1）で与えられる！！！。
Finding all maximally-matchable edgesEdit
マッチング理論の基本的な問題の1つは、与えられたグラフで最大マッチングに拡張できるすべての辺（そのような辺はmaximally-matchable edgesまたはallowable edgesと呼ばれる）を見つけることである。 この問題に対するアルゴリズムには次のものがある：
- For general graphs, a deterministic algorithm in time O ( V E ) {displaystyle O(VE)} ←クリックすると拡大表示されます。
and randomized algorithm in time O ~ ( V 2.376 ) {displaystyle {Tilde {O}}(V^{2.376})}}.
.
- For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time O ( V + E ) {displaystyle O(V+E) }.
.
Online bipartite matchingEdit
マッチングのオンラインアルゴリズムを開発するという問題は、1990年に Richard M. Karp, Umesh Vazirani, and Vijay Vazirani によって初めて考えられました。
オンライン設定では、2部グラフの片側のノードが一度にひとつずつ届き、すぐにグラフのもう片側にマッチされるか廃棄されなければなりません。 これは秘書問題の自然な一般化であり、オンライン広告オークションへの応用がある。 ランダム到着モデルによる重み付けなしの最大化の場合、最良のオンラインアルゴリズムは0.696の競争比を達成する。