ادامه ی تمرین های فصل 2 وزیرانی
6- گراف بدون جهت G داده شده، راسهای آن را با کمترین تعداد رنگ طوری رنگ کنید که دو سر یک یال رنگ متمایز داشته باشند.
الف) حریصانه و با delta+1 رنگ (delta ماکسیمم درجه)
از یک راس شروع می کنیم و آنرا رنگ می کنیم و همه ی همسایه های آن را با رنگ دیگری رنگ می کنیم. این کار را برای همسایه های آن راس هم انجام می دهیم. اگر دو سر یک یال همرنگ بود، رنگ یک سر آن را عوض می کنیم: چون هر راس حداکثر delta همسایه دارد و ما delta+1 رنگ داریم این کار همیشه امکان پذیر است.
ب) یک الگوریتم برای رنگ آمیزی گراف 3-رنگ پذیر با O(sqrt(n)) رنگ بدهید.
راهنمایی: یک راس و همسایه های آن یک گراف دوبخشی (زیرگراف G) است پس می تواند به صورت بهینه رنگ آمیزی شود. راسهایی که درجه ی بیشتر از sqrt(n) دارند با سه رنگ، رنگ کنید بعد الگوریتم قسمت الف را اجرا کنید.
اول همان طور که در راهنمایی گفته شده راسهای با درجه ی بیشتر از رادیکال n را با سه رنگ، رنگ می کنیم، بعد الگوریتم قسمت قسمت الف را اجرا می کنیم. چون سه رنگ پذیر است و در هر مرحله بهینه رنگ می شود پس به مشکل بر نمی خوریم.
7- ثابت کنید پوشش راسی حالت خاص پوشش مجموعه ای است.
پوشش مجموعه ای می گوید مجموعه ها اجتماعشان مجموعه مرجع شود و تعداد مجموعه های انتخاب شده کمینه باشد.
پوشش راسی می گوید راسهای انتخاب شده شامل حداقل یک سر هر یال باشند.
پس هر راس را مجموعه ی یالهای مجاور آن می گیریم. حالا اگر پوشش مجموعه ای این مجموعه ها را پیدا کنیم (مجموعه مرجع مجموعه ی همه ی یالها است) یک پوشش راسی برای یالهاست، چون مجموعه ی مرجع (همه ی یالها) را پوشش می دهد. دلیل کمینه بودن آن هم این است که اگر راسی اضافه انتخاب شده باشد، مجموعه ی متناظر آن را می توان حذف کرد و به پوشش مجموعه ای کمینه رسید، که با فرض کمینه بودن پوشش مجموعه ای تناقض دارد.
8- ثابت کنید پوشش مجموعه ای حریصانه ضریب تقریب H(k) دارد. (k=تعداد اعضای بزرگترین زیرمجموعه ی U)
(انتخاب حریصانه: cost(S)/(|S-C|) ماکسیمم شود.)
توی پستهای قبلی هست.
9- یک الگوریتم حریصانه بدهید که ضریب تقریب H(n) را برای پوشش چندگانه مجموعه ای تضمین کند. پوشش چندگانه مجموعه ای یک تعمیم از پوشش مجموعه ای است که (فکر کنم!) در آن هر عنصر باید حداقل به تعداد گفته شده ای برداشته بشه. فرض کنید هزینه ی برداشتن a کپی از مجموعه Si برابر a.cost(Si) است.
