تمرینهای فصل 1 کتاب
1- یک الگوریتم تقریبی با ضریب 1/2 بدهید که سوال زیر را حل کند:
زیرگراف بدون دور: یک گراف جهت دار G داده شده است، بزرگترین مجموعه یال از یالهای آن را بردارید که زیرگراف حاصل بدون دور باشد.
راهنمایی: راسها را دلخواه شماره گذاری کنید و مجموعه ی بزرگتر از بین یالهای از شماره کمتر به بیشتر و یالهای از شماره بیشتر به کمتر را بردارید. از چه شمایی برای کران بالای جواب بهینه استفاده می کنید؟
حل: حتما دور ندارد چون فقط از راسهای باشماره کوچک به بزرگ یا بزرگ به کوچک یال داریم. (هر کدام بیشتر بود).
چیزی که باید ثابت کنیم:
1/2OPT<=ALG
1/2*OPT <= max(deg_>, deg_<)
OPT <= 2*max(deg_>,deg_<)
OPT <= |E|=deg_>+deg_< <= 2*max(deg_>,deg_<)
2- یک الگوریتم با ضریب تقریب 2 بدهید که این مساله را حل کند: یک تطابق ماکسیمال با کمترین تعداد اعضا روی یک گراف بدون جهت به دست بیاورد.
راهنمایی: از این حقیقت استفاده کنید که هر تطابق ماکسیمالی حداقل به اندازه ی نصف تطابق بیشینه یال دارد.
حل:
یک تطابق از گراف می دهیم: یالها را به تطابق اضافه می کنیم تا وقتی که دیگر نتوانیم یال اضافه کنیم. (وقتی که یالی نماند که یک سر آن قبلا در یالهای دیگر انتخاب نشده باشد).
تعداد یالهای این تطابق کمتر از تعداد یالهای تطابق بیشینه و بیشتر از نصف تعداد یالهای تطابق بیشینه است.
تعداد یالهای تطابق ماکسیمال با کمترین اعضا (جواب بهینه) حداقل به اندازه ی نصف تطابق بیشینه است. (طبق راهنمایی)