マッチング多面体

グラフ理論において、与えられたグラフのマッチング多面体とは、グラフ内の可能なマッチングを表す幾何学的オブジェクトである。これは凸多面体であり、各頂点はマッチングに対応する。マッチング理論において理論的に大きな重要性を持つ。^{[1] : 273–285}

G = ( V , E ) をn = | V | 個のノードとm = | E | 個のエッジを持つグラフとします。

頂点のすべてのサブセットUについて、その接続ベクトル 1 _Uはサイズnのベクトルであり、要素vは、ノード v がU内にある場合は 1 、そうでない場合は 0 になります。同様に、エッジのすべてのサブセットFについて、その接続ベクトル1 _{Fはサイズ}mのベクトルであり、要素eは、エッジeがF内にある場合は 1 、そうでない場合は 0 になります。

V内のすべてのノードvについて、 vに隣接するE内のエッジの集合はE ( v )で表されます。したがって、各ベクトル1 _E(v)は 1 行m 列のベクトルであり、その要素eは、エッジeがvに隣接する場合は 1 、そうでない場合は 0 になります。グラフの接続行列はA _Gで表され、各行 v が接続ベクトル1 _E(V)であるn行m列の行列です。つまり、行列内の各要素v、eは、ノードv がエッジeに隣接する場合は 1 、そうでない場合は 0 になります。

以下に、接続行列の 3 つの例を示します。三角形グラフ(長さ 3 のサイクル)、正方形グラフ (長さ 4 のサイクル)、および 4 つの頂点を持つ完全グラフです。

エッジのすべてのサブセットFについて、ドット積 1 _E(v) · 1 _{F は、} vに隣接するF 内のエッジの数を表します。したがって、次のステートメントは同等です。

• エッジのサブセットFは G内のマッチングを表します。
• V内のすべてのノードvについて: 1 _E(v) · 1 _F ≤ 1。
• A _G · 1 _F ≤ 1 _V。

辺の 集合Fの濃度はドット積 1 _E · 1 _{Fである 。} したがって、Gにおける最大濃度マッチングは次の整数線形計画によって与えられる。

1 _E · xを最大化する

条件: xは{0,1} ^m内

__________ A _G · x ≤ 1 _V。

グラフGの分数マッチング多面体 （FMP( G )と表記）は、上記の線形計画の緩和によって定義される多面体であり、各xは整数だけでなく分数になることもあります。

1 _E · xを最大化する

条件: x ≥ 0 _E

__________ A _G · x ≤ 1 _V。

これは線形計画法です。m個の「少なくとも 0」制約とn 個の「1 未満」制約があります。その実行可能な解の集合は凸多面体です。この多面体の各点は分数マッチングです。たとえば、三角形のグラフには3 つの辺があり、対応する線形計画法には次の 6 つの制約があります。

x ₁ +x ₂ +x _{3を最大化}

ただし、x ₁ ≥0、x ₂ ≥0、x ₃ ≥0となります_。

__________ x ₁ +x ₂ ≤1 、x ₂ +x ₃ ≤1、x ₃ +x ₁ ≤1。

この不等式の集合は、3 次元ユークリッド空間 R ³内の多面体を表します。

多面体には 5 つのコーナー (端点) があります。これらは、6 つの定義不等式のうち 3 つで等式を達成する点です。コーナーは (0,0,0)、(1,0,0)、(0,1,0)、(0,0,1)、(1/2,1/2,1/2) です。^[2]最初のコーナー (0,0,0) は、自明な (空の) マッチングを表します。次の 3 つのコーナー (1,0,0)、(0,1,0)、(0,0,1) は、サイズ 1 の 3 つのマッチングを表します。5 番目のコーナー (1/2,1/2,1/2) は、マッチングを表しません。これは、各エッジが「半分入っていて、半分出ている」分数マッチングを表します。これは、このグラフで最大の分数マッチングであることに注意してください。サイズが 1 の 3 つの整数マッチングとは対照的に、重みは 3/2 です。

別の例として、4 サイクルには 4 つのエッジがあります。対応する LP には 4+4=8 の制約があります。FMP はR ⁴の凸多面体です。この多面体のコーナーは (0,0,0,0)、(1,0,0,0)、(0,1,0,0)、(0,0,1,0)、(0,0,0,1)、(1,0,1,0)、(0,1,0,1) です。最後の 2 つのコーナーはそれぞれ、最大マッチングであるサイズ 2 のマッチングを表します。この場合、すべてのコーナーの座標は整数であることに注意してください。

グラフGの積分マッチング多面体(通常は単にマッチング多面体と呼ばれる) はMP( G ) と表記され、その頂点がGの積分マッチングの接続ベクトルである多面体です。

