|
|
עמוד:355
העץ הפורש המינימלי הוא : . 3 אפשר להמיר את כל האלגוריתמים למציאת עץ פורש מינימלי באלגוריתמים למציאת עץ פורש מקסימלי . לפניכם גרסאות של שני אלגוריתמים למציאת עץ פורש מקסימלי ו גרסה : 1 חזור על התהליך הזה : מצא את הקשת בעלת המשקל הקטן ביותר בגרף הנתון , והסר אותו מהגרף בתנאי שהגרף נשאר קשיר . גרסה : 11 ניתן לבנות עץ פורש מקסימלי גם כך : בהתחלה בוחרים את הקשת שעלותה המקסימלית היא הגבוהה ביותר . לאחר מכן בוחרים את הקשת שעלותה הגבוהה ביותר מבין הקשתות הנותרות , וכך הלאה , ובלבד שבכל שלב הקשת שנבחרת אינה יוצרת מעגל . . 4 אפשר למצוא עץ פורש מינימלי עם עדיפות לקשתות . כך למשל , נתון גרף קשיר לא מכוון G = ( V , E ) שפונקציית המשקל שלו . W : E ^> R חלק מהקשתות צבועות בכחול , והיתר צבועות בלבן . אנו רוצים למצוא עץ פורש מינימלי עם מספר מקסימלי של קשתות כחולות . כאמור , באלגוריתם של קרוסקל ממיינים תחילה את קשתות הגרף בסדר עולה . לשם כך , בסדרה הממוינת של משקלי הקשתות , כאשר ישנן קשתות בעלות אותו משקל , ניתן עדיפות לקשתות הכחולות . כלומר , קודם נרשום בסדרה הממוינת את הקשת הכחולה ולאחריה את הקשת הלבנה שמשקלה זהה לזה של הקשת הכחולה .
|
|