שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 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 נק' לכל סעיף): **(א)** ציור של הגרף; **(ב)** מהי קבוצה מיוחדת מזערית בגרף (נדרש הסבר); **(ג)** איזו קבוצה מיוחדת האלגוריתם החמדן עלול להפיק (נדרש הסבר).

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

פתרון: **גרף נגדי.** נתבונן בעץ על $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$