מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 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 ו3 מתקיימים, אך יש מעגל.
|
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']
לכל קשת במעגל. במילים אחרות, היא הקשת היקרה ביותר (ממש) במעגל.
אנא הוכח שהקשת אינה שייכת לאף עפ"מ של .