Question

mst

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

  1. הציעו אלגוריתם הרץ בזמן לינארי, שבהינתן קשת ee, מכריע האם קיים עפ"מ המכיל את ee.
  2. הציעו אלגוריתם הרץ בזמן לינארי, שבהינתן קשת ee, מכריע האם כל עפ"מ מכיל את ee.
2

Answers

  1. נסיר את כל הקשתות שמשקלן גדול או שווה למשקל של ee פרט לקשת ee עצמה ונחזיר שקיים עפ"מ כזה אמ"מ ee לא שייכת לאף מעגל.

נכונות:

אם ee לא נמצאת על מעגל אז אפשר למצוא עפ"מ כזה בעזרת אלגוריתם קרוסקל כאשר ee הקשת הראשונה מבין הקשתות עם משקל זהה לזה של ee.

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

  1. נסיר את כל הקשתות שמשקלן גדול ממש ממשקל ee ונחזיר שקיים עפ"מ כזה אמ"מ ee לא שייכת לאף מעגל.

נכונות:

אם ee לא שייכת לאף מעגל אז בכל ריצה של קרוסקל היא תתווסף לעץ.

מצד שני, באופן דומה להוכחה של סעיף 1., אם קיים עץ שמכיל אותה אז ניתן להחליף אותה בקשת עם משקל קטן או שווה לה.

סיבוכיות: הסרת הקשתות נעשית בזמן לינארי, בדיקה אם קשת נמצאת על מעגל גם בזמן לינארי (למשל על ידי BFS, DFS).

2
Feedback