الگوریتم ادمون

در نظریه گراف، شاخه‌ای از ریاضیات، الگوریتم ادمون برای پیدا کردن انشعاب بهینهٔ بیشینه یا کمینه به کار می‌رود. زمانی که راس‌ها با یال‌های وزن دار و جهت دار به یکدیگر متصل شده باشند، دیگر نمی‌توانیم از الگوریتم درخت پوشای کمینه استفاده کنیم. بنابراین از الگوریتم انشعاب بهینه استفاده می‌کنیم که در سال ۱۹۶۷ توسط ادمون ارائه شد. برای یافتن مسیر با طول بیشینه، ابتدا یال‌ها بر اساس وزن شان مرتب می‌شوند. از بزرگترین یال شروع کرده و آن یال بین دو راس قرار می‌گیرد. بعد از آن به سراغ یال بزرگتر بعدی رفته و همین کار برای باقی یال‌ها نیز انجام می‌شود. اگر یالی باعث ایجاد دور در گراف شود، آن یال حذف می‌شود. برای پیدا کردن مسیر با طول کمینه نیز، یال‌ها از کوچک به بزرگ مرتب می‌شوند و کار با یال کوچکتر شروع می‌شود.

زمان اجرا

زمان اجرای این الگوریتم برابر با $O(EV)$ است. پیاده‌سازی سریعتری از این الگوریتم، توسط روبرت تارجان ارائه شد که زمان اجرای آن برای یک گراف نا متراکم $O(E\log V)$ و برای گراف متراکم برابر با $O(V^{2})$ است. زمان اجرای آن به تندی الگوریتم پریم، برای یافتن درخت پوشای کمینهٔ بدون جهت است. بعدها در سال ۱۹۸۶، گابو، گلیل، اسپنسر، و تارجان پیاده‌سازی سریعتری را ارائه کردند که زمان اجرای آن برابر است با $O(E+V\log V)$.

الگوریتم

تابعی مانند $f$ را در نظر می‌گیریم که به عنوان ورودی، یک گراف وزن دار و جهت دار $D$ و یک راس $r$ به عنوان ریشه می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با ریشهٔ $r$، به ما می‌دهد.
توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار مانند $D$، با ریشهٔ $r$، به این صورت عمل می‌کنیم که در ابتدا، مجموعهٔ یال‌های موازی(یال‌هایی که بین دو راس یکسان قرار دارند و دارای یک جهت می‌باشند) را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم.

توصیف

این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند $f$ را در نظر می‌گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار $D$، با یک راس $r$ به عنوان ریشه را می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می‌دهد.
توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار $D$ با ریشهٔ $r$، در ابتدا به این صورت عمل می‌کنیم که مجموعه‌ای از یال‌های موازی (یال‌های بین دو راس یکسان که دارای یک جهت هستند)را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم.
حالا برای هر راس $v$ به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه‌است را علامت(به‌طور قراردادی) می‌زنیم. راسی که در سر دیگر این یال قرار دارد را با $\pi (v)$ مشخص می‌کنیم. اگر یال‌های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می‌دادند، یعنی تابع $f(D)$ این SRT را مشخص کرده‌است. در غیر این صورت، مجموعه یال‌های علامت زده شده، تشکیل حداقل یک دور را می‌دهند. یکی از دورها را (به صورت دلخواه) $C$ بنامید. حالا ما یک گراف وزن دار و جهت دار $D^{\prime }$ که دارای ریشه $r^{\prime }$ است را تعریف می‌کنیم. به این صورت که، راس‌های $D^{\prime }$ مانند راس‌های $D$ هستند نه $C$، به اضافه یک راس جدید که با $v_{C}$ مشخص می‌شود.
اگر $(u,v)$ یالی در $D$ باشد، با این شرط که $u\notin C$، یال $e$ را به صورت شرح داده شده در زیر به $D^{\prime }$ اضافه می‌کنیم.
اگر $v\in C$، $e=(u,v_{C})$ و $w(e)=w(u,v)-w(\pi (v),v)$
در غیر این صورت، اگر $v\notin C$، $e=(u,v)$ و and $w(e)=w(u,v)$.
ما هیچ یال دیگری را به $D^{\prime }$ اضافه نمی‌کنیم.
ریشهٔ $r^{\prime }$ در $D^{\prime }$، همان ریشهٔ $r$ در $D$. است.
با صدا کردن تابع $f(D^{\prime })$، یک SRT در $D^{\prime }$ می‌یابیم. در نظر داشته باشید که در این SRT، یال ورودی (یکتا) به $v_{C}$، یال $(u,v_{C})$ است. این یال می‌تواند از زوج مرتب‌هایی مانند $(u,v)$ با شرط $u\notin C$ و $v\in C$ باشد. علامت $(\pi (v),v)$ را بردارید و $(u,v)$ را علامت بزنید. حالا مجموعه یال‌های علامت زده شده، یک SRT می‌سازند که ما می‌توانیم آن را مقدار تابع $f(D)$ در نظر بگیریم.
دقت کنید که تابع $f(D)$ به وسیله تابع $f(D^{\prime })$ تعریف شده‌است. و تابع $D^{\prime }$ که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف $D$ به شدت تعداد راس‌هایش کمتر است و استفاده از $f(D)$ برای یک گراف تک راس، کاری بیهوده‌است.

