Question

dfs
spring_18_a

גרף לא מכוון יקרא שרוכי אם לכל ריצת DFS (כלומר לכל בחירה של צומת התחלה וסדר סריקה של השכנים) עץ ה-DFS המתקבל הוא שרוך. תזכורת: גרף מכוון יקרא שרוך אם הוא עץ מכוון ויש לו עלה אחד, למשל:

tikz

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

1. שרוך

2. מעגל פשוט

3. גרף דו-צדדי מלא כך שאחד הצדדים בגודל kk ואחד הצדדים בגודל k+1k + 1, עבור kk כלשהו.

4. גרף דו צדדי מלא כך ששני הצדדים באותו הגודל.

5. שני מעגלים פשוטים בעלי צומת בודד משותף.

1

Answers

1. לא שרוכי, למשל עבור שרוך באורך 3 וריצת DFS מהצומת האמצעי נקבל את עץ ה-DFS הבא:

tikz

2. שורכי. נשים לב שבגלל סימטריה, עבור כל ריצת DFS נקבל שרוך.

3. לא שרוכי, למשל עבור k=1k = 1 וריצת DFS שמתחילה בצד הקטן נקבל שוב את עץ ה-DFS הבא:

tikz

4. שרוכי. שוב, מסימטריה אין חשיבות לסדר שבו סורקים את הצמתים ועבור כל ריצת DFS נקבל שרוך.

5. לא שרוכי. למשל עבור שני מעגלים בגודל 3 וריצת DFS מהצומת המשותף נקבל את עץ ה-DFS הבא:

tikz
1
Feedback