אלגוריתמים לעץ פורש מינימלי בגרף - מה הרעיון הכללי?

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

בשביל להסביר את האלגוריתם הכללי אני צריך עוד מושג אחד בגרפים, שהוא מאוד שימושי וחוזר בכל מקום - חתך. חתך בגרף הוא חלוקה של צמתי הגרף \( V \) לשתי קבוצות זרות \( A,B \) ולא ריקות. כלומר, כל צומת בגרף נמצא באחת מהקבוצות, ורק באחת מהן, ולא מתקיים שכל הצמתים נמצאים רק באחת מהן. בצורה גרפית אפשר לצייר את הצמתים ואז “לחתוך” את הנייר שעליו הן מצויירים באמצע כדי לחלק את הצמתים לשתי קבוצות, וזו אינטואיציה לפשר השם (אבל חתך הוא כל חלוקה של הצמתים לשתי קבוצות, גם אם אין דרך לממש אותה בפועל על ידי חיתוך של איזה דף נייר).

עכשיו, נאמר על קשת כלשהי שהיא עוברת דרך החתך אם היא מחוברת לצמתים משני צדי החתך. פורמלית, קשת \( e=(u,v) \) עוברת דרך החתך אם \( u\in A, v\in B \) (או הפוך - זה לא באמת משנה מי נמצא באיזו קבוצה, כל עוד הם בקבוצות שונות). בעזרת המושגים החדשים שלנו אפשר לתת הגדרה חדשה למושג של “גרף קשיר” - גרף הוא קשיר (כלומר, יש בו מסלול בין כל זוג צמתים) אם ורק אם לכל חתך בגרף, יש קשת שעוברת דרך החתך הזה. איך מוכיחים את הקריטריון הזה?

הרעיון הוא כזה: לכל צומת בגרף, אפשר לדבר על רכיב הקשירות שלו - אלו כל הצמתים בגרף שיש מסלול בינם ובין הצומת. גרף הוא קשיר אם ורק אם קיים בו רכיב קשירות יחיד. כעת, אם גרף אינו קשיר אז ניקח בו רכיב קשירות אחד באופן שרירותי ונסמן את צמתיו ב-\( A \) - הרכיב הזה אינו כל הגרף, ולכן אפשר לסמן את שאר צמתי הגרף ב-\( B \) ולקבל חתך של הגרף. בבירור לא יכולה להיות קשת שעוברת דרך החתך הזה, כי אז היינו מקבלים שיש ב-\( B \) צומת שמחוברת בקשת לצמתי \( A \) אבל אינה באותו רכיב קשירות כמו הצמתים הללו, וזו כמובן סתירה.

זה מוכיח לנו שאם הקריטריון מתקיים, אז הגרף קשיר, אבל צריך גם להוכיח שאם הגרף קשיר אז הקריטריון מתקיים, וגם זה קל: ניקח חתך כלשהו בגרף ונראה שיש קשת שעוברת דרכו. מכיוון שזה חתך, הוא מורכב משתי קבוצות לא ריקות; ניקח צומת בכל אחד מהן. הגרף קשיר, אז יש מסלול שמחבר את הצמתים - נתחיל לטייל עליו מתוך הצומת ששייך ל-\( A \). אנחנו יודעים שהטיול לאורך המסלול הולך להסתיים בצומת ששייך ל-\( B \), אז חייב להיות צעד אחד לפחות שבו אנחנו עוברים מצומת ב-\( A \) אל צומת ב-\( B \), והצעד הזה יהיה על קשת שעוברת דרך החתך - סיימנו!

עכשיו אפשר לתת את הרעיון שמאחורי האלגוריתם הגנרי למציאת עץ פורש מינימלי. האלגוריתם בונה את העץ הפורש קשת-קשת; הוא מתחיל עם קבוצה ריקה של קשתות ובכל צעד מוסיף לה קשת אחת. אחרי בדיוק \( n-1 \) צעדים (כאשר \( n \) הוא מספר הצמתים בגרף) האלגוריתם יסיים עם עץ. איך האלגוריתם בוחר איזו קשת להוסיף? הוא מוצא חתך כלשהו של הגרף שאף קשת מתוך הקבוצה שבנינו עד כה לא עוברת דרכו, ובוחר קשת שעוברת דרך החתך הזה ומוסיף אותה לקבוצה. איזו קשת הוא בוחר? ובכן, הוא נוקט במה שנקרא גישה חמדנית, שפירושה שבכל צעד בוחרים את האפשרות שנראית הכי טובה נקודתית: האלגוריתם יוסיף לקבוצה שהוא בונה את הקשת בעלת המשקל הקטן ביותר מבין כל הקשתות שעוברות דרך החתך (אם יש כמה קשתות עם משקל שהוא מינימלי בוחרים אחת מהן באופן שרירותי).

