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

[yuvalmadar]

לא מוכרת לי, תוכל לתת קישור?

(מדובר בתוכנה לציור גרפים או סתם תוכנת גרפיקה?)

 

[ברונסקי]

זה חלק מהאופיס של $M

יש בטח משהו גם ב-OpenOffice. יש תוכנה נחמדה שנקראת SmartDraw. ויש את Dia.

 

[ברונסקי]

בדיוק

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

 

[yuvalmadar]

באף אחד מהם אין צמתים כנדרש.. ../images/Emo12.gif

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

(אתה מנסה לפתור את השאלה כאשר השאלה מתייחסת לצמתים הנמצאים על כל מסלול קצר ביותר בין a לb, אבל בשאלה המקורית מדובר בכל מסלול בין a לb)

 

[ברונסקי]

אז קיבלנו שתי מנהרות באותו מחיר...

 

[yuvalmadar]

בהחלט ../images/Emo13.gif

 

[ron369]

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

מה הסיבוכיות שלו בכלל?

 

[ברונסקי]

לינארית

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

 

[yuvalmadar]

ואם יש מסלולים ארוכים יותר?

(אתה מסיר את הקשת שבה איתרת את המסלול בBFS?)

 

[yuvalmadar]

גם אני אשמח אם תפרט איך עשית

הכל.

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

 

[ברונסקי]

רק מסלולים בין a ל-b

אני מעוניין להסיר רק מסלולים בין a ל-b, שהם ארוכים מהמסלול הקצר ביותר ביניהם. למעשה, זה אפילו לא מצריך וריאציה על BFS. - מריצים BFS מ-a. עוברים על הקשתות (u,b). אם d > d z, אז מסירים את (u,b) מהגרף. - מריצים BFS מ-b. עוברים על הקשתות (a,u). אם d > d[a] z, אז מסירים את (a,u) מהגרף.

 

[ron369]

ואתה טוען שכך לא נשארים מלק"ב-ים?

(מסלול(-ים) לא קצר(-ים) ביותר

)

 

[ron369]

תמונה אחת שווה דוגמא נגדית אחת?

אבל אולי עדיף בלי תמונה (למרות שיש אחת מוכנה). תחשוב על: a-v1-v2-b ו: a-v1-v3-b..... ......./..\.......... ......v2........... כאשר במקרה הראשון אנחנו מדברים על כל המשקלים בקשתות הם 1, וכך גם בשני. נשים לב שבכל מקרה שני הגרפים נשארים גם אחרי הקיצוץ שלך. אבל! בראשון מדובר במספיק רכיבים קשירים, בעוד שבשני אין זה כך, וזאת למרות שברור שבשניהם כל המק"ב עוברים דרך שני קדקודים.

 

[yuvalmadar]

ב27 לחודש (חמישי הבא)

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

 

[yuvalmadar]

שאלה 24.1-8 (עץ פורש מינימלי)

נדמה היה לי שפתרתי את השאלה הזו בסמסטר הקודם, אבל אני לא מצליח לפתור אותה יותר.

"יהי T עפ"מ של G, ותהי L הרשימה הממוינת של משקלות הקשתות של T. הראה שעבור כל עפ"מ 'T אחר של G תתקבל אותה רשימת משקלות ממוינת." (שאלה 24.1-8 בספר של קורמן)

 

[yuvalmadar]

כדי שלא תחשבו...

שלא ניסיתי לפתור את השאלה לפי ששאלתי אתכם. (ואני סתם רוצה שתפתרו לי את השיעורים

) אציג פתרון שגוי שהגעתי אליו:

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

T-{v} T'-{v}​

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

 

[yuvalmadar]

* צומת שאינו צומת הפרדה = עלה

כתבתי בהתחלה עלה ובסוף תיקנתי לצומת שאינו צומת הפרדה, אבל במחשבה שנייה, בעץ הם היינו הך.

 

[yuvalmadar]

יותר מזה, החלק המצויין בכוכבית שגוי

למשל, עבור שרוך של 4 צמתים. (בגרף מלא בן 4 קודקודים בו כל הקשתות בעלות משקל 1, כל שרוך של 4 צמתים יהיה עפ"מ) ניתן לבחור כעפ"מ אחד את 1,2,3,4. (ואז 1,4 עלים) וכעפ"מ שני את 2,1,4,3. (ואז 2,3 עלים)

 

[gil levi]

המתרגלת פתרה את זה בתרגול.

נניח שרשימת המשקולות של T היא a1<=a2<=a3...<=ak ורשימת המשקולות של `T היא b1<=b2<=b3<=...<=bk. צ"ל ש ai=bi לכל i (אם הבנתי נכון). נניח שw היא פונ' המשקל. נסתמך על הטענה הבאה (שהוכחה בתרגול, אני יכול לכתוב את ההוכחה אם תרצה): תהי f היא פונ' מונוטונית עולה ממש מהממשיים לממשיים ונגדיר פונ' משקל חדשה w2 על ידי w2(e)=f(w(e) zzz אזי T הוא עפ"מ לפי w אמ"מ T הוא עפ"מ לפי w2. נחזור להוכחה הטענה: נניח בשלילה שקיים i כך ש ai!=bi ויהי i האינדקס המינימלי שעבורו זה מתקיים. בלי הגבלת הכלליות נניח ש ai>bi. נגדיר:

f(x) = x , x<=bi x+1, x>bi​

(f מוגדרת בהתלאה: אם x<=bi אז f(x)=x, אם x>bi אז f(x)=x+1) ). לא קשה להראות ש f עולה ממש. עכשיו צריך להראות שהמשקל של העצים T ו `T שונה לפי w2 שמוגדרת כמו בניסוח הטענה בפסקה השניה ואז אחד מהם הוא לא עפ"מ (כי הם המשקלים שונים אז אחד מהם גדול מהשני, אז הגדול מביניהם הוא לא עפ"מ). אני אשאיר זאת לך, אם תתקשה אשמח לעזור.

 

[yuvalmadar]

נפלא! תודה! ../images/Emo13.gif