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

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

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

שנה: 2026

סמסטר: א

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

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

נתון גרף קשיר ולא מכוון $G = (V, E)$ עם משקלים חיוביים $w(e) > 0$ בצלעות. המשקלים **יחודיים**, כלומר $w(e_1) \neq w(e_2)$ לכל $e_1 \neq e_2$. ברצוננו למצוא עץ פורש מזערי. הביטו באלגוריתם האיטרטיבי הבא, שבכל שלב שומר תת-גרף $G' = (V, F)$, $F \subseteq E$. בתחול, קבוצת הצלעות $F$ ריקה. בכל איטרציה: א. ראשית, נסרוק את רשימת כל רכיבי-הקשירות $C_1,...,C_k$ בתת-הגרף הנוכחי $G'$, ועבור כל רכיב $C_i$ נמצא את הצלע $e_i$ בעלת המשקל המזערי שיוצאת החוצה מ-$C_i$ (הקלט $G$ קשיר, לכן מכל $C_i$ יוצאת לפחות צלע אחת, ולכן קיימת צלע מזערית שיוצאת מ-$C_i$). ב. שנית, נוסיף לתת-הגרף $G'$ את **כל הצלעות** שמצאנו בשלב א', כלומר נעדכן $F \leftarrow F \cup \{e_1,...,e_k\}$ (הצלעות שהוספנו לא דווקא שונות — לדוגמה, הצלע שמחברת בין $C_2$ ל-$C_4$ עשויה להיות גם הצלע המזערית שיוצאת מ-$C_2$ וגם מ-$C_4$, ולכן $e_2 = e_4$. כשמוסיפים צלע שמחברת $C_i, C_j$ — שני הרכיבים מתלכדים לכדי רכיב אחד חדש). נעצור את האלגוריתם ברגע שבו $G'$ כולל רכיב-קשירות יחיד, ונחזיר את $G'$ כפלט. **הוכיחו/הפריכו:** גרף הפלט $G'$ הינו חסר מעגלים.

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

פתרון: הטענה **נכונה**: גרף הפלט $G'$ הינו חסר מעגלים. **הוכחה:** נוכיח שבאף איטרציה לא נוצר מעגל. נניח בסתירה שבסיום איטרציה מסוימת נוצר מעגל. כלומר, קבוצת הצלעות שנוספו $\{e_1,...,e_k\}$ יצרה מעגל $C$ בגרף $G'$. מעגל זה כולל לפחות שתי צלעות שנוספו באותה איטרציה. יהיו $C_{i_1}, C_{i_2},...,C_{i_m}$ ($m \geq 2$) הרכיבים שהשתתפו במעגל לפני האיטרציה, כך שהצלע $e_{i_j}$ מחברת בין $C_{i_j}$ ל-$C_{i_{j+1 \bmod m}}$. נגדיר $e_{i_1}$ כצלע בעלת המשקל **המרבי** בין כל הצלעות במעגל. הצלע $e_{i_1}$ יוצאת מ-$C_{i_1}$ אל $C_{i_2}$. עתה נבחן את הצלע $e_{i_m}$, שיוצאת מ-$C_{i_m}$ אל $C_{i_1}$. בגרף הלא-מכוון, $e_{i_m}$ היא גם צלע שמחברת בין $C_{i_1}$ ל-$C_{i_m}$, כלומר **יוצאת גם מ-$C_{i_1}$** לרכיב אחר. מכיוון ש-$e_{i_1}$ נבחרה כצלע מזערית היוצאת מ-$C_{i_1}$, ו-$e_{i_m}$ גם יוצאת מ-$C_{i_1}$: $$w(e_{i_1}) \leq w(e_{i_m})$$ אך הגדרנו ש-$e_{i_1}$ בעלת המשקל המרבי במעגל, כך ש-$w(e_{i_1}) \geq w(e_{i_m})$. לכן $w(e_{i_1}) = w(e_{i_m})$, אך המשקלים **יחודיים** — סתירה! לפיכך, לא יכול להיווצר מעגל בשום שלב, וגרף הפלט $G'$ הינו חסר מעגלים. $\blacksquare$

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

