الگوریتم ادمون
در نظریه گراف، شاخه‌ای از ریاضیات، الگوریتم ادمون برای پیدا کردن انشعاب بهینهٔ بیشینه یا کمینه به کار می‌رود. زمانی که راس‌ها با یال‌های وزن دار و جهت دار به یکدیگر متصل شده باشند، دیگر نمی‌توانیم از الگوریتم درخت پوشای کمینه استفاده کنیم. بنابراین از الگوریتم انشعاب بهینه استفاده می‌کنیم که در سال ۱۹۶۷ توسط ادمون ارائه شد. برای یافتن مسیر با طول بیشینه، ابتدا یال‌ها بر اساس وزن شان مرتب می‌شوند. از بزرگترین یال شروع کرده و آن یال بین دو راس قرار می‌گیرد. بعد از آن به سراغ یال بزرگتر بعدی رفته و همین کار برای باقی یال‌ها نیز انجام می‌شود. اگر یالی باعث ایجاد دور در گراف شود، آن یال حذف می‌شود. برای پیدا کردن مسیر با طول کمینه نیز، یال‌ها از کوچک به بزرگ مرتب می‌شوند و کار با یال کوچکتر شروع می‌شود.
زمان اجرای این الگوریتم برابر با formula_1 است. پیاده‌سازی سریعتری از این الگوریتم، توسط روبرت تارجان ارائه شد که زمان اجرای آن برای یک گراف نا متراکم formula_2 و برای گراف متراکم برابر با formula_3 است. زمان اجرای آن به تندی الگوریتم پریم، برای یافتن درخت پوشای کمینهٔ بدون جهت است. بعدها در سال ۱۹۸۶، گابو، گلیل، اسپنسر، و تارجان پیاده‌سازی سریعتری را ارائه کردند که زمان اجرای آن برابر است با formula_4.
تابعی مانند formula_5 را در نظر می‌گیریم که به عنوان ورودی، یک گراف وزن دار و جهت دار formula_6 و یک راس formula_7 به عنوان ریشه می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با ریشهٔ formula_7، به ما می‌دهد. توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار مانند formula_6، با ریشهٔ formula_7، به این صورت عمل می‌کنیم که در ابتدا، مجموعهٔ یال‌های موازی(یال‌هایی که بین دو راس یکسان قرار دارند و دارای یک جهت می‌باشند) را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم.
این الگوریتم یک توصیف شهودی بازگشتی دارد. تابعی مانند formula_5 را در نظر می‌گیریم. این تابع به عنوان ورودی، گراف وزن دار و جهت دار formula_6، با یک راس formula_7 به عنوان "ریشه" را می‌گیرد و به عنوان خروجی، یک درخت فراگیر ریشه دار، با کمترین هزینه، می‌دهد. توصیف دقیق الگوریتم در ادامه آمده‌است. با گرفتن یک گراف وزن دار و جهت دار formula_6 با ریشهٔ formula_7، در ابتدا به این صورت عمل می‌کنیم که مجموعه‌ای از یال‌های موازی (یال‌های بین دو راس یکسان که دارای یک جهت هستند)را با یک یال که وزن آن برابر با مینیمم مقدار وزن آن یال‌های موازی است، جایگزین می‌کنیم. حالا برای هر راس formula_16 به جز ریشه، یال ورودی به آن راس که دارای کمترین هزینه‌است را علامت(به‌طور قراردادی) می‌زنیم. راسی که در سر دیگر این یال قرار دارد را با formula_17 مشخص می‌کنیم. اگر یال‌های علامت زده شده، تشکیل یک SRT(درخت فراگیر ریشه دار) را می‌دادند، یعنی تابع formula_18 این SRT را مشخص کرده‌است. در غیر این صورت، مجموعه یال‌های علامت زده شده، تشکیل حداقل یک دور را می‌دهند. یکی از دورها را (به صورت دلخواه) formula_19 بنامید. حالا ما یک گراف وزن دار و جهت دار formula_20 که دارای ریشه formula_21 است را تعریف می‌کنیم. به این صورت که، راس‌های formula_20 مانند راس‌های formula_6 هستند نه formula_19، به اضافه یک راس "جدید" که با formula_25 مشخص می‌شود. اگر formula_26 یالی در formula_6 باشد، با این شرط که formula_28، یال formula_29 را به صورت شرح داده شده در زیر به formula_20 اضافه می‌کنیم. اگر formula_31، formula_32 و formula_33 در غیر این صورت، اگر formula_34، formula_35 و and formula_36. ما هیچ یال دیگری را به formula_20 اضافه نمی‌کنیم. ریشهٔ formula_21 در formula_20، همان ریشهٔ formula_7 در formula_6. است. با صدا کردن تابع formula_42، یک SRT در formula_20 می‌یابیم. در نظر داشته باشید که در این SRT، یال ورودی (یکتا) به formula_25، یال formula_45 است. این یال می‌تواند از زوج مرتب‌هایی مانند formula_26 با شرط formula_28 و formula_31 باشد. علامت formula_49 را بردارید و formula_26 را علامت بزنید. حالا مجموعه یال‌های علامت زده شده، یک SRT می‌سازند که ما می‌توانیم آن را مقدار تابع formula_18 در نظر بگیریم. دقت کنید که تابع formula_18 به وسیله تابع formula_42 تعریف شده‌است. و تابع formula_20 که یک گراف وزن دار، جهت دار و ریشه دار است، نسبت به گراف formula_6 به شدت تعداد راس‌هایش کمتر است و استفاده از formula_18 برای یک گراف تک راس، کاری بیهوده‌است.
BV را یک مجموعه‌ای برای رئوس و BE را مجموعه‌ای برای یال‌ها در نظر بگیرید. اگر "V" را یک راس در نظر بگیرید و "e" هم یالی با بیشترین وزن مثبت و متصل به "V" باشد، C یک دور خواهد بود. G = (V,E) گراف اصلی است و "u" یک راس جانشین برای C است.
codice_1