שאלות על : מיון טופולוגי, חיפוש רוחבי על רכיבי קשירות ומשפטים

שאלות על : מיון טופולוגי, חיפוש רוחבי על רכיבי קשירות ומשפטים

guy (guest) 15 Mar 2013 14:01

שלום,
כמה שאלות:

1. האם אפשר להשתמש במשפט ( למדנו בבדידה בעבר ) שאומר שסכום הדרגות בגרף הוא זוגי.

2. האם כאשר עושים BFS על גרף שמחולק למספר רכיבי קשירות, ומעוניינים לבצע את הBFS על כל הרכיבים ( על נציג מכל רכיב), הסיבוכיות עדיין נשמרת ?

אני נוטה להאמין שכן:

כיוון שלכל רכיב יש סיבוכיות לינארית לקשתות וצמתים, וסהכ סכום כל הצמתים וקשתות של הרכיבים זהה לסכום קשתות וצמתים של הגרף הכולל.
ואחרי שסיימנו רכיב, אפשר לעבור על רשימת הצמתים עד שמוצאים אחד לבן ולהמשיך ממנו.
מעבר על רשימה זו הוא תמיד קדימה ולכן לא חוזרים לאחור, ומעבר כזה הוא לינארי למספר הצמתים.
האם זה נכון? האם יש דרך יותר יעילה או פשוטה?

3. בתרגיל2 במצגת תרגול 3-

כשמבצעים על המיון הטופולוגי BFS מספר פעמים ( כל פעם מהנציג הבא ) מדוע אני יודע בוודאות שעוברים על כל צומת וקשת לכל היותר פעמיים?

(אני מבין שלא חוזרים אחורה, אבל מה מונע ממני שבהתקדמות קדימה לא יהיה מצב שגורם לחזרה על יותר מפעמיים?)

תודה רבה.

Re: שאלות על : מיון טופולוגי, חיפוש רוחבי על רכיבי קשירות ומשפטים

Shai V 16 Mar 2013 08:12

1. Yes
2. Yes. The proof of BFS still holds - BFS runs on each connected component in linear time - summing over the connected components gives us a total linear running time.
3. Actually, we can traverse each edge at most once (I will change the slides). Notice that we do a BFS only on the subgraph between the two consecutive relevant SCCs (strongly connected components). That is, on the example, you would think that the edge $f->g$ would appear when running a BFS from $a$, and also when running a BFS from $f$. But when running the BFS from $a$, when we traverse the edge $a->f$, we notice that the vertex we reached, $f$, is out of our range (because $f$ is after $d$, and right now we are only looking at the subgraph between $a$ and $d$). So we don't continue that part of the BFS.
This is exactly the reason it is important to topologically sort the graph and then run BFS between consecutive "relevant nodes" on the supergraph - to ensure we only traverse each edge once.