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

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

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

הגדרות

עץ לא מכוון

הגדרה: עץ (לא מכוון) הוא גרף (לא מכוון) קשיר וחסר מעגלים: קשיר - מכל צומת $\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$ ובעל מסלולים ייחודיים.

1. קשיר מ$\displaystyle u$ - יש מסלול מ$\displaystyle u$ לכל צומת $\displaystyle v$.
2. בעל מסלולים ייחודיים - לכל שני צמתים $\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|\leq 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