Question

winter_14-15_a
mst
shortest_path
proof

נתון גרף ממושקל (משקלים על הקשתות), לא מכוון, קשיר וחסר מעגלים שליליים, GG. עבור קבוע חיובי, cc, נסמן ב-GG' את הגרף המתקבל מ-GG אחרי הוספת cc למשקל של כל קשת, ונסמן ב-GG'' את הגרף המתקבל מ-GG אחרי הכפלת משקל כל קשת ב-cc.

הוכיחו/הפריכו את הטענות הבאות:

א. אם TT הוא עפ"מ של GG, אז TT הוא עפ"מ של GG'.

ב. אם TT הוא עפ"מ של GG, אז TT הוא עפ"מ של GG''.

ג. אם PP מסלול קל ביותר בין שני צמתים ב-GG, אז PP הוא מסלול קל ביותר ביניהם גם ב-GG'.

ד. אם PP מסלול קל ביותר בין שני צמתים ב-GG, אז PP הוא מסלול קל ביותר ביניהם גם ב-GG''.

1

Answers

נסמן ב-ww, ww' ו-ww'' את פונקציות המשקל של GG, GG' ו-GG'' בהתאמה.

א. הטענה נכונה. נשים לב שלכל עץ פורש TT מתקיים w(T)=w(T)+(n1)cw'(T) = w(T) + (n-1)c ולכן w(T1)w(T2)w(T_1) \leq w(T_2) אמ"מ w(T1)w(T2)w'(T_1) \leq w'(T_2).

ב. הטענה נכונה. נשים לב שלכל עץ פורש TT מתקיים w(T)=cw(T)w''(T) = cw(T) ומכיוון ש-cc חיובי אז w(T1)w(T2)w(T_1) \leq w(T_2) אמ"מ w(T1)w(T2)w''(T_1) \leq w''(T_2).

ג. הטענה לא נכונה, למשל בגרף הבא עבור c=2c = 2:

ד. הטענה נכונה. נשים לב שלכל מסלול PP מתקיים w(T)=cw(T)w''(T) = cw(T) ומכיוון ש-cc חיובי אז w(P1)w(P2)w(P_1) \leq w(P_2) אמ"מ w(P1)w(P2)w''(P_1) \leq w''(P_2).

1
Feedback