לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
סעיף ב. דוגמה ל"עץ רדוד": A שורש, ילדיו B ו-C; ל-B ילד D.
ששת הגרפים G1–G6 (גרפים לא מכוונים), לפי הקשתות שבתרשים:
- G1: A-C, B-C, C-D, C-E
- G2: A-B, B-D, D-C, C-A
- G3: A-B, B-C, C-D, D-E
- G4: A-B, A-C, A-D, B-C, B-D, C-D
- G5: A-B, B-C, C-D, C-E, D-E
- G6: A-B, B-E, A-C, C-D
לפניכם שבע טענות 1-7. בחרו בחמש מהן וכתבו את מספריהן. ציינו לגבי כל טענה שבחרתם האם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו ארבעה קודקודים לפחות. הטענות: (1) בגרף לא מכוון שבו לכל קודקוד דרגה זוגית הגדולה מ-0, קיים מעגל. (2) בגרף לא מכוון קשיר, הסרת קשת שאינה שייכת לאף מעגל תגרום לגרף להיות לא קשיר. (3) כל עץ הוא גרף דו-צדדי וגם כל גרף דו-צדדי הוא עץ. (4) אם בגרף מכוון קיים מעגל, אז הגרף קשיר חזק (היטב). (5) אם גרף לא מכוון הוא עץ, אז בין כל שני קודקודים בגרף קיים מסלול יחיד. (6) בגרף לא מכוון ללא מעגלים, אם מוסיפים קשת אחת כלשהי, בהכרח ייווצר מעגל. (7) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n-1 קשתות, בהכרח הוא עץ.
עץ נקרא "עץ רדוד" אם מכל צומת בעץ יש מרחק של לכל היותר 3 קשתות לכל צומת אחר בעץ (דוגמה: A שורש עם ילדים B,C, ול-B ילד D). גרף לא מכוון וקשיר נקרא "גרף BFS רדוד" אם בכל הרצת BFS על הגרף, מכל קודקוד התחלה שנבחר, מתקבל "עץ רדוד". לפניכם שישה גרפים G1-G6. בחרו בארבעה מהם, וכתבו לגבי כל גרף שבחרתם אם הוא "גרף BFS רדוד" או לא. אם כתבתם שלא – הציגו סריקת BFS שבעבורה מתקבל עץ שאינו "רדוד".
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.