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

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

רמז: הראו כיצד ניתן להמיר את בעיית מציאת עץ פורש מזערי עם משקלים כלשהם לבעיה שקולה עם משקלים אי-שליליים בלבד, על ידי הוספת קבוע מסוים לכל המשקלים, מבלי לשנות את זהות העצים המזעריים.

פתרון: ההוכחה תתבסס על **רדוקציה** מהבעיה הנתונה (מציאת עץ פורש מזערי בגרף עם משקלים כלשהם) לבעיה שכבר ידוע לנו פתרון עבורה (מציאת עץ פורש מזערי בגרף עם משקלים אי-שליליים). יהי $G=(V,E)$ גרף קשיר ולא מכוון עם פונקציית משקל $w: E \to \mathbb{R}$. נרצה להראות כי **אלגוריתם Kruskal** ו**אלגוריתם Prim** מוצאים **עץ פורש מזערי** (MST) גם כאשר ישנן צלעות עם משקל שלילי. ראשית, נגדיר בעיית MST חדשה ו"שקולה" על גרף $G$ עם משקלים אי-שליליים בלבד. נבחר קבוע $C \ge 0$ כך שלכל צלע $e \in E$ יתקיים $w(e) + C \ge 0$. בחירה טבעית לקבוע כזה היא $C = \max(0, -\min_{e \in E} \{w(e)\})$. כעת, נגדיר פונקציית משקל חדשה, $w': E \to \mathbb{R}_{iguplus 0}$, באופן הבא: $w'(e) = w(e) + C$ לכל $e \in E$. לפי הגדרת $C$, כל המשקלים תחת $w'$ הם אי-שליליים. על פי הנתון בשאלה, האלגוריתמים של Prim ו-Kruskal פועלים נכונה על גרפים עם משקלים אי-שליליים, ולכן ימצאו עץ פורש מזערי עבור הגרף $G$ עם פונקציית המשקל $w'$. כעת נוכיח שהפעולה של הוספת קבוע $C$ לכל הצלעות אינה משנה את קבוצת עצי הפורש המזעריים של הגרף. יהי $T$ עץ פורש כלשהו בגרף $G$. משקלו של $T$ תחת פונקציית המשקל המקורית $w$ הוא $W(T) = \sum_{e \in T} w(e)$. משקלו של אותו עץ $T$ תחת פונקציית המשקל החדשה $w'$ הוא: $W'(T) = \sum_{e \in T} w'(e) = \sum_{e \in T} (w(e) + C)$ מכיוון שבכל עץ פורש בגרף עם $|V|$ צמתים יש בדיוק $|V|-1$ צלעות, נוכל להמשיך ולפתח את הביטוי: $W'(T) = \sum_{e \in T} w(e) + \sum_{e \in T} C = W(T) + (|V|-1) \cdot C$ הביטוי $(|V|-1) \cdot C$ הוא קבוע שאינו תלוי בבחירת העץ הפורש $T$. נסמן קבוע זה ב-$K = (|V|-1) \cdot C$. אם כן, לכל עץ פורש $T$ מתקיים $W'(T) = W(T) + K$. כעת נראה שעץ $T^*$ הוא MST תחת $w$ אם ורק אם הוא MST תחת $w'$. ($\Rightarrow$) נניח ש-$T^*$ הוא MST תחת $w$. זה אומר שלכל עץ פורש $T$ אחר, $W(T^*) \le W(T)$. אם נוסיף $K$ לשני אגפי אי-השוויון, נקבל: $W(T^*) + K \le W(T) + K$ כלומר, $W'(T^*) \le W'(T)$. מכיוון שזה נכון לכל עץ פורש $T$, הרי ש-$T^*$ הוא MST גם תחת $w'$. ($\Leftarrow$) נניח ש-$T^*$ הוא MST תחת $w'$. זה אומר שלכל עץ פורש $T$ אחר, $W'(T^*) \le W'(T)$. נשתמש בקשר שמצאנו: $W(T^*) + K \le W(T) + K$ נחסר $K$ משני אגפי אי-השוויון ונקבל $W(T^*) \le W(T)$. מכיוון שזה נכון לכל עץ פורש $T$, הרי ש-$T^*$ הוא MST גם תחת $w$. **סיכום ההוכחה:** 1. בהינתן גרף $G$ עם משקלים $w$ (שחלקם שליליים), אנו יוצרים בעיה חדשה עם משקלים $w'(e) = w(e) + C$ המבטיחה אי-שליליות. 2. אנו יודעים שהאלגוריתמים של Prim ו-Kruskal ימצאו עץ פורש מזערי, נקרא לו $T_{alg}$, עבור הבעיה עם המשקלים $w'$. 3. הראינו שעץ הוא MST ביחס ל-$w'$ אם ורק אם הוא MST ביחס ל-$w$. 4. מכאן נובע שהעץ $T_{alg}$ שהאלגוריתמים מצאו הוא אכן עץ פורש מזערי עבור הבעיה המקורית עם המשקלים $w$. למעשה, ניתן להראות שהאלגוריתמים יפיקו בדיוק את אותו העץ בשני המקרים, מכיוון שהסדר היחסי בין משקלי הצלעות נשמר ($w(e_1) \le w(e_2) \iff w(e_1)+C \le w(e_2)+C$), והבחירות החמדניות של שני האלגוריתמים תלויות רק בסדר היחסי הזה. $\blacksquare$