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

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

רמז: שימו לב שהווריאנט מסתכל רק על הצלעות היוצאות מקדקוד יחיד $v^\*$, ולא על כל הצלעות היוצאות מהעץ $T(v^\*)$. בנו משולש שבו הצלע הקלה החוצה את החתך יוצאת מקדקוד **אחר** ב-$T(v^\*)$.

פתרון: **הווריאנט שגוי — הפרכה.** הטעות: הצלע המזערית היוצאת מקדקוד **יחיד** $v^\*$ אינה בהכרח הצלע המזערית היוצאת מכל העץ $T(v^\*)$, ולכן אין ערובה שהיא צלע בטוחה (למת-החתך דורשת את המזערית מבין **כל** הצלעות החוצות את החתך $(T(v^\*),\text{השאר})$). **דוגמה נגדית (משולש).** קדקודים $\{a,b,c\}$ עם הצלעות: $$w(a,b)=1,\quad w(b,c)=2,\quad w(a,c)=100.$$ - **העפ"מ הנכון:** $\{(a,b),(b,c)\}$ במשקל $1+2=3$. - **הרצת הווריאנט עם $v^\*=a$ קבוע:** באיטרציה הראשונה הצלע המזערית היוצאת מ-$a$ היא $(a,b)$ (משקל $1$) — מתווספת, ו-$T(a)=\{a,b\}$. באיטרציה השנייה, שוב $v^\*=a$: הצלע היחידה היוצאת מ-$a$ אל מחוץ ל-$\{a,b\}$ היא $(a,c)$ (משקל $100$) — מתווספת. הפלט $\{(a,b),(a,c)\}$ במשקל $101$. מכיוון שהווריאנט מתעלם מהצלע הקלה $(b,c)$ (שיוצאת מ-$b$, לא מ-$a$), הוא מחזיר עץ במשקל $101>3$ — אינו מזערי. $\blacksquare$