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).

Feedback