שלום,
בהצראה על אלגו' DFS ניתנה הלמה הבאה (למה 3.2):
"גרף מכוון G הוא חסר מעגלים אם"ם חיפוש DFS על G אינו יוצר קשתות אחוריות?"
למה הכוונה ה"אלגו' אינו יוצר"? אלגו' DFS מחזיר זמני פתיחה וסגירה של צמתים.
האם הכוונה ב"האלגו' אינו יוצר" היא "האלגוריתם אינו נתקל* בעת הריצה בקשת אשר הקודקוד בקצה השני של קשת זו הוא אפור (בעת המעבר על הקשת)"?
שמתי כוכבית על המילה "נתקל". ב"נתקל" אתם מתכוונים לשורות 4-5 באלגו'? הדגשתי את השורות הרלוונטיות.
DFS-VISIT(G,u)
1. time <- time+1
d(u) <- time
color(u) <- gray
foreach v in Adj(u):
if color(v) = white
pi(v) <- u
DFS-VISIT(G,v)
color(u) <- black
time <- time+1
f(u) <- time