שאלה למי שיודע

מנהל: TA_Isana

שלח תגובה
ohanonbar
הודעות: 12
הצטרף: 16:26 07/11/2009

שאלה למי שיודע

שליחה על ידי ohanonbar » 18:22 08/07/2010

אשמח לתשובות על השאלות:
1.מהו זמן הריצה של BFS כשאר גרף הקלט הוא מיוצג עי מטריצה והאלגוריתם מותאם לגרף כזה?
2.כתוב אלגוריתם יעיל הקובע האם גרף בילתי מכוון הוא דו צדדי.
תודה רבה

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: שאלה למי שיודע

שליחה על ידי TA_Yoni » 11:50 10/07/2010

1. כשמדברים על BFS אנו מניחים כי הייצוג הוא ברשימת שכנויות ולכן זמן הריצה יהיה (O(E+V . על מטריצה לא דברנו אך הזמן ריצה יכול להיות V^2.
 2. יש לבצע סריקת BFS על הגרף. אם נגלה קשת מקודקוד u לקודקוד v כך ש [d[v] = d[u, אז הגרף הוא לא דו צדדי. אחרת הגרף הוא דו צדדי והחלוקה המתאימה תתקבל לפי הזוגיות של הרמות (= שדה ה d )
קודקודים ברמה זוגית יהיו בקבוצה הראשונה וקודקודים ברמה אי זוגית יהיו בקבוצה השניה.

למה זה נכון?
מכיוון שהגרף קשיר , ניתן להגיע מכל קודקוד לכל קודקוד. כדי לקבל גרף דו חלקי צריך לחלק את הקודקודים לשתי קבוצות V ו U כך שהצלעות של הגרף הן מקודקודים u שב U לקודקודים v שב V. לכן אם סורקים את הגרף לפי שכבות מקודקוד מסויים s ונניח כי s ב U , כל הקודקודים בשכבה הראשונה חייבים להיות ב V , לאחר מכן כל הקודקודים בשכבה השנייה חייבים להיות ב V , לאחר מכן כל הקודקודים בשכבה השלישית חייבים להיות ב U וכן הלאה.... אם יש צלע בין קודקודים באותה שכבה ברור כי הגרף אינו דו-צדדי.
נערך לאחרונה על ידי TA_Yoni ב 16:17 10/07/2010, נערך פעם 1 בסך הכל.
המתרגל יוני

TA_Yoni
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: שאלה למי שיודע

שליחה על ידי TA_Yoni » 15:53 10/07/2010

טעות\תיקון:
1. התייחסנו לגרף כאל רשימת שכנויות וכך אם לא מצוין אחרת מדובר ברשימת שכנויות. אנחנו בד"כ לא מתעסקים בייצוגים אחרים ולכן שאלת הייצוג אינה חשובה
2. התייחסתי לגרף כקשיר וזה לא מה ששאלת.
אם הגרף לא קשיר הבדיקה תעשה רק עבור כל זוג קדקדים שבאותו רכיב קשירות.
המתרגל יוני

ohanonbar
הודעות: 12
הצטרף: 16:26 07/11/2009

Re: שאלה למי שיודע

שליחה על ידי ohanonbar » 18:05 10/07/2010

תודה יוני

שלח תגובה

חזור אל “- מבני נתונים 2010”