איך לתרגל שאלות עץ פורש מינימלי באלגוריתמים?

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

כמה שאלות עץ פורש מינימלי יש באלגוריתמים?

באתר prepd יש עשרות שאלות עץ פורש מינימלי באלגוריתמים ממבחנים, עם פתרונות לבדיקה עצמית. ניתן לסנן לפי רמת קושי, לאתר שאלות חוזרות ולתרגל ממוקד על נושא זה.

מה חשוב לדעת על עץ פורש מינימלי לקראת מבחן באלגוריתמים?

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

אלגוריתמים - עץ פורש מינימלי

עיצוב וניתוח אלגוריתמים, תכנות דינמי, אלגוריתמים חמדניים וגרפים

סטטיסטיקות מבחנים

תתי-נושאים של גרפים

רמת קושי:

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

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

G = (V, E)

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

w (e) > 0

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

e_{1} \neq = e_{2}

מתקיים

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

.

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

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

n

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה81 · 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^{'}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה81 · 2026 · סמסטר א

★★★★★

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

נתון גרף לא מכוון

G = (V, E)

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

w (e) > 0

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

F \subseteq E

נקראת מנתקת-מעגלים אם לאחר הסרתה לא נותרים מעגלים בגרף, כלומר

G^{'} = (V, E ∖ F)

חסר-מעגלים. משקלה של קבוצת צלעות

F

הוא

w (F) = \sum_{e \in F} w (e)

.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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 · סמסטר א

★★★★★

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

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

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 · סמסטר א

★★★★★

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

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

G = (V, E)

עם משקלים

w (e)

(חלקם עשויים להיות שליליים). הוכיחו כי האלגוריתמים של Prim ושל Kruskal מפיקים עפ"מ גם כאשר חלק מהמשקלים שליליים.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עץ פורש מינימלירדוקציהקרוסקלפריםגרפיםהוכחת נכונות

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

G = (V, E)

עם משקלי צלעות

w (e) > 0

. תהי

\emptyset \neq = S ⊊ V

. למת-החתך קובעת: אם

e^{*}

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

S

ל-

V ∖ S

), אזי יש עץ פורש מזערי

T^{*}

המקיים

e^{*} \in T^{*}

.

לפניכם ניסיון הוכחה:
1. יהי

T

עץ פורש מזערי. אם

e^{*} \in T

אז אין מה להוכיח. אחרת,
2. כל עץ פורש חייב לחבר בין

S

ל-

V ∖ S

, ולכן ישנה צלע

e \in T

החוצה את החתך.
3. תת-הגרף החדש

T^{*} := (T \cup {e^{*}}) ∖ {e}

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

T

עפ"מ אז גם

T^{*}

עפ"מ, המקיים

e^{*} \in T^{*}

.

א. החלק השגוי היחיד בטיעון הוא מספר 3. הסבירו במילים מהי הטעות. (11 נק')

ב. הציגו דוגמה נגדית ממושקלת פשוטה של

G, T, e, e^{*}

הממחישה את הטעות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הקלט הוא גרף קשיר ולא-מכוון

G = (V, E)

עם קדקוד מוצא

s

, ומשקלים חיוביים ייחודיים בצלעות (

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

לצלעות שונות). תזכורת:

T_{1}

הוא עץ מסלולים מזעריים (עמ"מ) מ-

s

, ו-

T_{2}

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

G

.

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

> "לכל עמ"מ

T_{1}

ולכל עפ"מ

T_{2}

יש לפחות צלע משותפת אחת."

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עץ פורש מינימלימסלולים קצריםגרפיםהוכחה

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

G = (V, E)

עם משקלי צלעות

w (e) > 0

ייחודיים. נתבונן בוריאנט הבא של Kruskal למציאת עפ"מ, שבו שלב הבחירה משתנה:

> בכל איטרציה בוחרים באקראי בהתפלגות אחידה את אחד העצים

T

ביער, ואז מוסיפים ליער את הצלע

e

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

T

ליתר הגרף.

(שאר האלגוריתם כמו Kruskal המקורי: מתחילים ביער של קדקודים בודדים, ומסתיימים כשנותר עץ יחיד.)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עץ פורש מינימליקרוסקלהוכחת נכונותגרפים

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

G = (V, E)

עם משקלי צלעות

w (e) > 0

ייחודיים. נזכיר את אלגוריתם Kruskal: (א) מתחילים ביער

F

שבו כל קדקוד הוא עץ נפרד; (ב) בכל איטרציה מוסיפים ליער את הצלע

e^{*}

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

G

המחברות שני עצים שונים של

F

, ומאחדים אותם; (ג) עד שנותר עץ פורש יחיד.

נתבונן בוריאנט הבא, שבו שלב (ב) משתנה:

> בכל איטרציה בוחרים קדקוד כלשהו

v^{*}

שממנו יוצאת לפחות צלע אחת אל מחוץ לעץ שלו

T (v^{*})

, ומוסיפים ליער את הצלע

e^{*}

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

v^{*}

אל מחוץ ל-

T (v^{*})

.

הוכיחו או הפריכו את נכונות הווריאנט (מציאת עפ"מ). זו אינה שאלה על יעילות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלות עץ פורש מינימלי באלגוריתמים עם פתרונות

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