Question

dfs
scc
spring_15_a

תזכורת: בור בגרף מכוון הוא צומת עם דרגת יציאה אפס. רכיב קשיר היטב (רק"ה) של גרף מכוון GG ייקרא מינימאלי אם הוא בור בגרף הרכיבים הקשירים היטב של GG.

א. הוכיחו/הפריכו: יהי GG גרף חסר מעגלים. בכל הרצה של DFS על GG, הצומת הראשון שנסוגים ממנו (כלומר, הצומת הראשון שמוצא מהמחסנית) הוא בור.

ב. הוכיחו/הפריכו בכל הרצה של DFS על גרף מכוון כלשהו GG, הצומת הראשון שנסוגים ממנו שייך לרק"ה מינימלי.

1

Answers

א. הטענה נכונה. אם צומת זה אינו בור אז יוצאת ממנו קשת. נשים לב שאם זוהי קשת קדמית או קשת חוצה אז היא מצביעה לצומת שכבר יצא מהמחסנית ולכן זו חייבת להיות קשת אחורית - סתירה.

ב. הטענה לא נכונה, למשל אם נריץ DFS מצומת 2 לצומת 3 לצומת 4 בגרף הבא:

tikz
1
Feedback