טענה: לכל עפ"מ קיים סדר על הקשתות והקודקודים כך שריצה של אלגוריתם Prim ייצר אותו.

ההוכחה:

זוהי הוכחה שראיתי באינטרנט:

------------------------

"

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

עכשיו צריך להראות שבכל שלב, אם Prim מסמן קשת ככחולה אז היא בהכרח על העץ.

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

נניח בשלילה שבשלב מסויים של האלגוריתם, Prim בוחר בקשת x-y שאינה על העץ, ונניח ש x ב S.

אז y לא ב S, כי סימנו את הקשת בכחול.

יש מסלול בעץ T מ s ל y, כך שהקשת שחוצה את החתך (S,V\S) (יש לפחות אחת כזו) אינה x-y. נניח שזאת הקשת u-v.

אז, המשקל של u-v גדול ממש ממשקל x-y, כי Prim בחר אותה קודם.

"

-------------------

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

המשך שלי:

לא ייתכן כי הקשתות u-v ו- x-y בעלות אותו משקל, כיוון שאם כך האלגוריתם היה בוחר בקשת הראשונה לפי סדר המיון שהיא u-v.

לכן בהכרח מתקיים כי המשקל של u-v גדול ממש ממשקל x-y .

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

האם זה נכון לומר שניתן להוריד מהעץ T את הקשת u-v ולהחליפה ב- x-y ועדיין להישאר עם עץ?(אני לא בטוח שזה נכון וגם לא מצליח להוכיח את זה. אבל אם אצליח אז סיימנו בזה כי הראנו עץ פורש מינימלי יותר בסתירה..)

תודה רבה למי שינסה לעזור (הדגש הוא על השאלה באדום)

אני לא כל כך הבנתי איך "עכשיו צריך להראות שבכל שלב, אם Prim מסמן קשת ככחולה אז היא בהכרח על העץ." מוכיח את הטענה שרצית להוכיח.

בכל אופן, אוליי המשפט הבא יכול לעזור לך להגיע לסתירה.

"כל שני עצים זהים במשקלים":

יהיו T1, T2 שני עצים פורשים מינימליים ויהיו:

x1<=x2<=....<=xn-1 המשקלים של צלעות T1,

y1<=y2<=....<=yn-1 המשקלים של צלעות T2.

אז xi = yi לכל i, כלומר שתי הסדרות זהות.

בהצלחה.