שאלות באלגוריתמים על גרפים.

[gil levi]

שאלות באלגוריתמים על גרפים.

פיצלתי את השאלות למספר הודעות כדי שיהיה יותר נוח.

 

[gil levi]

שאלה 1.

הוכיח שאם בגרף לא מכוון וקשיר יש בדיוק 2K קודקודים מדרגה אי זוגית אז ניתן לחלק את קשתותי לK מסלולים זרים (זרים בקשתות). בכיתה הוכחנו שגרף לא מכוון וקשיר שבו יש בדיוק 2 קודקודים מדרגה אי זוגית מכיל מסלול אוילר (מסלול העובר על כל קשת פעם אחת בלבד). ניסיתי להשתמש בטענה באופן הבא: "נבחר באקראי שני קודקודים מדרגה ותסתכל על הגרף בלי שאר הקודקודים מדרגה אי זוגית, לפי הטענה יש ביניהם מסלול אוילר...נמשיך באותו אופן עד שנקבל 2K מסלולים....", אבל זה לא נכון כי אם מסתכלים על הגרף בלי שאר הקודקודים מדרגה אי זוגית אז ייתכן שהוא לא קשיר. בגלל שאין לי שום קריטריון לבחור את הקודקודים המתאימים בכל פעם (אם בכלל יש כזה) אז אין לי שום דרך להמשיך בכיוון זה. מישהו יכול לתת לי רמז/הכוונה/הדרכה? תודה מראש.

 

[ron369]

רמז: אולי עדיף אינדוקציה (ספויילר)

פתרון, אולי: (*ספוווילר) עבור 1 אנחנו יודעים, אפשר. עבור n>1 נבחר שני קדקודים מסרגה אי-זוגית שיש ביניהם מסלול (ובהכרח קיימים כאלו, כי אם לא, זוהי סתירה לכך שבכל תת-גרף קשיר עם קדקוד אי-זוגי מספר הקשתות שווה לפעמיים |E| בתת הגרף לפי למת לחיצת הידיים (כי אז יש לנו קודקוד אחד עם דרגה אי זוגית, ולכן אם גם אין קדקוד אחר עם דרגה אי-זוגית, נקבל שהסכום הוא אי זוגי, כשהוא צריך להיות זוגי)(פשוט מחשבים את המשוואה, אם בא לך, וזה יוצא טוב)), נעיף את הקשתות מהמסלול מהגרף. ועכשיו יש לנו בעצם 2n-2 קדקודים מדרגה אי זוגית, כאשר כל השאר מדרגה זוגית. *CTRL-S*. אני היחיד שנוטה לעשות את זה, או כמעט לעשות את זה, לעתים רבות, בסוף כתיבת הודעות?

 

[gil levi]

תודה על הרמזים.

(גם לשאלה השניה). אני אעבור על זה רק מחר (בתקווה). גם לי יוצא לפעמים ללחוץ CTRL-S כשאני כותב הודעה. חבל שבאמת אין כזאת אופציה.

 

[gil levi]

שאלה 2.

