מסלולים בגרף לא מכוון

[yuvalmadar]

מסלולים בגרף לא מכוון

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

(אין לי סיבה אמיתית להאמין אחרת, אבל אני לא משוכנע שלא ניתן לעשות את זה בצורה מהירה יותר) תודה!

(אגב, יש סיכוי לא רע שאמלא את הפורום בשאלות בימים הקרובים

)

 

[vinney]

מועד ב'? יובל, אני מאוכזב.

לא קיבלת 100 במועד א'?

מה שעלה לי בראש (אני חושב שזה דומה לשלך, אבל לא כל כך הבנתי למה התכוונת

) 1. חפש מסלול קצר ביותר בין A לB, שים את כל הצמתים במסלול בקבוצה S, ותוריד מהגרף את כל הקשתות במסלול. 2. חזור על 1 (רק הפעם S תהיה החיתוך בין S הקודמת לבין קבוצת הצמתים במסלול הקצר ביותר הבא) עד שבS יהיה לא יותר מאיבר בודד או לא נמצא יותר אף מסלול בין A לB. 3. אם S בעלת איבר בודד או פחות - החזר "לא", אחרת החזר "כן". יוצא V*E, אאל"ט.

 

[yuvalmadar]

לא, לא 100 ../images/Emo8.gif

פישלתי קצת בבחינה הזו... הציון לא היה כל כך נורא (83) אבל אני די בטוח שאוכל לשפר אותו ל90+ (בתקווה, 95+

) אז לקחתי את הסיכון ונרשמתי למועד ב'.

ובנוגע לפתרון, כן. זה הפתרון שהתכוונתי אליו.

אקח את הערתך לתשומת ליבי ואפרט יותר את הפתרונות שלי בהמשך.

 

[yuvalmadar]

קבל תיקון, לא לזה התכוונתי ../images/Emo9.gif

קראתי ברפרוף כי הנחתי שהפתרון שלך זהה לשלי.

הרעיון שלי היה למצוא מסלול קצר ביותר:

(a,v1,v2,...,vn,b)​

