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

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

שימו לב: *נא להגיש רק את שאלות 1-5. שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.

1

נזכר בגרסה הראשונה שראינו של אלגוריתם Union-Find. משתמשים בה כך.

1	Sets = Connected-Components(G)

	# Prints True.
1	Print( Find-Set(Sets[1]) == Find-Set([3]) )

	# Prints False.
2	Print( Find-Set(Sets[2]) == Find-Set([3]) )

אנא הוכח את נכונות האלגוריתם, כלומר הראה שאכן

Find-Set(u) == Find-Set(v)

אמ"ם $\displaystyle u$ ו$\displaystyle v$ באותו רכיב קשירות.

2

נתון גרף לא-מכוון $\displaystyle G=(V,E)$ בעל $\displaystyle k$ רכיבי קשירות. מפעילים את Connected-Components למציאת רכיבי קשירות. כמה פעמים תקרא Find-Set? כמה פעמים תקרא Union? אנא בטא תשובתך ע"י $\displaystyle k$,‏ $\displaystyle |V|$,‏ ו$\displaystyle |E|$.

3

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

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

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

רמז לגרירה $\displaystyle 1\wedge 3\rightarrow 2$ נניח בשלילה ש1 ו3 מתקיימים, אך יש מעגל. הסבר מדוע בפשטות לא ייתכן שהמעגל כולל את כל הצמתים. נניח שהמעגל אינו כולל את כל הצמתים. חשוב מה יקרה כשנוסיף לגרף, מעבר למעגל, עוד צמתים וקשתות.

4

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות על הקשתות Edge-Costs. ידוע שקיימת קשת $\displaystyle e\in E$ כלשהי כך שEdge-Costs[e] < Edge-Costs[e'] לכל קשת $\displaystyle E\ni e'\neq e$. במילים אחרות, $\displaystyle e$ היא הקשת הזולה ביותר (ממש).

אנא הוכח או הפרך את הטענה הבאה. הקשת $\displaystyle e$ שייכת לכל עפ"מ של $\displaystyle G$.

שימו לב: משפט הקשת הקלה - קשת בטוחה מוכיח לכשלעצמו רק שקיים עפ"מ המכיל את $\displaystyle e$. השאלה מתייחסת לטענה חזקה יותר מכך.

5

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות לקשתות Weights. ידוע שאין שתי קשתות בעלות אותו המשקל: לכל שתי קשתות $\displaystyle e_{1}$ ו$\displaystyle e_{2}$, בהכרח Weights[e1] ≠ Weights[e2]. אנא הוכח או הפרך את הטענה הבאה: לגרף קיים עץ פורש מינימום יחידי.

6

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

7

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות על הקשתות Edge-Costs. בגרף יש מעגל, כלומר מסלול (פשוט) שמתחיל ומסתיים באותו צומת. ידוע שקיימת קשת $\displaystyle e\in E$ כלשהי כך שEdge-Costs[e] > Edge-Costs[e'] לכל קשת $\displaystyle E\ni e'\neq e$ במעגל. במילים אחרות, $\displaystyle e$ היא הקשת היקרה ביותר (ממש) במעגל.

אנא הוכח שהקשת $\displaystyle e$ אינה שייכת לאף עפ"מ של $\displaystyle G$.