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

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

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

קפיצה אל: ניווט, חיפוש

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

תוכן עניינים

1 הוספת קשת ויצירת מעגל
- 1.1 שאלה
- 1.2 תשובה
2 הגדרות שקולות לעץ
- 2.1 שאלה
- 2.2 תשובה

[עריכה] הוספת קשת ויצירת מעגל

[עריכה] שאלה

אנא הוכח שהוספת קשת לעץ בהכרח תיצור מעגל.

[עריכה] תשובה

נניח שנוסיף לגרף את הקשת $\displaystyle (u, v)$ . להלן העץ לפני הוספת הקשת.

נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת, היה מסלול $\displaystyle P$ מ $\displaystyle u$ ל $\displaystyle v$ .

לכן, לאחר הוספת הקשת $\displaystyle (u, v),$ יש מסלול מ $\displaystyle u$ לעצמו: המסלול $\displaystyle P$ שאליו משורשרת הקשת $\displaystyle (u, v)$ .

[עריכה] הגדרות שקולות לעץ

[עריכה] שאלה

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

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

אנא הוכח שכל שתיים משלוש התכונות בהכרח גוררת את התכונה הנותרת.

רמז לגרירה $\displaystyle 1 \wedge 3 \rightarrow 2$

נניח בשלילה ש1 ו3 מתקיימים, אך יש מעגל.

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

[עריכה] תשובה

משפט:

אם $\displaystyle G = (V, E)$ קשיר וחסר מעגלים, אז $\displaystyle |E| = |V| - 1$ .

הוכחה: הוכחנו זאת כבר בהרצאה.

משפט:

אם $\displaystyle G = (V, E)$ חסר מעגלים, ו $\displaystyle |E| = |V| - 1$ , אז $\displaystyle G$ קשיר.

הוכחה: כל גרף חסר מעגלים הוא יער; בפרט, נניח שמדובר ביער בעל $\displaystyle i$ עצים. אם $\displaystyle i = 1$ , אז ההוכחה הושלמה. אם $\displaystyle i > 1$ , אז, בהנחה שבעץ ה $\displaystyle j$ יש $\displaystyle |V_j|$ צמתים (ולכן $\displaystyle |V_j| - 1$ קשתות), יש בגרף סך הכל $\displaystyle \sum_{j = 1}^i|V_j|$ צמתים, אך רק $\displaystyle \sum_{j = 1}^i[|V_j| - 1] = \sum_{j = 1}^i|V_j| - i < |V| - 1$ קשתות.

משפט:

אם $\displaystyle G = (V, E)$ קשיר, ו $\displaystyle |E| = |V| - 1$ , אז $\displaystyle G$ חסר מעגלים.

הוכחה: נניח שבגרף יש מעגל בעל $\displaystyle n' \le n$ צמתים. קל לראות אז שבמעגל יש $\displaystyle n'$ קשתות. אם $\displaystyle n' = n$ , אז לא ייתכן ש $\displaystyle |E| = |V| - 1$ . נניח לכן ש $\displaystyle n' < n$ . נגדיר כ $\displaystyle G'_1$ את המעגל.

מספירה פשוטה, קל לראות שקיים צומת כלשהו ב $\displaystyle G$ שאינו חלק מ $\displaystyle G'_1$ . היות ש $\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_1$ לצומת הנ"ל. נגדיר כ $\displaystyle G'_2$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב $\displaystyle G'_2$ יש $\displaystyle n' + 1$ צמתים, ו $\displaystyle n' + 1$ קשתות.
מספירה פשוטה, קל לראות שקיים צומת כלשהו ב $\displaystyle G$ שאינו חלק מ $\displaystyle G'_2$ . היות ש $\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_2$ לצומת הנ"ל. נגדיר כ $\displaystyle G'_3$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב $\displaystyle G'_3$ יש $\displaystyle n' + 2$ צמתים, ו $\displaystyle n' + 2$ קשתות.
...
מספירה פשוטה, קל לראות שקיים צומת כלשהו ב $\displaystyle G$ שאינו חלק מ $\displaystyle G'_{n - n'}$ . היות ש $\displaystyle G$ קשיר, יש קשת המחברת בין $\displaystyle G'_{n - n'}$ לצומת הנ"ל. נגדיר כ $\displaystyle G'_{n - n' + 1}$ את הגרף המתקבל מהוספת הצומת והקשת. נשים לב שב $\displaystyle G'_{n - n' + 1}$ יש $\displaystyle n$ צמתים, ו $\displaystyle n$ קשתות.קל לראות שהסעיף האחרון סותר את הקביעה $\displaystyle |E| = |V| - 1$ .