ואז לבדוק לכל i האם הצומת v_i שייך לכל מסלול המחבר בין a,b. (ואיך לעשות את זה? להפעיל BFS על a בגרף {G-{v_i) וזמן הריצה של הפתרון הזה הוא ((O(V(V+E. (הרצת BFS שזמן ריצתו לינארי על כל צמתי המסלול - לכל היותר V צמתים) אבל נראה לי שניתן לכתוב באמת פתרון טוב יותר. (הפתרון של רון נראה מצוין, אבל ברונסקי ציין שזה בעייתי מעט כי אין רכיבים קשירים היטב בגרף לא מכוון. הבעיה היא שאת הפתרון של ברונסקי לא הבנתי

)

 

[ron369]

אני חושב שיש אלגוריתם מהיר יותר

דבר ראשון, ויני, נראה לי שמה שכתבת לא עובד. נניח שקיים צומת שנמצא על כל המסלולים. ולכן, בשלב השני של האלגוריתם שלך, הוא יוצא מן הגרף, ולכן לא יהיו יותר מסלולים (בכלל, וקצרים בפרט). בעיה, לא? דבר שני, אני חושב שיש אלגוריתם מהיר יותר. נשים לב שהדרישה הנ"ל שקולה לכך שקיימים שני צמתים, כך שהם "מחלקים" את הגרף לשני חלקים ללא קשתות ביניהם, כאשר אחד עם A, והשני עם B. כעת נשתמש בטכניקה מעצבנת ושטותית, שאני שונא מספיק כדי אוטומטית לנסותה ראשונה כמעט בכל תרגיל שאפילו דומה לנושא (וכך עליתי על כך בתרגיל זה, ככל הנראה)(או לפחות, ברוב גדול), של חלוקת הגרף לרכיבים קשירים היטב. כלומר, כעת, אם בין A ו-B מפרידים שני רכיבים קשירים היטב (והצמתים המחברים אותם) או יותר, התשובה היא אמת. אחרת שקר. אין מעגלים בגרף הרכיבים הקשירים היטב, ולכן זה די טריוויאלי לבדיקה, ע"י מק"ב. סיבוכיות זמן הריצה של האלגוריתם הגועלי הנ"ל היא O(V+E), אם אני לא טועה. ד"א, יובל, מתי המבחן? גם אני צריך להתכונן. כצפוי, גם אני עושה מועד ב' (והיא עוד וויתרה לי על הסעיף ההוא!)

 

[vinney]

לא הבנתי

אם צומת קיים בכל המסלולים, אז הוא ישאר בחיתוך, למה שיצא? לגבי ההצעה שלך, זה נראה לי נכון

 

[ron369]

זה בסדר, הוא יישאר בחיתוך, אבל אמרת

שגם: "ותוריד מהגרף את כל הקשתות במסלול", וזה כבר נשמע לי די בעייתי...

 

[vinney]

קשתות

לא צמתים

 

[vinney]

הא, הבנתי מה אתה אומר ../images/Emo13.gif

צודק

 

[ron369]

הממ, בטוח?

דווקא עמדתי לסוג (כי באמת חשבתי על צמתים ולא על קשתות, מסיבה כלשהי)

אבל אני מניח שבאמת יש דוגמא נגדית לכך...

 

[vinney]

כן

כי אם יש לך שני רכיבים קשירים היטב עם קשת אחת שמחברת בינהם, A באחד מהם, B בשני - אז יכול להיות יותר ממסלול אחד שיעבור בקשת הזאת, אבל במסלול הראשון - אוריד אותה ואז לא אמצא אף מסלול אחר.

 

[ברונסקי]

נראה שיש, אבל קצת אחרת

ראשית, מדובר על גרף לא מכוון, אז לא ניתן לדבר כאן על רכיבים קשירים היטב. במקום זה, אפשר להסתכל על גרף הרכיבים הדו-קשירים (שהוא בעצם עץ). בשלב ראשון, נמצא את אורך המסלול הקצר ביותר בין a ל-b. לאחר מכן, נוודא (באמצעות וריאציה של BFS) שאין בגרף מסלולים ארוכים יותר בין a ל-b. אם במהלך החיפוש מתגלה מסלול בין a ל-b, שהוא ארוך מהמסלול הקצר ביותר, ננתק את הקשת האחרונה שלו. נפעיל את התהליך על מסלולים בין a ל-b ובין בין b ל-a. בסיומו של התהליך, אם הדרגה של a ו-b היא 1, אז סיימנו. אחרת, צריך למצוא שני צמתי הפרדה בין a ו-b, כלומר מסלול באורך 2 בין הרכיב של a לרכיב של b בגרף הרכיבים הדו-קשירים.

 

[yuvalmadar]

אני לא חושב שהבנתי ../images/Emo9.gif

לא ממש הבנתי מה הייתה מטרת מציאת המסלול הקצר ביותר ביניהם וקיצוץ כל האחרים. אבל השורה האחרונה (בדיקת מספר צמתי ההפרדה במסלול היחיד בגרף הרכיבים הדו קשירים בין הרכיב של a והרכיב של b) נראית לי הגיונית ביותר.

למה היא לא מספיקה?

 

[ברונסקי]

אנסה שוב

[אני מודה שמה שכתבתי היה טיפה טלגרפי] מהתבוננות בגרף הרכיבים הלא-קשירים אפשר להסיק לגבי קיום קודקודים משותפים בין כל המסלולים, אבל פה נדרש להסתכל רק על המסלולים הקצרים ביותר בין a ל-b. נניח שאני מוסיף עוד

צמתים חדשים על שרשרת אחת בין a ל-b. זה לא ישנה את התשובה לשאלה, אבל ישבור את האלגוריתם, כי עכשיו a ו-b יהיו ברכיב דו-קשיר אחד והלך עלינו. לכן צריכים איכשהו לוודא שבין a ל-b ישארו רק המסלולים הקצרים ביותר כאשר אנחנו מתחילים להסתכל על גרף הרכיבים. בין לבין אפשר לקחת קיצור דרך קטן: אם הדרגה של a ו-b אחרי התספורת היא 1, אז הקדקודים המבוקשים אלה השכנים שלהם.

 

[yuvalmadar]

אני חושש שזה עדיין לא ברור לי

אתה משוכנע בנחיצות ה"תספורת"? אם כן, אשמח אם תתן לי דוגמא שבה האלגוריתם הבא לא יעבוד: 1. בנה מG גרף רכיבים דו-קשירים 2. מצא את הרכיבים הדו-קשירים של a ושל b. (נקרא להם V_a, V_b בהתאמה) 3. מצא את המרחק בין V_a לV_b בגרף הרכיבים הדו קשירים. אם מרחק זה 4 או יותר, החזר "קיימים" והחזר את שניים מצמתי ההפרדה שנמצאו במסלול בין שני הרכיבים הדו קשירים. אני חושב שזה מספיק תוך הנחת ההנחות הבאות על גרף הרכיבים הדו-קשירים (אני אומר "מניח הנחות" למקרה שהטעות שלי נובעת מכך שאני לא זוכר את החומר כמו שצריך, כי עברו חודשיים מאז שהתעסקתי איתו

): 1. גרף זה מורכב מרכיבים דו קשירים וצמתי הפרדה המפרידים ביניהם כך שבכל מסלול נמצאים רכיבים דו קשירים וצמתי הפרדה לסירוגין. (וכל צמת הפרדה שייך לכל הרכיבים הדו-קשירים הקשורים אליו) 2. גרף זה הוא עץ, כלומר בין כל שני צמתים עליו מחבר מסלול פשוט אחד ויחיד. (אם היה נוצר מעגל בגרף, היו כל הרכיבים הדו-קשירים שעליו רכיב דו-קשיר יחיד) לכן, משלב 3 באלגוריתם נסיק שהמסלול היחיד המחבר בין V_a וV_b בגרף הרכיבים הדו קשירים מכיל לפחות שני צמתי הפרדה, ולפי הגדרתם, הם מופיעים בכל מסלול המחבר בין שני צמתים ברכיבים דו-קשירים אלה, בפרט בין a לb. (ולהפך, אם לא היו שני צמתי הפרדה על המסלול, הרי שכל צמת שכן נמצא עליו ניתן "לעקוף" באמצעות מסלול חלופי ברכיב הדו-קשיר)

 

[yuvalmadar]

הערה נוספת

אם a וb יהיו באותו רכיב דו קשיר, אז המרחק בין V_a לV_b בגרף הרכיבים הדו-קשירים יהיה 0<4 כרצוי.

 

[ברונסקי]

דוגמה

a ו-b באותו רכיב דו-קשיר. האלגוריתם לא יבחין בין שני המקרים.

 

[yuvalmadar]

אבל אז לא יהיה מסלול פשוט...

באורך 2 (/4 אם אתה סופר את רכיבי הדו-קשירות ואת צמתי ההפרדה) בגרף הרכיבים הדו קשירים. המסלול הפשוט היחיד יהיה באורך 0.

 

[yuvalmadar]

אגב, עם איזה תוכנה ציירת את התמונה?

 

[ברונסקי]

visio