مسایل فصل 1 کتاب وزیرانی

سوال 1:

برای اینکه از عدم وجود دور در گراف مطمئن باشیم از این روش استفاده می کنیم که به یک رأس یا وارد می شویم یا از آن خارج می شویم. در ایصورت در گراف جهت دار دوری نخواهیم داشت. 

طبق راهنمایی سؤال رئوس را به ترتیب دلخواه شماره گذاری می کنیم و و به این ترتیب کل یال ها را به دو دسته تقسیم می کنیم :

دسته اول یال هایی که از رأس با شماره بزرگتر به رأس با شماره کوچکتر می روند و یال هایی که از رأس با شماره کوچکتر به رأس با شماره بزرگتر می روند . از بین این دو دسته دسته بزرگتر را انتخاب می کنیم. بدیهی است که در اینصورت دور نداریم. 

و چون دست کم نصف یال ها را با این الگوریتم انتخاب خواهیم کرد و تعداد بهینه یال ها برای این الگوریتم حداکثر برابر کل تعداد یال ها در گراف اصلی است به وضوح این الگوریتم از فاکتور 1/2 است.

سؤال 2:

یک تطابق از گراف پیدا می کنیم. به این ترتیب که از یک رأس شروع می کنیم و با یکی از همسایگانش تطبیق می دهیم و از گراف حذف می کنیم. و به همین ترتیب ادامه می دهیم. این یک تطابق maximal از گراف می دهد که طبق راهنمایی سؤال از نصف تطابق ماکزیمم بیشتر است یعنی تطابق ماکزیمم از 2 برابر تطابق بیشینه کمتر است و از تطابق بیشینه بیشتر است( بدیهی است!) یعنی الگوریتمی با فاکتور 2

البته توجه کنید که این یک الگوریتم پیدا کردن کمینه است و مقداری که ما ممکن است پیدا کنیم ماکزیمم تطابق است که چون از 2 برابر هر ماکزیمال تطابقی کمتر است ( حتی جواب بهینه ما در اینجا یعنی تطابق ماکزیمال با کمترین کاردینالیتی ) بنابراین طبق نامساوی هایی که در بالا گفته شد فاکتر 2 می شود این الگوریتم! :)

سؤال 3:

ابتدا نشان می دهیم که مجموعه انتخاب شده یک vertex cover برای گراف هست. با توجه به اینکه در پیمایش عمقی گراف برگ ها فقط به پدرشان یا به گره های جدشان یال دارند بنابراین با توجه به اینکه تمام گره های غیر برگ در این مجموعه قرار گرفته اند بنابراین نیازی به انتخاب برگ ها نیست چون برای تمام یال ها یک سرشان در این مجموعه قرار گرفته است و این یک VC است. 

حالا فاکتور 2 را اثبات می کنیم. برای این می دانیم که گره ها فقط به پدر یا اجدادشان یال دارند. بنابراین کافیست گره های غیر برگ در عمق های فرد را با گره های غیر برگ در عمق زوج تطابق دهیم و دو سر این تطابق را ( که یک تطابق ماکزیمال است ) به عنوان جواب گزارش کنیم. تعداد این تطابق حداکثر برابر نصف گره های غیر برگ است. ( این در حالتی اتفاق می افتد که تعداد گره ها در عمق زوج و فرد با هم برابر باشد.) که می دانیم تعداد این تطابق ها همیشه از کاردینالیتی کمتر است.( lower bound)  بنابراین فاکتور 2 اثبات می شود.

مثال tight : گراف دو بخشی است.  که به صورت زیگزاگ به هم یال دارند. 

سؤال 4: 

مثال tight  رو سر کلاس دکتر آبام گفتن. اما شکلش رو میذارم بعداً. حتماًً................. :)

سؤال 5: 

سؤال 9:

فرض کنید k  برابر OPT_VC روی گراف با گره هایی با وزن 1 باشد. راه حلی از مرتبه چند جمله ای برای پیدا کردن اینکه گراف دارای این VC هست یا نه نداریم. که بعد از آن بخواهیم می نیمم هزینه را برای این دربیاوریم! راه حل چند جمله ای ما در بهترین حالت از فاکتور 2 است. 

بنابراین این مسأله هم NP-optimization  است. در واقع این مسئله همان ورژن تصمیم گیری مسئله VC است.