最大限にマッチするエッジ

グラフ理論では、グラフ内の最大マッチング可能な辺とは、グラフ内の少なくとも1つの最大濃度マッチングに含まれる辺のことである。 ^[1]代替用語として辺も使用できる。^{[2] [3]}

マッチング理論における基本的な問題は、グラフGが与えられたときに、 G内のすべての最大マッチング可能なエッジの集合を見つけることです。これは、 G内のすべての最大マッチングの和集合を見つけることと同等です(これは、 G内の単一の最大マッチングを見つけるというより単純な問題とは異なります)。この問題に対するアルゴリズムはいくつか知られています。

男性と女性のプールを持つ結婚仲介業者を考えてみましょう。候補者の好みを考慮して、代理店は、男性と女性が相性が良ければその男性と女性の間にエッジがある二部グラフを構築します。代理店の最終的な目標は、できるだけ多くの相性の良いカップルを作ること、つまり、このグラフで最大濃度のマッチングを見つけることです。この目標に向けて、代理店は最初にグラフのエッジを選択し、エッジの両端にいる男性と女性に会うように提案します。ここで、代理店は最大濃度のマッチングが可能なエッジのみを選択するように注意する必要があります。これは、最大濃度のマッチングが不可能なエッジを選択した場合、最大濃度のマッチングを完了できないエッジで行き詰まる可能性があるためです。^[1]

G = ( V , E ) をグラフとします。ここで、Vは頂点、Eは辺です。GのマッチングはEのサブセットMであり、Vの各頂点はMの 1 つの辺にしか隣接しません。最大マッチングは、最大の基数を持つマッチングです。

Eのエッジe は、 eを含む最大マッチングM が存在する場合、最大マッチング可能（または許可されている）と呼ばれます。

現在、一般的なグラフに対する最もよく知られている決定論的アルゴリズムは、時間で実行されます。^[2]${\displaystyle O(VE)}$

一般的なグラフには時間に対するランダム化アルゴリズムがある。^[4]${\displaystyle {\チルダ {O}}(V^{2.376})}$

二部グラフでは、単一の最大濃度マッチングがわかっている場合、最大限にマッチング可能なすべてのエッジを線形時間で見つけることが可能です 。^[1]${\displaystyle O(V+E)}$

最大マッチングが不明な場合は、既存のアルゴリズムで見つけることができます。この場合、一般的な二部グラフの場合は全体の実行時間が、密な二部グラフの場合は になります。 ${\displaystyle O(V^{1/2}E)}$${\displaystyle O((V/\log V)^{1/2}E)}$${\displaystyle E=\シータ (V^{2})}$

グラフが完全なマッチングを許容する場合、最大限にマッチング可能なエッジを見つけるアルゴリズムはより簡単になります。^{[1] ：sub.2.1}

二部グラフを （ および ）とします。完全マッチングを とします。 ${\displaystyle G=(X+Y,E)}$${\displaystyle X=(x_{1},\ldots,x_{n})}$${\displaystyle Y=(y_{1},\ldots ,y_{n})}$${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$

定理:辺eが最大限にマッチング可能であるのは、 e がM 交代サイクル( M内の辺とMにない辺が交互に現れるサイクル)に含まれている場合のみです。証明:

• e が交互サイクル内にある場合、 e はM内にあるか、サイクルを反転させることでe を含む新しい完全マッチングが得られます。したがって、e は最大限にマッチング可能です。
• 逆に、e が最大限にマッチング可能な場合、それはある完全なマッチングNに存在します。 M と N の対称差を取ることで、 e を含む交代サイクルを構築できます。

ここで、有向グラフ を考えます。ここで、 Hにから への辺が存在する場合と、 Gにとの間に辺が存在する場合とで同じです(仮定により、このような辺はMには存在しないことに注意してください)。 Gの各M交代サイクルは、 Hの有向サイクルに対応します。有向辺が有向サイクルに属する場合と、その両端点が同じ強く連結されたコンポーネントに属する場合とで同じです。すべての強く連結されたコンポーネントを線形時間で見つけるアルゴリズムがあります。したがって、最大限に一致可能なすべての辺の集合は、次のように見つけることができます。 ${\displaystyle H=(Z,E)}$${\displaystyle Z=(z_{1},\ldots ,z_{n})}$${\displaystyle z_{i}}$${\displaystyle z_{j}}$${\displaystyle i\neq j}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$

• 無向二部グラフと完全マッチングMが与えられた場合、M内のすべてのエッジを最大限マッチング可能としてマークします。${\displaystyle G=(X+Y,E)}$${\displaystyle (x_{i},y_{i})}$
• 上記のように有向グラフを構築します。${\displaystyle H=(Z,E)}$
• H内のすべての強連結成分を見つけます。
• 同じコンポーネント内にある各i、jについて、エッジを最大限一致可能としてマークします。${\displaystyle (z_{i},z_{j})}$${\displaystyle (x_{i},y_{j})}$
• 残りのすべてのエッジを最大限一致可能ではないものとしてマークします。

二部グラフを、およびとします。与えられた最大マッチングを、および とします。Eの辺は2 つのクラスに分類できます。 ${\displaystyle G=(X+Y,E)}$${\displaystyle X=(x_{1},\ldots,x_{n})}$${\displaystyle Y=(y_{1},\ldots ,y_{n'})}$${\displaystyle n\leq n'}$${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{t},y_{t})\}}$${\displaystyle t\leq n\leq n'}$

• 両端がMで飽和している辺。このような辺をM-upper と呼びます。
• ちょうど 1 つの端点がMで飽和している辺。このような辺をM 下位辺と呼びます。
• 両端がMによって飽和していないエッジは存在しないことに注意してください。これはMの最大性と矛盾するためです。

定理:すべての-下辺は最大マッチング可能である。^{[1] : サブ.2.2}証明: が飽和しており、が飽和していないと仮定する。このとき、から を削除して を追加すると、新しい最大濃度マッチングが得られる。 ${\displaystyle M}$ ${\displaystyle e=(x_{i},y_{j})}$${\displaystyle x_{i}}$${\displaystyle y_{i}}$${\displaystyle e=(x_{i},y_{j})}$${\displaystyle M}$${\displaystyle e=(x_{i},y_{j})}$

したがって、 M個の上位エッジの中で最大限にマッチング可能なエッジを見つけることが残っています。

H をM飽和ノードによって誘導されるGのサブグラフとします。M は H において完全マッチングであることに注意してください。したがって、前のサブセクションのアルゴリズムを使用すると、 Hにおいて最大限にマッチング可能なすべてのエッジを見つけることができます。Tassa ^{[1] は}、残りの最大限にマッチング可能なエッジを見つける方法と、グラフが変化したときに最大限にマッチング可能なエッジのセットを動的に更新する方法を説明しています。