エドモンズのアルゴリズム

グラフ理論において、エドモンズのアルゴリズムまたはチュー・リウ/エドモンズのアルゴリズムは、最小の重みを持つ全域木（最適分岐と呼ばれることもある）を見つけるアルゴリズムである。これは、最小全域木問題の有向類似物である。このアルゴリズムは、最初はヨン・ジン・チューとツェン・ホン・リウ（1965年）によって独立に提案され、その後ジャック・エドモンズ（1967年）によって提案された。

このアルゴリズムは、有向グラフ( はノードの集合、は有向エッジの集合)、ルートと呼ばれる特別な頂点、および各エッジの実数値の重みを入力として受け取ります。最小の重み を根とする全域樹状線 を返します。ここで、樹状線の重みは、そのエッジの重み の合計として定義されます。 ${\displaystyle D=\langle V,E\rangle }$${\displaystyle V}$${\displaystyle E}$${\displaystyle r\in V}$${\displaystyle w(e)}$${\displaystyle e\in E}$ ${\displaystyle A}$${\displaystyle r}$${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$

アルゴリズムは再帰的に記述されます。最小の重みを持つ を根とする全域樹状線を返す関数を とします。まず、 から宛先がであるエッジをすべて削除します。また、任意の平行エッジ セット (同じ方向にある同じ 2 つの頂点間のエッジ) を、これらの平行エッジの重みの最小値に等しい重みを持つ単一のエッジに置き換えることもできます。 ${\displaystyle f(D,r,w)}$${\displaystyle r}$${\displaystyle E}$${\displaystyle r}$

ここで、ルート以外の各ノードについて、 に入るエッジのうち、重みが最も小さいものを見つけます (同点の場合は任意に決定します)。このエッジのソースを で表します。エッジの集合にサイクルが含まれていない場合は、 となります。 ${\displaystyle v}$${\displaystyle v}$${\displaystyle \pi (v)}$${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$${\displaystyle f(D,r,w)=P}$

それ以外の場合、には少なくとも 1 つのサイクルが含まれます。これらのサイクルの 1 つを任意に選択し、 と呼びます。ここで、サイクルが 1 つのノードに「縮小」された新しい重み付き有向グラフを次のように定義します。 ${\displaystyle P}$${\displaystyle C}$${\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }$${\displaystyle C}$

のノードは、に含まれないのノードと、で示される新しいノードです。 ${\displaystyle V^{\prime}}$${\displaystyle V}$${\displaystyle C}$${\displaystyle v_{C}}$

• が 内の辺であり、 （サイクルに入ってくる辺）である場合 、新しい辺 に を含め、を定義します。${\displaystyle (u,v)}$${\displaystyle E}$${\displaystyle u\notin C}$${\displaystyle v\in C}$${\displaystyle E^{\prime}}$${\displaystyle e=(u,v_{C})}$${\displaystyle w^{\prime }(e)=w(u,v)-w(\pi (v),v)}$
• が 内の辺であり、（サイクルから離れる辺）である場合、新しい辺に を含め、 を定義します。${\displaystyle (u,v)}$${\displaystyle E}$${\displaystyle u\in C}$${\displaystyle v\notin C}$${\displaystyle E^{\prime}}$${\displaystyle e=(v_{C},v)}$${\displaystyle w^{\prime }(e)=w(u,v)}$
• が および（サイクルとは無関係のエッジ）を含む内のエッジである場合、 を新しいエッジに含め、 を定義します。${\displaystyle (u,v)}$${\displaystyle E}$${\displaystyle u\notin C}$${\displaystyle v\notin C}$${\displaystyle E^{\prime}}$${\displaystyle e=(u,v)}$${\displaystyle w^{\prime }(e)=w(u,v)}$

の各エッジについて、それが のどのエッジに対応するかを記憶します。 ${\displaystyle E^{\prime}}$${\displaystyle E}$

ここで、の呼び出しを使用して、の最小全域樹状線を見つけます。は全域樹状線なので、各頂点にはちょうど 1 つの入ってくる辺があります。におけるへの唯一の入ってくる辺を とします。この辺はの辺に対応します。から辺を削除して、サイクルを破壊します。 の残りの各辺にマークを付けます。 の各辺に対して、 の対応する辺にマークを付けます。ここで、を最小全域樹状線を形成するマークされた辺の集合と 定義します。${\displaystyle A^{\prime}}$${\displaystyle D^{\prime}}$${\displaystyle f(D^{\prime },r,w^{\prime })}$${\displaystyle A^{\prime}}$${\displaystyle (u,v_{C})}$${\displaystyle v_{C}}$${\displaystyle A^{\prime}}$${\displaystyle (u,v)\in E}$${\displaystyle v\in C}$${\displaystyle (\pi (v),v)}$${\displaystyle C}$${\displaystyle C}$${\displaystyle A^{\prime}}$${\displaystyle E}$${\displaystyle f(D,r,w)}$

はによって定義され、の頂点の数は より確実に少ないことに注意してください。単一頂点グラフ の検出は簡単 (それ自体である) なので、再帰アルゴリズムは必ず終了します。 ${\displaystyle f(D,r,w)}$${\displaystyle f(D^{\prime },r,w^{\prime })}$${\displaystyle D^{\prime}}$${\displaystyle D}$${\displaystyle f(D,r,w)}$${\displaystyle D}$

このアルゴリズムの実行時間は です。Robert Tarjanによるこのアルゴリズムのより高速な実装は、疎グラフでも密グラフでも で実行されます。これは、無向最小全域木に対するPrim のアルゴリズムと同じ速さです。1986 年に、Gabow、Galil、Spencer、およびTarjan は、実行時間 のより高速な実装を作成しました。 ${\displaystyle O(EV)}$${\displaystyle O(E\log V)}$${\displaystyle O(V^{2})}$${\displaystyle O(E+V\log V)}$

• チュー・ヨンジン、リウ・ツェンホン（1965）「有向グラフの最短樹状突起について」（PDF）、中央科学、XIV（10）：1396–1400
• エドモンズ、J. (1967)、「最適分岐」、国立標準局研究ジャーナルセクションB、71B (4): 233–240、doi : 10.6028/jres.071b.032
• Tarjan, RE (1977)、「最適な分岐を見つける」、Networks、7 : 25–35、doi :10.1002/net.3230070103
• カメリーニ首相。フラッタ、L. Maffioli, F. (1979)、「最適な分岐の発見に関するメモ」、Networks、9 (4): 309–312、doi :10.1002/net.3230090403
• ギボンズ、アラン（1985）、アルゴリズムグラフ理論、ケンブリッジ大学出版局、ISBN 0-521-28881-9
• Gabow, HN ; Galil, Z. ; Spencer, T.; Tarjan, RE (1986)、「無向グラフと有向グラフの最小全域木を見つけるための効率的なアルゴリズム」、Combinatorica、6 (2): 109–122、doi :10.1007/bf02579168、S2CID  35618095

• Edmonds のアルゴリズム (edmonds-alg) – C++で記述され、MIT ライセンスの下でライセンスされているEdmonds のアルゴリズムの実装。このソースは、密なグラフに Tarjan の実装を使用しています。
• BSDで配布されているPythonライブラリである NetworkX には、Edmonds のアルゴリズムが実装されています。