שאלה 4אלגוריתמיקה2026 קיץ מועד אעץ פורש מינימליסה״כ 25 נק׳
טענות על גרפים ועצים פורשים מסוג שרשרת
לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
משימות
אמשימה א
נימוקניקוד לא ידוע
לפניכם שבע טענות (1)-(7). בחרו בחמש מהן, וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא לא נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) נתון גרף G שאינו מכוון. אם בגרף יש קשת בין שני הקודקודים x, y, הרכיבים הקשירים של x ושל y זהים.
(2) נתון גרף G מכוון. אם בגרף יש קשת מקודקוד x לקודקוד y וקשת מקודקוד y לקודקוד x, הרכיבים הקשירים היטב של x ושל y זהים.
(3) בגרף מכוון שיש בו מעגל, יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ־0.
(4) אם בגרף ממושקל קשיר לא מכוון יש לכל קשת משקל שונה, אז המסלול הקצר (הקל) בין כל שני קודקודים בגרף הוא מסלול יחיד (כלומר אין יותר ממסלול קצר אחד בין קודקוד לקודקוד).
(5) בגרף מכוון שבו המשקל של כל קשת הוא משקל שונה יש עץ פורש מינימלי יחיד.
(6) לא קיים גרף מכוון ממושקל שבו האלגוריתם של דייקסטרה מקודקוד y אל קודקוד x ייתן את אותו מסלול קצר (קל) שהאלגוריתם BFS נותן.
(7) אפשר לעשות מיון טופולוגי בעבור כל גרף מכוון.
במשימה ב
תשובהניקוד לא ידוע
עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר.
✎ דוגמה
לעץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר:
A → B → C → D → E → F
גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת מתקבל בגרף עץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר.
לפניכם שבעה גרפים G1–G7. בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף DFS שרשרתיאם בכל סריקת DFS מכל צומת מתקבל בגרף עץ פורש "שרשרת" או לא. אם כתבתם שלא – הציגו סריקת DFS שבעבורה מתקבל גרף שאינו עץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר.
G1: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, B–D, B–E, B–FG2: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, D–EG3: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, C–D, D–E, E–F, A–FG4: קודקודים A, B, C, E, D
קשתות: A–B, B–C, B–E, C–D, D–EG5: קודקודים A, B, C, D
קשתות: A–B, B–C, A–D, B–DG6: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, E–F, D–E, A–D, C–F, B–EG7: קודקודים A, B, C, D
קשתות: A–B, A–C, A–D, B–C, B–D, C–D
שפת התכנות שלי
שאלה 4אלגוריתמיקה2026 קיץ מועד אעץ פורש מינימליסה״כ 25 נק׳
טענות על גרפים ועצים פורשים מסוג שרשרת
לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
משימות
אמשימה א
נימוקניקוד לא ידוע
לפניכם שבע טענות (1)-(7). בחרו בחמש מהן, וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא לא נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) נתון גרף G שאינו מכוון. אם בגרף יש קשת בין שני הקודקודים x, y, הרכיבים הקשירים של x ושל y זהים.
(2) נתון גרף G מכוון. אם בגרף יש קשת מקודקוד x לקודקוד y וקשת מקודקוד y לקודקוד x, הרכיבים הקשירים היטב של x ושל y זהים.
(3) בגרף מכוון שיש בו מעגל, יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ־0.
(4) אם בגרף ממושקל קשיר לא מכוון יש לכל קשת משקל שונה, אז המסלול הקצר (הקל) בין כל שני קודקודים בגרף הוא מסלול יחיד (כלומר אין יותר ממסלול קצר אחד בין קודקוד לקודקוד).
(5) בגרף מכוון שבו המשקל של כל קשת הוא משקל שונה יש עץ פורש מינימלי יחיד.
(6) לא קיים גרף מכוון ממושקל שבו האלגוריתם של דייקסטרה מקודקוד y אל קודקוד x ייתן את אותו מסלול קצר (קל) שהאלגוריתם BFS נותן.
(7) אפשר לעשות מיון טופולוגי בעבור כל גרף מכוון.
במשימה ב
תשובהניקוד לא ידוע
עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר.
✎ דוגמה
לעץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר:
A → B → C → D → E → F
גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת מתקבל בגרף עץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר.
לפניכם שבעה גרפים G1–G7. בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף DFS שרשרתיאם בכל סריקת DFS מכל צומת מתקבל בגרף עץ פורש "שרשרת" או לא. אם כתבתם שלא – הציגו סריקת DFS שבעבורה מתקבל גרף שאינו עץ פורש שרשרתעץ שבו לכל צומת יש בן אחד לכל היותר.
G1: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, B–D, B–E, B–FG2: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, D–EG3: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, C–D, D–E, E–F, A–FG4: קודקודים A, B, C, E, D
קשתות: A–B, B–C, B–E, C–D, D–EG5: קודקודים A, B, C, D
קשתות: A–B, B–C, A–D, B–DG6: קודקודים A, B, C, F, E, D
קשתות: A–B, B–C, E–F, D–E, A–D, C–F, B–EG7: קודקודים A, B, C, D
קשתות: A–B, A–C, A–D, B–C, B–D, C–D
