ブロッサムアルゴリズム

グラフ理論において、ブロッサムアルゴリズムはグラフ上で最大マッチングを構成するアルゴリズムである。このアルゴリズムは1961年にジャック・エドモンズによって開発され、 ^[1] 1965年に発表された。^[2]一般グラフ $G$ $= ($ $V$ $,$ $E$ $)$ が与えられた場合、このアルゴリズムは $V$ の各頂点が $M$ の辺の1つ以下に接続し、 $|$ $M$ $|$ が最大化されるようなマッチング $M を見つける。マッチングは、グラフ内の増加パスに沿って初期の空マッチングを反復的に改善することによって構築される。$ 二部マッチングとは異なり、重要な新しいアイデアは、グラフ内の奇数長のサイクル (ブロッサム) が単一の頂点に縮小され、縮小されたグラフ内で検索が反復的に継続されるという点である。

このアルゴリズムは $O (| E || V | 2)$ の時間で実行されます。ここで、 $| E |$ はグラフの辺の数、 $| V |は$ 頂点の数です。同じタスクをより短時間で実行するには、Micali と Vazirani のより複雑なアルゴリズムを使用します。^[3] $O(|E|{\sqrt {|V|}})$

ブロッサムアルゴリズムが重要である主な理由は、最大サイズのマッチングが多項式量の計算時間で見つけられることを初めて証明したことです。もう1つの理由は、マッチング多面体の線形計画多面体記述につながり、最小重量マッチングのアルゴリズムが得られたことです。^[4]Alexander Schrijver が詳述したように、この結果のさらなる重要性は、これが整数性の証明が「単に全ユニモジュラ性から導かれるのではなく、その記述が多面体組合せ論における画期的な進歩であった」最初の多面体であったという事実にあります。^[5]

パスの拡張

$G = (V, E)と$ $G$ のマッチング $M$ が与えられたとき、 $M$ のどの辺も $v$ に接続していない場合は頂点 $vは$ 露出している。 $G$ 内のパスは、辺が交互に $Mになく$ $M$ にある場合(または $Mにあり$ $M$ にない場合)、交互パスである。増加パス $P$ は、2 つの異なる露出頂点で始まり、終わる交互パスである。増加パス内の一致しない辺の数は一致する辺の数より 1 多いため、増加パス内の辺の総数は奇数である。増加パス $Pに沿った$ マッチング増加は、 $M を$ 新しいマッチングで置き換える操作である。

M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)

。

ベルゲの補題によれば、マッチング $Mが最大となるのは、$ $Gに$ $M$ 増加パスが存在しないときのみである。^[6]^[7]したがって、マッチングは最大であるか、または増加可能である。したがって、初期マッチングから始めて、増加パスが見つかる限り現在のマッチングを増加させることで最大マッチングを計算し、増加パスが残っていないときはいつでも戻ることができる。アルゴリズムは次のように形式化できる。

   入力: グラフG、G上の初期マッチングM
   出力: G上の最大マッチングM* 
A1関数find_maximum_matching ( G、M ) : M* 
A2      P ← find_augmenting_path ( G、M ) 
A3      Pが空でない場合は A4 
find_maximum_matching          ( G 、 Pに沿ってMを増やす)を返す 
A5     そうでなければ
A6         戻りM
A7     終了の場合、 
A8終了関数

拡張パスを効率的に見つける方法をまだ説明する必要があります。拡張パスを見つけるためのサブルーチンは、ブロッサムとコンストラクションを使用します。

開花と収縮

$G = (V, E)と$ $G$ のマッチング $M が$ 与えられた場合、花 $Bは$ $G$ 内のサイクルであり、 $2$ $k$ $+ 1 個$ の辺のうち $k 個だけが$ $M$ に属し、サイクルの頂点 $vの 1 つ ($ 基底) には、 $v$ から露出した頂点 $w$ への偶数の長さの交互パス (茎)が存在することになります。

花を見つける:

