שאלה על גרפים

[white shadow 3]

שאלה על גרפים

יש את האלגוריתם למציאת מסלולים זוגיים קצרים על גרף לא מכוון ע"י יצירת גרף G' דו צדדי והרצת BFS.

איך ניתן ליישם את הגרף G' על גרף G שהוא מכוון? איך יראו הקשתות בגרף G' הזה?
(נגיד, לדוגמא, בגרף G יש קשת מכוונת בין צומת 1 לצומת 2, ומכוונת בין צומת 1 לצומת 3, ומכוונת בין צומת 3 לצומת 2, אבל כשאני מנסה להעביר את זה לגרף G' אז יש קשת בין
1a לבין 2b, ובין 1a לבין 3b, ובין 3a ל-2b אבל אז כיבול אם אני מתחיל ב-1a וממתקדם ל-2b אז כביכול יש מעבר ל-3a, אלא אם תהיה שם איזשהיא הגדרה שמתנע את המעבר הזה)

תודה!

 

[EyesToSee]

השאלה ממש ברורה והתאור שלה מצוין,אבל...

אם לא קשה לך, אפשר לקבל תאור גרפי(ציורי) ולחזור על השאלה שוב,הפעם בעברית?

 

[white shadow 3]

הי.

האלגוריתם הראשון שתואר מתייחס לפתרון בעיה "בהינתן גרף לא מכוון, יהיה s קודקוד (s belongs to V). יש למצוא לכל v belongs to V את המרחק הזוגי הקצר ביותר שלו מ-s"
אז הפתרון היה לבנות גרף G' דו צדדי מ-G המקורי (שכפול הצמתים והעברת קשתות בין שני הצדדים עבור כל קשת שנמצאת בגרךף המקורי G) (תמונה א')
המשך הפתרון הוא שמריצים BFS על הגרף החל מצומת המקור הנתונה (נניח בתמונה [1]1 ומחזירים לכל צומת v את שדה ה-d שלה.

עכשיו נשאלת שאלה דומה - רק הפעם נתון גרף G מכוון ונתונים שני צמתים u,v כך שצריך למצוא את המרחק הזוגי הקצר ביותר בינן (אם קיים, או "אינסוף" אם לא).
חשבתי להפעיל צורת פתרון דומה לזו המתוארת למעלה (ע"י בניית גרף עזר דו צדדי) אבל קצת נתקעתי עם אופן בניית הגרף G' כך שאכן יתאר את הגרף המכוון G.

 

[Javali]

עושים גרף דו צדדי מכוון

ואז יש מ-1a ל-2b ומ-3a ל-2b אבל אין מ-2b ל-3a.

 

[white shadow 3]

הבנתי, תודה

ושאלה קטנה נוספת -
הראו לנו הוכחה שאומרת: יהיה G גרף לא מכוון ויהיה s שייך ל-V.
אזי "המרחק הזוגי בין s ל-u בגרף G שווה למרחק בין s0 ל-u0 בגרף G' הדו-צדדי"
&nbsp
ההוכחה/נכונות של זה תקפה רק למקרה שבו G לא מכוון (כי הם ציינו את זה בניסוח של המשפט" או שזה נכון גם לגרף מכוון?
כי למיטב הבנתי זה אמור להיות נכון גם בגרף מכוון כי אם קיים מסלול כזה ב-G אז הוא יבוא לידי ביטוי גם ב-G' והפוך, אם קיים ב-G' אז הוא צריך להיות קיים גם ב-G
&nbsp

 

[white shadow 3]

help...(שאלת המשך לשאלה הקודמת)

הראו לנו הוכחה שאומרת: יהיה G גרף לא מכוון ויהיה s שייך ל-V.
אזי "המרחק הזוגי בין s ל-u בגרף G שווה למרחק בין s0 ל-u0 בגרף G' הדו-צדדי"
ההוכחה/נכונות של זה תקפה רק למקרה שבו G לא מכוון (כי הם ציינו את זה בניסוח של המשפט" או שזה נכון גם לגרף מכוון?
כי למיטב הבנתי זה אמור להיות נכון גם בגרף מכוון כי אם קיים מסלול כזה ב-G אז הוא יבוא לידי ביטוי גם ב-G' והפוך, אם קיים ב-G' אז הוא צריך להיות קיים גם ב-G
&nbsp
תודה!