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

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

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

שנה: 2022

סמסטר: א

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

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

נתון גרף קשיר ולא-מכוון $G=(V,E)$ עם משקלים $w(e)$ בצלעות. כל המשקלים חיוביים, למעט **צלע בודדת** $e^*=\{u,v\}$ שמשקלה שלילי. לשם פשטות נתון שהמשקלים שלמים וייחודיים: $w(e_1)\ne w(e_2)$ לכל $e_1\ne e_2$. בשאלה זו נבדוק את נכונותה של **"הרצה לסירוגין"** של האלגוריתם של Prim משני קצותיה $u,v$ של הצלע השלילית. **הגדרת ההרצה לסירוגין.** מאתחלים שני עצים $T_u\leftarrow\{u\}$ ו-$T_v\leftarrow\{v\}$ (כל עץ מכיל אך ורק אחד מקצות הצלע השלילית). ממשיכים באיטרציות, המתעלמות מהצלע השלילית; בכל איטרציה: **(א)** מוסיפים ל-$T_u$ צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-$T_u$; ואז **(ב)** מוסיפים ל-$T_v$ צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-$T_v$. האלגוריתם עוצר ברגע שבו $T_u\cup T_v$ פורש את כל קדקודי $G$ (העצירה עשויה להתרחש בסוף איטרציה או באמצעה, בהתאם לזוגיות $|V|$). **הנחה מקלה.** נתון ששני העצים לא התאחדו באף איטרציה — הצלעות שנוספו ל-$T_u$ אינן מובילות ל-$T_v$ ולהפך. לכן מובטח שברגע העצירה $T:=T_u\cup\{e^*\}\cup T_v$ הוא עץ פורש של $G$. **הוכיחו או הפריכו** את הטענה: "$T$ הוא עפ"מ של $G$".

רמז: מה שמצדיק את Prim הוא תכונת החתך: הצלע המזערית היוצאת מהרכיב הקשיר שנבנה עד כה היא בטוחה. שאלו את עצמכם מהו הרכיב שכבר נבנה כאן — האם הוא $T_u$ לבדו? — ומה עלול לקרות כאשר כופים על עץ אחד להתרחב בעוד שהצלע הזולה יוצאת דווקא מן העץ השני.

פתרון: **הטענה אינה נכונה.** נפריך אותה בדוגמה נגדית בת ארבעה קדקודים. **הדוגמה הנגדית.** $$V=\{u,v,a,b\},\qquad w(\{u,v\})=-1,\quad w(\{u,a\})=10,\quad w(\{v,b\})=1,\quad w(\{a,b\})=2.$$ הגרף קשיר; המשקלים שלמים וייחודיים; וכולם חיוביים למעט $e^*=\{u,v\}$ — כל תנאי השאלה מתקיימים. **מעקב אחר ההרצה לסירוגין.** - **(א)** הצלע החיובית היחידה היוצאת מ-$T_u=\{u\}$ היא $\{u,a\}$ במשקל $10$; מוסיפים אותה, וכעת $T_u=\{u,a\}$. - **(ב)** הצלע החיובית היחידה היוצאת מ-$T_v=\{v\}$ היא $\{v,b\}$ במשקל $1$; מוסיפים אותה, וכעת $T_v=\{v,b\}$. - $T_u\cup T_v$ פורש את $V$, ולכן האלגוריתם עוצר. שני העצים לא התאחדו, כנדרש בהנחה המקלה. הפלט הוא $T=\big\{\{u,a\},\ e^*,\ \{v,b\}\big\}$ שמשקלו $$w(T)=10+(-1)+1=10.$$ **אך $T$ אינו עפ"מ.** נתבונן ב-$T'=\big\{e^*,\ \{v,b\},\ \{a,b\}\big\}$: שלוש צלעות הפורשות את ארבעת הקדקודים ומחברות אותם, כלומר עץ פורש, ומשקלו $$w(T')=-1+1+2=2\ <\ 10=w(T).$$ (אכן, Kruskal בוחר בדיוק את הצלעות $-1,\,1,\,2$ ומחזיר את $T'$.) לכן הטענה מופרכת. $\blacksquare$ **מדוע ההרצה לסירוגין נכשלת.** לאחר שהצלע $e^*$ מחברת בין $u$ ל-$v$, הרכיב שנבנה עד כה הוא **האיחוד** $T_u\cup T_v$, ולפי תכונת החתך הצעד הבטוח הוא הוספת הצלע המזערית היוצאת מן האיחוד הזה. ואכן, Prim על הגרף המתקבל מכיווץ $e^*$ היה בוחר תחילה את $\{v,b\}$ במשקל $1$, ורק אז את $\{a,b\}$ במשקל $2$ — ומקבל את $T'$. ההרצה לסירוגין, לעומת זאת, מחייבת את $T_u$ להוסיף את הצלע המזערית היוצאת **ממנו בלבד**, ולכן היא כופה עליו את הצלע הכבדה $\{u,a\}$ עוד לפני שהתברר שאפשר להגיע ל-$a$ בזול דרך הצד השני.

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

