עמוד:335

תיצור מעגל . לפיכך , נמצא עתה את הקשת , ( A , F ) שהיא בעלת המשקל הקטן ביותר מבין הקשתות שאינן שייכות ליער , ובתום האיטרציה הרביעית ייראה היער כך , באיטרציה החמישית מוצאים את הקשת , ( fi , D ) שהיא בעלת המשקל הקטן ביותר מבין הקשתות שאינן שייכות ליער . ואולם לא נוסיף ליער את הקשת , ( B , D ) כיוון שהוספתה תיצור מעגל . לכן נמצא עתה את הקשת , { B , E ) שהיא בעלת המשקל הקטן ביותר מבין הקשתות שאינן שייכות ליער , ובתום האיטרציה החמישית ייראה היער כך כמובטח , לאחר חמש איטרציות נקבל עץ פורש מינימלי . שימו לב לכך , שעץ פורש מינימלי אינו בהכרח אחד ויחיד . לדוגמה , באיטרציה החמישית אפשר לבחור את הקשת ל £ , ( 5 , שמשקלה , 12 ולא את הקשת ( B , E ) שנבחרה ושגם משקלה . 12 בתרשים שלהלן מוצג עץ פורש מינימלי אחר עבור הגרף הזה .

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר