בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
סעיף ב. העץ שהתקבל מהרצת DFS מקודקוד התחלה s: השורש s; ילדיו a ו-b; ילדיו של b הם d ו-c.
שלושת העצים (i), (ii), (iii):
- (i): השורש a; ילדו b; ילדיו של b הם d ו-c; ילדו של c הוא s.
- (ii): השורש a; ילדו s; ילדו של s הוא b; ילדו של b הוא d; ילדו של d הוא c.
- (iii): השורש a; ילדו s; ילדו של s הוא b; ילדיו של b הם d ו-c.
לפניכם שש טענות 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 התקבל העץ שבסרטוט הנתון: השורש s; ילדיו a ו-b; ילדיו של b הם d ו-c. בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G , מקודקוד התחלה a . נמקו את קביעותיכם.
- (i): השורש a; ילדו b; ילדיו של b הם d ו-c; ילדו של c הוא s.
- (ii): השורש a; ילדו s; ילדו של s הוא b; ילדו של b הוא d; ילדו של d הוא c.
- (iii): השורש a; ילדו s; ילדו של s הוא b; ילדיו של b הם d ו-c.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.