Network

ادعا می‌کنیم که‌یال‌های جواب یک زیردرخت فراگیر کمینه (MST) می‌سازند. بدیهی است که جواب بهینه‌یک درخت است وگرنه دور دارد و می‌توان یک یال را حذف کرد و هزینه کم‌تر شود. حال ثابت می‌کنیم که جواب بهینه‌یک MST هم هست. کوتاه‌ترین یالی که در MST آمده و در جواب بهینه‌ی ما نیست را در نظر می‌گیریم و $e$ می‌نامیم. $e$ را به جواب بهینه اضافه کرده و طولانی‌ترین یالی که با $e$ در یک دور قرار دارد را حذف می‌کنیم تا به‌یک درخت جدید برسیم. بدیهی است که می‌توان درخت جدید را مشابه جواب بهینه با سیم‌ها بپوشانیم، با این تفاوت که به جای اینکه‌یال حذف شده را بپوشانیم، $e$ را می‌پوشانیم. (طول $e$ کم‌تر از یال حذف شده است زیرا اگر یال حذف شده کوتاه‌تر از e بود در دوری که با $e$ تشکیل داده اند، همه‌یال‌ها کوتاه تر از $e$ بودند و چون همه‌یال‌های کوتاه تر از $e$ در MST آمده‌اند در MST اولیه دور داشته‌ایم که تناقض است(! پس اگر با سیم‌های موجود می‌توانستیم جواب بهینه را سیم‌کشی کنیم درخت جدید را هم می‌توانیم و چون طول $e$ کم‌تر است، هزینه کل درخت جدید از هزینه کل جواب بهینه کم‌تر است که تناقض است پس جواب بهینه‌یک MST است. پیدا کردن یک MST از $O(e \log n)$ است که می‌توان با الگوریتم‌هایی نظیر kruskal یا prim آن را بدست آورد.

بدون اینکه به کلیت مسئله لطمه وارد شود می‌توان فرض کرد که $p_0< p_1$ است. از آنجا که مجموع طول یال‌های MST ثابت است بدیهی است که در جواب بهینه بیش‌ترین مقدار ممکن که می‌توان را با سیم‌های $p_0$ پوشانده‌ایم و باقی را به ناچار با $p_1$ یعنی بین دو جواب، جوابی که مقدار بیش‌تری از $p_0$ استفاده کرده‌ایم بهتر است. حال مسئله به این تبدیل می‌شود که $n-1$ شی با اندازه‌های $L_i$ (وزن یال $i$ ام در (MST داریم و می‌خواهیم بیش‌ترین مقدار از آن‌ها (از لحاظ مجموع وزن)‌ را درون یک کیسه با اندازه $q_0$ جا دهیم. این مسئله به knapsack یا مسئله کوله پشتی معروف است که به صورت پویا از $O(q_0 n)$ حل میشود.