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

שאלה 4 – קביעת קבוצה מינימלית ממשקלות מעגליות נתונה רשת קשיר ולא מכוון $G=(V,E)$ עם משקלות שלמים חיוביים $w(e)>0$ לכל הצלעות, וקביצות צלעות $F\subseteq E$ קבוצות צלעות. קביצות צלעות מנויות-מעגליות אם כזומור חוגף $G'=(V,E\setminus F)$ של קביצות הצלעות של קביצות הצלעות של קביצות משקלי הצלעות בקביצות $w(F)=\sum_{e\in F} w(e)$ משקלי הצלעות בקביצות מעגליות בעלת משקל מינימלי מתחשבנות בתוך לחיפוש שמופעלת לתוך. למה מרכזית: אם $F$ קביצות מנויות-מעגליות אז $G'=(V,E\setminus F)$ היינו. חוקרות החמיכה המרכזיות: 2 3 4 5 _6 _7 אלגוריתמים למצואיות קביצות צלעות מנויות-מעגליות במעגל מטוני:

רמז: חשבו על הקשר בין מציאת קבוצת צלעות להסרה במשקל מינימלי לבין מציאת קבוצת הצלעות הנותרות במשקל מקסימלי. מהי התכונה המבנית של קבוצת הצלעות הנותרות?

פתרון: השאלה כפי שהיא מנוסחת אינה ברורה לחלוטין. אנו נפרש אותה כבעיה קלאסית מתורת הגרפים, המתאימה להקשר של הקורס: מציאת **קבוצת שוברת מעגלים (feedback edge set) במשקל מינימלי** בגרף קשיר, לא מכוון וממושקל $G=(V,E)$. קבוצת שוברת מעגלים $F \subseteq E$ היא קבוצת צלעות שהסרתן מהגרף הופכת אותו לחסר מעגלים (ליער). המטרה היא למצוא $F$ כזו שמשקלה הכולל $w(F)=\sum_{e\in F} w(e)$ הוא מינימלי.\n\n**הבעיה השקולה**\n\nנשים לב כי אם מסירים קבוצת צלעות $F$ מהגרף $G$, קבוצת הצלעות הנותרת היא $T = E \setminus F$. הדרישה שהגרף $G'=(V, T)$ יהיה חסר מעגלים אומרת ש-$T$ מהווה יער.\nמשקל הקבוצה $F$ הוא $w(F) = w(E) - w(T)$, כאשר $w(E) = \sum_{e \in E} w(e)$ הוא סכום משקלי כל הצלעות בגרף והוא ערך קבוע.\nכדי למזער את $w(F)$, עלינו למקסם את $w(T)$. לכן, הבעיה שקולה למציאת יער $T$ בעל משקל כולל מקסימלי.\nמכיוון שהגרף הנתון $G$ קשיר, היער בעל המשקל המקסימלי חייב להיות **עץ פורש מקסימלי** (Maximum Spanning Tree). כל יער שאינו עץ פורש (כלומר, אינו מקשר את כל צמתי הגרף) ניתן להרחיב על ידי הוספת צלע מבלי ליצור מעגל, ובכך להגדיל את משקלו (כי המשקלים חיוביים). לכן, הפתרון האופטימלי יהיה עץ המקשר את כל הצמתים.\n\n**אלגוריתם**\n\nהאלגוריתם לפתרון הבעיה הוא כדלקמן:\n1. מצא עץ פורש מקסימלי $T_{max}$ של הגרף $G$.\n2. החזר את קבוצת הצלעות $F = E \setminus T_{max}$.\n\nניתן למצוא עץ פורש מקסימלי על ידי שינוי קל באלגוריתמים למציאת עץ פורש מינימלי:\n* **אלגוריתם קרוסקל למשקל מקסימלי:** מיין את הצלעות בסדר **יורד** של משקלן, ועבור על הצלעות הממוינות. הוסף כל צלע שאינה סוגרת מעגל עם הצלעות שכבר נבחרו.\n* **אלגוריתם פרים למשקל מקסימלי:** התחל מצומת שרירותי. בכל שלב, הוסף לעץ את הצלע בעלת המשקל **המקסימלי** המחברת צומת שכבר בעץ לצומת שמחוץ לעץ.\n\n**הוכחת נכונות**\n\nיהי $T_{max}$ עץ פורש מקסימלי של $G$, ויהי $F = E \setminus T_{max}$.\nראשית, $F$ היא אכן קבוצת שוברת מעגלים, מכיוון שהגרף שנותר לאחר הסרתה הוא $(V, T_{max})$, שהוא עץ, ועל כן חסר מעגלים.\nכעת נוכיח כי $w(F)$ מינימלי. נניח בשלילה שקיימת קבוצת שוברת מעגלים $F'$ כך ש-$w(F') < w(F)$.\nנסמן $T' = E \setminus F'$. מכיוון ש-$F'$ שוברת מעגלים, $T'$ הוא יער.\nמההנחה $w(F') < w(F)$ נובע ישירות כי $w(T') > w(T_{max})$.\nאבל $T_{max}$ הוא עץ פורש בעל משקל מקסימלי בגרף $G$. בפרט, משקלו הוא מקסימלי מבין כל תתי-הגרפים חסרי המעגלים של $G$.\nהעובדה ש-$w(T') > w(T_{max})$ כאשר $T'$ הוא יער (תת-גרף חסר מעגלים) עומדת בסתירה להגדרת $T_{max}$ כעץ פורש מקסימלי.\nלפיכך, ההנחה שגויה, ובהכרח $F$ היא קבוצת שוברת מעגלים בעלת משקל מינימלי.\n$\blacksquare$\n\n**סיבוכיות**\n\nהסיבוכיות של האלגוריתם נשלטת על ידי שלב מציאת העץ הפורש המקסימלי.\n* באמצעות אלגוריתם קרוסקל (עם מיון צלעות ומבנה Union-Find), הסיבוכיות היא $O(|E|\log|E|)$.\n* באמצעות אלגוריתם פרים (עם ערימה בינארית), הסיבוכיות היא $O(|E|\log|V|)$.\nבשני המקרים, האלגוריתם הוא פולינומיאלי ויעיל.