אלגוריתמים - DFS וגרפים
אני מתכונן למבחן באלגוריתמים ונתקלתי בשאלה שאותה אני לא מצליח לפתור כבר כמה ימים: (הz ים נועדו ליישר את הכתב) יהיה G=(V,E) z גרף קשיר ולא מכוון. G שרוכי אמ"מ בכל ריצה של DFS (מכל צומת ב V), העץ המתקבל הוא מסלול פשוט המתחיל בצומת (משהו כזה: v->a1->a2->a3.... ) G שפיר אמ"מ בכל ריצת DFS שבה מחושבים ערכי L[v] z הכוונה ל Lowpoints ואם מישהו מכיר בשם אחר אז הכוונה לזמן הגילוי הקטן ביותר של הצומת שניתן להגיע אליו מ v ע"י ירידה ב 0 או יותר קשתות קדימה, ושימוש בקשת אחורה, או ע"י השארות במקום. צריך להראות G שפיר אמ"מ - G שרוכי. אשמח לקבל כיוון או פתרון. תודה!
אני מתכונן למבחן באלגוריתמים ונתקלתי בשאלה שאותה אני לא מצליח לפתור כבר כמה ימים: (הz ים נועדו ליישר את הכתב) יהיה G=(V,E) z גרף קשיר ולא מכוון. G שרוכי אמ"מ בכל ריצה של DFS (מכל צומת ב V), העץ המתקבל הוא מסלול פשוט המתחיל בצומת (משהו כזה: v->a1->a2->a3.... ) G שפיר אמ"מ בכל ריצת DFS שבה מחושבים ערכי L[v] z הכוונה ל Lowpoints ואם מישהו מכיר בשם אחר אז הכוונה לזמן הגילוי הקטן ביותר של הצומת שניתן להגיע אליו מ v ע"י ירידה ב 0 או יותר קשתות קדימה, ושימוש בקשת אחורה, או ע"י השארות במקום. צריך להראות G שפיר אמ"מ - G שרוכי. אשמח לקבל כיוון או פתרון. תודה!
