Question

mst
spring_18_b

נתון גרף לא מכוון, G=(V,E)G = (V, E), ופונקציית משקל w:ERw:E \to \mathbb{R}.

א. הוכיחו/הפריכו: אם ל-GG קיים עפ"מ שמכיל קשת במשקל xx אז לכל קשת במשקל xx קיים עפ"מ של GG שמכיל אותה.

ב. הציעו אלגוריתם שבהינתן גרף לא מכוון, G=(V,E)G = (V, E), פונקציית משקל, w:ERw:E \to \mathbb{R}, וערך xx, מוצא את כל הקשתות במשקל xx כך שקיים עפ"מ של GG שמכיל אותן. על האלגוריתם לרוץ בזמן O(E+V)O(E + V)יש לנתח סיבוכיות ולהוכיח נכונות.

ג. הציעו אלגוריתם שבהינתן גרף לא מכוון, G=(V,E)G = (V, E), ופונקציית משקל, w:ERw:E \to \mathbb{R} מוצא את כל הקשתות כך שקיים עפ"מ של GG שמכיל אותן. על האלגוריתם לרוץ בזמן O(ElogV)O(E \log V). יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

1

Answers

א. הטענה לא נכונה, למשל בגרף הבא:

tikz

הקשת 3434 מופיעה בכל עץ פורש ואילו הקשת 1212 לא מופיעה באף עפ"מ.

ב. האלגוריתם:

  • הסר את כל הקשתות במשקל גדול או שווה ל-xx מהגרף.
  • מצא יער BFS (או DFS או כל אלג' סריקה גנרי) של הגרף המתקבל.
  • לכל קשת במשקל xx, ee, קבע שקיים עפ"מ של GG שמכיל אותה אמ"מ היא מחברת שני רכיבי קשירות שונים ביער הנ"ל.

סיבוכיות: את כל הפעולות ניתן לעשות בזמן לינארי.

נכונות: נניח שקשת ee מחברת שני רכיבי קשירות שונים ביער שנוצר, C1,C2C_1, C_2,

אז היא קשת במשקל מינימלי בחתך C1VC_1 \subset V ב-GG אחרת קיימת קשת במשקל קטן משלה שמחברת את C1C_1 לרכיב קשירות אחר סתירה לכך שזהו יער BFS, ולכן, ניתן לצבוע אותה בכחול על פי הכלל הכחול.

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

ג. האלגוריתם: נריץ וריאציה של אלגוריתם קרוסקל:

  • מיין את הקשתות לפי משקלן.
  • עבור כל קבוצת משקל
    • לכל קשת בקבוצת משקל אם היא מחברת שני רכיבי קשירות שונים קבע כי קיים עפ"מ שמכיל אותה.
    • לכל קשת בקבוצת משקל אם היא מחברת שני רכיבי קשירות שונים הוסף אותה ליער.

סיבוכיות:

  • מיון הקשתות לוקח O(ElogV)O(E \log V).
  • נשים לב שעל כל קשת עוברים פעמיים
    • בדיקה אם היא שייכת לשני רכיבי קשירות ב-O(1)O(1)
    • הוספת כל הקשתות (כמו בקרוסקל) על ידי שימוש במבנה נתונים שממש union find בצורה יעילה, ניתן לעשות בזמן כוללO(VlogV)O(V \log V).
2
Feedback