שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - אלגוריתמים חמדניים

נתון גרף לא מכוון $G=(V,E)$. תת-קבוצה של קדקודים $C \subseteq V$ נקראת **"מיוחדת"** אם היא נוגעת בכל הצלעות, כלומר לכל $e=\{u,v\}\in E$ מתקיים $u\in C$ או $v\in C$ (כיסוי קדקודים). ברצוננו למצוא קבוצה מיוחדת מזערית. הציגו אלגוריתם למציאת קבוצה מיוחדת מזערית כאשר נתון ש-$G$ הוא **יער** (גרף חסר מעגלים), והוכיחו את נכונותו.

רמז: לצלע של **עלה**, כדאי תמיד להעדיף את השכן (ההורה) על פני העלה — ההורה עשוי לכסות צלעות נוספות, העלה מכסה רק את עצמו. עבדו מהעלים כלפי מעלה.

פתרון: **האלגוריתם (חמדני על עלים).** נשרש כל עץ ביער ונעבד את הקדקודים בסדר post-order (מהעלים כלפי מעלה). נחזיק קבוצה $C=\varnothing$, ונסמן צלעות כ"מכוסות". לכל קדקוד $v$ שמעובד: אם קיימת צלע $\{v,\text{parent}(v)\}$ שאינה מכוסה — נוסיף את **ההורה** $\text{parent}(v)$ ל-$C$, ונסמן את כל הצלעות הנוגעות בהורה כמכוסות. בסוף נחזיר את $C$. שקול לניסוח האיטרטיבי: **כל עוד יש צלעות, בחר עלה $v$, הוסף ל-$C$ את שכנו $u$, והסר את $u$ ואת כל הצלעות הנוגעות בו.** **זמן ריצה.** $O(|V|+|E|)=O(|V|)$ (ביער $|E|<|V|$). **הוכחת נכונות.** נראה שקיים כיסוי מזערי שאינו כולל את העלה $v$ אלא את שכנו $u$. תהי $\{u,v\}$ צלע כך ש-$v$ עלה. כל כיסוי חייב להכיל את $u$ או את $v$ כדי לכסות את הצלע $\{u,v\}$. בהינתן כיסוי מזערי $C^\*$ המכיל את $v$ (ולא את $u$): $v$ מכסה **רק** את הצלע $\{u,v\}$ (כי $v$ עלה), ואילו $u$ עשוי לכסות צלעות נוספות; לכן $C^\* \setminus \{v\} \cup \{u\}$ הוא כיסוי בגודל זהה או קטן יותר. מכאן שקיים כיסוי מזערי הכולל את $u$ — בדיוק כפי שהאלגוריתם בוחר. לאחר הוספת $u$ והסרת הצלעות שנוגעות בו, נותרת בעיה קטנה יותר (יער) שנפתרת רקורסיבית באותו אופן; באינדוקציה על מספר הצלעות מתקבל כיסוי מזערי. $\blacksquare$ > **הערה — תיקון לפתרון נפוץ:** אין לבחור פשוט את "הצד הקטן מבין שני צבעי היער הדו-צדדי". זהו אמנם כיסוי, אך **אינו מזערי** בהכרח: ב"כוכב-כפול" $u\!-\!v$ עם עלים $u_1,u_2$ ל-$u$ ו-$v_1,v_2$ ל-$v$, שני הצבעים בגודל $3$ כל אחד, אך הכיסוי המזערי הוא $\{u,v\}$ בגודל $2$.