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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים

מבני נתונים ואלגוריתמים - מחברת קורס

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

כדאי לדעת:

בספר הקורס, הפרק "Sets, Etc." (תת-פרק 5) מכסה נושא זה.

תוכן עניינים

1 הגדרות
- 1.1 עץ לא מכוון
- 1.2 עץ מכוון
2 מספר משפטים
3 עץ פורש
4 הקשר לאלגוריתמי גרפים אחרים שנלמד

[עריכה] הגדרות

[עריכה] עץ לא מכוון

הגדרה:

עץ (לא מכוון) הוא גרף (לא מכוון) קשיר וחסר מעגלים:

קשיר - מכל צומת $\displaystyle u \in V$ יש מסלול לכל צומת $\displaystyle v \in V$ .
חסר מעגלים - אם מצומת $\displaystyle u \in V$ יש מסלול חזרה אליו, אז המסלול משתמש לפחות בקשת אחת פעמיים. (אם יש מסלול מ $\displaystyle u$ ל $\displaystyle u$ בלי להשתמש באותה קשת פעמיים, אז לגרף יש מעגל.)

דוגמה:

בתרשים הבא:

A אינו עץ, מפני שאינו קשיר (אין מסלול בין $\displaystyle 1$ ל $\displaystyle 7$ , לדוגמה).
B אינו עץ, מפני שאינו חסר-מעגלים (הוא מכיל את המעגל $\displaystyle 6 \rightarrow 7 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6$ , לדוגמה).
כל אחד מC וD אכן עץ.

הגדרה:

גרף (לא מכוון) חסר מעגלים נקרא יער.

עכשיו תורך:

כל יער הוא בהכרח אוסף עצים. וודא שהנך מבין מדוע.

דוגמה:

בתרשים הקודם, A,‏ C,‏ וD מראים גרפים חסרי מעגלים. A מראה יער בעל שני עצים, וכ"א מC וD מראה יער בעל עץ יחיד.

[עריכה] עץ מכוון

עץ מכוון בעל שורש $\displaystyle u$ הוא גרף (מכוון) קשיר מ $\displaystyle u$ ובעל מסלולים ייחודיים.

קשיר מ $\displaystyle u$ - יש מסלול מ $\displaystyle u$ לכל צומת $\displaystyle v$ .
בעל מסלולים ייחודיים - לכל שני צמתים $\displaystyle w, v$ , יש לכל היותר מסלול אחד מ $\displaystyle w$ ל $\displaystyle v$ .

דוגמה:

בתרשים הבא:

A אינו עץ, מפני שאינו קשיר מ1 (אין מסלול מ $\displaystyle 1$ ל $\displaystyle 7$ ).
B אינו עץ, מפני שאינו בעל מסלולים ייחודיים (הוא מכיל שני מסלולים שונים מ $\displaystyle 6$ ל $\displaystyle 4$ ).
כל אחד מC וD אכן עץ ששורשו $\displaystyle 1$ .

גרפים (מכוונים) שהם עצים, וגרפים (מכוונים) שאינם עצים.

[עריכה] מספר משפטים

משפט:

נתון גרף (מכוון או לא מכוון) $\displaystyle G = (V, E)$ . אם G הוא עץ (מכוון או לא מכוון), אז $\displaystyle |E| = |V| - 1$ .

הוכחה: ההוכחה באינדוקציה על מספר הצמתים, $\displaystyle |V|$ .

(בסיס האינדוקציה) כש $\displaystyle |V| = 1$ , אז עץ (שכאמור הינו חסר מעגלים), בהכרח אינו מכיל אף קשת. אם אין אף קשת, אז $\displaystyle |E| = 0 = |V| - 1 = 1 - 1$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עבור $\displaystyle |V| \le n - 1$ , ונראה שהיא נכונה עבור $\displaystyle |V| = n$ . ניקח עץ בעל $\displaystyle n$ צמתים, ונבחר צומת $\displaystyle u$ כלשהו. נניח שהקשתות היוצאות מ $\displaystyle u$ הן $\displaystyle e_1, ..., e_i$ . אם נמחק מהגרף את $\displaystyle u$ והקשתות היוצאות ממנו, נקבל גרף בעל $\displaystyle |V| - 1$ צמתים, ו $\displaystyle |E| - i$ קשתות. הדבר מתואר בתרשים הבא:

