Question

mst

יהא G=(V,E)G = (V,E) גרף לא מכוון וקשיר, ותהא ww פונקציית משקל עבור EE. יהא TT עפ"מ של GG.

  1. מוסיפים קשת חדשה, ee, ל-EE עם משקל w(e)w(e). הציעו אלגוריתם המעדכן את TT כך שיהיה עפ"מ של הגרף החדש G=(V,E{e})G' = (V, E \cup \{e\}).
  2. מסירים קשת, ee, מ-EE. הציעו אלגוריתם המעדכן את TT כך שיהיה עפ"מ של הגרף החדש G=(V,E{e})G' = (V, E \setminus \{e\}) או מודיע שאין עפ"מ לגרף זה.
2

Answers

פתרון ללא הוכחה.

  1. נוסיף את ee ל-TT ונסיר את הקשת הכבדה ביותר מהמעגל שנוצר.
  2. אם eTe \notin T אין צורך לעשות דבר. אחרת נסתכל על החתך שמגדירה ee ביחס ל-TT ונוסיף את הקשת הקלה ביותר שחוצה את החתך ל-TT, אם לא קיימת כזו נקבע שלא קיים עץ פורש ל-GG'.

סיבוכיות:

  1. הוספת הקשת, מציאת המעגל והסרה של הקשת הכבדה ניתן לעשות בזמן לינארי.
  2. יש צורך לסווג כל צומת לאיזה צד של החתך הוא שייך (למשל על ידי הרצה בודדת של BFS או DFS) ובנוסף יש לעשות מעבר בודד על הקשתות כדי למצוא את הקשת הקלה ביותר. סך הכל ניתן לבצע זאת בזמן לינארי.
3
Feedback