公開された頂点からグラフをトラバースします。
その頂点から始めて、外側の頂点 $o$ としてラベルを付けます。
隣接する 2 つの頂点が同じラベルを持たないように、内側の $i 頂点$ と外側の $o$ 頂点の間でラベル付けを交互に行います。
最終的に 2 つの隣接する頂点が外側の $o$ としてラベル付けされると、奇数の長さのサイクルが生成され、その結果、花が咲きます。

縮約グラフ $G' を、$ $B$ のすべての辺を縮約することによって $G$ から得られるグラフとして定義し、縮約マッチング $M' を、$ $M$ に対応する $G'$ のマッチングとして定義します。

$G' が$ $M'$ 増加パスを持つのは、 $G が$ $M$ 増加パスを持つ場合のみであり、 $G'$ 内の任意の $M'$ 増加パス $P' は、$ $B$ による縮約を元に戻すことによって $G内の$ $M$ 増加パスに持ち上げることができ、その結果、 $v$ $B$ $を通過するP'$ のセグメント（存在する場合）は、 $B を$ 通過する適切なセグメントに置き換えられます。^[8]より詳しくは、次のとおりです。

$P' が$ $G'$ 内の線分 $u \to v B \to w を$ 通過する場合、この線分は $G$ 内の線分 $u$ $\to ($ $u'$ $\to \dots \to$ $w'$ $) \to$ $w$ に置き換えられます。ここで、花の頂点 $u'$ と $w'$ およびu ' から $w'$ に向かう $B$ の辺 $($ $u'$ $\to$ $\dots \to$ $w'$ $)$ は、新しいパスが依然として交互であることを保証するように選択されます ( $u'$ は、に関して公開されます)。 $M\cap B$ $\{w',w\}\in E\setminus M$

$P' が$ 終点 $v B を$ 持つ場合、 $G'$ のパスセグメント $u \to v B$ $はG$ のセグメント $u$ $\to ($ $u'$ $\to \dots \to$ $v'$ $)$ に置き換えられます。ここで、花の頂点 $u'$ と $v'$ 、および $u'から$ $v'$ に向かう $B$ の辺 $($ $u'$ $\to \dots \to$ $v'$ $)$ は、パスが交互であること ( $v'$ が露出していること) を保証するために選択されます。 $\{u',u\}\in E\setminus M$

このように、花を縮小し、縮小されたグラフ内で検索を実行できます。この縮小がエドモンズのアルゴリズムの核心です。

拡張パスを見つける

増加パスの探索では、個々のツリーがグラフ $Gの特定の部分に対応する$ フォレスト $F$ で構成される補助データ構造が使用されます。実際、フォレスト $F は、$ 二部グラフで最大マッチングを見つけるために使用されるものと同じです(縮小する花は必要ありません)。各反復で、アルゴリズムは (1) 増加パスを見つける、(2) 花を見つけて対応する縮小グラフに再帰する、または (3) 増加パスがないと結論付ける、のいずれかを行います。補助構造は、次に説明する増分手順によって構築されます。^[8]

構築手順では、 $G$ の頂点 $v$ と辺 $e を$ 考慮し、必要に応じて $F を段階的に更新します。$ $v が$ フォレストのツリー $T内にある場合、$ $T$ のルートをで表します。 $u$ と $vの両方が$ $F$ 内の同じツリー $T$ 内にある場合、 $T$ 内の $uから$ $v$ への一意のパスの長さをで表します。 root(v)distance(u,v)

    入力: グラフG、G上のMと一致する 出力: G内の
    パスPを拡張するか、見つからない場合は空のパス
B01関数 find_augmenting_path ( G , M ) : P 
B02     F ← 空のフォレストB03 G
のすべての頂点と辺のマークを外し、 Mのすべての辺をマークします
B05    公開されている各頂点vに対して実行
B06 シングルトン ツリー { v } を作成し、ツリーをFに追加します
B07    終了
B08    距離 (v、root (v))が偶数のマークされていない頂点vがFに存在する間実行
B09        マークされていない辺e = { v、w } が存在する間実行
B10             w がFに存在しない場合
                   // wは一致するため、eとw の一致する辺をFに追加します
B11                 x ← Mでwに一致する頂点
B12 辺 { v、w } と { w、x } をvのツリーに追加します
B13            それ以外の場合
B14                距離 (w、root (w))が奇数の場合    
                       // 何もしません。