בגרף החדש אין מעגלים (כי מחיקת צמתים וקשתות אינה יכולה ליצור מעגל), ולכן הוא יער, כלומר אוסף של עצים. קל מאד לראות ש $\displaystyle i$ "ילדיו" של $\displaystyle u$ הם $\displaystyle i$ עצים (הם קשירים עפ"י ההגדרה, והגרף כאמור חסר מעגלים). אבל, יותר מכך, קל לראות שכל צומת בגרף (למעט כמובן $\displaystyle u$ ) נמצא באחד מ $\displaystyle i$ העצים: אם קיים צומת כזה, אז לא ייתכן שהגרף היה קשיר (הצומת אינו קשיר לאף עץ, ולא היה קשיר ל $\displaystyle u$ ). מכאן קל לראות שמדובר ביער של $\displaystyle i$ עצים.

כל אחד מהעצים בהכרח מכיל פחות מ $\displaystyle n$ צמתים (כי הוא אינו כולל את $\displaystyle u$ ), ולכן הנחת האינדוקציה חלה לגביו. נניח שלעץ הראשון יש $\displaystyle |V_1|$ צמתים, לעץ השני יש $\displaystyle |V_2|$ צמתים, וכן הלאה. לפי הנחת האינדוקציה, לעץ הראשון יש $\displaystyle |V_1| - 1$ קשתות, לעץ השני יש $\displaystyle |V_2| - 1$ קשתות, וכן הלאה. מספר הצמתים בגרף החדש, לכן, הוא $\displaystyle \sum_{i = 1}^i[|V_i|]$ , ומספר הקשתות בו הוא $\displaystyle \sum_{i = 1}^i[|V_i| - 1]$ .

הגרף החדש, אבל, נוצר ממחיקת צומת אחד ו $\displaystyle i$ קשתות מהגרף המקורי. בגרף המקורי, לכן, היו $\displaystyle |V| = \sum_{i = 1}^i[|V_i|] + 1$

צמתים, ומספר קשתותיו

$\displaystyle |E| =$
$\displaystyle \sum_{i = 1}^i[|V_i| - 1] + i =$
$\displaystyle \sum_{i = 1}^i[|V_i] - i + i =$
$\displaystyle \sum_{i = 1}^i[|V_i] =$
$\displaystyle |V| - 1$

המשפט הבא הוא הרחבה של המשפט שאותו הוכחנו כרגע (תתבקש להוכיחו בשיעורי הבית).

משפט:

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

$\displaystyle G$ קשיר
$\displaystyle G$ חסר מעגלים
$\displaystyle |E| = |V| - 1$

[עריכה] עץ פורש

הגדרה:

נתון גרף (מכוון או לא מכוון) $\displaystyle G = (V, E)$ . נאמר ש $\displaystyle G' = (V, T)$ הוא עץ פורש של $\displaystyle G$ , אם:

$\displaystyle T \subseteq E$
$\displaystyle G'$ הוא עץ

דוגמה:

בתרשים הבא, A הוא גרף (לא מכוון) קשיר שאינו עץ (מפני שהוא מכיל מעגלים). כל אחד מB וC הוא עץ פורש של A.

מכאן ועד סוף הדף נוכיח את המשפט החשוב הבא. (משפט זה ישמש אותנו, בין היתר באלגוריתם Kruskal ואלגוריתם Prim.)

משפט:

אם $\displaystyle G$ גרף לא מכוון קשיר, אז יש עץ פורש ל $\displaystyle G$ .

כדי להוכיח את המשפט, נשתמש ב"פסוודו-קוד" הבא:

# 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. נראה שבתחילת האיטרציה ה $\displaystyle i$ , יש יער בעל $\displaystyle |V| - i + 1$ עצים.

(בסיס האינדוקציה) בתחילת האיטרציה הראשונה עדיין לא בחרנו אף קשת, ולכן יש קבוצה של $\displaystyle |V|$ צמתים בודדים, או, במילים אחרות, עצים בגודל 1 כל אחד.

(מעבר האינדוקציה) נניח שבתחילת האיטרציה ה $\displaystyle i$ יש יער בעל $\displaystyle |V| - i + 1$ עצים. אם אין קשת $\displaystyle e = (u, v) \in E$ המחברת בין שני צמתים מעצים שונים, אז הגרף המקורי אינו קשיר (בניגוד להנחתנו הבסיסית). נניח, אם כן, שיש קשת כזו, המחברת בין שני עצים; נניח שקבוצת צמתי העץ של $\displaystyle u$ היא $\displaystyle V_u$ , וקבוצת צמתי העץ של $\displaystyle v$ היא $\displaystyle V_v$ . קל לראות שהוספת $\displaystyle (u, v)$ גורמת ל $\displaystyle V_u \bigcup V_v$ להיות קשירה. מעבר לכך, אבל, הוספת הקשת גם אינה מייצרת מעגלים ב $\displaystyle V_u \bigcup V_v$ : מספר הקשתות של $\displaystyle V_u \bigcup V_v$ הוא בהכרח $\displaystyle |V_u| - 1 + |V_v| - 1 + 1 = |V_u| + |V_v| - 1$ , ולכן בהכרח מדובר בעץ (ציינו זאת מקודם). לכן בסוף האיטרציה ה $\displaystyle i$ יהיו $\displaystyle |V| - i$ עצים.

[עריכה] הקשר לאלגוריתמי גרפים אחרים שנלמד

כדאי לדעת:

בקורס נלמד מספר אלגוריתמים (ודמויי-אלגוריתמים) לבניית עץ פורש. הם מתוארים בתרשים הבא:

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

הפרק הקודם:
גרפים וייצוגיהם

עצים
תרגילים

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

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] הגדרות

[עריכה] עץ לא מכוון

[עריכה] עץ מכוון

[עריכה] מספר משפטים

[עריכה] עץ פורש

[עריכה] הקשר לאלגוריתמי גרפים אחרים שנלמד

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא