Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:الگوریتم ها:سوال ۴

سوال ۴

یک گراف جهت‌دار وزن‌دار G با مجموعه‌ی رئوس V(G) و مجموعه‌ی یال‌های E(G) داریم. یال جهت‌دار از u به v را با (u,v) نشان می‌دهیم. وزن‌ یال از u به v را w(u,v) تعریف می‌کنیم. به یک زیرگراف H از گراف G، MSTr گوییم؛ هرگاه گراف زمینه‌ی H درخت باشد و در H از r به تمام رئوس G مسیر جهت‌دار وجود داشته باشد و مجموع وزن یال‌های H کمینه باشد. f(G,r) برابر با مجموع وزن یال‌های MSTr در گراف G است. می‌خواهیم f(G,r) را پیدا کنیم. «ادموند» الگوریتم بازگشتی زیر را برای این کار ارائه می‌دهد:

برای هر رأس به جز r مانند v، یال ورودی با وزن کمینه به v را در نظر بگیرید (اگر چند یال با وزن کمینه وجود داشت، یکی را به دل‌خواه انتخاب می‌کنیم) و فرض کنید آن یال از رأس π(v) خارج می‌شود. به زیرگراف با مجموعه رئوس V(G) و مجموعه‌ی یال‌های مذکور، H می‌گوییم. اگر در H دور جهت‌دار وجود نداشت، H پاسخ مسئله است؛ در غیر این صورت یکی از دورهای H را به دل‌خواه در نظر گرفته و آن را C بنامید. گراف G را به روش زیر می‌سازیم:

V(G) را برابر {V(G)V(C)}a در نظر می‌گیریم که a یک رأس جدید است. یال‌های G را نیز به این صورت می‌سازیم:

  • اگر (u,v) یک یال در E(G) بود؛ طوری که uC و vC، یک یال در E(G) از u به a با وزن w(u,v)w(π(v),v) می‌گذاریم.
  • اگر (u,v) یک یال در E(G) بود؛ طوری که uC و vC، یک یال در E(G) از a به v با وزن w(u,v) می‌گذاریم.
  • اگر (u,v) یک یال در E(G) بود؛ طوری که uC و vC، یک یال در E(G) از u به v با وزن w(u,v) می‌گذاریم.

حال الگوریتم را روی G اجرا می‌کنیم تا f(G,r) به دست آید. مجموع وزن یال‌های C را g(C) در نظر می‌گیریم. در انتها مقدار f(G,r) را f(G,r)+g(C) اعلام می‌کنیم.

ثابت کنید الگوریتم ادموند درست کار می‌کند.


ابزار صفحه