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

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

רמז: חפשו גרף שבו קדקוד יחיד בעל דרגה גבוהה "מפתה" את החמדני, אך הפתרון האופטימלי בוחר דווקא כמה קדקודים בעלי דרגה בינונית. עץ קטן עם קדקוד מרכזי ושלושה ענפים באורך 2 מספיק.

פתרון: **גרף נגדי.** נתבונן בעץ על $7$ קדקודים $\{a,b_1,b_2,b_3,c_1,c_2,c_3\}$ עם $6$ הצלעות הבאות: $$\{a,b_1\},\ \{a,b_2\},\ \{a,b_3\},\ \{b_1,c_1\},\ \{b_2,c_2\},\ \{b_3,c_3\}.$$ כלומר קדקוד מרכזי $a$ מחובר לשלושה קדקודים $b_1,b_2,b_3$, ולכל $b_i$ תלוי עלה $c_i$: ``` a / | \ b1 b2 b3 | | | c1 c2 c3 ``` **מה מחזיר החמדני:** דרגת $a$ היא $3$ (המרבית), ולכן הוא נבחר ראשון. לאחר מחיקת $a$ נותרות שלוש הצלעות $\{b_i,c_i\}$ שאינן נוגעות זו בזו; לכיסוי כל אחת נדרש עוד קדקוד — $3$ נוספים. הפלט: קבוצה בגודל $4$ (למשל $\{a,b_1,b_2,b_3\}$ או $\{a,c_1,c_2,c_3\}$). **הפתרון האופטימלי:** הקבוצה $\{b_1,b_2,b_3\}$ (בגודל $3$) מכסה את כל הצלעות — כל צלע $\{a,b_i\}$ וכל צלע $\{b_i,c_i\}$ נוגעת ב-$b_i$. לכן החמדני מחזיר $4>3$, ואינו מזערי. $\blacksquare$