پیاده سازی

BV را یک مجموعه‌ای برای رئوس و BE را مجموعه‌ای برای یال‌ها در نظر بگیرید. اگر V را یک راس در نظر بگیرید و e هم یالی با بیشترین وزن مثبت و متصل به V باشد، C_i یک دور خواهد بود. G_۰ = (V_۰,E_۰) گراف اصلی است و u_i یک راس جانشین برای C_i است.

$BV\leftarrow BE\leftarrow \varnothing$
i=0


A:
if $BV=V_{i}$ then goto B
for some vertex $v\notin BV$ and $v\in V_{i}$ {
   $BV\leftarrow BV\cup \lbrace v\rbrace$
   find an edge $e=(x,v)$ such that w(e) = max{ w(y,v)|(y,v) $\in$ Ei}
   if w(e) ≤ 0 then goto A
}
if $BE\cup \lbrace e\rbrace$ contains a circuit {
   i=i+1
   construct $G_{i}$ by shrinking $C_{i}$ to $u_{i}$
   modify BE, BV and some edge weights
}
$BE\leftarrow BE\cup {e}$
goto A


B:
while i ≠ 0 {
   reconstruct $G_{i-1}$ and rename some edges in BE
   if $u_{i}$ was a root of an out-tree in BE {
       $BE\leftarrow BE\cup \lbrace e|e\in C_{i}$ and $e\neq e_{0}^{i}\rbrace$
   }else{
       $BE\leftarrow BE\cup \lbrace e|e\in C_{i}$ and $e\neq {\tilde {e}}_{i}\rbrace$
   }
   i=i-1
}
Maximum branching weight = $\sum _{e\in BE}w(e)$

منابع

• Y. J. Chu and T. H. Liu, "On the Shortest Arborescence of a Directed Graph", Science Sinica, vol. 14, 1965, pp.  1396–1400.
• J. Edmonds, “Optimum Branchings”, J. Res. Nat. Bur. Standards, vol. 71B, 1967, pp.  233–240.
• R. E. Tarjan, "Finding Optimum Branchings", Networks, v.7, 1977, pp.  25–35.
• P.M. Camerini, L. Fratta, and F. Maffioli, "A note on finding optimum branchings", Networks, v.9, 1979, pp.  309–312.
• Alan Gibbons Algorithmic Graph Theory, Cambridge University press, 1985 ISBN 0-521-28881-9
• H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica 6 (1986), 109-122.

پیوند به بیرون

• The Directed Minimum Spanning Tree Problem Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
• Edmonds's algorithm (edmonds-alg) – An متن‌باز implementation of Edmonds's algorithm written in C++ and licensed under the پروانه ام‌آی‌تی. This source is using Tarjan's implementation for the dense graph.
• AlgoWiki – Edmonds's algorithm - A public-domain implementation of Edmonds's algorithm written in Java.