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

[אלוהים1980]

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

אני מתכונן למבחן בשבוע הבא, באמצעות מבחנים מהשנים הקודמות ונתקלתי בשאלה הזאת, שלא הבנתי את הפתרון שלה: בהינתן גרף לא מכוון, פשוט, ולא ממושקל, מותן של גרף הוא המעגל הפשוט הקצר ביותר בגרף. המתרגל הציע את האלגוריתם הבא למציאת אורך המותן של גרף נתון: לכל צומת נמצא את אורך המעגל הקצר ביותר שבו הוא משתתף, ונחזיר את המינימום מבין הערכים שמצאנו. על מנת למצא את אורך המעגל הקצר ביותר שבו משתתף צומת v: הרץ BFS החל מ- v, עם השינוי הבא: כאשר מגיעים לצומת u כלשהו בפעם השנייה, ויהא w הצומת ממנו הגענו ל- u החזר את

d(u)+d(v)+1​

נראה לי שהאלגוריתם הזה יעבוד, אולם משום מה, הפתרון הוא שזה יעבוד רק עם אורך המותן הוא זוגי. יש לכם מושג למה?

 

[vinney]

שאלה קטנה

נניח הגרף הוא "משולש" : קודקודי המשולש הם הצמתים וצלעות המשולש - הקשתות. למה האלגוריתם לא יעבוד במקרה הזה? לדעתי הוא יעבוד, ואורך המותן הוא 3- אי זוגי. לא?

 

[אלוהים1980]

גם לי זה נראה ככה. בגלל זה אני שואל

פשוט בטופס המבחן התשובה שסומנה כנכונה היתה שזה יעבוד בוודאות רק במקרה שאורך המותן זוגי. אולי קיימת דוגמה נגדית מיוחדת שבה זה לא עובד עבור מותן באורך אי זוגי?