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

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

زمان اجرا

زمان اجرای این الگوریتم برابر با  است. پیاده‌سازی سریعتری از این الگوریتم، توسط روبرت تارجان ارائه شد که زمان اجرای آن برای یک گراف نا متراکم  و برای گراف متراکم برابر با  است. زمان اجرای آن به تندی الگوریتم پریم، برای یافتن درخت پوشای کمینهٔ بدون جهت است. بعدها در سال ۱۹۸۶، گابو، گلیل، اسپنسر، و تارجان پیاده‌سازی سریعتری را ارائه کردند که زمان اجرای آن برابر است با .

الگوریتم

تابعی مانند  را در نظر می‌گیریم که به عنوان ورودی، یک گراف وزن دار و جهت دار  و یک راس  به عنوان ریشه می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با ریشهٔ ، به ما می‌دهد.

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

توصیف

این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند  را در نظر می‌گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار ، با یک راس  به عنوان ریشه را می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می‌دهد.

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

حالا برای هر راس  به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه‌است را علامت(به‌طور قراردادی) می‌زنیم. راسی که در سر دیگر این یال قرار دارد را با  مشخص می‌کنیم. اگر یال‌های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می‌دادند، یعنی تابع   این SRT را مشخص کرده‌است. در غیر این صورت، مجموعه یال‌های علامت زده شده، تشکیل حداقل یک دور را می‌دهند. یکی از دورها را (به صورت دلخواه)  بنامید. حالا ما یک گراف وزن دار و جهت دار  که دارای ریشه  است را تعریف می‌کنیم. به این صورت که، راس‌های  مانند راس‌های   هستند نه  ، به اضافه یک راس جدید که با  مشخص می‌شود.

اگر   یالی در  باشد، با این شرط که ، یال  را به صورت شرح داده شده در زیر به   اضافه می‌کنیم.

اگر ،   و 

در غیر این صورت، اگر ،  و and .

ما هیچ یال دیگری را به  اضافه نمی‌کنیم.

ریشهٔ  در ، همان ریشهٔ  در . است.

با صدا کردن تابع ، یک SRT در  می‌یابیم. در نظر داشته باشید که در  این SRT، یال ورودی (یکتا) به ، یال  است. این یال می‌تواند از زوج مرتب‌هایی مانند  با شرط  و   باشد. علامت   را بردارید و  را علامت بزنید. حالا مجموعه یال‌های علامت زده شده، یک SRT می‌سازند که ما می‌توانیم آن را مقدار تابع  در نظر بگیریم.

دقت کنید که تابع  به وسیله تابع  تعریف شده‌است. و تابع  که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف  به شدت تعداد راس‌هایش کمتر است و استفاده از  برای یک گراف تک راس، کاری بیهوده‌است.

پیاده سازی

BV را یک مجموعه‌ای برای رئوس و BE را مجموعه‌ای برای یال‌ها در نظر بگیرید. اگر V را یک راس در نظر بگیرید و e هم یالی با بیشترین وزن مثبت و متصل به V باشد،  Cᵢ یک دور خواهد بود. G۰ = (V۰,E۰) گراف اصلی است و uᵢ یک راس جانشین برای Cᵢ است.

i=0

A:
if  then goto B
for some vertex  and  {
   
   find an edge  such that w(e) = max{ w(y,v)|(y,v)  Eᵢ}
   if w(e) ≤ 0 then goto A
}
if  contains a circuit {
   i=i+1
   construct  by shrinking  to 
   modify BE, BV and some edge weights
}

goto A

B:
while i ≠ 0 {
   reconstruct  and rename some edges in BE
   if  was a root of an out-tree in BE {
        and 
   }else{
        and 
   }
   i=i-1
}
Maximum branching weight =