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

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

רמז: הזיזו את כל המשקלים בקבוע $\delta$ כך שכולם יהיו אי-שליליים. הראו שמשקל כל עץ פורש גדל בדיוק ב-$(|V|-1)\delta$ — ולכן זהות העפ"מ נשמרת.

פתרון: **הרדוקציה (הזזת משקלים).** 1. סרוק את הצלעות ומצא צלע $e_0$ בעלת המשקל המזערי. 2. הגדר $\delta := \max\big(0,\,-w(e_0)\big)$, ופונקציית משקל חדשה $w_0:E\to\mathbb{R}$ לפי $w_0(e)=w(e)+\delta$. כעת $w_0(e)\ge 0$ לכל $e$. 3. הרֵץ את Prim/Kruskal על $G$ עם $w_0$ (מקרה אי-שלילי — נכונותם מובטחת). 4. החזר את העץ המתקבל; נראה שהוא עפ"מ גם עבור $w$. **הוכחת נכונות (שלב 4).** תהיינה $T,T_0$ העפ"מים ביחס ל-$w$ ול-$w_0$ בהתאמה. שניהם עצים פורשים עם $n:=|V|-1$ צלעות. לכל עץ פורש $T'$: $$w(T')=\sum_{e\in T'} w(e)=\sum_{e\in T'}\big(w_0(e)-\delta\big)=w_0(T')-n\delta.$$ כלומר הוספת קבוע $\delta$ לכל צלע מזיזה את משקל **כל** עץ פורש באותו סכום $n\delta$, ולכן סדר המשקלים בין העצים נשמר. נניח בשלילה ש-$T_0$ (העפ"מ של $w_0$) אינו עפ"מ של $w$; אז $w(T)<w(T_0)$, ומכאן $w_0(T)-n\delta < w_0(T_0)-n\delta$, כלומר $w_0(T)<w_0(T_0)$ — בסתירה לכך ש-$T_0$ עפ"מ ביחס ל-$w_0$. $\blacksquare$ **זמן ריצה.** סריקת הגרף $O(|E|+|V|)$, הגדרת $w_0$ ב-$O(1)$ לצלע, והרצת Prim/Kruskal — סה"כ אותה סיבוכיות כמו Prim/Kruskal הרגילים.