Question

mst

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

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

Answers

האלגוריתם:

מצא עפ"ם של $G$ , $T$ .
הסר מ- $T$ את $k - 1$ הקשתות הכבדות ביותר, $A$ .

נכונות: קל לראות שמתקבל יער-k-פורש. נניח בשלילה שהוא לא מינימלי ונסתכל על יער-k-פורש מינימלי, $F$ . נשים לב שאפשר להשלים את $F$ לעץ פורש, $T'$ על ידי $k-1$ קשתות מ- $T$ , $B$ .

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

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