שאלה 7 במסלול אלגוריתמים. לפניכם שש טענות א–ו על גרפים. בבחינה יש לבחור בחמש מהן ולציין לכל אחת אם היא נכונה או לא נכונה: אם נכונה — לנמק, ואם לא נכונה — להביא דוגמה נגדית. כאן פתורות כל שש הטענות.

כל עץ המתקבל מהרצת DFS על גרף G לא מכוון, יכול להתקבל גם מהרצת BFS על אותו הגרף.

כל עץ המתקבל מהרצת DFS על גרף G לא מכוון מלא הוא עץ שבו לכל צומת יש רק בן אחד.

נתון גרף מכוון G וקודקוד v. אם אפשר להגיע מקודקוד v לכל אחד מן הקודקודים בגרף, ואפשר גם להגיע מכל אחד מן הקודקודים אל קודקוד v, הגרף G הוא בהכרח גרף קשיר היטב (חזק).

אם בגרף G שאינו מכוון המסלול הקצר ביותר מן הצומת sj אל הצומת sn הוא S[sj … sm … sk … sn], בהכרח התת-מסלול מ-sm ועד sk הוא המסלול הקצר ביותר מן הצומת sm אל הצומת sk.

גרף שיש בו מעגל אינו יכול להיות גרף דו-צדדי.

לכל גרף G ממושקל, לא מכוון, יש עץ פורש מינימלי יחיד.