לפניכם שש טענות א–ו. בחרו בחמש מהן, וציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם הטענה לא נכונה – הביאו דוגמה נגדית.
א. כל עץ המתקבל מהרצת DFS על גרף G לא מכוון, יכול להתקבל גם מהרצת BFS על אותו הגרף.
ב. כל עץ המתקבל מהרצת DFS על גרף G לא מכוון מלא הוא עץ שבו לכל צומת יש רק בן אחד.
ג. נתון גרף מכוון G וקודקוד v. אם אפשר להגיע מקודקוד v לכל אחד מן הקודקודים בגרף, ואפשר גם להגיע מכל אחד מן הקודקודים אל קודקוד v, הגרף G הוא בהכרח גרף קשיר היטב (חזק).
ד. אם בגרף G שאינו מכוון המסלול הקצר ביותר מן הצומת s_j אל הצומת s_n הוא S[s_j...s_m...s_k...s_n], בהכרח התת־מסלול מ־s_m ועד s_k הוא המסלול הקצר ביותר מן הצומת s_m אל הצומת s_k.
ה. גרף שיש בו מעגל אינו יכול להיות גרף דו־צדדי.
ו. לכל גרף G ממושקל, לא מכוון, יש עץ פורש מינימלי יחיד.
לפניכם שש טענות א–ו. בחרו בחמש מהן, וציינו בנוגע לכל טענה שבחרתם אם היא נכונה או לא נכונה. אם הטענה נכונה – נמקו מדוע, ואם הטענה לא נכונה – הביאו דוגמה נגדית.
א. כל עץ המתקבל מהרצת DFS על גרף G לא מכוון, יכול להתקבל גם מהרצת BFS על אותו הגרף.
ב. כל עץ המתקבל מהרצת DFS על גרף G לא מכוון מלא הוא עץ שבו לכל צומת יש רק בן אחד.
ג. נתון גרף מכוון G וקודקוד v. אם אפשר להגיע מקודקוד v לכל אחד מן הקודקודים בגרף, ואפשר גם להגיע מכל אחד מן הקודקודים אל קודקוד v, הגרף G הוא בהכרח גרף קשיר היטב (חזק).
ד. אם בגרף G שאינו מכוון המסלול הקצר ביותר מן הצומת s_j אל הצומת s_n הוא S[s_j...s_m...s_k...s_n], בהכרח התת־מסלול מ־s_m ועד s_k הוא המסלול הקצר ביותר מן הצומת s_m אל הצומת s_k.
ה. גרף שיש בו מעגל אינו יכול להיות גרף דו־צדדי.
ו. לכל גרף G ממושקל, לא מכוון, יש עץ פורש מינימלי יחיד.