B15                 else 
B16                     if  root(v) ≠ root(w)  then // F { e }
                           内の増加パスを報告します。 $\cup$ 
B17                         P ← パス (ルート( v ) → ... → v ) → ( w → ... →ルート( w ))
B18                         return  P 
B19                     else // G
                           内の花を縮小し、縮小されたグラフ内のパスを探します。
B20                         B ← Tのパスv → w上のeとエッジによって形成さ
れ                        た花
B21                         G'、M' ← BによってGとM を縮小B22 P' ← find_augmenting_path ( G'、M' )
B23                         P ← P' をGに持ち上げる
B24                         Pを返す 
B25                     if終了
B26                 if終了
B27             if 終了B28 辺e
をマーク
B29         while終了 B30 頂点v を
マーク
B31     while 終了
B32    空のパスを返す
B33終了関数

例

次の 4 つの図は、アルゴリズムの実行を示しています。破線は現在フォレスト内に存在しないエッジを示しています。まず、アルゴリズムは現在のフォレストの拡張を引き起こすフォレスト外のエッジを処理します (行 B10 ～ B12)。

次に、花が咲いていることを検出し、グラフを縮小します (行 B20 ～ B21)。

最後に、縮小されたグラフ (行 B22) で増加パス $P' を$ 見つけ、それを元のグラフ (行 B23) に持ち上げます。ここで、アルゴリズムが花を縮小する能力が重要であることに注意してください。アルゴリズムの行 B17 では、ルートから均等な距離にある頂点間のフォレスト外エッジのみが考慮されるため、アルゴリズムは元のグラフで $P を直接見つけることができません。$

分析

この関数によって構築される森林 $Fは$ find_augmenting_path()交代森林である。^[9]

$G$ 内の木Tが $M$ に関して交代木である場合、
- $Tには、$ ツリールートと呼ばれる露出頂点 $rが$ 1つだけ含まれる。
- 根から奇数距離にあるすべての頂点は $T$ にちょうど2つの接続辺を持ち、
- $rから$ $T$ の葉へのすべてのパスは長さが偶数であり、その奇数辺は $M$ に含まれず、偶数辺は $M$ に含まれる。
$G$ 内の森Fが $M$ に関して交代森である場合、
- その連結成分は交互木であり、
- $G$ の公開された頂点はすべて $F$ の交代木の根である。

行 B09 から始まるループの各反復では、 $F$ のツリー $T$ に追加するか(行 B10)、増加パスを見つけるか (行 B17)、またはブロッサムを見つけます (行 B20)。実行時間はであることが簡単にわかります。 $O(|E||V|^{2})$

二部マッチング

$G$ が二部グラフの場合、 $G$ には奇数サイクルは存在しません。その場合、花は決して見つからないため、アルゴリズムの行 B20 – B24 を削除するだけです。したがって、このアルゴリズムは、二部グラフで最大濃度マッチングを構築するための標準的なアルゴリズム^[7]に簡略化されます。このアルゴリズムでは、単純なグラフ走査によって増加パスを繰り返し検索します。これは、たとえばFord–Fulkerson アルゴリズムの場合です。

重み付けマッチング

マッチング問題は、 $G$ の辺に重みを割り当て、最大（最小）の総重みのマッチングを生成する集合Mを求めること $で一般化できます。これが$ 最大重みマッチング問題です。この問題は、重み付けされていないエドモンズのアルゴリズムをサブルーチンとして使用する組み合わせアルゴリズムによって解決できます。^[6]コルモゴロフは、これを効率的にC++で実装しています。^[10]

参考文献