G = (V, E)

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

w (e) > 0

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

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

לכל

e_{1} \neq = e_{2}

. ברצוננו למצוא עץ פורש מזערי. הביטו באלגוריתם האיטרטיבי הבא, שבכל שלב שומר תת-גרף

G^{'} = (V, F)

F \subseteq E

. בתחול, קבוצת הצלעות

F

ריקה. בכל איטרציה:

א. ראשית, נסרוק את רשימת כל רכיבי-הקשירות

C_{1}, ..., C_{k}

בתת-הגרף הנוכחי

G^{'}

, ועבור כל רכיב

C_{i}

נמצא את הצלע

e_{i}

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

C_{i}

(הקלט

G

קשיר, לכן מכל

C_{i}

יוצאת לפחות צלע אחת, ולכן קיימת צלע מזערית שיוצאת מ-

C_{i}

).

ב. שנית, נוסיף לתת-הגרף

G^{'}

את כל הצלעות שמצאנו בשלב א', כלומר נעדכן

F \leftarrow F \cup {e_{1}, ..., e_{k}}

(הצלעות שהוספנו לא דווקא שונות — לדוגמה, הצלע שמחברת בין

C_{2}

ל-

C_{4}

עשויה להיות גם הצלע המזערית שיוצאת מ-

C_{2}

וגם מ-

C_{4}

, ולכן

e_{2} = e_{4}

. כשמוסיפים צלע שמחברת

C_{i}, C_{j}

— שני הרכיבים מתלכדים לכדי רכיב אחד חדש).

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

G^{'}

כולל רכיב-קשירות יחיד, ונחזיר את

G^{'}

כפלט.

הוכיחו/הפריכו: גרף הפלט

G^{'}

הינו חסר מעגלים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

הטענה נכונה: גרף הפלט

G^{'}

הינו חסר מעגלים.

הוכחה: נוכיח שבאף איטרציה לא נוצר מעגל.

נניח בסתירה שבסיום איטרציה מסוימת נוצר מעגל. כלומר, קבוצת הצלעות שנוספו

{e_{1}, ..., e_{k}}

יצרה מעגל

C

בגרף

G^{'}

. מעגל זה כולל לפחות שתי צלעות שנוספו באותה איטרציה.

יהיו

C_{i_{1}}, C_{i_{2}}, ..., C_{i_{m}}

(

m \geq 2

) הרכיבים שהשתתפו במעגל לפני האיטרציה, כך שהצלע

e_{i_{j}}

מחברת בין

C_{i_{j}}

ל-

C_{i_{j + 1 mod m}}

. נגדיר

e_{i_{1}}

כצלע בעלת המשקל המרבי בין כל הצלעות במעגל.

הצלע

e_{i_{1}}

יוצאת מ-

C_{i_{1}}

אל

C_{i_{2}}

. עתה נבחן את הצלע

e_{i_{m}}

, שיוצאת מ-

C_{i_{m}}

אל

C_{i_{1}}

. בגרף הלא-מכוון,

e_{i_{m}}

היא גם צלע שמחברת בין

C_{i_{1}}

ל-

C_{i_{m}}

, כלומר **יוצאת גם מ-

C_{i_{1}}

** לרכיב אחר.

מכיוון ש-

e_{i_{1}}

נבחרה כצלע מזערית היוצאת מ-

C_{i_{1}}

, ו-

e_{i_{m}}

גם יוצאת מ-

C_{i_{1}}

w (e_{i_{1}}) \leq w (e_{i_{m}})

אך הגדרנו ש-

e_{i_{1}}

בעלת המשקל המרבי במעגל, כך ש-

w (e_{i_{1}}) \geq w (e_{i_{m}})

. לכן

w (e_{i_{1}}) = w (e_{i_{m}})

, אך המשקלים יחודיים — סתירה!

לפיכך, לא יכול להיווצר מעגל בשום שלב, וגרף הפלט

G^{'}

הינו חסר מעגלים.

■

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