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

נתון גרף לא-מכוון קשיר $G=(V,E)$ עם משקלי צלעות $w(e)>0$. תהי $\varnothing\neq S\subsetneq V$. **למת-החתך** קובעת: אם $e^\*$ היא צלע בעלת משקל מזערי מבין כל הצלעות החוצות את החתך (המחברות בין $S$ ל-$V\setminus S$), אזי יש עץ פורש מזערי $T^\*$ המקיים $e^\*\in T^\*$. לפניכם ניסיון הוכחה: 1. יהי $T$ עץ פורש מזערי. אם $e^\*\in T$ אז אין מה להוכיח. אחרת, 2. כל עץ פורש חייב לחבר בין $S$ ל-$V\setminus S$, ולכן ישנה צלע $e\in T$ החוצה את החתך. 3. תת-הגרף החדש $T^\*:=(T\cup\{e^\*\})\setminus\{e\}$ הוא עץ פורש (כי החלפנו צלע חוצה בצלע חוצה אחרת). 4. לתת-הגרף החדש יש משקל קטן או שווה למשקל המקורי. לכן אם $T$ עפ"מ אז גם $T^\*$ עפ"מ, המקיים $e^\*\in T^\*$. **א.** החלק השגוי היחיד בטיעון הוא מספר **3**. הסבירו במילים מהי הטעות. (11 נק') **ב.** הציגו דוגמה נגדית ממושקלת פשוטה של $G,T,e,e^\*$ הממחישה את הטעות.

רמז: הוספת $e^\*$ יוצרת מעגל יחיד. מדוע לא כל צלע חוצה $e\in T$ שוברת אותו? חפשו דוגמה קטנה שבה $T$ מכיל שתי צלעות חוצות, ורק אחת מהן על המעגל.

פתרון: **א. הטעות בשלב 3.** הוספת $e^\*$ ל-$T$ יוצרת **מעגל** יחיד. כדי לחזור לעץ יש להסיר צלע **שנמצאת על אותו מעגל**. אולם שלב 3 מסיר צלע חוצה $e\in T$ **שרירותית** — ואין הכרח שהיא על המעגל שנוצר. אם $e$ אינה על המעגל, תת-הגרף $T^\*$ עדיין מכיל את המעגל (ולכן אינו עץ) וגם מתפצל לרכיב מנותק. בקיצור: לא כל צלע חוצה שוברת את המעגל שיצרה $e^\*$. **ב. דוגמה נגדית.** ניקח $S=\{a,b\}$, $V\setminus S=\{c,d\}$, וכל הצלעות במשקל $1$: $$T=\{(a,c),(c,d),(b,d)\},\qquad e^\*=(a,d)\notin T.$$ - $e^\*=(a,d)$ היא צלע חוצה בעלת משקל מזערי ($1$), ו-$T$ הוא עפ"מ (משקל $3$; כל הצלעות $1$). - הצלעות החוצות שב-$T$ הן $(a,c)$ ו-$(b,d)$. הוספת $e^\*=(a,d)$ יוצרת את המעגל $a\!-\!c\!-\!d\!-\!a$. - אם שלב 3 מסיר את הצלע החוצה $(b,d)$ — שאינה על המעגל — מתקבל $T^\*=\{(a,c),(c,d),(a,d)\}$: הוא **מכיל את המעגל** $a\!-\!c\!-\!d\!-\!a$ ומשאיר את $b$ מבודד, ולכן **אינו עץ**. התיקון הנכון: להסיר את הצלע החוצה שנמצאת על המעגל שיצרה $e^\*$ (כאן $(a,c)$), ואז $T^\*=\{(c,d),(b,d),(a,d)\}$ הוא אכן עפ"מ המכיל את $e^\*$. $\blacksquare$