Proof of claim from recitation (group 12)
I didn't have enough time to prove this claim, but you need it for the exercise, so here it is.
Note: If Hebrew text and math seem garbled, you must be using a faulty web browser. Please use a standards compliant browser instead (e.g., Firefox, Safari, Chrome).
טענה: גרף לא מכוון וקשיר ניתן לכיוון לגרף קשיר בחוזקה אמ"מ אין בו גשרים.
הוכחה:
- תהי $(u,v)$ קשת, ונניח שכיוונו אותה $u\to v$. מכיוון שקיבלנו גרף קשיר בחוזקה, יש גם מסלול $v\leadsto u$ ולכן $(u,v)$ נמצאת על מעגל בגרף ומכאן שאינה גשר.
- נריץ DFS מצומת שרירותי $s$ ונכוון קשתות עץ מהורה לבן וקשתות אחוריות מצאצא לאב קדמון. די להראות שלכל צומת $v\in V$ יש מסלולים מכוונים $s\leadsto v, v\leadsto s$, ולכן לכל זוג צמתים $u,v\in V$ קיים מסלול $u\leadsto s\leadsto v$ ולהיפך.
המסלול $s\leadsto v$ משתמש רק בקשתות עץ ה-DFS, בו $s$ שורש. קיומו של מסלול הפוך נוכיח באינדוקציה על עומק $v$ בעץ ה-DFS. אם $v=s$ כמובן סיימנו; אחרת, יהי $u$ ההורה של $v$ בעץ ה-DFS. הקשת $(u,v)$ אינה גשר (לפי ההנחה) ולכן נמצאת על מעגל (לפי טענה קודמת). כלומר, קיימת קשת אחורית מ-$v$ או צאצא שלו ל-$u$ או אב קדמון שלו, שנקרא לו $w$. הצומת $w$ עמוק פחות מ-$v$ ולכן מהנחת האינדוקציה יש מסלול $w\leadsto s$, שבצירוף המסלול $v\leadsto w$ ייתן את המבוקש.