הבודק טען שהפתרון אינו קביל, אבל אני לא מוצא את הטעות בו:
2) אלגוריתם: תחילה נריץ PRIM על G פעם אחת, וכל קשת שנמצאת בעפ"מ T1 שהתקבל – נסמן בצבע אדום.
כעת נריץ את PRIM מחדש עם שינוי קל: כאשר אנו רצים על רשימת הקשתות של צומת, תחילה נרוץ רק על הקשתות שאינן אדומות, נבדוק עבורן את התנאים הרגילים ונשנה את ערכי הצומת pai(v) ו-key(v) בהתאם. לאחר מכן, נרוץ על הקשתות האדומות של הצומת ונבדוק אותן, ובמקרה הצורך, נשנה את ערכי הצומת בהתאם.
אם בסוף האלגוריתם קיבלו שבעפ"מ החדש T2 יש את אותן קשתות כמו ב-T1 – נדע ששתי העפ"מים זהים בדיוק, ושיש רק עפ"מ אפשרי אחד. אחרת – יש לפחות 2 עפ"מים עבור G.
נכונות: נראה שאם רק אם יש עפ"מ נוסף עבור G, בהרצת האלגוריתם PRIM השניה (עם השינויים), בהכרח יהיו בעפ"מ החדש קשתות שאינן אדומות (ולכן נקבל רשימת קשתות שונה).
: נניח שקיים עפ"מ נוסף עבור G. בהרצה השניה של PRIM אנו עוברים על עבור כל צומת קודם כל על הקשתות שאינן אדומות, ומעדכנים את ערכי pai(v) ו-key(v) שלהן בהתאם.
רק לאחר מכן אנו עוברים על הקשתות האדומות של הצומת.
מההנחה שקיים עפ"מ נוסף, חייבות להיות קשתות נוספות להן משקל זהה לחלק מהקשתות האדומות (לא ייתכן במשקל קטן יותר, אחרת היו מתגלות בעפ"מ של ההרצה הראשונה), וכיוון שבהרצה השניה אנו עוברים על אלה שאינן אדומות קודם, בהכרח נגלה אותן קודם. ומכיוון שהערכים הרלוונטים מתעדכנים רק אם משקל הקשת קטן מ-key(v), הערכים לא יתעכנו עבור קשת אדומה ששווה במשקלה לקשת שהתגלתה קודם. ולכן, אם קיים עפ"מ נוסף עבור G, הוא יכיל קשתות שאינן אדומות.
: אם בעפ"מ החדש שקיבלנו יש קשתות שאינן אדומות, מן הסתם שיש שתי עפ"מים שונים זה מזה עבור G.
אם בעפ"מ השני שקיבלנו יש רק קשתות מסומנות, בהכרח מדובר באותו עפ"מ, שכן בעפ"מ יש V-1 קשתות, ואם כולן מסומנות הרי שגילינו את כולן בהרצה הראשונה, וזה בעצם אותו עפ"מ.
סיבוכיות: הרצת PRIM בפעם הראשונה תיקח O(E+VlogV). זמן צביעת הקשתות בעץ שהתקבל הוא O(V). זמן ריצת PRIM השניה, עם השינויים, ייקח גם הוא 2E+VlogV שזה O(E+VlogV), כי בסך הכל עבור כל צומת אנו רצים על רשימת הקשתות שלה פעמיים – וקודם כל מעדכנים את ערכי הצומת עבור אלו שאינן אדומות, ואח"כ מעדכנים עבור אלו שכן אדומות.
סכ"ה סיבוכיות O(E+VlogV) (במימוש ערימת פיבונאצ'י כמובן).
תודה!