گراف بدون جهت و وزن‌دار $G$ (با وزن‌های مثبت) و رئوس $s_1,s_2,…,s_k$ از آن داده شده است. می‌خواهیم از این گراف تعدادی یال حذف کنیم به طوری که اولا با حذف این یال‌ها هر کدام از $s_i$ ها در یک مولفه‌ی هم‌بندی قرار گیرد و ثانیا مجموع وزن این یال‌ها کمینه باشد. برای این کار زیر برنامه‌ای داریم که به ازای هر $a$ کم‌وزن‌ترین مجموعه از یال‌ها را می‌دهد که $s_a$ را از بقیه‌ی $s_i$ ها جدا می‌کند. برای حل مسئله‌ی اصلی الگوریتم زیر را پیشنهاد می‌کنیم:

الگوریتم: در هر مرحله به ازای هر $a$، $1\leq a\leq k$، هزینه‌ی جدا کردن $s_a$ از بقیه را حساب می‌کنیم و $a$ ای را انتخاب می‌کنیم که این هزینه برای آن کمینه باشد. یال‌هایی که این راس را از بقیه جدا می‌کند، حذف کرده، در هر یک از مولفه‌هایی که شامل لااقل دو $s_i$ باشد، این کار را به صورت بازگشتی تکرار می‌کنیم.

الف) مثال ارائه کنید که در آن، مجموعه‌ای که الگوریتم ما به دست می‌آورد، بهینه نباشد.

ب) ثابت کنید جواب که این الگوریتم به دست می‌آورد، حداکثر $(2-\frac{2}{k})$ برابر جواب بهینه است.

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