שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2020 - עץ פורש מינימלי

נתון גרף קשיר ולא-מכוון $G=(V,E)$ עם משקלי צלעות $w(e)>0$ **ייחודיים**. נתבונן בוריאנט הבא של Kruskal למציאת עפ"מ, שבו שלב הבחירה משתנה: > בכל איטרציה בוחרים **באקראי בהתפלגות אחידה** את אחד העצים $T$ ביער, ואז מוסיפים ליער את הצלע $e$ בעלת המשקל **המזערי מבין כל הצלעות המחברות את $T$ ליתר הגרף**. (שאר האלגוריתם כמו Kruskal המקורי: מתחילים ביער של קדקודים בודדים, ומסתיימים כשנותר עץ יחיד.) הפריכו או הוכיחו את נכונות הווריאנט. שימו לב שהאלגוריתם הסתברותי: אם שגוי — הציגו קלט וסדרת בחירות אקראיות שעבורן הפלט שגוי; אם נכון — הוכיחו שלכל קלט ולכל סדרת בחירות הפלט נכון.

רמז: בכל איטרציה, איזה חתך של הגרף מוגדר על ידי העץ $T$ שנבחר? בדקו תחילה האם צלעות היער הנוכחי חוצות את החתך הזה, ורק אז שאלו מה תכונת החתך אומרת על הצלע המזערית שחוצה אותו.

פתרון: **הווריאנט נכון — לכל קלט ולכל סדרת בחירות אקראיות.** הסיבה: בחירת **עץ שלם** $T$ והוספת הצלע המזערית היוצאת ממנו היא בדיוק יישום של **תכונת החתך**. נוכיח באינדוקציה שהיער נשאר תת-יער של עפ"מ. **בסיס.** יער הקדקודים הבודדים (0 צלעות) הוא תת-יער של כל עפ"מ. **הנחה.** נניח שאחרי איטרציה כלשהי היער $F$ הוא תת-יער של עפ"מ. **צעד.** נבחר (באקראי) עץ $T$ ביער. נתבונן בחתך $(V(T),\,V\setminus V(T))$. הצלע $e$ שהאלגוריתם מוסיף היא הצלע המזערית מבין **כל** הצלעות החוצות חתך זה. לפי **תכונת החתך**, ומכיוון שהמשקלים ייחודיים, $e$ שייכת ל**כל** עפ"מ; בפרט לעפ"מ המכיל את $F$. לכן $F\cup\{e\}$ עדיין תת-יער של עפ"מ, והשמורה נשמרת — ללא תלות בעץ $T$ שנבחר. בסיום מתקבל עץ פורש שהוא תת-יער של עפ"מ, כלומר עפ"מ בעצמו. $\blacksquare$ > **הבחנה:** בניגוד לוריאנט שבו בוחרים את הצלע המזערית היוצאת מ**קדקוד** בודד (שגוי), כאן בוחרים את המזערית היוצאת מ**עץ** שלם — וזוהי בדיוק הצלע המזערית החוצה את החתך, ולכן בטוחה.