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

סעיף א — שבע טענות. בחרו בחמש מן הטענות (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 שבעבורה מתקבל עץ פורש שאינו עץ פורש "שרשרת".

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

G1:  A-B, B-C, B-D, B-E, B-F
     a star: B is joined to A, C, D, E, F ; nothing else is joined
         A     C
          \   /
            B
          / | \
         F  E  D

G2:  A-B, B-C, C-D, D-E
     a simple path on 5 vertices
     A --- B --- C --- D --- E

G3:  A-B, B-C, C-D, D-E, E-F, F-A
     one cycle of length 6
     A --- B --- C
     |           |
     F --- E --- D

G4:  A-B, B-C, C-D, D-E, E-B
     the cycle B-C-D-E plus the leaf A hanging on B
     A --- B --- C
           |     |
           E --- D

G5:  A-B, B-C, A-D, B-D
     the triangle A-B-D plus the leaf C hanging on B
     A --- B --- C
      \   /
       \ /
        D

G6:  A-B, B-C, C-F, F-E, E-D, D-A, B-E
     the cycle  A - B - C - F - E - D - A  (length 6)
     plus ONE chord  B - E  joining two opposite vertices of that cycle
     (in the printed drawing the chord B-E is the vertical line, and the
      edges A-D and C-F are the two long diagonals that cross each other)

G7:  A-B, A-C, A-D, B-C, B-D, C-D
     the complete graph K4 - every pair out of A, B, C, D is joined
     A --- B
     | \ / |
     | / \ |
     C --- D

דוגמה לעץ פורש "שרשרת": שרשרת קודקודים A-B-C-D-E-F (חיצים חד-כיווניים ברצף).

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

שבעה גרפים G1-G7 לבדיקת האם DFS מכל צומת נותן עץ פורש "שרשרת".

G1: A-B(-F,-C); B-E; C-D  (B מרכזי מחובר ל-A,C,F,E; C מחובר ל-D)
G2: A-B-C-D-E (שרשרת ישרה)
G3: A-B-C, B-F-E-D, C-D (מעגל/רשת: A-B,B-C,B-F,F-E,E-D,D-C)
G4: A-B-C, B-E-D, C-D (A-B,B-C,B-E,E-D,D-C)
G5: A-B-C, A-D, B-D (משולש A-B-D + B-C)
G6: A-B-C (עם X בין A-B-C ו-F-E-D, כלומר A-E,B-F,B-D,C-E... צומת עם צלבים בין שורה עליונה A,B,C לשורה תחתונה F,E,D), F-E-D
G7: A-B, C-D, ועם צלב A-D,B-C (K4 חלקי: A-B,C-D,A-D,B-C, A-C or B-D צולבים)
[תיקון קריאה 03.09 מול תמונת העמוד: G1 = כוכב: B מחובר ל-A, C, D, E, F (5 קשתות); שאר הקודקודים עלים.]
[תיקון קריאה 03.09 מול תמונת העמוד: G6 = מעגל A-B-C-F-E-D-A ועוד מיתר יחיד B-E (7 קשתות); A-D ו-C-F הם האלכסונים המצטלבים.]
[תיקון קריאה 03.09 מול תמונת העמוד: G7 = גרף מלא על 4 קודקודים K4 (6 קשתות).]