Question

mst

יהא G=(V,E)G = (V, E) גרף לא מכוון ופונקציית משקל w:ERw:E \to \mathbb{R}. יער k-פורש הוא תת גרף T=(V,E)T = (V, E') של GG המהווה יער עם k עצים. יער k-פורש יקרא יער k-פורש מינימלי אם סכום משקלות קשתותיו אינו גדול מסכום המשקלות של אף יער k-פורש אחר.

הציעו אלגוריתם המוצא יער k-פורש מינימלי.

1

Answers

האלגוריתם:

  • מצא עפ"ם של GG, TT.
  • הסר מ-TT את k1k - 1 הקשתות הכבדות ביותר, AA.

נכונות: קל לראות שמתקבל יער-k-פורש. נניח בשלילה שהוא לא מינימלי ונסתכל על יער-k-פורש מינימלי, FF. נשים לב שאפשר להשלים את FF לעץ פורש, TT' על ידי k1k-1 קשתות מ-TT, BB.

מכיוון ש-TT עפ"ם ומכיוון ש-AA הן הקשתות הכבדות ביותר אז מתקיים ש-w(F)=w(T)w(B)w(T)w(A)w(F) = w(T') - w(B) \geq w(T) - w(A) - סתירה.

סיבוכיות: מציאת עפ"ם ניתן לעשות בזמן O(ElogV)O(E \log V) ובזמן זה ניתן גם להסיר את kk הקשתות הכבדות.

1
Feedback