تمرین های فصل 3

1- سختی مساله درخت اشتاینر در مشخص کردن زیرمجموعه بهینه از راسهای اشتاینر است که باید در درخت باشند. نشان دهید که اگر این مجموعه داده شده باشد، مساله ی درخت اشتاینر به صورت بهینه در زمان چند جمله ای قابل محاسبه است.

راهنمایی: یک MST روی اجتماع این مجموعه و مجموعه رئوس "لازم" پیدا کنید.

گراف جدیدی می سازیم و فقط این راسها و یالهای بین آنها را نگه می داریم چون بقیه راسها نمی توانند در جواب وجود داشته باشند. درخت با کمترین هزینه که این راسها را داشته باشد همان MST گراف است. زمان حذف یالها و راسهای اضافی و به دست آوردن MST گراف جدید هم چند جمله ای است. چون تعریف MST و درخت اشتاینر در این حالت یکی می شود دیگر اثبات هم نمی خواهد.

2- گراف با یالهای وزندار نامنفی داده شده است. S مجموعه ی فرستنده ها و R مجموعه گیرنده ها دو زیرمجموعه مجزا از رئوس هستند. مساله پیدا کردن زیر گراف با کمترین هزینه است که هر گیرنده را به حداقل یک فرستنده وصل کند. نمونه ها را به دو مجموعه تقسیم کنیم: آنهایی که اجتماع این دو مجموعه تمام رئوس می شود و حالتی که نمی شود. نشان دهید این دو مساله به ترتیب در P و NP-hard هستند. برای حالت دوم الگوریتم تقریبی با ضریب 2 بدهید.

راهنمایی: یک راس جدید اضافه کنید که به هر فرستنده با یال با هزینه ی 0 وصل شده باشد. راس جدید و همه ی گیرنده ها را "لازم" و بقیه رئوس را اشتاینر در نظر بگیرید. درخت اشتاینر با کمترین هزینه را پیدا کنید.

حالتی که اجتماع این دو مجموعه کل رئوس شود: همه ی راسهای فرستنده را با هم ادغام می کنیم و یک ابر راس می سازیم. در این گراف MST را حساب می کنیم. چون هدف سوال وصل کردن این راسها با هزینه ی مینیمم است جواب بهینه MST است پس مساله در P است.

حالتی که اجتماع این مجموعه کل رئوس نشود: چون مجموعه ای از رئوس هستند که حضور آنها لازم نیست مساله به درخت اشتاینر تبدیل می شود که در NP-Hard است. برای حل آن راهنمایی سوال را اجرا می کنیم و الگوریتم با ضریب تقریب 2 به دست می آوریم.

3- کاهشی با حفظ ضریب تقریب از مساله پوشش مجموعه ای به مساله بعد بدهید و نشان دهید که این مساله نمی تواند ضریب تقریب بهتر از O(log n) داشته باشد.

درخت اشتاینر جهت دار: یک گراف جهت دار با یالهای با هزینه ی نامنفی داده شده است. مجموعه رئوس V به دو زیرمجموعه "لازم" و "اشتاینر" افراز شده است. یکی از راسهای لازم (r) یک راس ویژه است. مساله پیدا کردن درخت با کمترین هزینه است که ریشه ی آن r باشد و شامل همه ی راسهای لازم و هر زیر مجموعه ای از راسهای اشتاینر باشد.

راهنمایی: یک گراف سه لایه بسازید: لایه 1 شامل راسهای ضروری معادل هر عضو، لایه 2 شامل راسهای اشتاینر معادل هر مجموعه و لایه 3 شامل r.

همان طور که راهنمایی گفته است هر عضو مجموعه مرجع را یک راس ضروری در نظر می گیریم و هر مجموعه را یک راس اشتاینر در نظر می گیریم و با میانگین وزن اعضای آن به راسهای لازم متناظر آنها وصل می کنیم. چون این گراف همبند نیست یک راس r اضافه می کنیم و به همه ی راسهای اشتاینر آن را با هزینه 0 وصل می کنیم. (مثلا فرض کنید مجموعه تهی است). حالا با محاسبه ی درخت اشتاینر جهت دار، همه ی اعضای مجموعه مرجع انتخاب می شود و این کار با کمترین هزینه انجام می شود، پس جواب بهینه مساله پوشش مجموعه ای است. پس نمی تواند ضریب تقریب بهتری از این مساله که ضریب تقریب O(log n) دارد داشته باشد.