מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/עצים
דף זה עוסק בעצים, שהם סוג מסוים וחשוב מאד של גרפים. הדף מגדיר הן עצים מכוונים והן עצים לא מכוונים (על גרפים מכוונים ולא מכוונים, בהתאמה), אך מתמקד בעיקר בעצים לא מכוונים.
כדאי לדעת: בספר הקורס, הפרק "Sets, Etc." (תת-פרק 5) מכסה נושא זה. |
הגדרות
עריכהעץ לא מכוון
עריכה
הגדרה: עץ (לא מכוון) הוא גרף (לא מכוון) קשיר וחסר מעגלים:
|
דוגמה: בתרשים הבא:
|
הגדרה: גרף (לא מכוון) חסר מעגלים נקרא יער. |
עכשיו תורכם: כל יער הוא בהכרח אוסף עצים. וודא שהנך מבין מדוע. |
דוגמה: בתרשים הקודם, A, C, וD מראים גרפים חסרי מעגלים. A מראה יער בעל שני עצים, וכ"א מC וD מראה יער בעל עץ יחיד. |
עץ מכוון
עריכהעץ מכוון בעל שורש הוא גרף (מכוון) קשיר מ ובעל מסלולים ייחודיים.
- קשיר מ - יש מסלול מ לכל צומת .
- בעל מסלולים ייחודיים - לכל שני צמתים , יש לכל היותר מסלול אחד מ ל .
דוגמה: בתרשים הבא:
|
מספר משפטים
עריכה
משפט: נתון גרף (מכוון או לא מכוון) . אם G הוא עץ (מכוון או לא מכוון), אז . |
הוכחה: ההוכחה באינדוקציה על מספר הצמתים, .
(בסיס האינדוקציה) כש , אז עץ (שכאמור הינו חסר מעגלים), בהכרח אינו מכיל אף קשת. אם אין אף קשת, אז .
(מעבר האינדוקציה) נניח שהטענה נכונה עבור , ונראה שהיא נכונה עבור . ניקח עץ בעל צמתים, ונבחר צומת כלשהו. נניח שהקשתות היוצאות מ הן . אם נמחק מהגרף את והקשתות היוצאות ממנו, נקבל גרף בעל צמתים, ו קשתות. הדבר מתואר בתרשים הבא:
בגרף החדש אין מעגלים (כי מחיקת צמתים וקשתות אינה יכולה ליצור מעגל), ולכן הוא יער, כלומר אוסף של עצים. קל מאד לראות ש "ילדיו" של הם עצים (הם קשירים עפ"י ההגדרה, והגרף כאמור חסר מעגלים). אבל, יותר מכך, קל לראות שכל צומת בגרף (למעט כמובן ) נמצא באחד מ העצים: אם קיים צומת כזה, אז לא ייתכן שהגרף היה קשיר (הצומת אינו קשיר לאף עץ, ולא היה קשיר ל ). מכאן קל לראות שמדובר ביער של עצים.
כל אחד מהעצים בהכרח מכיל פחות מ צמתים (כי הוא אינו כולל את ), ולכן הנחת האינדוקציה חלה לגביו. נניח שלעץ הראשון יש צמתים, לעץ השני יש צמתים, וכן הלאה. לפי הנחת האינדוקציה, לעץ הראשון יש קשתות, לעץ השני יש קשתות, וכן הלאה. מספר הצמתים בגרף החדש, לכן, הוא , ומספר הקשתות בו הוא .
הגרף החדש, אבל, נוצר ממחיקת צומת אחד ו קשתות מהגרף המקורי. בגרף המקורי, לכן, היו
צמתים, ומספר קשתותיו
המשפט הבא הוא הרחבה של המשפט שאותו הוכחנו כרגע (תתבקש להוכיחו בשיעורי הבית).
משפט: נתון גרף (לא מכוון) . אם שתיים משלוש התכונות הבאות מתקיימות, אז גם השלישית מתקיימת:
|
עץ פורש
עריכה
הגדרה: נתון גרף (מכוון או לא מכוון) . נאמר ש הוא עץ פורש של , אם:
|
דוגמה: בתרשים הבא, A הוא גרף (לא מכוון) קשיר שאינו עץ (מפני שהוא מכיל מעגלים). כל אחד מB וC הוא עץ פורש של A. |
מכאן ועד סוף הדף נוכיח את המשפט החשוב הבא. (משפט זה ישמש אותנו, בין היתר באלגוריתם Kruskal ואלגוריתם Prim.)
משפט: אם גרף לא מכוון קשיר, אז יש עץ פורש ל . |
כדי להוכיח את המשפט, נשתמש ב"פסוודו-קוד" הבא:
# Takes a connected undirected graph (G)
# Returns a set of edges E' such that (V(G), E') is a tree.
Grow-Tree(G)
1 V= V(G)
2 E' = {}
3 while (V, E') isn't a tree
4 e = some (u, v) where u, v are from different trees
5 E' = E' ∪ {e}
6 return E'
דוגמה: בתרשים הקודם, B וC היו עצים פורשים של A. התרשים הבא מראה סידרת פעולות אפשרית שהיתה מובילה מA לB בתרשים הקודם. |
נסיים בהוכחת המשפט. נראה שה"פסוודו-קוד" אכן בונה עץ פורש.
הוכחה: ההוכחה היא באינדוקציה על איטרציית הלולאה 3-5. נראה שבתחילת האיטרציה ה , יש יער בעל עצים.
(בסיס האינדוקציה) בתחילת האיטרציה הראשונה עדיין לא בחרנו אף קשת, ולכן יש קבוצה של צמתים בודדים, או, במילים אחרות, עצים בגודל 1 כל אחד.
(מעבר האינדוקציה) נניח שבתחילת האיטרציה ה יש יער בעל עצים. אם אין קשת המחברת בין שני צמתים מעצים שונים, אז הגרף המקורי אינו קשיר (בניגוד להנחתנו הבסיסית). נניח, אם כן, שיש קשת כזו, המחברת בין שני עצים; נניח שקבוצת צמתי העץ של היא , וקבוצת צמתי העץ של היא . קל לראות שהוספת גורמת ל להיות קשירה. מעבר לכך, אבל, הוספת הקשת גם אינה מייצרת מעגלים ב : מספר הקשתות של הוא בהכרח , ולכן בהכרח מדובר בעץ (ציינו זאת מקודם). לכן בסוף האיטרציה ה יהיו עצים.
הקשר לאלגוריתמי גרפים אחרים שנלמד
עריכהכדאי לדעת: בקורס נלמד מספר אלגוריתמים (ודמויי-אלגוריתמים) לבניית עץ פורש. הם מתוארים בתרשים הבא:
|
הפרק הקודם: גרפים וייצוגיהם |
עצים תרגילים |
הפרק הבא: אלגוריתם Union-Find |