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

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

הגדרות

עץ לא מכוון

תבנית:משימה

עץ מכוון

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

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

מספר משפטים

תבנית:הוכחה

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

עץ פורש

מכאן ועד סוף הדף נוכיח את המשפט החשוב הבא. (משפט זה ישמש אותנו, בין היתר באלגוריתם 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'

נסיים בהוכחת המשפט. נראה שה"פסוודו-קוד" אכן בונה עץ פורש.

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

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