מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/חוסר שימוש בקשת היקרה ביותר במעגל/תשובה

בתרשים הבא מצויירים צמתי המעגל, $\displaystyle v_{1},v_{2},\ldots ,v_{i}$ (הקשתות אינן מצויירות וכך גם שאר הצמתים). נניח שהקשת $\displaystyle e$ היא הקשת $\displaystyle (v_{1},v_{i})$.

מעגל בבניית עפ"מ - מצב המעגל ההתחלתי.

נניח בשלילה ש$\displaystyle e$ אכן שייכת לעפ"מ. אפשר לבנות את העפ"מ ע"י הוספת קשתות בסדר שרירותי (באופן שקול: לאחר שקובעים את קשתות העפ"מ, אפשר לתאר אותן בסדר שרירותי). נניח לכן ש$\displaystyle e$ אחרונה. כמה עצים יש בדיוק לפני הוספת $\displaystyle e$? יש בהכרח שני עצים. לו היה עץ יחיד, הוספת $\displaystyle e$ היתה מייצרת מעגל, ולו היו שלושה (או יותר) עצים, קשת אחת לא היתה יכולה לחבר ביניהם.

נניח לכן שיש כרגע שני עצים: עץ אדום ועץ שחור. נניח ש$\displaystyle v_{1}$ שייך לעץ השחור. אז בהכרח $\displaystyle v_{i}$ שייך לעץ האדום (מדוע?). התרשים הבא מראה זאת.

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

נשים לב שאם $\displaystyle v_{1}$ שייך לעץ השחור ו$\displaystyle v_{i}$ לעץ האדום, אז בהכרח יש $\displaystyle 1\leq j<i$ כך ש$\displaystyle v_{j}$ שייך לעץ השחור אך $\displaystyle v_{j+1}$ שייך לעץ האדום.

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

הקשת $\displaystyle (v_{j},v_{j+1})$ שייכת למעגל, ולכן בהכרח זולה מ$\displaystyle e$ (מדוע?). לכן ברור שנקבל עפ"מ זול יותר (ממש) אם בצעד האחרון נשתמש ב$\displaystyle (v_{j},v_{j+1})$ במקום ב$\displaystyle e$, דבר שסותר את הנחתנו ש$\displaystyle e$ נמצאת בעפ"מ.