מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 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)

אמ"ם ו באותו רכיב קשירות.

2[עריכה]

נתון גרף לא-מכוון בעל רכיבי קשירות. מפעילים את Connected-Components למציאת רכיבי קשירות. כמה פעמים תקרא Find-Set? כמה פעמים תקרא Union? אנא בטא תשובתך ע"י ,‏ ,‏ ו.

3[עריכה]

נתון גרף לא-מכוון . להלן שלוש תכונות:

  1. קשיר.
  2. חסר מעגלים.
  3. .

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


רמז לגרירה

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

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


4[עריכה]

נתון גרף לא-מכוון וקשיר , וכן טבלת עלויות על הקשתות Edge-Costs. ידוע שקיימת קשת כלשהי כך שEdge-Costs[e] < Edge-Costs[e'] לכל קשת . במילים אחרות, היא הקשת הזולה ביותר (ממש).

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


שימו לב:

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


5[עריכה]

נתון גרף לא-מכוון וקשיר , וכן טבלת עלויות לקשתות Weights. ידוע שאין שתי קשתות בעלות אותו המשקל: לכל שתי קשתות ו, בהכרח Weights[e1] ≠ Weights[e2]. אנא הוכח או הפרך את הטענה הבאה: לגרף קיים עץ פורש מינימום יחידי.

6[עריכה]

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

7[עריכה]

נתון גרף לא-מכוון וקשיר , וכן טבלת עלויות על הקשתות Edge-Costs. בגרף יש מעגל, כלומר מסלול (פשוט) שמתחיל ומסתיים באותו צומת. ידוע שקיימת קשת כלשהי כך שEdge-Costs[e] > Edge-Costs[e'] לכל קשת במעגל. במילים אחרות, היא הקשת היקרה ביותר (ממש) במעגל.

אנא הוכח שהקשת אינה שייכת לאף עפ"מ של .