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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

زمان اجرا[ویرایش]

زمان اجرای این الگوریتم برابر با 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 باشد، Ci یک دور خواهد بود. G۰ = (V۰,E۰) گراف اصلی است و ui یک راس جانشین برای Ci است.

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 \ne e_0^i\rbrace }else{ BE \leftarrow BE \cup \lbrace e|e \in C_i and e \ne \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.

پیوند به بیرون[ویرایش]