G = (V, E)

עם משקלים

w (e)

בצלעות. כל המשקלים חיוביים, למעט צלע בודדת

e^{*} = {u, v}

שמשקלה שלילי. לשם פשטות נתון שהמשקלים שלמים וייחודיים:

w (e_{1}) \neq = w (e_{2})

לכל

e_{1} \neq = e_{2}

.

בשאלה זו נבדוק את נכונותה של "הרצה לסירוגין" של האלגוריתם של Prim משני קצותיה

u, v

של הצלע השלילית.

הגדרת ההרצה לסירוגין. מאתחלים שני עצים

T_{u} \leftarrow {u}

ו-

T_{v} \leftarrow {v}

(כל עץ מכיל אך ורק אחד מקצות הצלע השלילית). ממשיכים באיטרציות, המתעלמות מהצלע השלילית; בכל איטרציה:
(א) מוסיפים ל-

T_{u}

צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-

T_{u}

; ואז
(ב) מוסיפים ל-

T_{v}

צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-

T_{v}

.

האלגוריתם עוצר ברגע שבו

T_{u} \cup T_{v}

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

G

(העצירה עשויה להתרחש בסוף איטרציה או באמצעה, בהתאם לזוגיות

∣ V ∣

).

הנחה מקלה. נתון ששני העצים לא התאחדו באף איטרציה — הצלעות שנוספו ל-

T_{u}

אינן מובילות ל-

T_{v}

ולהפך. לכן מובטח שברגע העצירה

T := T_{u} \cup {e^{*}} \cup T_{v}

הוא עץ פורש של

G

.

הוכיחו או הפריכו את הטענה: "

T

הוא עפ"מ של

G

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

מה שמצדיק את Prim הוא תכונת החתך: הצלע המזערית היוצאת מהרכיב הקשיר שנבנה עד כה היא בטוחה. שאלו את עצמכם מהו הרכיב שכבר נבנה כאן — האם הוא

T_{u}

לבדו? — ומה עלול לקרות כאשר כופים על עץ אחד להתרחב בעוד שהצלע הזולה יוצאת דווקא מן העץ השני.

הטענה אינה נכונה. נפריך אותה בדוגמה נגדית בת ארבעה קדקודים.

הדוגמה הנגדית.

V = {u, v, a, b}, w ({u, v}) = - 1, w ({u, a}) = 10, w ({v, b}) = 1, w ({a, b}) = 2.

הגרף קשיר; המשקלים שלמים וייחודיים; וכולם חיוביים למעט

e^{*} = {u, v}

— כל תנאי השאלה מתקיימים.

מעקב אחר ההרצה לסירוגין.

(א) הצלע החיובית היחידה היוצאת מ- $T_{u} = {u}$ היא ${u, a}$ במשקל $10$ ; מוסיפים אותה, וכעת $T_{u} = {u, a}$ .
(ב) הצלע החיובית היחידה היוצאת מ- $T_{v} = {v}$ היא ${v, b}$ במשקל $1$ ; מוסיפים אותה, וכעת $T_{v} = {v, b}$ .
$T_{u} \cup T_{v}$ פורש את $V$ , ולכן האלגוריתם עוצר. שני העצים לא התאחדו, כנדרש בהנחה המקלה.

הפלט הוא

T = {{u, a}, e^{*}, {v, b}}

שמשקלו

w (T) = 10 + (- 1) + 1 = 10.

אך

T

אינו עפ"מ. נתבונן ב-

T^{'} = {e^{*}, {v, b}, {a, b}}

: שלוש צלעות הפורשות את ארבעת הקדקודים ומחברות אותם, כלומר עץ פורש, ומשקלו

w (T^{'}) = - 1 + 1 + 2 = 2 < 10 = w (T) .

(אכן, Kruskal בוחר בדיוק את הצלעות

- 1, 1, 2

ומחזיר את

T^{'}

.) לכן הטענה מופרכת.

■

מדוע ההרצה לסירוגין נכשלת. לאחר שהצלע

e^{*}

מחברת בין

u

ל-

v

, הרכיב שנבנה עד כה הוא האיחוד

T_{u} \cup T_{v}

, ולפי תכונת החתך הצעד הבטוח הוא הוספת הצלע המזערית היוצאת מן האיחוד הזה. ואכן, Prim על הגרף המתקבל מכיווץ

e^{*}

היה בוחר תחילה את

{v, b}

במשקל

1

, ורק אז את

{a, b}

במשקל

2

— ומקבל את

T^{'}

. ההרצה לסירוגין, לעומת זאת, מחייבת את

T_{u}

להוסיף את הצלע המזערית היוצאת ממנו בלבד, ולכן היא כופה עליו את הצלע הכבדה

{u, a}

עוד לפני שהתברר שאפשר להגיע ל-

a

בזול דרך הצד השני.

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