====== درخت تقریبا سنگین ======



**تعاریف:**

وزن زیرگراف یک گراف وزن‌دار، مجموع وزن یال‌های زیر گراف است.

گراف اقلیدسی گرافی است که به ازای هر $x،y،z$ اگر هر سه یال $xy$  و $yz$ و $xz$ در گراف باشند، آن‌گاه وزن یال $xy$  ازمجموع وزن یال‌های $xz$ و $yz$ کم‌تر است.

ستاره‌ی فراگیر با مرکز $v$ درختی است که از مجموعه‌ی یال‌های متصل به $v$ تشکیل می‌شود.

الگوریتم زیر در گراف کامل وزن‌دار اقلیدسی $G$ درخت فراگیر $T$ را به این ترتیب انتخاب می‌کند:

  - راس $v$ را به طور تصادفی انتخاب کن.
  - راس $u$ را که سنگین‌ترین یال را به $v$ دارد پیدا کن.
  - از بین دو ستاره‌ی فراگیر به مرکزهای $v$ و $u$ آن را انتخاب کن که وزنش بیش‌تر است و اسم آن را $T$ بگذار. $T$ همان درخت مورد نظر است.


اگر $T'$  درخت فراگیری باشد که وزن آن بیشینه است، اثبات کنید وزن $T$ از یک‌چهارم وزن $T'$ کم‌تر نیست.



<پاسخ>



</پاسخ>


  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]