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

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

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

שנה: 2021

סמסטר: א

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

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

נתון גרף קשיר ולא מכוון $G = (V, E)$ עם משקלים שלמים וחיוביים $w(e) > 0$ בצלעות. נתונים גם עץ-פורש מסוים $T = (V, F)$ של $G$ וצלע מסוימת $e = \{u, v\} \in F$ מהעץ. ניתן להוכיח (ומבחינתכם הדבר נתון), שאם מסירים מהעץ-הפורש $T$ את הצלע $e$, אז מתקבלים שני עצים זרים בצורה שנסמנם $T_1 = (V_1, F_1)$ ו-$T_2 = (V_2, F_2)$. נסמן ב-$G \setminus V_j$ את הגרף שמתקבל מ-$G$, לאחר שמשמיטים ממנו את כל הקדקודים של $V_j$. ניתן להוכיח (ושוב, הדבר נתון עבורכם) כי $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$)"

רמז: שימו לב שהצלע $e$ ותת-העץ $T_2$ אינם תלויים כלל בבחירת הצלעות בתוך $V_1$. מה זה אומר על הפירוק של $w(T)$ לשלושה חלקים, ומה יקרה אם נחליף את $T_1$ בעץ פורש אחר של $G\setminus V_2$?

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

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

G = (V, E)

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

w (e) > 0

בצלעות. נתונים גם עץ-פורש מסוים

T = (V, F)

של

G

וצלע מסוימת

e = {u, v} \in F

מהעץ. ניתן להוכיח (ומבחינתכם הדבר נתון), שאם מסירים מהעץ-הפורש

T

את הצלע

e

, אז מתקבלים שני עצים זרים בצורה שנסמנם

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

ו-

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

. נסמן ב-

G ∖ V_{j}

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

G

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

V_{j}

. ניתן להוכיח (ושוב, הדבר נתון עבורכם) כי

T_{1}

הינו עץ-פורש של

G ∖ V_{2}

, וכי

T_{2}

הינו עץ פורש של

G ∖ V_{1}

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

"אם

T

הינו עפ"מ של

G

אזי (

T_{1}

הינו עפ"מ של

G ∖ V_{2}

ו-

T_{2}

הינו עפ"מ של

G ∖ V_{1}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 75 · 2021 · סמסטר א

★★★★★

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

שימו לב שהצלע

e

ותת-העץ

T_{2}

אינם תלויים כלל בבחירת הצלעות בתוך

V_{1}

. מה זה אומר על הפירוק של

w (T)

לשלושה חלקים, ומה יקרה אם נחליף את

T_{1}

בעץ פורש אחר של

G ∖ V_{2}

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

נניח בשלילה שהטענה אינה נכונה. כלומר,

T

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

G

, אך לפחות אחד משני התנאים הבאים אינו מתקיים:
1.

T_{1}

הוא עפ"מ של

G ∖ V_{2}

.
2.

T_{2}

הוא עפ"מ של

G ∖ V_{1}

.

בלי הגבלת הכלליות, נניח כי

T_{1}

אינו עפ"מ של

G ∖ V_{2}

.
הגרף

G ∖ V_{2}

הוא תת-הגרף של

G

המושרה על ידי קבוצת הקדקודים

V_{1}

.
מאחר ש-

T_{1}

הוא עץ פורש של

G ∖ V_{2}

אך אינו עפ"מ, קיים עץ פורש אחר של

G ∖ V_{2}

, נסמנו

T_{1}^{'}

, כך שמשקלו קטן ממש ממשקלו של

T_{1}

. כלומר,

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

.

כעת, נבנה גרף חדש

T^{'}

עבור הגרף המקורי

G

. קבוצת הצלעות של

T^{'}

, שנסמנה

F^{'}

, תהיה איחוד של קבוצות הצלעות של

T_{1}^{'}

T_{2}

, והצלע

e

F^{'} = E (T_{1}^{'}) \cup E (T_{2}) \cup {e}

הגרף החדש הוא

T^{'} = (V, F^{'})

.

נוכיח ש-

T^{'}

הוא עץ פורש של

G

:
1. הגרף פורש את

V

: קבוצת הקדקודים של

T_{1}^{'}

היא

V_{1}

ושל

T_{2}

היא

V_{2}

. מכיוון ש-

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

T^{'}

אכן פורש את כל קדקודי

G

.
2. מספר הצלעות:

T_{1}^{'}

הוא עץ פורש של

G ∖ V_{2}

(המוגדר על

∣ V_{1} ∣

קדקודים) ולכן יש לו

∣ V_{1} ∣ - 1

צלעות.

T_{2}

הוא עץ פורש של

G ∖ V_{1}

(המוגדר על

∣ V_{2} ∣

קדקודים) ולכן יש לו

∣ V_{2} ∣ - 1

צלעות. מספר הצלעות הכולל ב-

F^{'}

הוא:

∣ F^{'} ∣ = (∣ V_{1} ∣ - 1) + (∣ V_{2} ∣ - 1) + 1 = ∣ V_{1} ∣ + ∣ V_{2} ∣ - 1 = ∣ V ∣ - 1

.
3. קשירות:

T_{1}^{'}

קושר את כל הקדקודים ב-

V_{1}

, ו-

T_{2}

קושר את כל הקדקודים ב-

V_{2}

. הצלע

e = {u, v}

מחברת קדקוד מ-

V_{1}

לקדקוד מ-

V_{2}

, ולכן הגרף

T^{'}

כולו קשיר.
מכיוון ש-

T^{'}

הוא גרף קשיר על

∣ V ∣

קדקודים עם

∣ V ∣ - 1

צלעות, הרי שהוא עץ. ומכיוון שהוא פורש את

V

, הוא עץ פורש של

G

.

כעת נשווה את משקל העץ

T^{'}

למשקל העץ המקורי

T

.
משקל העץ

T

הוא סכום משקלי רכיביו:

w (T) = w (T_{1}) + w (T_{2}) + w (e)

.
משקל העץ החדש

T^{'}

הוא:

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

.

לפי הנחת השלילה,

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

. לכן:

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

כלומר,

w (T^{'}) < w (T)

.

מצאנו עץ פורש

T^{'}

של

G

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

T

. הדבר עומד בסתירה להנחה המקורית ש-

T

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

G

.
לפיכך, ההנחה שלנו ש-

T_{1}

אינו עפ"מ של

G ∖ V_{2}

שגויה.

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

T_{2}

אינו עפ"מ של

G ∖ V_{1}

, נגיע לסתירה דומה.
מכאן שהטענה המקורית נכונה: אם

T

הוא עפ"מ של

G

, אז בהכרח

T_{1}

הוא עפ"מ של

G ∖ V_{2}

וגם

T_{2}

הוא עפ"מ של

G ∖ V_{1}

■

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