^ ジャック・エドモンズ (1991)、「天国の一瞥」、JK Lenstra にて。 AHGリンノイ・カン; A. Schrijver (編)、「数学的プログラミングの歴史 --- A Collection of Personal Reminiscences」、CWI、アムステルダムおよび北オランダ、アムステルダム、32–54 ページ
^ エドモンズ、ジャック (1965)。「小道、木、花」。Can . J. Math . 17 :449–467. doi : 10.4153/CJM-1965-045-4。
^ Micali, Silvio; Vazirani, Vijay (1980)。一般グラフで最大マッチングを見つけるためのO(V ^1/2 E) アルゴリズム。第 21 回コンピュータサイエンスの基礎に関する年次シンポジウム。IEEE Computer Society Press、ニューヨーク。pp. 17–27。
^ エドモンズ、ジャック (1965)。「最大マッチングと 0,1 頂点を持つ多面体」。国立標準局セクション B 研究ジャーナル。69 : 125–130。doi : 10.6028 / jres.069B.013。
^ Schrijver, Alexander (2003). 組合せ最適化: 多面体と効率性。アルゴリズムと組合せ論。ベルリンハイデルベルク: Springer- Verlag。ISBN 9783540443896。
^ ab ロヴァース、ラースロー;マイケル・プラマー(1986)。マッチング理論。アカデミアイ・キアド。ISBN 963-05-4168-8。
^ ab Karp, Richard、「Edmonds の非二部マッチングアルゴリズム」、コースノート。UC Berkeley (PDF) 、 2008 年 12 月 30 日のオリジナル(PDF)からアーカイブ
^ ab Tarjan, Robert、「Edmonds の驚くべき Shrinking Blossom アルゴリズムによる一般マッチングに関する概略メモ」、コースノート、プリンストン大学コンピュータサイエンス学部(PDF)
^ クレア、ケニオン; Lovász, László、「Algorithmic Discrete Mathematics」、テクニカルレポート CS-TR-251-90、プリンストン大学コンピューターサイエンス学部
^ コルモゴロフ、ウラジミール (2009)、「Blossom V: 最小コスト完全マッチングアルゴリズムの新しい実装」、数学プログラミング計算、1 (1): 43–67、doi :10.1007/s12532-009-0002-8

[glimpse-1] ジャック・エドモンズ (1991)、「天国の一瞥」、JK Lenstra にて。 AHGリンノイ・カン; A. Schrijver (編)、「数学的プログラミングの歴史 --- A Collection of Personal Reminiscences」、CWI、アムステルダムおよび北オランダ、アムステルダム、32–54 ページ

[algorithm-2] エドモンズ、ジャック (1965)。「小道、木、花」。Can . J. Math . 17 :449–467. doi : 10.4153/CJM-1965-045-4。

[micali-3] Micali, Silvio; Vazirani, Vijay (1980)。一般グラフで最大マッチングを見つけるためのO(V ^1/2 E) アルゴリズム。第 21 回コンピュータサイエンスの基礎に関する年次シンポジウム。IEEE Computer Society Press、ニューヨーク。pp. 17–27。

[weighted-4] エドモンズ、ジャック (1965)。「最大マッチングと 0,1 頂点を持つ多面体」。国立標準局セクション B 研究ジャーナル。69 : 125–130。doi : 10.6028 / jres.069B.013。

[5] Schrijver, Alexander (2003). 組合せ最適化: 多面体と効率性。アルゴリズムと組合せ論。ベルリンハイデルベルク: Springer- Verlag。ISBN 9783540443896。

[matching_book-6] ロヴァース、ラースロー;マイケル・プラマー(1986)。マッチング理論。アカデミアイ・キアド。ISBN 963-05-4168-8。

[karp_notes-7] Karp, Richard、「Edmonds の非二部マッチングアルゴリズム」、コースノート。UC Berkeley (PDF) 、 2008 年 12 月 30 日のオリジナル(PDF)からアーカイブ

[tarjan_notes-8] Tarjan, Robert、「Edmonds の驚くべき Shrinking Blossom アルゴリズムによる一般マッチングに関する概略メモ」、コースノート、プリンストン大学コンピュータサイエンス学部(PDF)

[kenyon_report-9] クレア、ケニオン; Lovász, László、「Algorithmic Discrete Mathematics」、テクニカルレポート CS-TR-251-90、プリンストン大学コンピューターサイエンス学部

[blossom5-10] コルモゴロフ、ウラジミール (2009)、「Blossom V: 最小コスト完全マッチングアルゴリズムの新しい実装」、数学プログラミング計算、1 (1): 43–67、doi :10.1007/s12532-009-0002-8