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

נתון גרף לא מכוון $G=(V,E)$. מעגל פשוט ב-$G$ נקרא **ענק** אם הוא עובר בכל הקדקודים (מעגל המילטוני). בבעיית המעגלים הענקיים, **אלגוריתם-הכרעה** נדרש לקבוע האם קיים ב-$G$ מעגל ענק (משיב "כן"/"לא"), ו**אלגוריתם-חיפוש** נדרש למצוא מעגל ענק אם קיים, ואחרת לדווח שאין. הוכיחו באמצעות רדוקציה מתאימה: אם קיים אלגוריתם-הכרעה לבעיה בזמן פולינומי, אז קיים גם אלגוריתם-חיפוש בזמן פולינומי. הקפידו לדייק בהוכחת הנכונות.

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

פתרון: נניח שנתון אלגוריתם-הכרעה $D$ הרץ בזמן פולינומי ומשיב האם לגרף נתון יש מעגל ענק. נבנה אלגוריתם-חיפוש: **האלגוריתם.** 1. הרֵץ $D(G)$. אם התשובה "לא" — דווח שאין מעגל ענק וסיים. 2. אחרת, עבור על צלעות $G$ אחת-אחת. לכל צלע $e\in E$: - הגדר $G'=(V,E\setminus\{e\})$ והרֵץ $D(G')$. - אם $D(G')=$ "כן" — עדכן $G \leftarrow G'$ (הצלע $e$ מיותרת ואפשר לוותר עליה). - אם $D(G')=$ "לא" — השאר את $e$ (היא הכרחית לכל מעגל ענק שנותר). 3. החזר את קבוצת הצלעות שנותרה. **הוכחת נכונות (שמורת לולאה).** השמורה: *לגרף הנוכחי יש מעגל ענק*. **בסיס:** מתקיים בזכות שלב 1. **צעד:** כאשר $D(G')=$ "כן", הסרת $e$ שומרת על קיום מעגל ענק, ולכן העדכון שומר את השמורה; כאשר $D(G')=$ "לא", כל מעגל ענק של הגרף הנוכחי משתמש ב-$e$, ולכן משאירים אותה והשמורה נשמרת. **בסיום:** לכל צלע שנותרה הראינו שהיא הכרחית — אי-אפשר להסיר אף צלע בלי לאבד את המעגל הענק. במצב זה כל קדקוד הוא בעל דרגה **בדיוק 2** (דרגה גבוהה יותר הייתה מאפשרת להסיר צלע עודפת), ולכן הצלעות שנותרו מהוות בדיוק מעגל ענק יחיד — אותו מחזירים. $\blacksquare$ **סיבוכיות.** מבצעים $|E|+1$ קריאות לאלגוריתם-ההכרעה. אם זמן ריצתו $\Theta(n^a)$ ($n=|V|$), סך זמן החיפוש הוא $O(|E|\cdot n^a)$ — מכפלת פולינומים, ולכן **פולינומי**.