MP( G ) は常に FMP( G ) に含まれます。上記の例では、

• 三角形グラフの MP は非整数コーナー (1/2, 1/2, 1/2) を含まないため、FMP に厳密に含まれます。
• 4 サイクル グラフの MP は、FMP のすべてのコーナーが整数であるため、FMP と同一です。

上記の例は、次の一般定理の特別な場合である: ^{[1] : 274}

G が二部グラフである 場合、かつその場合に限り、MP( G ) = FMP( G ) であり、かつその場合に限り、FMP( G ) のすべての角は整数座標のみを持ちます。

この定理はいくつかの方法で証明できます。

Gが二部行列の場合、その接続行列A _{G は}完全にユニモジュラです。つまり、そのすべての正方部分行列の行列式は 0、+1、または -1 です。証明は、部分行列のサイズ ( Kで表す) kに関する帰納法によって行われます。基数k = 1 は、 A _G の定義から得られます。つまり、そのすべての要素は 0 または 1 です。k >1 の場合、いくつかのケースがあります。

• K にゼロのみで構成される列がある場合、det K = 0 になります。
• K に1 つの 1 を含む列がある場合、det K はこの列について展開でき、( k  − 1) 行 ( k  − 1) 列の行列式の +1 倍または -1 倍に等しくなります。これは、帰納法の仮定により 0 または +1 または -1 になります。
• それ以外の場合、Kの各列には 1 が 2 つあります。グラフは二部グラフなので、行を 2 つのサブセットに分割できます。各列では、1 つの 1 が上部サブセットに、もう 1 つの 1 が下部サブセットにあります。つまり、上部サブセットの合計と下部サブセットの合計は、どちらも1 _Eマイナス | E |の 1 のベクトルに等しいということです。つまり、 Kの行は線形従属なので、det  K  = 0 です。

たとえば、4 サイクル (二部) では、det  A _G = 1 です。対照的に、3 サイクル (二部ではない) では、det  A _G  = 2 です。

FMP( G ) の各コーナーは、等式を伴うm 個の線形独立不等式の集合を満たします。したがって、コーナーの座標を計算するには、 A _Gの正方部分行列によって定義される連立方程式を解く必要があります。クラメールの規則により、解は分母がこの部分行列の行列式である有理数です。この行列式は +1 または -1 でなければならないため、解は整数ベクトルです。したがって、すべてのコーナーの座標は整数です。

n 個の「1 未満」制約により、コーナーの座標は 0 または 1 のいずれかになります。したがって、各コーナーはG内の積分マッチングの発生ベクトルです。したがって、FMP( G ) = MP( G ) です。

多面体の面とは、多面体の本質的な定義不等式を等式で満たす点の集合である。多面体が d次元の場合、その面は ( d  − 1) 次元である。任意のグラフGに対して、 MP( G )の面は次の不等式で与えられる: ^{[1] : 275–279}

• x ≥ 0 _E
• 1 _{E ( v )} · x ≤ 1 (ここで、 v は孤立していない頂点であり、v に隣接する頂点がuのみである場合、{ u , v } は G の連結成分であり、v に隣接する頂点がちょうど 2 つある場合、それらは隣接していません)。
• 1 _{E ( S )} · x ≤ (| S | − 1)/2 （ここでS は2連結因子臨界サブグラフを張る。）

グラフGの 完全マッチング多面体(PMP( G ) と表記) は、その頂点がGの完全マッチングの入射ベクトルである多面体です。^{[1] : 274}明らかに、PMP( G ) は MP( G )に含まれます。実際、PMP(G) は MP( G )の面であり、次の等式によって決定されます。

1 _E · x = n / 2です。

エドモンズ^[3]は、あらゆるグラフGに対して、PMP(G)は次の制約によって記述できることを証明した。

1 _E(v) · x = 1 はV内のすべてのv に対して成り立ちます (-- vに隣接する 1 つの辺だけがマッチングに含まれます)

1 _E(W) · x ≥ 1 であり、 |W| が奇数であるVのすべての部分集合Wに対して成り立ちます (少なくとも 1 つの辺が W を V\W に接続している必要があります)。これらの制約は奇数カット制約と呼ばれます。

x ≥ 0 _E

この特徴付けとファルカスの補題を用いると、完全マッチングを持つグラフの良好な特徴付けが得られる。^{[4] : 206}凸集合上のアルゴリズム問題を解くことで、最小重みの完全マッチングを見つけることができる。^{[4] : 206--208}

• 安定マッチング多面体

• 一致する多面体、マイケル・ゴーマンス著
• マッチング多面体、Jan Vondrak 作
• 一致する多面体、ヴィンセント・ジョスト作