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

מנהל: TA_Isana

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

הודעהעל ידי ohanonbar » 17:22 08/07/2010

אשמח לתשובות על השאלות:
1.מהו זמן הריצה של BFS כשאר גרף הקלט הוא מיוצג עי מטריצה והאלגוריתם מותאם לגרף כזה?
2.כתוב אלגוריתם יעיל הקובע האם גרף בילתי מכוון הוא דו צדדי.
תודה רבה
ohanonbar
 
הודעות: 12
הצטרף: 16:26 07/11/2009

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

הודעהעל ידי TA_Yoni » 10: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 בתאריך 15:17 10/07/2010, נערך פעם אחת בסך הכל.
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

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

הודעהעל ידי TA_Yoni » 14:53 10/07/2010

טעות\תיקון:
1. התייחסנו לגרף כאל רשימת שכנויות וכך אם לא מצוין אחרת מדובר ברשימת שכנויות. אנחנו בד"כ לא מתעסקים בייצוגים אחרים ולכן שאלת הייצוג אינה חשובה
2. התייחסתי לגרף כקשיר וזה לא מה ששאלת.
אם הגרף לא קשיר הבדיקה תעשה רק עבור כל זוג קדקדים שבאותו רכיב קשירות.
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

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

הודעהעל ידי ohanonbar » 17:05 10/07/2010

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


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים