====== سوال ۶ ======


$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$ پس از چند مرحله به ستاره تبدیل می‌شود.

  * [[سوال ۷|سوال بعد]]
  * [[سوال ۵|سوال قبل]]