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

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

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

שנה: 2022

סמסטר: ב

נושאים: מסלולים קצרים, גרפים, הוכחה, הוכח או הפרך

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

בבעיית המסלולים המזעריים נתון גרף מכוון $G=(V,E)$ עם קדקוד מוצא $s$ ומשקלי צלעות $w(e)>0$. עץ $T$ של מסלולים מזעריים (**עמ"מ**) מ-$s$ הוא תת-גרף פורש שבו לכל קדקוד המרחק מ-$s$ שווה למרחק ב-$G$ (למשל, עץ הפלט של Dijkstra). לכל גרף קלט יש לפחות עמ"מ אחד. הוכיחו או הפריכו: > "ישנם מספר עמ"מ שונים $T_1 \neq T_2$ מהמוצא $s$ — **אם ורק אם** יש קדקוד $v$ עם מספר מסלולים מזעריים שונים מ-$s$."

רמז: שני עמ"מ שונים נבדלים בצלע $e$ המובילה לקדקוד $v$ — ומכאן שני מסלולים מזעריים שונים ל-$v$. בכיוון ההפוך, שני מסלולים מזעריים ל-$v$ מאפשרים "להחליף" צלע בעמ"מ נתון ולקבל עמ"מ אחר.

פתרון: **הטענה נכונה.** נוכיח את שני הכיוונים. **($\Rightarrow$) מספר עמ"מ שונים $\Rightarrow$ קדקוד עם מספר מסלולים מזעריים.** נניח $T_1\neq T_2$ שני עמ"מ. שניהם פורשים את אותם הקדקודים אך נבדלים בצלע אחת לפחות; תהי $e\in T_1\setminus T_2$, ותהי $v$ הקצה של $e$ הרחוק מ-$s$. המסלול ב-$T_1$ מ-$s$ ל-$v$ משתמש ב-$e$. מכיוון ש-$T_2$ עמ"מ, גם בו יש מסלול מזערי מ-$s$ ל-$v$, והוא **אינו** מכיל את $e$. קיבלנו שני מסלולים מזעריים שונים מ-$s$ ל-$v$ ב-$G$ (שכן $T_1,T_2\subseteq G$). $\blacksquare$ **($\Leftarrow$) קדקוד עם מספר מסלולים מזעריים $\Rightarrow$ מספר עמ"מ שונים.** נניח שלקדקוד $v$ יש שני מסלולים מזעריים שונים $P_1\neq P_2$ מ-$s$. $P_1$ מוכל בעמ"מ $T_1$ כלשהו. המסלולים נבדלים; יהי $v'$ הקדקוד האחרון המשותף להם לפני שנפרדים, ותהיינה $e_1$ (של $P_1$) ו-$e_2$ (של $P_2$) הצלעות היוצאות ממנו, $e_1\neq e_2$. מכיוון ששני המסלולים מזעריים, $\text{dist}(s,\text{end}(e_2))$ מושג גם דרך $e_2$. נגדיר $T_2 = (T_1\setminus\{e_1\})\cup\{e_2\}$: זהו עדיין עץ פורש (החלפת צלע אחת בתוך המעגל שנוצר), וכל המרחקים מ-$s$ נשמרים, ולכן $T_2$ עמ"מ. כמו כן $e_1\neq e_2$ ולכן $T_2\neq T_1$. קיבלנו שני עמ"מ שונים. $\blacksquare$

בבעיית המסלולים המזעריים נתון גרף מכוון

G = (V, E)

עם קדקוד מוצא

s

ומשקלי צלעות

w (e) > 0

. עץ

T

של מסלולים מזעריים (עמ"מ) מ-

s

הוא תת-גרף פורש שבו לכל קדקוד המרחק מ-

s

שווה למרחק ב-

G

(למשל, עץ הפלט של Dijkstra). לכל גרף קלט יש לפחות עמ"מ אחד.

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

> "ישנם מספר עמ"מ שונים

T_{1} \neq = T_{2}

מהמוצא

s

— אם ורק אם יש קדקוד

v

עם מספר מסלולים מזעריים שונים מ-

s

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מסלולים קצריםגרפיםהוכחההוכח או הפרך

שני עמ"מ שונים נבדלים בצלע

e

המובילה לקדקוד

v

— ומכאן שני מסלולים מזעריים שונים ל-

v

. בכיוון ההפוך, שני מסלולים מזעריים ל-

v

מאפשרים "להחליף" צלע בעמ"מ נתון ולקבל עמ"מ אחר.

הטענה נכונה. נוכיח את שני הכיוונים.

(

\Rightarrow

) מספר עמ"מ שונים

\Rightarrow

קדקוד עם מספר מסלולים מזעריים. נניח

T_{1} \neq = T_{2}

שני עמ"מ. שניהם פורשים את אותם הקדקודים אך נבדלים בצלע אחת לפחות; תהי

e \in T_{1} ∖ T_{2}

, ותהי

v

הקצה של

e

הרחוק מ-

s

. המסלול ב-

T_{1}

מ-

s

ל-

v

משתמש ב-

e

. מכיוון ש-

T_{2}

עמ"מ, גם בו יש מסלול מזערי מ-

s

ל-

v

, והוא אינו מכיל את

e

. קיבלנו שני מסלולים מזעריים שונים מ-

s

ל-

v

ב-

G

(שכן

T_{1}, T_{2} \subseteq G

■

(

\Leftarrow

) קדקוד עם מספר מסלולים מזעריים

\Rightarrow

מספר עמ"מ שונים. נניח שלקדקוד

v

יש שני מסלולים מזעריים שונים

P_{1} \neq = P_{2}

מ-

s

P_{1}

מוכל בעמ"מ

T_{1}

כלשהו. המסלולים נבדלים; יהי

v^{'}

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

e_{1}

(של

P_{1}

) ו-

e_{2}

(של

P_{2}

) הצלעות היוצאות ממנו,

e_{1} \neq = e_{2}

. מכיוון ששני המסלולים מזעריים,

dist (s, end (e_{2}))

מושג גם דרך

e_{2}

. נגדיר

T_{2} = (T_{1} ∖ {e_{1}}) \cup {e_{2}}

: זהו עדיין עץ פורש (החלפת צלע אחת בתוך המעגל שנוצר), וכל המרחקים מ-

s

נשמרים, ולכן

T_{2}

עמ"מ. כמו כן

e_{1} \neq = e_{2}

ולכן

T_{2} \neq = T_{1}

. קיבלנו שני עמ"מ שונים.

■

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