על ידי 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, נערך פעם אחת בסך הכל.
המתרגל יוני