تعاریف:

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

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

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

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

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

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

• سوال بعد
• سوال قبل