שאלה בגרפים (עץ פורש מינימלי)

[yythe1]

שאלה בגרפים (עץ פורש מינימלי)

יהי G גרף לא מכוון וממושקל עם פונקצית משקל w ויהי T עץ פורש מינימלי ב-G . תהי e קשת שנמצאת ב-G ואינה ב-T . נניח שמשקלה של e השתנה . נסמן ב-G' את הגרף המעודכן לאחר השינוי . א. הצע אלגוריתם המוצא עץ פורש מינימלי בגרף המעודכן G' (בהנחה ש-T נתון) הרץ בזמן O(

) zz ב. נתחו סיבוכיות זמן האלגוריתם (כלומר הראו שהזמן אכן O(

) zz תודה מראש...

 

[yythe1]

זה זמן O של V בערך מוחלט