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

דף זו עוסק באלגוריתם למציאת ההעץ הפורש הזול ביותר בגרף לא מכוון בעל טבלת עלויות לקשתות.

כדאי לדעת: בספר הקורס, הפרק "Minimum Spanning Tree" מכסה נושא זה.

הבעיה

נתונים גרף לא מכוון $\displaystyle G=(V,E)$ וטבלת עלויות לקשתות $\displaystyle E$. רוצים לדעת מהי קבוצת הקשתות הזולה ביותר כך שכל שני צמתים יהיו מחוברים.

דוגמה: בתרשים הבא, המספרים שבקשתות מציינים את עלותן. בעיית העפ"מ. קבוצת הקשתות הזולה ביותר שתחבר כל שני צמתים, היא $\displaystyle \{(1,2),(1,6),(6,7),(7,3),(3,4),(4,5)\}$. קשתות קבוצה זו מודגשות בתרשים הבא. פתרון בעיית העפ"מ.

הרעיון הכללי

כבר ראינו (בעצים) "אלגוריתם" למציאת עץ פורש. נשנה אותו מעט:

# Takes a connected undirected graph (G) and a cost table (Edge-Costs)
# Returns a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
Grow-MST(G, Edge-Costs)
1	V= V(G)
2	E' = {}

3	while (V, E') isn't a tree
4		e = some (u, v): u, v are from different trees; e is a light edge
5		E' = E' ∪ {e}

6	return E'

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

קשתות קלות

הגדרה: נתון גרף (לא מכוון) $\displaystyle G=(V,E)$. נניח ש$\displaystyle E'\subseteq E$ מייצרת יער מ$\displaystyle V$.‏ $\displaystyle e=(u,v)$ היא קשת קלה אם: היא מחברת בין $\displaystyle u,v\in V$ משני עצים שונים. היא הזולה ביותר מבין הקשתות היוצאות מ(לפחות) אחד העצים.

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

דוגמה: בתרשים הבא, A מראה גרף $\displaystyle G=(V,E)$; קבוצת הקשתות המודגשות, $\displaystyle E'\subseteq E$, אכן מייצרת יער. B מראה את כל אחד משלושת העצים מסומן באליפסה. קשתות קלות. בגרף זה: הקשת $\displaystyle (3,7)$ אכן קשת קלה - מבין הקשתות היוצאות מהעץ שצמתיו $\displaystyle \{3,4,5\}$, היא הזולה ביותר. הקשת $\displaystyle (3,4)$ איננה קשת קלה - היא איננה מחברת בין שני עצים שונים. הקשת $\displaystyle (6,7)$ אכן קשת קלה - מבין הקשתות היוצאות מהעץ שצמתיו $\displaystyle \{1,2,6\}$, היא הזולה ביותר. (גם מבין הקשתות היוצאות מהעץ שצמתיו $\displaystyle \{7\}$, היא הזולה ביותר.) הקשת $\displaystyle (2,3)$ איננה קשת קלה - היא איננה הקשת הזולה ביותר היוצאת מעץ כלשהו.

המשפט הקשת הקלה - קשת בטוחה

המשפט הבא ידוע בשם Light Edge - Safe Edge, והוא אחד המשפטים המפורסמים יותר בגרפים:

משפט: קשת קלה - קשת בטוחה נתון גרף (לא מכוון) $\displaystyle G=(V,E)$. נניח ש$\displaystyle E'\subseteq E$ מייצרת יער מ$\displaystyle V$,‏ ויותר מכך, נניח ש$\displaystyle E'$ היא תת-קבוצה של קשתות עפ"מ (עץ פורש מינימום - או עץ פורש שהוא הזול ביותר מבין כל העצים הפורשים). אם $e'$ היא קשת קלה, אז גם $\displaystyle E'\bigcup \{e'\}$ תת קבוצה של קשתות עפ"מ.

לפני שנוכיח את המשפט, נשים לב להשלכותיו.

שימו לב: ברעיון הכללי ראינו "פסוודו-קוד" למציאת עפ"מ. על פי משפט זה, של 3-5 של Grow-MST יבנו עפ"מ.

כעת נוכיח את המשפט.

הוכחה: ננסח מחדש את הטענה. נניח גרף קשיר לא-מכוון $\displaystyle G=(V,E)$ כלשהו. אם בחרנו תת-קבוצה של קשתות עפ"מ, ואחד העצים הוא $\displaystyle U$, אז יש גם עפ"מ הכולל את הקשת הקלה היוצאת מ$\displaystyle U$.

בתרשים הבא, לדוגמה, אם הקשתות המייצרות את העצים $\displaystyle U$,‏ $\displaystyle U'_{1}$,‏ $\displaystyle U'_{2}$,‏ $\displaystyle U'_{3}$,‏ $\displaystyle U'_{4}$,‏ ו$\displaystyle U'_{5}$ אכן חלק מעפ"מ כלשהו - אז הקשת שעלותה 10 (המחברת בין צומת כלשהו ב$\displaystyle U$לצומת כלשהו ב$\displaystyle U'_{1}$) גם היא (יחד עם הקשתות שנבחרו עד כה) חלק מעפ"מ כלשהו.

