שאלה 6אלגוריתמיקה2026 קיץ מועד בסריקה לעומקסה״כ 27 נק׳
טענות על גרפים ועצים, ו"גרף BFS רדוד"
לפניכם שני סעיפים, א-ב, שאין קשר ביניהם. ענו על שני הסעיפים.
משימות
אמשימה א
נימוקניקוד לא ידוע
לפניכם שבע טענות 1-7. בחרו בחמש מהן וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) בגרף לא מכוון שבו לכל קודקוד דרגה זוגית הגדולה מ־0, קיים מעגל.
(2) בגרף לא מכוון קשיר, הסרת קשת שאינה שייכת לאף מעגל תגרום לגרף להיות לא קשיר.
(3) כל עץ הוא גרף דו צדדי וגם כל גרף דו צדדי הוא עץ.
(4) אם בגרף מכוון קיים מעגל, אז הגרף קשיר חזק (היטב).
(5) אם גרף לא מכוון הוא עץ, אז בין כל שני קודקודים בגרף קיים מסלול יחיד.
(6) בגרף לא מכוון ללא מעגלים, אם מוסיפים קשת אחת כלשהי, בהכרח ייווצר מעגל.
(7) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n-1 קשתות, בהכרח הוא עץ.
במשימה ב
תשובהניקוד לא ידוע
עץ נקרא "עץ רדוד" אם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ.
✎ דוגמה לעץ רדודאם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ
קודקודים: A, B, C, D
קשתות: A–B, A–C, B–D
גרף לא מכוון וקשיר נקרא "גרף BFS רדוד" אם בכל הרצת BFS על הגרף, מכל קודקוד התחלה שנבחר, מתקבל עץ רדודאם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ.
לפניכם שישה גרפים G1–G6. בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף BFS רדודאם בכל הרצת BFS על הגרף, מכל קודקוד התחלה שנבחר, מתקבל "עץ רדוד" או לא. אם כתבתם שלא – הציגו סריקת BFS שבעבורה מתקבל עץ שאינו "רדוד".
G1: קודקודים A, B, C, D, E
קשתות: C–A, C–B, C–D, C–EG2: קודקודים A, B, C, D
קשתות: A–B, A–C, B–D, C–DG3: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, D–EG4: קודקודים A, B, C, D
קשתות: A–B, A–C, A–D, B–C, B–D, C–DG5: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, C–E, D–EG6: קודקודים A, B, C, D, E
קשתות: A–B, B–E, A–C, C–D
שפת התכנות שלי
שאלה 6אלגוריתמיקה2026 קיץ מועד בסריקה לעומקסה״כ 27 נק׳
טענות על גרפים ועצים, ו"גרף BFS רדוד"
לפניכם שני סעיפים, א-ב, שאין קשר ביניהם. ענו על שני הסעיפים.
משימות
אמשימה א
נימוקניקוד לא ידוע
לפניכם שבע טענות 1-7. בחרו בחמש מהן וכתבו את מספריהן. ציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות.
(1) בגרף לא מכוון שבו לכל קודקוד דרגה זוגית הגדולה מ־0, קיים מעגל.
(2) בגרף לא מכוון קשיר, הסרת קשת שאינה שייכת לאף מעגל תגרום לגרף להיות לא קשיר.
(3) כל עץ הוא גרף דו צדדי וגם כל גרף דו צדדי הוא עץ.
(4) אם בגרף מכוון קיים מעגל, אז הגרף קשיר חזק (היטב).
(5) אם גרף לא מכוון הוא עץ, אז בין כל שני קודקודים בגרף קיים מסלול יחיד.
(6) בגרף לא מכוון ללא מעגלים, אם מוסיפים קשת אחת כלשהי, בהכרח ייווצר מעגל.
(7) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n-1 קשתות, בהכרח הוא עץ.
במשימה ב
תשובהניקוד לא ידוע
עץ נקרא "עץ רדוד" אם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ.
✎ דוגמה לעץ רדודאם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ
קודקודים: A, B, C, D
קשתות: A–B, A–C, B–D
גרף לא מכוון וקשיר נקרא "גרף BFS רדוד" אם בכל הרצת BFS על הגרף, מכל קודקוד התחלה שנבחר, מתקבל עץ רדודאם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ.
לפניכם שישה גרפים G1–G6. בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף BFS רדודאם בכל הרצת BFS על הגרף, מכל קודקוד התחלה שנבחר, מתקבל "עץ רדוד" או לא. אם כתבתם שלא – הציגו סריקת BFS שבעבורה מתקבל עץ שאינו "רדוד".
G1: קודקודים A, B, C, D, E
קשתות: C–A, C–B, C–D, C–EG2: קודקודים A, B, C, D
קשתות: A–B, A–C, B–D, C–DG3: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, D–EG4: קודקודים A, B, C, D
קשתות: A–B, A–C, A–D, B–C, B–D, C–DG5: קודקודים A, B, C, D, E
קשתות: A–B, B–C, C–D, C–E, D–EG6: קודקודים A, B, C, D, E
קשתות: A–B, B–E, A–C, C–D
