לפניכם שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

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

(1) נתון גרף G שאינו מכוון. אם בגרף יש קשת בין שני הקודקודים x, y – הרכיבים הקשירים של x ושל y זהים. (2) נתון גרף G מכוון. אם בגרף יש קשת מקודקוד x לקודקוד y וגם קשת מקודקוד y לקודקוד x – הרכיבים הקשירים היטב של x ושל y זהים. (3) בגרף מכוון שיש בו מעגל, יש לפחות שני קודקודים שדרגת הכניסה שלהם גדולה מ-0. (4) אם בגרף ממושקל קשיר לא מכוון יש לכל קשת משקל שונה, אז המסלול הקצר (הקל) בין כל שני קודקודים בגרף הוא מסלול יחיד (כלומר אין יותר ממסלול קצר אחד בין קודקוד לקודקוד). (5) בגרף מכוון שבו המשקל של כל קשת הוא משקל שונה יש עץ פורש מינימלי יחיד. (6) לא קיים גרף מכוון ממושקל שבו האלגוריתם של דייקסטרה מקודקוד x אל קודקוד y ייתן את אותו מסלול קצר (קל) שהאלגוריתם BFS נותן. (7) אפשר לעשות מיון טופולוגי בעבור כל גרף מכוון.

סעיף ב — גרפים "DFS שרשרתי". עץ פורש "שרשרת" הוא עץ שבו לכל צומת יש בן אחד לכל היותר. דוגמה לעץ פורש "שרשרת":

A -> B -> C -> D -> E -> F

גרף קשיר לא מכוון מכונה "DFS שרשרתי" אם בכל סריקת DFS מכל צומת בגרף מתקבל עץ פורש "שרשרת". לפניכם שבעה גרפים G1–G7. בחרו בארבעה מהם, וכתבו בנוגע לכל גרף שבחרתם אם הוא גרף "DFS שרשרתי" או לא. אם כתבתם שלא – הציגו סריקת DFS שבעבורה מתקבל עץ פורש שאינו עץ פורש "שרשרת".

רשימות הקשתות של שבעת הגרפים (כל הגרפים לא מכוונים):

G1:  A-B, B-C, B-D, B-E, B-F
     כוכב: B מחובר ל-A, C, D, E, F, ואין קשתות נוספות
         A     C
          \   /
            B
          / | \
         F  E  D

G2:  A-B, B-C, C-D, D-E
     מסלול פשוט על 5 קודקודים
     A --- B --- C --- D --- E

G3:  A-B, B-C, C-D, D-E, E-F, F-A
     מעגל אחד באורך 6
     A --- B --- C
     |           |
     F --- E --- D

G4:  A-B, B-C, C-D, D-E, E-B
     המעגל B-C-D-E ועוד העלה A המחובר ל-B
     A --- B --- C
           |     |
           E --- D

G5:  A-B, B-C, A-D, B-D
     המשולש A-B-D ועוד העלה C המחובר ל-B
     A --- B --- C
      \   /
       \ /
        D

G6:  A-B, B-C, C-F, F-E, E-D, D-A, B-E
     המעגל A - B - C - F - E - D - A (באורך 6)
     ועוד מיתר יחיד B - E המחבר שני קודקודים נגדיים במעגל

G7:  A-B, A-C, A-D, B-C, B-D, C-D
     הגרף המלא K4: כל זוג מתוך A, B, C, D מחובר
     A --- B
     | \ / |
     | / \ |
     C --- D