הוכחת הקשת הקלה - הקשת הבטוחה - 1.

לצורך ההוכחה, נניח שקיבלנו שהתבקשנו בשיעורי הבית למצוא עפ"מ ל$\displaystyle G$. (למרבה החלחלה והזעזוע) לא פתרנו את שיעורי הבית, ובמקום זאת התקשרנו לחבר שפתר את הבעיה (כלומר מצא עפ"מ), וביקשנו שיקריא לנו את התשובה. נשים לב לדברים הבאים:

1. התשובה היא בסה"כ רשימה של קשתות $\displaystyle T\subseteq E$.
2. ההנחה היא שהחבר אכן מצא עפ"מ ללא טעות.
3. על אף האמור בסעיף הקודם, ייתכנו שיחות שונות שבהן יקריא החבר רשימות קשתות שונות זו מזו:
   1. איננו יודעים בוודאות שקיים עפ"מ יחיד.
   2. אם רשימת קשתות כלשהי אכן מייצרת עפ"מ, אז גם כל פרמוטציה שלה מייצרת עפ"מ.

מהסעיף הקודם נוכל להסיק שתי מסקנות:

1. קיימת לפחות שיחת טלפון אחת בה בשלב כלשהו החבר הקריא תת-קבוצה שיוצרת את העצים שברשותנו כרגע. ככלות הכל, הנחנו שיש בידינו תת-קבוצה של קשתות עפ"מ.
2. כל שעלינו להוכיח הוא שקיימת לפחות שיחה אחת בה ימשיך החבר ויקריא את הקשת הקלה היוצאת מ$\displaystyle U$.

שימו לב: וודא שהנך מבין מדוע איננו חייבים להוכיח שבכל שיחה יקריא לנו החבר את הקשת הקלה היוצאת מ$\displaystyle U$.

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

הוכחת הקשת הקלה - הקשת הבטוחה - 2.

כעת, כל עץ שנותר בהכרח יתחבר ישירות ל$\displaystyle U$, וזאת מפני שהחבר סיים להקריא לנו את כל הקשתות למעט אלו המחברות ל$\displaystyle U$. אם זה המצב, אז נוכל להתעלם מהקשתות שאינן מחברות בין $\displaystyle U$ לעץ אחר.

התרשים הבא, לדוגמה, מראה את היער שמתקבל לאחר שמשמיטים את הקשתות שלבטח לא יקריא יותר החבר בשיחה זו::

הוכחת הקשת הקלה - הקשת הבטוחה - 3.

בנקודה זו, ברור לחלוטין שעבור כל עץ שנותר, החבר יבחר בקשת הזולה ביותר המחברת את $\displaystyle U$ אליו. בפרט, החבר יהיה חייב לבחור (בשיחה זו) בקשת הקלה היוצאת מ$\displaystyle U$.

שימו לב: נשים לב לנקודה הבאה (בה נוטים להתבלבל מדי שנה). משמעות המשפט היא: הקשת הקלה בטוחה לשימוש. משמעות המשפט איננה: בטוח משתמשים בקשת הקלה. כלומר, אם יש יער שנוצר מתת-קבוצת קשתות עפ"מ, ו$\displaystyle e$ היא הקשת הקלה ביותר היוצאת מאחד העצים, אז בטוח מותר להשתמש בה, אבל לא בטוח שכל עפ"מ משתמש בה.

הקשר לאלגוריתמים אחרים בגרפים

כדאי לדעת: בקורס נלמד מספר אלגוריתמים (ודמויי-אלגוריתמים) לבניית עץ פורש. הם מתוארים בתרשים הבא: היררכיית האלגוריתמים לבניית עץ פורש. "אלגוריתם" Grow-Tree בונה עץ פורש מגרף לא-מכוון קשיר. קל לשנותו כך שיבנה יער קטן ככל האפשר מגרף לא-מכוון. אלגוריתם Union-Find מוצא את רכיבי הקשירות של גרף לא מכוון. קל לשנותו כך שיבנה עץ פורש מגרף לא מכוון קשיר. "אלגוריתם" Grow-MST בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מקרה פרטי של Grow-Tree. אלגוריתם Kruskal בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST. אלגוריתם Prim בונה עץ פורש מינימום מגרף לא-מכוון קשיר בעל טבלת עלויות לקשתות. הוא מימוש של Grow-MST.

הפרק הקודם: אלגוריתם Union-Find

אלגוריתמים למציאת עפ"מ תרגילים

הפרק הבא: אלגוריתם Kruskal