ההגיון מאחורי האלגוריתם הזה ברור - אנחנו חייבים לבחור קשת כלשהי שעוברת דרך החתך או שהגרף שאנחנו בונים לא יהיה קשיר (כי הנה, יהיה חתך שאין לנו אף קשת שעוברת דרכו), אז למה שלא נבחר את הזולה ביותר האפשרית? כמובן, זו אמנם אינטואיציה נחמדה, אבל זה ממש לא מוכיח שהאלגוריתם עובד; בבעיות מורכבות יותר הגישה החמדנית כושלת בצורה מחפירה. תחשבו למשל על האפשרות ההיפותטית שאם ניקח עכשיו קשת יקרה קצת יותר, היא “תחסל” את כל החתכים בגרף, בעוד שאם ניקח את הקשת הזולה יותר היא תחסל רק חצי מהחתכים בגרף, ואז נצטרך לטפל בעוד חתך, ניקח עבורו עוד קשת, וסכום המחירים שלהן יהיה גדול יותר. זה עשוי, היפותטית, לקרות; אני רוצה להוכיח עכשיו שבפועל זה לא יכול לקרות, ומכאן שהגישה החמדנית אכן פותרת את הבעיה של מציאת עץ פורש מינימלי.

אז איך תעבוד ההוכחה? באמצעות שימוש בתעלול סטנדרטי שהמתמטיקאים מאוד אוהבים, עד כדי כך שהוא כיכב בפוסט הראשון אי פעם בבלוג - שמורות. נציג תכונה כלשהי שקיימת בתחילת האלגוריתם ונשמרת על ידי צעדי האלגוריתם, ומספיקה לנו כדי לראות שבסוף האלגוריתם השגנו את מה שרצינו. במקרה שלנו השמורה היא כזו: בכל שלב, האלגוריתם מחזיק קבוצה \( A \) של קשתות של הגרף שבו מחפשים עץ פורש מינימלי; הקבוצה הזו היא תמיד תת-קבוצה של קבוצת הקשתות של עץ פורש מינימלי כלשהו של הגרף. בניסוח טיפה שונה - תמיד ניתן להשלים אותה לעץ פורש מינימלי על ידי הוספת קשתות (או שהיא עצמה כבר עץ פורש מינימלי שכזה).

ברור שהתכונה הזו מתקיימת בתחילת ריצת האלגוריתם, כי אז הקבוצה ריקה (ובכל גרף אכן קיים עץ פורש מינימלי אחד לפחות). ברור גם שבסוף ריצת האלגוריתם, כאשר בקבוצה יש \( n-1 \) קשתות, קיום השמורה מעיד על כך שהקבוצה עצמה היא עץ פורש מינימלי (למה?), ולכן רק צריך להראות שהשמורה אכן נשמרת. נניח אם כן שהשמורה לא נשמרת; זה אומר שהיה רגע אחד שבו היא התקיימה, ואחריו כבר לא. נסמן את קבוצת הקשתות לפני שהשמורה התקלקלה ב-\( A \); מה שקרה הוא שמצאנו חתך כלשהו \( C \) כך ש-\( A \) לא עוברת דרכו, מצאנו קשת בעלת משקל מינימלי \( e=(u,v) \) שכן עוברת דרך החתך והוספנו אותה ל-\( A \) ובכך קלקלנו את השמורה. זה אומר שאת \( A \) אפשר היה להרחיב לעץ פורש מינימלי, אבל את \( A\cup\left\{e\right\} \) כבר אי אפשר.

אם כן, הבה ונסתכל על עץ פורש מינימלי שמרחיב את \( A \). הסיבה היחידה שבגללה העץ הזה לא מרחיב את \( A\cup\left\{e\right\} \) היא בגלל ש-\( e \) לא נמצאת בו (כי שאר הצמתים כן), אז התעלול שנרצה לבצע הוא להעיף מהעץ קשת כלשהי שאינה שייכת ל-\( A \) ולדחוף את \( e \) במקומה, כך שהתוצאה שתתקבל עדיין תהיה עץ פורש מינימלי. נסו להבהיר לעצמכם מדוע אם עשינו את זה, סיימנו.

האינטואיציה הראשונית שלי היא להגיד “אוקיי, בואו נסתכל על החתך \( C \). בגלל שהעץ קשיר, יש קשת שעוברת דרך החתך; נעיף אותה ונכניס את \( e \) במקומה”. רק שזה לא עובד, ואני ממליץ לכם בחום לנסות לבנות דוגמה נגדית שעבורה זה לא עובד. אמנם, זה באמת יהיה מה שאעשה בסופו של דבר, אבל אני לא יכול לבחור סתם קשת שנמצאת על החתך - ייתכן מאוד שיהיו כמה קשתות כאלו, ואני צריך לבחור אחת מהן בחוכמה. מה שאני רוצה לנסות לשמר הוא את תכונת הקשירות של העץ; המינימליות שלו ממילא מובטחת מכך ש-\( e \) היא הקשת בעלת המשקל המינימלי מבין כל הקשתות שעל החתך (למעשה, די ברור שהקשתות היחידות ש”מתחרות” איתה הן קשתות בעלות אותו משקל ורק אותן יש סיכוי להסיר בכלל אם העץ שממנו אנחנו מתחילים הוא מינימלי).

