Question

mst
summer_18_b

א. הוכיחו: אם TT עץ בעל קוטר dd, eTe \in T, ו-e/Te' \notin T, כך ש-T=T{e}{e}T' = T \cup \{e'\} \setminus \{e\} הוא עץ, אז הקוטר של TT' הוא לכל היותר 2d+12d + 1.

תזכורת: קוטר של גרף הוא המרחק הגדול ביותר בין שני צמתים בגרף.

ב. הוכיחו: אם T1T_1 ו-T2T_2 עפ"מים של GG ו-eT2T1e \in T_2 \setminus T_1 אז קיימת קשת eT1e' \in T_1 כך ש-T1{e}{e}T_1 \cup \{e\} \setminus \{e'\} עפ"מ של GG.

ג. נתון גרף לא מכוון עם משקלים על הקשתות, GG, ונתונים שני עפ"מים שלו, T1T_1 ו-T2T_2 בעלי קטרים 20 ו-100 בהתאמה.

הציעו אלגוריתם שמוצא עפ"מ של GG עם קוטר גדול ממש מ-40 וקטן ממש מ-90.יש להוכיח נכונות ולנתח סיבוכיות.

1

Answers

א. נסמן ב-AA ו-BB את רכיבי הקשירות של TT לאחר הסרת הקשת ee ונסמן e=uve' = uv כאשר uA,vBu \in A, v \in B. נשים לב שעבור שני צמתים ב-AA או ב-BB המסלול היחיד ביניהם הוא באורך dd לכל היותר (לפי הגדרת הקוטר) ולשני צמתים aA,bBa \in A, b \in B קיים מסלול auvba \rightsquigarrow u \to v \rightsquigarrow b שאורכו 2d+12d + 1 לכל היותר.

ב. נניח בשלילה שלא קיימת קשת כזאת. נוסיף את ee ל-T1T_1 ונסתכל על קשת במעגל שנוצר שחוצה את החתך ש-ee מגדירה ביחד ל-T2T_2 מהנחת השלילה נובע שמשקל הקשת הנ"ל גדול ממש ממשקלה של ee ולכן אם נסיר אותה מקבל עץ ששוקל פחות מ-T1T_1 - סתירה.

ג. אלגוריתם:

  • נאתחל TT1T \leftarrow T_1
  • כל עוד הקוטר של TT קטן או שווה ל-40
    • בחר קשתות eTT2e \in T \setminus T_2 ו-eT2e' \in T_2 כך ש-T=T{e}{e}T' = T \setminus \{e\} \cup \{e'\} עץ.
    • עדכן TTT \leftarrow T'
  • החזר את TT

נכונות: נשים לב שלפי סעיף ב' קיימות קשתות כנדרש ושבכל צעד של האלגוריתם TT2|T \cap T_2| גדל ב-1 ולכן לאחר nn צעדים לכל היותר נקבל עץ עם קוטר 100. נשים לב שבאתחול הקוטר של TT הוא 20 ולפי סעיף א' אם הקוטר של TT בצעד ה-ii הוא dd אז בצעד ה-i+1i + 1 הוא 2d+12d + 1 לכל היותר, ולכן בפעם הראשונה שהקוטר של TT יהיה גדול ממש מ-40 הוא יהיה 81 לכל היותר כמתבקש.

סיבוכיות: כל צעד של האלגוריתם ניתן לממש בזמן לינארי (הוספת קשת ומחיקת קשת, למשל על ידי DFS) ולכל היותר נדרשים nn צעדים ולכן בסך הכל O(n2)O(n^2).

1
Feedback