Question

spanning_tree
median
bottleneck

יהא G=(V,E)G = (V, E) גרף לא מכוון עם משקלות על הקשתות. הכובד של עץ פורש TT של GG הוא משקל הקשת הכבדה ביותר בעץ (לקשת כזו נקרא צוואר בקבוק). עץ פורש שהכובד שלו הוא הקטן ביותר מבין כל העצים הפורשים יקרא עץ פורש קל ביותר.

  1. הוכיחו/הפריכו - כל עץ פורש מינימום הוא גם עץ פורש קל ביותר.
  2. הוכיחו/הפריכו - כל עץ פורש קל ביותר הוא גם עץ פורש מינימום.
  3. הציעו אלגוריתם, אשר בהינתן מספר bb, מכריע האם כובד עץ פורש קל ביותר הוא לכל היותר bb. על האלגוריתם לרוץ בזמן O(E)O(E).
  4. הציעו אלגוריתם המוצא עץ פורש קל ביותר בסיבוכיות זמן O(E)O(E).
3

Answers

1. נכון. נניח בשלילה שלא ונסתכל על החתך שיוצרת הקשת הכבדה ביותר בעפ"מ, מכיוון שיש עץ פורש יותר קל אז את החתך חוצה קשת יותר קלה - סתירה.

2. לא נכון, למשל:

tikz

הקשתות הכחולות מהוות עץ קל ביותר אבל לא עפ"מ.

3. ניתן להסיר את כל הקשתות במשקל גדול ממש משל bb ולבדוק אם קיים עץ פורש.

4. האלגוריתם:

  • אם לכל הקשתות אותו משקל החזר עץ פורש (BFS/DFS) של הגרף.
  • מצא חציון של משקלי הקשתות, bb.
  • בדוק אם קיים עץ פורש קל ביותר במשקל bb לכל היותר.
    • אם כן הסר את כל הקשתות במשקל גדול ממש משל bb והמשך רקורסיבית.
    • אם לא מצא יער (למשל יער DFS) עם קשתות במשקל קטן או שווה ל-bb, "כווץ" את רכיבי הקשירות לצמתים והמשך רקורסיבית על הגרף שהתקבל.

סיבוכיות:מציאת חציון ויער DFS ניתן לעשות בזמן לינארי. נשים לב שבקריאות הרקורסיביות מספר הקשתות קטן בחצי כל פעם ולכן הסיבוכיות הכוללת היא O(E+E/2+1)=O(E)O(E + E/2 + \dots 1) = O(E).

2
Feedback