את התעלול שנעשה עכשיו אפשר לתאר מילולית כך: נוסיף את \( e \) לעץ. זה יגרום בודאות להיווצרות מעגל. נחפש קשת על המעגל שעוברת דרך החתך ואינה \( e \), נסיר אותה מהגרף ונקבל שוב עץ. פורמלית, מה שעושים הוא זה: מכיוון שכרגע יש לנו ביד עץ, הרי שיש כבר מסלול שמחבר את \( u,v \) (הקצוות של הקשת \( e \)). נסתכל על המסלול הזה. הוא בהכרח עובר מצד אחד של החתך לצד השני שלו (כי \( u,v \) נמצאים בצדדים שונים של החתך) ולכן יש על המסלול הזה קשת, \( (x,y) \) שעוברת דרך החתך כחלק מהמסלול. נסיר את הקשת הזו מהעץ, ונכניס את \( e \) לגרף שהתקבל. די להוכיח שהוא עדיין קשיר, ולשם כך די להראות שאפשר להגיע מ-\( x \) אל \( y \) (כלומר “לסמלץ” את מה שהקשת \( (x,y) \) נתנה לנו). איך נעשה את זה? פשוט מאוד: קודם ראינו שיש מסלול מהצורה \( u\rightarrow x\rightarrow y\rightarrow v \); כעת פשוט נשתמש במסלול הזה בצורה קצת שונה, תוך הסתמכות חזקה על כך שהגרף אינו מכוון: קודם כל נלך מ-\( x \) אל \( u \), אחר כך נחצה את הקשת \( e \) ונגיע אל \( v \), ולסיום נלך מ-\( v \) אל \( y \). פשוט מאוד, ומסיים את ההוכחה.

עכשיו אפשר להסביר איך קרוסקל ופרים הם מקרים פרטיים של האלגוריתם הזה. נתחיל עם קרוסקל. מה שקרוסקל עושה הוא להתחיל במיון של כל הקשתות לפי משקלן, מהקלה ביותר לכבדה ביותר. עכשיו הוא עובר עליהן אחת אחת, ולכל קשת כזו הוא בודק האם היא מחברת צמתים אשר שייכים לרכיבי קשירות שונים בגרף. אם זה לא המצב, עוברים לקשת הבאה; אם זה אכן המצב, הרי שרכיבי הקשירות הללו יוצרים לנו חתך בגרף (או, אם להיות מדוייקים פורמלית, רכיב הקשירות של אחד מצמתי הקשת הוא קבוצה אחת בחתך, וכל יתר הגרף הוא הקבוצה השניה), ואז מוסיפים את הקשת לגרף. מובטח לנו בודאות מוחלטת שהקשת שלנו היא הקלה ביותר על החתך הזה, שכן בקשתות יותר קלות שעל החתך כבר היינו מטפלים קודם ומוסיפים אחת מהן לעץ שאנחנו בונים.

עיקר הקושי בקרוסקל הוא הבדיקה האם שני צמתים שייכים לאותו רכיב שקילות או לא, והדגש הוא על שימוש במבנה נתונים שיאפשר לבצע את הבדיקה הזו עם מחיר מינימלי לזמן הריצה. לשם כך צריך מבנה נתונים שיודע לנהל מחלקות שקילות של אובייקטים, ותומך בצורה יעילה בשתי פעולות: מציאת נציג למחלקת שקילות של איבר (ואז בדיקה אם שני איברים שייכים לאותה מחלקת שקילות כוללת את מציאת הנציגים שלהם והשוואתם), ואיחוד של שתי מחלקות שקילות קיימות (שהרי מה שקורה כשמוסיפים קשת לגרף הוא ששני רכיבי קשירות מתאחדים לרכיב קשירות אחד). מבנה נתונים שמנהל ביעילות את שתי הפעולות הללו מכונה Union/Find ואציג אותו בפוסט הבא - זה מבנה נתונים חביב מאוד, שמספר התחכמויות פשוטות הופכות אותו ליעיל למדי.

האלגוריתם של פרים נוקט גישה שונה למדי. הוא מתחיל מצומת “שורש” נתון כלשהו, ובכל שלב של הריצה שלו, החתך שהוא בוחר מורכב ממחלקת השקילות של אותו “שורש” ויתר הגרף, והאלגוריתם בוחר בכל שלב בקשת הקלה ביותר שנמצאת על החתך הזה. לשם כך האלגוריתם מתחזק תור עדיפויות שכולל את כל הצמתים בגרף שאינם ברכיב הקשירות של השורש, כאשר העדיפות של צומת נקבעת על פי משקל הקשת הקלה ביותר שמחברת אותו לרכיב הקשירות של השורש (אם אין כזו, אז העדיפות של הצומת היא “מינוס אינסוף” - הגרועה ביותר האפשרית). בכל צעד האלגוריתם שולף את הצומת שבראש התור, מוסיף את הקשת הקלה ביותר שמחברת אותו לרכיב הקשירות אל העץ שאותו האלגוריתם בונה, ואז מעדכן את תור העדיפויות בהתאם לשינויים (כל שכן של הצומת החדש עשוי להתעדכן מבחינת מחיר החיבור שלו לרכיב הקשירות של השורש).

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

בפעם הבאה: קרוסקל, ו-Union/Find. יהיה אקשן!