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

באתר 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)

, ונתונות שתי קבוצות של קדקודים זרות

A, B \subseteq V

.

קבוצה של צלעות

D \subseteq E

תקרא "קבוצה מפרידה" אם הסרתה מהגרף תנתק את

A

מ-

B

(כלומר, בגרף

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

לא נותר אף מסלול שמתחיל בקדקוד של

A

ומסתיים בקדקוד של

B

). קבוצה מפרידה מזערית הינה קבוצה מפרידה בעלת גודל

∣ D ∣

מזערי.

קבוצה של צלעות

C \subseteq E

תקרא "קבוצת חתך" אם ישנה קבוצת קדקודים

\emptyset \neq = S \subseteq V

כך ש-

C

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

S

(כלומר

C = {(x, y) \in E ∣ x \in S, y \in / S}

).

הוכיחו/הפריכו כל אחת מהטענות הבאות (טענה א' 11 נק', טענה ב' 22 נק'):

טענה א': "כל קבוצה מפרידה הינה קבוצת חתך."

טענה ב': "כל קבוצה מפרידה מזערית הינה קבוצת חתך."

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה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)

עם קדקוד מוצא

s

ומשקלי צלעות

w (e) > 0

. עץ

T

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

s

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

s

שווה למרחק ב-

G

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

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

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

T_{1} \neq = T_{2}

מהמוצא

s

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

v

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

s

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

. תת-קבוצה של קדקודים

C \subseteq V

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

e = {u, v} \in E

מתקיים

u \in C

או

v \in C

(כיסוי קדקודים). ברצוננו למצוא קבוצה מיוחדת שגודלה מזערי.

האלגוריתם החמדני: נאתחל

G^{'} = G

ואת

C

להיות הקבוצה הריקה. נמשיך באיטרציות: (א) נוסיף ל-

C

קדקוד

v

בעל דרגה מרבית בגרף הנוכחי

G^{'}

, ואז (ב) נמחק את

v

מ-

G^{'}

ונסיר את הצלעות הנוגעות בו. הפלט

C

הוא תמיד קבוצה מיוחדת.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הציגו דוגמה פשוטה של רשת-זרימה עם צלע

e

, המקיימת את שתי התכונות הבאות: (א) בהרצת Edmonds-Karp על הרשת ישנן שתי איטרציות שונות, שבהן תוספת הזרימה דרך

e

זהה לקיבולת השיורית של

e

(באותה איטרציה). (ב) הצלע

e

מחברת בגרף המקורי בין שני קדקודים שמרחקם מהמקור

s

שונה. לא יינתן ניקוד על דוגמה שמתאימה להרצה של Ford-Fulkerson אבל לא מתאימה להרצה של Edmonds-Karp. (כרגיל, המושג "מרחק" מתייחס למספר הצלעות במסלול הקצר ביותר.)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 88 · 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)

עם קדקוד מוצא

s

ומשקלים

w (e)

(חלקם עשויים להיות שליליים). ידוע שאין ב-

G

מעגלים שליליים, ולכן קיים עץ מסלולים מזעריים (עמ"מ)

T

מ-

s

. הגדרה: הגרף

G

ייקרא "מיוחד" אם לכל קדקוד

v \neq = s

קיימת לפחות צלע שלילית אחת שיוצאת מ-

v

.

הכריעו את נכונותן של הטענות הבאות:

א. "לכל גרף מיוחד יש עמ"מ

T

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

ב. "קיימת סדרה אינסופית של גרפים מיוחדים (שמספר הקדקודים בהם הולך וגדל), ועבור כל גרף מיוחד בסדרה מתקיים שכל עמ"מ

T

כולל רק צלעות חיוביות.\"

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

. תת-קבוצה של קדקודים

C \subseteq V

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

e = {u, v} \in E

מתקיים

u \in C

או

v \in C

(כיסוי קדקודים). ברצוננו למצוא קבוצה מיוחדת מזערית.

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

G

הוא יער (גרף חסר מעגלים), והוכיחו את נכונותו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

אלגוריתמים חמדנייםגרפיםהוכחת נכונות

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

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