Question

mst

יהיו G1=(V,E1)G_1 = (V,E_1) ו-G2=(V,E2)G_2 = (V, E_2) שני גרפים לא מכוונים וקשירים מעל אותה קבוצת צמתים, עם משקלות על הקשתות. יהיו T1=(V,E1)T_1 = (V, E'_1) ו-T2=(V,E2)T_2 = (V, E'_2) שני עצים פורשים מינימום של G1G_1 ו-G2G_2 בהתאמה. נסמן ב-GG את גרף האיחוד של G1G_1 ו-G2G_2 - G=(V,E1E2)G = (V, E_1 \cup E_2).

1. הוכיחו/הפריכו - כל עץ פורש מינימום של GG מכיל קשתות מ-E1E2E'_1 \cup E'_2 בלבד.

2. הוכיחו/הפריכו - קיים עץ פורש מינימום של GG המכיל קשתות מ-E1E2E'_1 \cup E'_2 בלבד.

3. הציעו אלגוריתם שרץ בסיבוכיות זמן של O(VlogV)O(|V|\log |V|) ובהינתן G1,G2,T1,T2G_1,G_2,T_1,T_2 מוצא עץ פורש מינימום של GG.

1

Answers

1. לא נכון, למשל אם G1=G2=G=K3G_1 = G_2 = G = K_3 (מעגל בגודל 3) ו-T1=T2T_1 = T_2 (ל-GG יש 3 עצים פורשים מינימום שונים).

2. נכון, נשים לב שלפי הכלל האדום אפשר למחוק את כל הקשתות ב-E1E1E_1 \setminus E_1' וגם ב-E2E2E_2 \setminus E_2'.

3. האלגוריתם מוצא עפ"מ של T1T2T_1 \cup T_2. הנכונות נובעת מסעיף 2. והסיבוכיות הרצויה מתקבלת על ידי שימוש באלג' פרים או קרוסקל והאבחנה שב-T1T2T_1 \cup T_2 יש לכל היותר 2V22|V| - 2 קשתות.

1
Feedback