טוען...
טוען...
בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם שש טענות 1-6. בחרו בארבע מהן, כתבו את מספר הטענה, וציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
(1) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n - 1 קשתות, בהכרח אין בו מעגלים.
(2) נתון גרף ממושקל (אי־שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.
(3) נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף n - 1 רכיבי קשירות.
(4) נתון גרף לא מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים בגרף שיש ביניהם מסלול.
(5) נתון גרף מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים שיש ביניהם מסלול.
(6) נתון גרף לא מכוון. בעץ פורש DFS של הגרף שהורץ מקודקוד התחלה s, יש קודקוד v ולו x בנים. לכן בכל עץ פורש DFS של הגרף שהורץ מקודקוד התחלה v, בהכרח יש לקודקוד v לפחות x בנים.
נתון גרף לא מכוון G ובו 5 קודקודים: a, b, c, d, s.
לאחר הרצת DFS מקודקוד התחלה s התקבל העץ שבסרטוט הנתון:
בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G, מקודקוד התחלה a. נמקו את קביעותיכם.
(i)
(ii)
(iii)
בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
לפניכם שש טענות 1-6. בחרו בארבע מהן, כתבו את מספר הטענה, וציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם היא אינה נכונה – הביאו דוגמה נגדית מגרף שיש בו 4 קודקודים לפחות.
(1) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n - 1 קשתות, בהכרח אין בו מעגלים.
(2) נתון גרף ממושקל (אי־שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.
(3) נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף n - 1 רכיבי קשירות.
(4) נתון גרף לא מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים בגרף שיש ביניהם מסלול.
(5) נתון גרף מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים שיש ביניהם מסלול.
(6) נתון גרף לא מכוון. בעץ פורש DFS של הגרף שהורץ מקודקוד התחלה s, יש קודקוד v ולו x בנים. לכן בכל עץ פורש DFS של הגרף שהורץ מקודקוד התחלה v, בהכרח יש לקודקוד v לפחות x בנים.
נתון גרף לא מכוון G ובו 5 קודקודים: a, b, c, d, s.
לאחר הרצת DFS מקודקוד התחלה s התקבל העץ שבסרטוט הנתון:
בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G, מקודקוד התחלה a. נמקו את קביעותיכם.
(i)
(ii)
(iii)