Question

dfs

גרף מכוון יקרא טורניר אם לכל שני צמתים u,vVu,v \in V קיימת בדיוק אחת משתי הקשתות (u,v)(u,v) או (v,u)(v,u) (אם הצמתים בגרף מייצגים שחקנים וכל שני שחקנים שיחקו בניהם בדיוק פעם אחת אז הקשתות מסמלות איזה שחקן ניצח בכל משחק).

צומת uu הוא שורש בגרף אם לכל vVv \in V קיים מסלול מכוון מ-uu ל-vv.

  1. הוכיחו: בכל טורניר קיים שורש.
  2. הציעו אלגוריתם המוצא שורש של טורניר בזמן O(E+V)O(|E| + |V|).
1

Answers

1. נסתכל צומת, uu, שמספר הצמתים שישיגים ממנו מקסימלי. אם uu אינו שורש אז קיים צומת שאינו ישיג ממנו, vv. מכיוון שזהו טורניר אז הקשת vuvu נמצאת בגרף - סתירה (כל הצמתים שישיגים מ-uu ישיגים גם מ-vv ובנוסף uu ישיג מ-vv).

2. כזכור, העץ שהתגלה אחרון ביער ה-DFS מכיל את כל שורשי הגרף. מכיוון שקיים שורש בגרף, שורש העץ האחרון הוא שורש של הגרף. אלגוריתם לינארי, אם כן, הרץ DFS והחזר את שורש העץ האחרון שהתגלה.

1
Feedback