נתון גרף מכוון G=(V,E)zzz. תארו אלגוריתם שרץ בזמן O(

*|E|)zzz ומוצא מעגל מכוון קצר ביותר אם קיים בG. ניסיתי את הכיוון הבא: ניקח קודקוד אקראי u. נבנה גרף חדש G_u באופן הבא: נעתיק לגרף החדש את u וכל קשת שיוצאת ממנו או נכנסת אליו. נסמן את u ב0 וכל קודקוד שממנו יוצאת קשת הנכנסת לu נסמן ב 1- וכל קודקוד שאליו נכנסת קשת שיוצאת מu נסמן ב1. אם נרצה לסמן קודקוד במספר חיובי אחרי שהוא כבר סומן במספר שלילי אז מצאנו מעגל. יהי v קודקוד שממנו יוצאת קשת הנכנסת לu. עבור v נעתיק כל קשת הנכנסת אליו רק שהפעם נעתיק רק קשתות שלא נמצאות בגרף ("באג", לבדוק לוקח יותר מדי זמן) ונסמן ב2 את הקודקודים ה"חדשים" (כמו מקודם). יהי w קודקוד שאליו נכנסת קשת היוצאת מu. עבור w נעתיק כל קשת היוצאת ממנו רק שהפעם נעתיק רק קשתות שלא נמצאות בגרף (שוב, אותו "באג") ונסמן ב2- את הקודקודים ה"חדשים". אם נרצה לסמן קודקוד במספר חיובי אחרי שהוא כבר סומן במספר שלילי אז מצאנו מעגל. (המספור אמור לסייע בבדיקת האורך שלו, לא ממש בדקתי אם זה באמת עוזר כי בגלל ה"באג" שמצאתי האלגוריתם ממילא לא טוב). נמשיך באותו אופן בבניית G_u ואח"כ נבנה גרפים לכל הקודקודים בG. במבט לאחור די ברור שהכיוון מוטעה כי זה בעצם נסיון למצוא את כל המעגלים בגרף (ועלול להיות מספר אקספוננציאלי של מעגלים). רעיון אחר להשתמש באלגוריתם אחר למציאת כל הקשתות שנמצאות על מעגלים שאורכם קטן מK (על ידי BFS מכל קודקוד, קשת (u,v) נמצאת על מעגל באורך <=K אמ"מ המרחק מv לu קטן מK), אבל הרעיון הטריוויאלי (להריץ עבור K=1 ואח"כ K=2 וכן הלאה) רץ בזמן ארוך מדי. מישהו יכול לתת לי רמז/הדרכה? תודה מראש.

 

[ron369]

מנסה את מזלי

רמז: אם יש לך O(V*E) בתור חסם עליון, זה אומר שאתה יכול להריץ BFS מכל קודקוד, נכון? (אם V>E נעיף את הקדקודים ללא קשתות). *ספווילר, אולי, בהמשך* פתרון, אולי: מה שאומר, בעצם, שיש לך את המרחק בין כל זוג קדקודים בכל אחד משני הכיוונים. ועכשיו, בהנחה ש E>V, נוכל פשוט לחשב את המרחק הקצר ביותר של "ללכת מקודקוד אחד לשני", ושל "לחזור את הדרך בחזרה" (הרי כבר חישבנו את המידע הזה). אז, יש לנו מערך אנקי של V^2 ערכים, והקטן מכולם, הוא התשובה. וכן, אני יודע שזה פתרון מסריח לחלוטין (למרות שעל המערך בשלב האחרון אפשר לוותר). סליחה.

 

[gil levi]

שאלה 3.

תארו אלגוריתם שמחליט בזמן O(

)zzz האם בגרף לא מכוון G=(V,E) zzz יש מעגל. פה פשוט אין לי מושג. הוצאתי מראש BFS, DFS כי זמן הריצה שלהם גבוה מדי. מישהו יכול לתת לי רמז/הדרכה? תודה מראש.

 

[ron369]

חכה שניה, אתה בטוח?!

O(V)? לא O(E V)?

 

[gil levi]

נראה לי שכן.

 

[yuvalmadar]

תזכור שאם E>V, יש מעגל אוטומטית.../images/Emo13.gif

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

 

[ron369]

כן, גם אתה, נכון? (יאללה, תתחבר../images/Emo3.gif)

(אני רוצה חידות

) (צודק

)

 

[ron369]

אה, בכלל לא שאלת אותי ../images/Emo13.gif

סליחה

 

[gil levi]

לא,

אני לוקח את הקורס עכשיו. אני בכלל לומד באת"א אגב. תודה על הרמז ובהצלחה בבחינה.

 

[yuvalmadar]

תודה! ../images/Emo13.gif

 

[gil levi]

תפוז מעצבן. ../images/Emo127.gif זה הגודל של V.

 

[ron369]

נו, אין עוד שאלות?

אני צריך להתכונן למבחן, ואשמח לעוד כמה.

 

[yuvalmadar]

בוודאי שיש! ../images/Emo13.gif (רשתות זרימה)

השאלה הזו הייתה במבחן שלי, ולא הצלחתי לפתור את סעיף ב' שלה.

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

) אז, אשמח מאד אם תעזרו לי לפתור את השאלה!

 

[yuvalmadar]

סעיף ב'!

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

 

[ron369]

איזה רשע אתה ../images/Emo6.gif

אתה יודע שגם אני נפלתי בשאלה הזו, לא?

 

[yuvalmadar]

חשבתי שאולי מצאת פתרון מאז ../images/Emo9.gif

גם אף אחד אחר בפורום הקורס לא מצא פתרון.

(לפחות כל אלה שמתחברים) מצאתי את השאלה אפילו בש"ב שנתנו באתר הטכניון לפני כמה סמסטרים (אני מניח שהרכזת לקחה את השאלה משם, למעשה

) אבל לא הופיע שם פתרון.

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