שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה

קורס: אלגוריתמים

אוניברסיטה: האוניברסיטה הפתוחה

נושאים: עץ פורש מינימלי, גרפים, הוכחה, הוכח או הפרך

רמת קושי: בינוני

נתון גרף קשיר ולא מכוון $G=(V,E)$ עם משקלים שלמים וחיוביים $w(e)>0$ בכל הצלעות, ונתון עץ פורש $T=(V,F)$ של $G$ (לאו דווקא מזערי). אם מסירים מהעץ $T$ צלע אחת $e$, מתקבלים שני עצים זרים $T_1=(V_1,F_1)$ ו-$T_2=(V_2,F_2)$, כאשר $V_1 \cup V_2 = V$. נסמן ב-$G \setminus V_2$ את הגרף המתקבל מ-$G$ לאחר השמטת כל קדקודי $V_2$ (והצלעות הנוגעות בהם), ובדומה $G \setminus V_1$. נתון כי $T_1$ הוא עץ פורש של $G \setminus V_2$, וכי $T_2$ הוא עץ פורש של $G \setminus V_1$. הוכיחו או הפריכו: אם $T$ הוא עץ פורש מזערי (עפ"מ) של $G$, אזי $T_1$ הוא עפ"מ של $G \setminus V_2$ ו-$T_2$ הוא עפ"מ של $G \setminus V_1$.

רמז: הניחו בשלילה ש-$T_1$ אינו מזערי, קחו עץ פורש זול יותר $T_1'$ של $G\setminus V_2$, וחברו אותו חזרה ל-$T_2$ דרך הצלע שהוסרה — מתקבל עץ פורש של $G$ הזול מ-$T$.

פתרון: **הטענה נכונה.** נוכיח אותה בדרך השלילה. נניח כי $T$ הוא עפ"מ של $G$, ונניח בשלילה שאחד משני העצים — בה"כ $T_1$ — **אינו** עפ"מ של $G \setminus V_2$. אזי קיים עץ פורש $T_1'$ של $G \setminus V_2$ עם משקל קטן יותר: $$w(T_1') < w(T_1).$$ יהי $e$ הצלע שהוסרה מ-$T$ כדי לפצל אותו ל-$T_1,T_2$. נתבונן בגרף $$T' = T_1' \cup \{e\} \cup T_2.$$ **$T'$ הוא עץ פורש של $G$:** - הוא **פורש** את $V$, שכן $T_1'$ פורש את $V_1$, $T_2$ פורש את $V_2$, ו-$V_1\cup V_2=V$. - הוא **קשיר**, שכן הצלע $e$ מחברת את שני תתי-הגרפים $T_1'$ (על $V_1$) ו-$T_2$ (על $V_2$). - מספר צלעותיו הוא $(|V_1|-1)+1+(|V_2|-1)=|V|-1$, ולכן בהיותו קשיר על $|V|$ קדקודים הוא חסר-מעגלים — כלומר עץ. משקלו: $$w(T') = w(T_1') + w(e) + w(T_2) < w(T_1) + w(e) + w(T_2) = w(T).$$ קיבלנו עץ פורש $T'$ של $G$ שמשקלו קטן ממשקל $T$, בסתירה לכך ש-$T$ הוא עפ"מ. לכן ההנחה שגויה ו-$T_1$ הוא עפ"מ של $G\setminus V_2$; באופן סימטרי $T_2$ הוא עפ"מ של $G\setminus V_1$. $\blacksquare$

נתון גרף קשיר ולא מכוון

G = (V, E)

עם משקלים שלמים וחיוביים

w (e) > 0

בכל הצלעות, ונתון עץ פורש

T = (V, F)

של

G

(לאו דווקא מזערי). אם מסירים מהעץ

T

צלע אחת

e

, מתקבלים שני עצים זרים

T_{1} = (V_{1}, F_{1})

ו-

T_{2} = (V_{2}, F_{2})

, כאשר

V_{1} \cup V_{2} = V

. נסמן ב-

G ∖ V_{2}

את הגרף המתקבל מ-

G

לאחר השמטת כל קדקודי

V_{2}

(והצלעות הנוגעות בהם), ובדומה

G ∖ V_{1}

. נתון כי

T_{1}

הוא עץ פורש של

G ∖ V_{2}

, וכי

T_{2}

הוא עץ פורש של

G ∖ V_{1}

.

הוכיחו או הפריכו: אם

T

הוא עץ פורש מזערי (עפ"מ) של

G

, אזי

T_{1}

הוא עפ"מ של

G ∖ V_{2}

ו-

T_{2}

הוא עפ"מ של

G ∖ V_{1}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן דוגמא

★★★★★

עץ פורש מינימליגרפיםהוכחההוכח או הפרך

הניחו בשלילה ש-

T_{1}

אינו מזערי, קחו עץ פורש זול יותר

T_{1}^{'}

של

G ∖ V_{2}

, וחברו אותו חזרה ל-

T_{2}

דרך הצלע שהוסרה — מתקבל עץ פורש של

G

הזול מ-

T

הטענה נכונה. נוכיח אותה בדרך השלילה.

נניח כי

T

הוא עפ"מ של

G

, ונניח בשלילה שאחד משני העצים — בה"כ

T_{1}

— אינו עפ"מ של

G ∖ V_{2}

. אזי קיים עץ פורש

T_{1}^{'}

של

G ∖ V_{2}

עם משקל קטן יותר:

w (T_{1}^{'}) < w (T_{1}) .

יהי

e

הצלע שהוסרה מ-

T

כדי לפצל אותו ל-

T_{1}, T_{2}

. נתבונן בגרף

T^{'} = T_{1}^{'} \cup {e} \cup T_{2} .

T^{'}

הוא עץ פורש של

G

הוא פורש את $V$ , שכן $T_{1}^{'}$ פורש את $V_{1}$ , $T_{2}$ פורש את $V_{2}$ , ו- $V_{1} \cup V_{2} = V$ .
הוא קשיר, שכן הצלע $e$ מחברת את שני תתי-הגרפים $T_{1}^{'}$ (על $V_{1}$ ) ו- $T_{2}$ (על $V_{2}$ ).
מספר צלעותיו הוא $(∣ V_{1} ∣ - 1) + 1 + (∣ V_{2} ∣ - 1) = ∣ V ∣ - 1$ , ולכן בהיותו קשיר על $∣ V ∣$ קדקודים הוא חסר-מעגלים — כלומר עץ.

משקלו:

w (T^{'}) = w (T_{1}^{'}) + w (e) + w (T_{2}) < w (T_{1}) + w (e) + w (T_{2}) = w (T) .

קיבלנו עץ פורש

T^{'}

של

G

שמשקלו קטן ממשקל

T

, בסתירה לכך ש-

T

הוא עפ"מ. לכן ההנחה שגויה ו-

T_{1}

הוא עפ"מ של

G ∖ V_{2}

; באופן סימטרי

T_{2}

הוא עפ"מ של

G ∖ V_{1}

■

שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה - עץ פורש מינימלי