Question

mst

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

תהי TM\mathcal{T}_M קבוצת כל העצים הפורשים של GG שבהם כל צמתי MM הם עלים. בהנחה ש-TM\mathcal{T}_M \neq \emptyset, אנו מעוניינים למצוא TTMT' \in \mathcal{T}_M בעל משקל מינימלי.

  1. הוכיחו שאם TTMT \in \mathcal{T}_M אז אין ב-TT קשת (u,v)(u,v) כך ש-u,vMu,v \in M
  2. יהי GG' תת גרף של GG המתקבל ממחיקת כל הצמתים של MM וכל הקשתות שנוגעות בהם. הוכיחו שתת העץ המתקבל מ-T'T על ידי מחיקת צמתי MM והקשתות שנוגעות בהם, הוא עפ"מ של G'G.
  3. תארו אלגוריתם יעיל ככל שתוכלו המוצא TT'.
1

Answers

  1. נניח בשלילה שקיימת קשת (u,v)T(u, v) \in T כך ש-u,vMu,v \in M. מכיוון ש-MVM \subset V אז קיימת קשת שחוצה את החתך {u,v}\{u,v\} ולכן הדרגה של vv או של uu היא לפחות 2 - סתירה.
  2. נשים לב שמכיוון ש-MM קבוצה של עלים אז לאחר מחיקת העלים והקשתות שנוגעות בהם נשאר לנו עץ פורש TT'' נניח בשלילה ש-T^\hat{T}עץ פורש של GG' עם משקל קטן מזה של TT'' אז ניתן לחבר את הצמתים מ-MM עם הקשתות שהסרנו ולקבל עץ עם משקל קטן משל TT' - סתירה.
  3. אלגוריתם: (ללא הוכחת נכונות)
  • הסר את MM וכל הקשתות שנוגעות בהם מ-GG לקבלת GG'
  • מצא עפ"מ ל-GG' - TT'
  • חבר כל צומת ב-MM ל-T'T על ידי הקשת המינימלית שמחברת אותו ל-GG' בו.
1
Feedback