ガライ・エドモンズ分解

例のグラフの Gallai-Edmonds 分解における 3 つの集合の図解。

グラフ理論において、ガライ・エドモンズ分解とは、グラフの頂点を3つの部分集合に分割するものであり、グラフ内の最大マッチング構造に関する情報を提供します。ティボール・ガライ^{[1] [2]}とジャック・エドモンズ^[3]は独立してこれを発見し、その主要な性質を証明しました。

グラフの Gallai-Edmonds 分解は、Blossom アルゴリズムを使用して求めることができます。

プロパティ

グラフ が与えられると、その Gallai–Edmonds 分解は 、、および という 3 つの互いに素な頂点集合から構成され、それらの和集合はのすべての頂点の集合となります。まず、 の頂点は必須頂点( 内のすべての最大マッチングによってカバーされる頂点) と非必須頂点( 内の少なくとも 1 つの最大マッチングではカバーされない頂点)に分割されます。集合 はすべての非必須頂点を含むと定義されます。必須頂点は と に分割されます。集合 はの少なくとも 1 つの頂点に隣接するすべての必須頂点を含むと定義され、は のどの頂点にも隣接しないすべての必須頂点を含むと定義されます。^[4]${\displaystyle G}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$

集合、、 を、それらの集合から誘導される部分グラフと同一視することは一般的です。例えば、「 の成分」とは、によって誘導される部分グラフの連結成分を意味します。 ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$

ガライ・エドモンズ分解には以下の性質がある: ^[5]

1. の成分は因数臨界グラフである。つまり、各成分は奇数個の頂点を持ち、これらの頂点のいずれか1つを省略した場合、残りの頂点は完全にマッチングする。特に、各成分はほぼ完全なマッチング、つまり1つを除くすべての頂点をカバーするマッチングを持つ。${\displaystyle D(G)}$
2. によって誘導されるサブグラフは完全マッチングを持ちます。${\displaystyle C(G)}$
3. すべての空でない部分集合には、 の少なくとも 1 つ以上の要素に近傍が存在します。${\displaystyle X\subseteq A(G)}$ ${\displaystyle |X|+1}$ ${\displaystyle D(G)}$
4. におけるすべての最大マッチングは、次の構造を持ちます。 の各要素のほぼ完全なマッチング、 の完全なマッチング、および のすべての頂点から の異なる要素へのエッジで構成されます。${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$
5. に要素がある場合、 の任意の最大マッチングにおける辺の数はです。${\displaystyle D(G)}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle {\frac {1}{2}}(|V(G)|-k+|A(G)|)}$

工事

グラフのガライ・エドモンズ分解は、多少非効率的ではありますが、最大マッチングを求める任意のアルゴリズムから始めることで求めることができます。定義より、頂点がに含まれる場合と、 （ を削除して得られるグラフ）が と同じサイズの最大マッチングを持つ場合とで同値です。したがって、すべての頂点についてと の最大マッチングを計算することで、を識別できます。 の補集合は、定義から直接 とに分割できます。${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle Gv}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle Gv}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$

グラフ内の最大マッチングを見つけるための特定の方法の 1 つに、エドモンズのブロッサム アルゴリズムがあり、このアルゴリズムによる処理により、ガライ - エドモンズ分解を直接見つけることができます。

グラフ における最大マッチングを見つけるために、ブロッサムアルゴリズムは小さなマッチングから始め、マッチングのサイズを1辺ずつ増やしながら複数の反復処理を行います。ガライ・エドモンズ分解は、ブロッサムアルゴリズムの最後の反復処理、つまり最大マッチング に達したときに行われた処理から求めることができます。この最大マッチング は、それ以上大きくすることはできません。 ${\displaystyle G}$ ${\displaystyle M}$

ブロッサムアルゴリズムは、各反復において、 「ブロッサム」と呼ばれる部分グラフを単一の頂点に縮約することで、グラフからより小さなグラフへと遷移します。最後の反復でこの処理が行われると、ブロッサムは特別な性質を持ちます。 ${\displaystyle G}$

1. 花のすべての頂点は、より大きなグラフの重要でない頂点です。
2. 花を縮小することによって形成される頂点は、小さい方のグラフの非本質的な頂点です。

最初の性質はアルゴリズムから導かれる。花の頂点はすべて、マッチングによって覆われていない頂点から始まる交互経路の終点である。2番目の性質は最初の性質から以下の補題から導かれる。 ^[6]

をグラフとし、におけるマッチングとし、を の辺を含む長さ の閉路とし、 の残りの部分とは頂点独立であるとします。から を1つの頂点に縮小して新しいグラフを構築します。すると、が における最大マッチングとなる場合、かつ が における最大マッチングとなる場合に限られます。${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle 2k+1}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle M'=ME(Z)}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle G}$

この補題は、花が収縮されたとき、花の外側の非本質的頂点の集合は同じままであることも意味します。

アルゴリズムによってすべての花が縮約されると、結果はより小さなグラフ、 と同じサイズの における最大マッチング、および に関するにおける交代フォレストとなる。 におけるガライ・エドモンズ分解は簡単に説明できる。 の頂点は内部頂点（ においてルートから奇数距離にある頂点）と外部頂点（ においてルートから偶数距離にある頂点）に分類される。 は内部頂点の集合であり、 は外部頂点の集合である。 の頂点はの形式には含まれない。^[7]${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle F'}$ ${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle A(G')}$ ${\displaystyle D(G')}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle C(G')}$

ブロッサムを縮約しても、重要でない頂点の集合は保存されます。したがって、ブロッサムの一部として縮約されたすべての頂点と 内のすべての頂点を取ることで、から を求めることができます。 と の頂点は決して縮約されません。そして です。 ${\displaystyle D(G)}$ ${\displaystyle D(G')}$ ${\displaystyle G}$ ${\displaystyle D(G')}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)=A(G')}$ ${\displaystyle C(G)=C(G')}$

一般化

ガライ・エドモンズ分解は、ダルメージ・メンデルソン分解を二部グラフから一般グラフに一般化したものである。^[8]

ガライ・エドモンズの分解定理の多辺マッチングへの拡張は、カタジナ・パルチの「容量付きランク最大マッチング」に示されている。^[9]

参考文献

1. Galrai、Tibor (1963)、「Kritsche grafen II」、Magyar Tud.アカド。マット。クタト国際空港コズル。、8 : 373–395​
2. Gallai、Tibor (1964)、「Maximale Systeme unabhängiger Kanten」、Magyar Tud.アカド。マット。クタト国際空港コズル。、9 : 401–413​
3. エドモンズ、ジャック（1965）、「道、木、花」、カナダ数学ジャーナル、17：449–467、doi：10.4153/CJM-1965-045-4、S2CID  18909734
4. ロヴァシュ、ラズロ; Plummer、Michael D. (1986)、Matching Theory (第 1 版)、北オランダ、セクション 3.2、ISBN 978-0-8218-4759-6
5. Lovász と Plummer の定理 3.2.1、p. 94
6. Lovász と Plummer の補題 9.1.1、p. 358
7. Lovász と Plummer の演習 9.1.2、p. 360
8. kピースパッキング問題に対するエドモンズ-ガライ分解」、 The Electronic Journal of Combinatorics、12、doi : 10.37236/1905、S2CID  11992200
9. Paluch, Katarzyna (2013年5月22日)、「Capacitated Rank-Maximal Matchings」、Algorithms and Complexity、Lecture Notes in Computer Science、vol. 7878、Springer、ベルリン、ハイデルベルク、pp.  324– 335、doi :10.1007/978-3-642-38233-8_27、ISBN 978-3-642-38232-1