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

(שאלה רלוונטית לסטודנטים משנת 2024 בלבד)

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

G = (V, E)

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

w (e) > 0

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

e_{1} \neq = e_{2}

מתקיים

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

.

הוכיחו/הפריכו: אם משקלי-הצלעות יחודיים, אז לגרף יש עפ"מ יחיד (כלומר לא יתכנו שני עפ"מ שונים).

(נדרשת הוכחה מדויקת או דוגמה נגדית של גרף עם

n

קדקודים גדול כרצוננו.)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הנח בסתירה שקיימים שני עפ"מ

T_{1} \neq = T_{2}

; בחר את הצלע הקלה ביותר בהפרש הסימטרי שלהם; הוסף אותה לעפ"מ שאינו מכיל אותה והסר צלע כבדה יותר מהמעגל שנוצר — תקבל עץ פורש קל יותר, סתירה.

הטענה נכונה: כאשר כל משקלי-הצלעות שונים זה מזה, עץ הפורש המינימלי יחיד.

הוכחה: נניח בסתירה שקיימים שני עפ"מ שונים

T_{1} \neq = T_{2}

. נגדיר

e^{*}

כצלע ממשקל מינימלי בהפרש הסימטרי

T_{1} △ T_{2}

. בלא הגבלת הכלליות,

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

.

הוספת

e^{*} = (u, v)

ל-

T_{2}

יוצרת מעגל יחיד

C

ב-

T_{2} \cup {e^{*}}

. המעגל

C

חייב לכלול צלע

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

(אחרת

C \subseteq T_{1}

, סתירה לכך ש-

T_{1}

עץ). בפרט

f \in T_{1} △ T_{2}

, לכן לפי הגדרת

e^{*}

w (e^{*}) \leq w (f)

מכיוון שהמשקלים יחודיים,

w (e^{*}) \neq = w (f)

, לכן

w (e^{*}) < w (f)

.

כעת

T_{2}^{'} = T_{2} \cup {e^{*}} ∖ {f}

הינו עץ פורש (מחיקת צלע ממעגל מחזירה עץ). משקלו:

w (T_{2}^{'}) = w (T_{2}) + w (e^{*}) - w (f) < w (T_{2})

כלומר

T_{2}^{'}

עץ פורש ממשקל קטן יותר מ-

T_{2}

— סתירה לכך ש-

T_{2}

הוא עפ"מ!

■

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