|
|
עמוד:336
כאמור , בכל צעד האלגוריתם של קרוסקל מוסיף ליער קשת בעלת משקל קטן ככל האפשר בתנאי שהוספתה לא תיצור מעגל . עתה נשאלת השאלה : כיצד נוכל לקבוע האם הוספה לעץ הפורש של הקשת הנבחנת בעלת המשקל הקטן ביותר לא תיצור מעגל ? כזכור , בהתחלה האלגוריתם של קרוסקל יוצר | V | רכיבי קשירות ( יער ) עבור הגרף . G- ( V , E ) בכל שלב של האלגוריתם מוסיפים ליער קשת ( A , B ) שהיא בעלת משקל מינימלי מבין כל הקשתות המחברות שני עצים כלשהם ביער . אס לאחר מספר איטרציות ביער ישנם k עצים "זרים" זה לזה , כפי שמראה האיור שלהלן ו אזי , לאחר הוספת הקשת ( U , V ) ליער , יהיו k- 1 עצים זרים זה לזה . שימו לב לכך , שאם v e c .-o u & 0 , כאשר , i / w אזי הוספת הקשת ( U , V ) לא תיצור מעגל , אך אם י ] u & , וגם v & ci בעבור / כלשהו , אזי הוספת הקשת ( U , V ) תיצור מעגל , לפי משפט . 6 . 2 . 4
|
|