Question

mst

יהא G=(V,E)G = (V,E) גרף לא מכוון וקשיר עם משקלות על הקשתות.

הציעו אלגוריתם המכריע האם ל-GG בדיוק שני עפ"מ-ים.

1

Answers

אלגוריתם:

  1. מצא עפ"מ TT
  2. עבור כל קשת שלא בעפ"מ
    • הוסף אותה ל-TT ובדוק אם קיימת קשת אחרת במעגל שנוצר עם משקל זהה
  3. החזר שקיימים בדיוק 2 אמ"מ בשלב 2. מצאנו בדיוק קשת אחת כזאתTT'.בדיוק בקשת אחת.

טענה: אם TT ו-TT' עפ"מים ו-eTTe \in T \setminus T' אז קיימת קשת eTTe' \in T' \setminus T כך ש-T{e}eT' \cup \{e\} \setminus e' עפ"מ.

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

נכונות: נובעת ישירות מהטענה הנ"ל.

סיבוכיות: עוברים על כל הקשתות ולכל קשת בודקים את המעגל שנוצר. ניתן לעשות זאת ב-O(E2)O(E^2).

1
Feedback