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

נתון גרף לא מכוון $G=(V,E)$ משוקלל, עם משקלים שלמים וחיוביים $w(e)>0$ לכל הצלעות. קבוצת צלעות $F \subseteq E$ נקראת **מנתקת-מעגלים** אם לאחר הסרתה לא נותרים מעגלים בגרף, כלומר $G'=(V,E\setminus F)$ חסר-מעגלים. משקלה של קבוצת צלעות $F$ הוא $w(F)=\sum_{e\in F} w(e)$. הציגו אלגוריתם למציאת קבוצת צלעות מנתקת-מעגלים בעלת משקל מזערי, והוכיחו את נכונותו.

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

פתרון: **רעיון מרכזי.** מכיוון ש-$w(E)=w(F)+w(E\setminus F)$ קבוע, מזעור $w(F)$ שקול ל**מקסום** $w(E\setminus F)$. הקבוצה $E\setminus F$ חייבת להיות חסרת-מעגלים ולפרוש את רכיבי הקשירות של $G$ — כלומר **יער פורש**. לכן $E\setminus F$ צריכה להיות **יער פורש מקסימלי** (מקסימום משקל), ו-$F$ המבוקשת היא משלימתו. **האלגוריתם.** 1. הרֵץ אלגוריתם לעץ (יער) פורש **מקסימלי** — למשל קרוסקל כשממיינים את הצלעות בסדר **יורד**, או פרים שבו בכל צעד בוחרים את הצלע ה**כבדה** ביותר החוצה מהעץ. יהי $T$ קבוצת צלעותיו. 2. החזר $F = E \setminus T$. **הוכחת נכונות.** תהי $F^\ast$ קבוצה מנתקת-מעגלים כלשהי; אז $E\setminus F^\ast$ חסרת-מעגלים ופורשת את רכיבי הקשירות, ולכן היא יער בעל $|V|-c$ צלעות ($c$ = מספר רכיבי הקשירות). לכל קבוצה מנתקת-מעגלים מתקיים $|E\setminus F|\le |V|-c$, ולקבוצה **מזערית** מתקיים שוויון (אחרת אפשר להחזיר עוד צלע בלי ליצור מעגל, בסתירה למזעריות). לכן מזעור $w(F)$ שקול למקסום $w(E\setminus F)$ תחת האילוץ ש-$E\setminus F$ יער פורש — וזהו בדיוק יער פורש מקסימלי, שהאלגוריתם מוצא. $\blacksquare$ **סיבוכיות.** האלגוריתם החמדני (פרים עם ערימה, או קרוסקל) רץ בזמן $O(|E|+|V|\log|V|)$, ומעבר נוסף על הצלעות ב-$O(|E|)$ מחזיר את $F=E\setminus T$. סה"כ $O(|E|+|V|\log|V|)$.