מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/קבוצת היזון חוזר/תשובה

ראשית נאפיין את $\displaystyle E\setminus E'$בעזרת התנאי שניתן על $\displaystyle E'$.

משפט: אם $\displaystyle E'$היא קבוצת ההיזון החוזר הזולה ביותר, אז $\displaystyle E\setminus E'$היא קבוצת קשתות עץ פורש מקסימום.

נסמן כ$\displaystyle w_{e}$ את מחיר כל קשת $\displaystyle e$ (כלומר Edge-Costs[e]), ונסמן כ$\displaystyle w$את סך משקל הקשתות, $\displaystyle \sum _{e\in E}[w_{e}]$.

הוכחה: הקבוצה $\displaystyle E'$, היא, עפ"י ההגדרה, הקבוצה המביאה למינימום את

$\displaystyle \sum _{e\in E'}[w_{e}]=w-\sum _{e\in E\setminus E'}[w_{e}]$
כך ש$\displaystyle E\setminus E'$חסרת מעגלים. במילים אחרות, הקבוצה $\displaystyle E'$היא הקבוצה כך שהקבוצה $\displaystyle E\setminus E'$היא הקבוצה היקרה ביותר שעדיין חסרת מעגלים, ולכן $\displaystyle E\setminus E'$היא היער היקר ביותר. אבל קל לראות שאם $\displaystyle E\setminus E'$ איננה עץ, אז יש קבוצה חסרת מעגלים יקרה לפחות כמוה (הגרף קשיר, ולכן תהיה לפחות עוד קשת אחת המחברת שני עצים ממנה).

נמצא, לכן, דרך יעילה למצוא עץ פורש מקסימום בגרף.

נסמן כ$\displaystyle {\bar {u}}$ את מחיר הקשת היקרה ביותר פלוס 1 (כלומר $\displaystyle {\bar {u}}=\max _{e\in E}[w_{e}]+1$),‏ ונסמן לכל קשת $\displaystyle e$,‏ $\displaystyle w'_{e}={\bar {u}}-w_{e}$.

משפט: אם נבנה טבלה Edge-Costs'כל שלכל קשת $\displaystyle e$,‏ Edge-Costs'[e] $\displaystyle =w'_{e}$, ונריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', אז קבוצת הקשתות שתוחזר תהווה קשתות לעץ פורש מקסימום עם Edge-Costs.

הוכחה: נשים לב שכל $\displaystyle w'_{e'}$ חיובי ממש (לפי הבניה), ולכן נוכל להריץ אלגוריתם עץ פורש מינימום עם Edge-Costs', והקבוצה $\displaystyle W$ שתוחזר לנו תהיה קבוצה בת גודל $\displaystyle |V|-1$. בנוסף,

$\displaystyle \min _{W}\sum _{e\in W}[w'_{e}]=$
$\displaystyle \min _{W}\sum _{e\in W}[{\bar {u}}-w_{e}]=$
$\displaystyle \min _{W}[(|V|-1)\cdot {\bar {u}}-\sum _{e\in W}[w_{e}]]=$
$\displaystyle (|V|-1)\cdot {\bar {u}}-\max _{W}\sum _{e\in W}[w_{e}].$

נוכל, לכן, לפתור את הבעיה בשלבים הבאים:

1. נבנה את טבלת העלויות Edge-Costs'(בסיבוכיות $\displaystyle \Theta (|E|)$).
2. נריץ את אלגוריתם Prim עם Edge-Costs' (בסיבוכיות $\displaystyle \Theta ((|V|+|E|)\cdot \log(|V|)$).
3. נמצא את הקשתות שלא הוחזרו מאלגוריתם Prim (בסיכוכיות $\displaystyle \Theta (|E|)$).

הסיבוכיות הכוללת היא $\displaystyle \Theta ((|V|+|E|)\cdot \log(|V|)$.