Question

winter_16-17_a
mst

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

נאמר כי עץ פורש הוא v-קטן אם vv הוא עלה בעץ, וכן העץ הוא בעל המשקל הקטן ביותר מבין על העצים הפורשים בהם vv הוא עלה.

הציעו אלגוריתם המחשב עץ vv-קטן.

2

Answers

אלגוריתם:

  1. נסיר את vv מהעץ.
  2. נחשב עפ"מ של G[V{v}]G[V\setminus\{v\}], TT.
  3. נחבר את vv ל-TT עם קשת במשקל מינימלי, vwvw, והחזר את העץ שנוצר.

נכונות:

נשים לב שלפי הגדרת האלגוריתם הפלט הוא עץ פורש ו-vv עלה. נסתכל על עץ פורש כלשהו, TT', כך ש-vv עלה שלו. נסמן ב-uu את השכן של vv ב-TT' ונסמן T=T[V{u}]T'' = T'[V \setminus \{u\}] נשים לב ש-TT'' עץ פורש של G[V{v}]G[V \setminus \{v\}] ולכן מתקיים w(T)+w(vw)w(T)+w(uv)=w(T)w(T) + w(vw) \leq w(T'') + w(uv) = w(T').

סיבוכיות:

  • את ההסרה של vv מהגרף והחזרתו ניתן לעשות בזמן לינארי.
  • חישוב TT ניתן לעשות בזמן O(VlogV)O(|V|\log |V|) על ידי קרוסקל למשל.

סך הכל O(VlogV)O(|V|\log |V|).

1
Feedback