שאלה 4 במסלול אלגוריתמים. בסעיף א בוחרים ארבע מתוך שש טענות בגרפים (קשירות, עצים, MST, סריקת DFS ומרחקים) וקובעים נכון/לא נכון. בסעיף ב, שאין לו קשר לסעיף א, בודקים אילו משלושה עצים נתונים יכלו להתקבל מסריקת DFS על אותו גרף שממנו התקבל עץ נתון מקודקוד s, כשהפעם ההתחלה היא מקודקוד a.
שאלה 4 במסלול אלגוריתמים. בסעיף א בוחרים ארבע מתוך שש טענות בגרפים (קשירות, עצים, MST, סריקת DFS ומרחקים) וקובעים נכון/לא נכון. בסעיף ב, שאין לו קשר לסעיף א, בודקים אילו משלושה עצים נתונים יכלו להתקבל מסריקת DFS על אותו גרף שממנו התקבל עץ נתון מקודקוד s, כשהפעם ההתחלה היא מקודקוד a.
עמוד 9, סעיף ב: העץ שהתקבל מהרצת DFS מקודקוד התחלה s
undirected DFS spanning tree obtained from start vertex s (edges drawn as plain lines):
s at the top; s—a (down-left), s—b (down-right); b—d (down-left), b—c (down-right).
עמוד 9, סעיף ב: שלושת העצים (i), (ii), (iii)
three candidate trees, printed right-to-left on the page as (i), (ii), (iii):
(i) a—b ; b—d ; b—c ; c—s (a on top, b below it, d and c below b, s below c)
(ii) a—s ; s—b ; b—d ; d—c (a on top, s below it, b to the RIGHT of s on the same level, d below b, c below d)
(iii) a—s ; s—b ; b—d ; b—c (a on top, s below it, b to the RIGHT of s on the same level, d and c below b)
לפניכם שש טענות 1–6. בחרו בארבע מהן, כתבו את מספר הטענה, וציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n−1 קשתות, בהכרח אין בו מעגלים.
נתון גרף ממושקל (אי־שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.
נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף n−1 רכיבי קשירות.
נתון גרף לא מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים בגרף שיש ביניהם מסלול.
נתון גרף מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים שיש ביניהם מסלול.
נתון גרף לא מכוון. בעץ פורש DFS של הגרף שהורץ מקודקוד התחלה s , יש קודקוד v ולו x בנים. לכן בכל עץ פורש DFS של הגרף שהורץ מקודקוד התחלה v , בהכרח יש לקודקוד v לפחות x בנים.
נתון גרף לא מכוון G ובו 5 קודקודים: a , b , c , d , s . לאחר הרצת DFS מקודקוד התחלה s התקבל העץ שבסרטוט הנתון: [העץ ב-figures] בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G , מקודקוד התחלה a . נמקו את קביעותיכם. [שלושת העצים ב-figures]
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.