Algorithms Tirgul 2

Report
‫אלגוריתמים – תרגול ‪2‬‬
‫חידה‪:‬‬
‫האם אפשר לצבוע‬
‫את המפה בשלושה‬
‫צבעים כך שאף ‪2‬‬
‫מדינות סמוכות לא‬
‫יצבעו באותו צבע?‬
‫‪1‬‬
‫צביעת מפות – הקשר לגרפים‬
‫‪2‬‬
‫צביעת מפות – הקשר לגרפים‬
‫הבעיה שקיבלנו‪ :‬האם אפשר‬
‫לצבוע את קודקודי הגרף‬
‫בשלושה צבעים כך שאין‬
‫קשת בין שני קודקודים עם‬
‫אותו צבע?‬
‫‪3‬‬
‫גירסה פשוטה יותר‬
‫‪ ‬הבעיה הזו מסובכת מדי בשבילנו (אולי תפגשו אותה‬
‫בקורסים מתקדמים יותר)‪.‬‬
‫‪ ‬נעבור לגירסה יותר פשוטה – בהנתן גרף‪ ,‬אנו רוצים‬
‫לדעת האם ניתן לצבוע אותו בשני צבעים‪.‬‬
‫‪4‬‬
‫‪‬‬
‫גרף דו‪-‬צדדי ‪Bipartite Graph /‬‬
‫הגדרה‪ :‬גרף לא מכוון נקרא דו צדדי אם"ם אפשר‬
‫לצבוע את קודקודיו בשני צבעים‪ ,‬כך שאף קשת לא‬
‫מחברת בין שני קודקודים בעלי אותו צבע‪.‬‬
‫‪1‬‬
‫‪4‬‬
‫‪5‬‬
‫‪2‬‬
‫‪3‬‬
‫‪6‬‬
‫‪3‬‬
‫‪5‬‬
‫‪6‬‬
‫‪2‬‬
‫‪5‬‬
‫‪1‬‬
‫‪4‬‬
‫האם הגרף דו‪-‬צדדי?‬
‫‪6‬‬
‫האם הגרף דו‪-‬צדדי? תנאי הכרחי ומספיק‬
‫טענה‪ :‬גרף ) ‪ G  (V , E‬הינו דו‪-‬צדדי אמ"מ‬
‫הוא אינו מכיל מעגל באורך אי זוגי‪.‬‬
‫‪7‬‬
‫הוכחת הטענה – כיוון ראשון‬
‫‪ ‬נניח ש‪ G -‬הינו דו‪-‬צדדי ונראה שלא קיים בו מעגל‬
‫באורך אי‪-‬זוגי‪:‬‬
‫◦ כל קשת ב‪ G -‬עוברת מקבוצת קודקודים אחת לשניה‬
‫("מצד לצד")‪.‬‬
‫◦ כל מסלול שמתחיל ונגמר באותו צד – חייב להיות בעל‬
‫מס' קשתות זוגי‪.‬‬
‫◦ מעגל חייב להכיל מספר זוגי של קשתות‪.‬‬
‫‪8‬‬
‫הוכחת הטענה – כיוון שני‬
‫‪ ‬נניח שאין ב‪ G -‬מעגל באורך אי זוגי ונראה שהוא‬
‫דו‪-‬צדדי‪:‬‬
‫◦ אם הגרף אינו קשיר‪ ,‬מספיק להוכיח‬
‫את הטענה לכל רכיב קשירות בנפרד‪.‬‬
‫לכן‪ ,‬נניח שהגרף קשיר‪.‬‬
‫◦ נתאר אלג' שצובע את הגרף בשני‬
‫צבעים ונוכיח שהוא תמיד עובד‪.‬‬
‫‪9‬‬
‫אלגוריתם לצביעת קודקודים‬
‫‪ ‬נבחר קודקוד ‪ v‬באופן שרירותי ונריץ עליו ‪.BFS‬‬
‫‪ ‬את הקודקודים ברמות זוגיות בעץ ה‪ BFS-‬נצבע‬
‫בצהוב‪ ,‬ואת הקודקודים ברמות האי‪-‬זוגיות‬
‫בירוק‪.‬‬
‫‪1‬‬
‫‪3‬‬
‫‪2‬‬
‫‪1‬‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪6‬‬
‫‪10‬‬
‫‪6‬‬
‫‪5‬‬
‫‪4‬‬
‫הוכחת הטענה – נכונות האלגוריתם‬
‫‪ ‬נראה שאין קשת בין שני קודקודים בעלי אותו צבע‪:‬‬
‫◦ כל קשת בגרף מחברת בין קודקודים ברמות עוקבות של העץ‬
‫או בין קודקודים מאותה רמה‪.‬‬
‫◦ קשת בין שתי רמות עוקבות תמיד תכיל קודקוד אחד צהוב‬
‫וקודקוד אחד ירוק‪.‬‬
‫◦ נותר להראות שלא קיימות קשתות המחברות בין קודקודים‬
‫באותה רמה‪.‬‬
‫‪11‬‬
‫הוכחת הטענה – נכונות האלגוריתם‬
‫‪ ‬נניח שקיימת קשת המחברת בין הקודקודים ‪ u‬ו‪ v -‬אשר‬
‫נמצאים באותה רמה בעץ‪.‬‬
‫‪ ‬יהי ‪ w‬ה‪ lowest common ancestor -‬של ‪ u‬ו‪. v-‬‬
‫‪w‬‬
‫‪u‬‬
‫‪12‬‬
‫‪v‬‬
‫הוכחת הטענה – נכונות האלגוריתם‬
‫‪ ‬נסמן ב‪ p -‬את המסלול בין ‪ u‬ל‪ w-‬בעץ‪ ,‬ונסמן את אורך‬
‫המסלול ב‪. k -‬‬
‫‪ ‬באופן דומה‪ ,‬נסמן ב‪ q -‬את המסלול בין ‪ v‬ל‪ w -‬בעץ‪,‬‬
‫ונשים לב שאורכו אף הוא ‪.k‬‬
‫‪ ‬הקשת ) ‪ (v, u‬יוצרת מעגל באורך ‪2k  1‬‬
‫יחד עם ‪ p‬ו‪q -‬‬
‫!‬
‫סתירה‬
‫‪.‬‬
‫‪w‬‬
‫לכן לא תיתכן קשת בין שני קודקודים‬
‫באותה רמה‪.‬‬
‫‪13‬‬
‫‪u‬‬
‫‪v‬‬
‫שאלה ‪ - 2‬גרף המסלולים הקצרים ביותר‬
‫‪ ‬הגדרה‪ :‬עבור גרף ) ‪ G  (V , E‬וזוג קודקודים ‪, s, t  V‬‬
‫מסלול קצר ביותר מ‪ s -‬ל‪ t -‬הינו מסלול אשר מכיל מספר‬
‫קשתות מינימאלי מבין כל המסלולים מ‪ s -‬ל‪( t -‬יכולים להיות‬
‫כמה כאלו)‪.‬‬
‫‪ ‬גרף המסלולים הקצרים ביותר מ‪ s -‬הינו הגרף ) ' ‪G'  (V , E‬‬
‫כך ש‪-‬‬
‫‪E'  e  E : e is part of a shortestpathfroms‬‬
‫‪14‬‬
‫שאלה ‪ - 2‬גרף המסלולים הקצרים ביותר‬
‫‪ ‬תרגיל‪ :‬נתון גרף לא מכוון ) ‪ G  (V , E‬וקודקוד ‪.s V‬‬
‫תארו אלג' המחשב את גרף המסלולים הקצרים ביותר‬
‫מ‪ s -‬בזמן ‪.OV  E ‬‬
‫‪s‬‬
‫‪ ‬דוגמא‪:‬‬
‫‪c‬‬
‫‪d‬‬
‫‪c‬‬
‫‪a‬‬
‫‪s‬‬
‫‪b‬‬
‫‪b‬‬
‫‪d‬‬
‫‪15‬‬
‫‪f‬‬
‫‪e‬‬
‫‪a‬‬
‫‪e‬‬
‫‪f‬‬
‫פתרון פשוט (שנכשל)‬
‫‪ ‬נריץ ‪ BFS‬מ‪.s -‬‬
‫‪ ‬נקבל עץ אשר מכיל מסלול קצר ביותר מ‪ s -‬לכל קודקוד‬
‫‪.v V‬‬
‫‪ ‬אך ייתכנו מסלולים קצרים ביותר שאינם מוכלים בעץ זה!‬
‫‪s‬‬
‫‪s‬‬
‫‪b‬‬
‫‪a‬‬
‫‪c‬‬
‫‪16‬‬
‫‪b‬‬
‫‪a‬‬
‫‪c‬‬
‫שיפור הפתרון‬
‫‪ ‬כאשר אנו מריצים אלג' ‪ ,BFS‬אנו זורקים שני‬
‫סוגים של קשתות מהגרף‪:‬‬
‫◦ קשתות בין קודקודים באותה הרמה‪.‬‬
‫◦ קשתות בין קודקודים ברמות עוקבות‪.‬‬
‫‪17‬‬
‫‪s‬‬
‫שיפור הפתרון‬
‫‪ ‬נריץ ‪ BFS‬עם שינוי‪:‬‬
‫‪ ‬נזרוק מהגרף רק קשתות בין קודקודים באותה‬
‫)‪.‬‬
‫הקשתות‬
‫שאר‬
‫כל‬
‫את‬
‫ונשאיר‬
‫(‬
‫הרמה‬
‫‪s‬‬
‫‪s‬‬
‫‪18‬‬
‫הוכחת נכונות‬
‫‪ ‬קשת ‪ e‬בין קודקוד ‪ v‬ברמה ‪ i  1‬לבין קודקוד ‪u‬‬
‫ברמה ‪ i‬תמיד נמצאת במסלול קצר ביותר אל ‪.u‬‬
‫◦ אורך המסלול הקצר ביותר בין ‪ s‬לבין ‪ u‬הינו ‪.i‬‬
‫◦ קיים מסלול באורך ‪ i  1‬בין ‪ s‬לבין ‪.v‬‬
‫◦ אם נוסיף את הקשת ) ‪ (v, u‬למסלול‪ ,‬נקבל‬
‫מסלול באורך ‪ i‬בין ‪ s‬לבין ‪u‬‬
‫(כלומר‪ ,‬מסלול קצר ביותר)‪.‬‬
‫‪ ‬באותו אופן קל להראות שקשת בין‬
‫קודקודים באותה הרמה היא לא חלק‬
‫ממסלול קצר ביותר (תרגיל)‪.‬‬
‫‪19‬‬
‫‪u‬‬
‫‪s‬‬
‫‪v‬‬
‫שאלה ‪ - 3‬המסלולים הקצרים מ‪ s-‬אל ‪t‬‬
‫‪ ‬הגדרה‪ :‬עבור גרף ) ‪ G  (V , E‬וזוג קודקודים ‪, s, t  V‬‬
‫גרף המסלולים הקצרים ביותר מ‪ s -‬ל‪ t -‬הינו הגרף‬
‫) ' ‪ , G'  (V , E‬כך ש‪-‬‬
‫‪E'  e  E : e is part of a shortestpathfroms tot‬‬
‫‪t‬‬
‫‪20‬‬
‫‪s‬‬
‫שאלה ‪ - 3‬המסלולים הקצרים מ‪ s-‬אל ‪t‬‬
‫‪ ‬תרגיל‪ :‬נתון גרף מכוון ) ‪ G  (V , E‬וזוג קודקודים ‪.s, t V‬‬
‫תארו אלג' המחשב את גרף המסלולים הקצרים ביותר מ‪s -‬‬
‫ל‪ t -‬בזמן ‪.OV  E ‬‬
‫‪21‬‬
‫‪ BFS‬על גרף מכוון‬
‫‪ ‬כאשר אנו מריצים אלג' ‪ BFS‬על גרף מכוון‪ ,‬אנו‬
‫זורקים שלושה סוגים של קשתות מהגרף‪:‬‬
‫◦ קשתות בין קודקודים באותה הרמה‪.‬‬
‫◦ קשתות בין קודקודים ברמות עוקבות‪.‬‬
‫◦ קשתות מקודקוד ברמה ‪ i‬אל קודקוד‬
‫ברמה ‪.i  j‬‬
‫‪22‬‬
‫‪s‬‬
‫פתרון‬
‫‪ ‬נשנה את אלג' ה‪:BFS-‬‬
‫◦ האלג' החדש לא יזרוק קשתות היוצאות מקודקוד ברמה ‪i  1‬‬
‫אל קודקוד ברמה ‪.i‬‬
‫‪s‬‬
‫‪ ‬נקבל גרף שמכיל את כל‬
‫המסלולים הקצרים ביותר‪,‬‬
‫אך מכיל גם קשתות מיותרות‪.‬‬
‫‪23‬‬
‫‪t‬‬
‫פתרון‬
‫‪ ‬נוסיף עוד שלב בסוף האלג'‪:‬‬
‫◦ נהפוך את הכיוון של כל קשתות הגרף שקיבלנו‪.‬‬
‫‪s‬‬
‫‪s‬‬
‫‪24‬‬
‫‪t‬‬
‫‪t‬‬
‫פתרון‬
‫‪ ‬נוסיף עוד שלב בסוף האלג'‪:‬‬
‫◦ נהפוך את הכיוון של כל קשתות הגרף שקיבלנו‪.‬‬
‫◦ נריץ אלג' ‪ BFS‬מ‪ . t -‬נשתמש שוב בגרסה של האלג'‬
‫‪s‬‬
‫שאינה זורקת קשתות בין רמות עוקבות‪.‬‬
‫◦ כל מסלול מ‪ s -‬ל‪ t -‬הופך למסלול‬
‫מ‪ t -‬ל‪ . s -‬מכיוון שכל המסלולים נכנסים‬
‫ל‪ , s -‬וכעת אנחנו מסתכלים רק על‬
‫מסלולים שיוצאים מ‪ , t -‬נקבל בדיוק את‬
‫כל המסלולים מ‪ t -‬ל‪ s -‬בגרף ה"הפוך"‪.‬‬
‫‪25‬‬
‫‪t‬‬
‫פתרון‬
‫◦ נהפוך בחזרה את הכיוון של כל הקשתות בגרף שקיבלנו‪ .‬גרף זה‬
‫יהיה גרף המסלולים הקצרים ביותר מ‪ s -‬ל‪. t -‬‬
‫‪s‬‬
‫‪t‬‬
‫‪26‬‬
‫‪t‬‬
‫סיבוכיות‬
‫‪ ‬הרצת ‪ BFS‬משופר פעמיים‪.OV  E  :‬‬
‫‪ ‬הפיכת כיוון קשתות (פעמיים )‪.O E  :‬‬
‫‪ ‬סה"כ‪.OV  E  :‬‬
‫‪s‬‬
‫‪t‬‬
‫‪27‬‬

similar documents