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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:گراف:سوال ۶

سوال ۶

F(v,G) را برابر مجموع فاصله‌ی راس v تا همه‌ی راس‌ها در گراف G تعریف می‌کنیم (در صورتی که G ناهمبند باشد مقدار این تابع بی‌نهایت است)

H(v,u,w,T) را گرافی تعریف می‌کنیم که از حذف یال (v,u) از T و اضافه کردن یال (v,w) به آن بوجود می‌آید در شروع یک درخت T داریم. در هر مرحله اگر یک یال (v,u) و یک راس w در T وجود داشت به طوری که F(v,H(v,u,w,T))<F(v,T) آن‌گاه H(v,u,w,T) را جایگزین T می‌کنیم و همین کار را تکرار می‌کنیم.

ثابت کنید مستقل از روش انتخاب یال (v,u) و راس w گراف T پس از چند مرحله به ستاره تبدیل می‌شود.


ابزار صفحه