גרפים›ייצוג גרפים

שאלה 6 במסלול אלגוריתמים. בסעיף א שבע טענות כלליות בתורת הגרפים (קשירות, מעגלים, עצים, דו-צדדיות, קשירות חזקה) — התלמיד בוחר חמש ומנמק/מפריך כל אחת. בסעיף ב, שאין לו קשר לסעיף א, מוגדר מושג "גרף BFS רדוד" (כל הרצת BFS ממנו נותנת עץ שעומקו לכל היותר 3), והתלמיד מסווג ארבעה מתוך שישה גרפים נתונים.

דוגמה ל"עץ רדוד": A שורש, ילדים B,C; ל-B ילד D

A->B, A->C, B->D

שישה גרפים G1-G6 לסיווג "גרף BFS רדוד" (p-11.png)

G1: star, hub C, leaves A,B,D,E (edges A-C,B-C,C-D,C-E). G2: 4-cycle A-B-D-C-A (edges A-B,B-D,D-C,C-A). G3: path A-B-C-D-E. G4: K4 on A,B,C,D (all 6 edges, drawn with a visible crossing X). G5: A-B, B-C, C-D, C-E (tree). G6: A-B, B-E, A-C, C-D (tree).

סעיף א

לפניכם שבע טענות 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 שבעבורה מתקבל עץ שאינו "רדוד".

שאלות ותגובות על השאלה

🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות

שאלו כאן — ותקבלו מענה מוסמך.

🎓 מרצה לתכנות עונה כאן — תקבלו מענה מקצועי

דלגו לשאלה דומה ←