Question

spring_9_b
mst

יהא G=(V,E)G = (V,E) גרף עם משקלות על הקשתות. נניח ונתון בידנו עפ"מ TT של GG. מוסיפים כעת ל-GG צומת חדש, vv, וקשתות ממושקלות מ-vv לחלק מצמתי הגרף. את הגרף המתקבל נסמן ב-GG'.

א. הוכיחו/הפריכו: כל עפ"מ של GG' מכיל את TT.

ב. הציעו אלגוריתם הרץ בזמן O(VlogV)O(V\log V) המוצא עפ"מ של GG'. הוכיחו נכונות ונתחו סיבוכיות.

1

Answers

א. הטענה לא נכונה, למשל עבור GG' הבא כאשר הצומת השמאלי הוא הצומת החדש:

ב.

טענה: קיים עפ"מ של GG' שמוכל ב-TET \cup E', כאשר EE' היא קבוצת הקשתות שנוגעות ב-vv, הצומת החדש.

הוכחה: על שאר הקשתות ניתן להפעיל את הכלל האדום.

אלגוריתם: הרץ את קרוסקל על TET \cup E'.

נכונות: מיידי מהטענה ומנכונות קרוסקל.

סיבוכיות: נשים לב שמספר הקשתות הוא O(V)O(V) ולכן הסיבוכיות היא O(VlogV)O(V \log V).

2
Feedback