Question

mst
proof

יהא G=(V,E)G = (V,E) גרף לא מכוון, קשיר ובעל משקלות על הקשתות. יהיו Ts,TtT_s, T_t שני עצים פורשים מינימום של GG.

הוכיחו כי קיימת סדרה Ts=T1,,Tk=TtT_s = T_1, \ldots, T_k = T_t של עצים פורשים מינימום של GG כך שכל שני עצים עוקבים הם סמוכים במובן הבא: לכל 1ik1 \leq i \leq k ישנה רק קשת אחת הנמצאת ב-TiT_i ולא ב-Ti+1T_{i + 1}.

1

Answers

נוכיח באינדוקציה על TtTs|T_t \setminus T_s|.

בסיס: כאשר TtTs=0|T_t \setminus T_s| = 0 הטענה מתקיימת.

צעד: נניח ש-TtTs=i|T_t \setminus T_s| = i נבחר קשת eTtTse \in T_t \setminus T_s ונוסיף אותה ל-TsT_s לקבלת מעגל CeC_e. ב-CeC_e חייבת להיות קשת eee' \neq e שמקיימת w(e)=w(e)w(e') = w(e) או ש-TsT_s אינו עפ"מ. אז מתקיים ש-T=Ts{e}{e}T' = T_s \cup \{e\} \setminus \{e'\} עפ"מ, TTs=1|T' \setminus T_s| = 1, וש-TtT=i1|T_t \setminus T'| = i - 1. ולכן קיימת סדרה כנדרשTs=T,T2,Tk=TtT_s = T',T_2 \ldots, T_k = T_t כאשר T2,,Tk=TtT_2, \ldots, T_k = T_t קיימת לפי הנחת האינדוקציה.

0
Feedback