דף 1 מתוך 1

מבחן 2002 מועד ב'

נשלח: 23:51 25/06/2010
על ידי michal cohen
שאלה 3 סעיף שני.
למה זה O(v)? הרי זה צריך להיות כמו בDFS רגיל שבמקרה הגרוע מצאנו את המעגל רק בסוף. אז כאילו עברנו על כל הצלעות ועל כל הקדקודים... לא?

Re: מבחן 2002 מועד ב'

נשלח: 12:24 26/06/2010
על ידי בר כהן
לא ממש, האלגוריתם שלהם , בניגוד ל DFS רגיל, ייעצר כאשר הוא יגיע למעגל, כלומר הוא לכל היותר רץ קדימה V|| קודקודים ולכן גם על |V| צלעות.
תחשבי על זה ככה, על קוד קודקוד שהאלגוריתם נכנס אליו, הוא קופץ לקודקוד שכן (כלומר מעבר על צלע אחת) מבלי לבדוק בכלל את שאר השכנים (רקורסיה)
וידוע שיש מעגל, לכן בהכרח במהלך הדרך הוא יסגור מעגל

Re: מבחן 2002 מועד ב'

נשלח: 12:29 26/06/2010
על ידי michal cohen
אתה צודק, אבל מה אם יש כמה רכיבי קשירות?
ז"א אולי עברתי על אלף רכיבי קשירות שאין בהם מעגל ורק בסוף יש מעגל של שלוש צלעות שהוא אפסי לעומת כל שאר קדקודים שעברתי עליהם?

Re: מבחן 2002 מועד ב'

נשלח: 12:42 26/06/2010
על ידי בר כהן
אז? אם עברת על אלף רכיבי קשירות בלי מעגלים, אז עברת עד כה על 1-|V| צלעות לכל היותר בכל הרכיבים יחד.
תחשבי על זה רגע :)