|
|
עמוד:344
6 , 4 האלגוריתם של פרים ( Prim ) נתונה הרשת G = ( V , E ) ומתחילים ליצור עץ פורש מקדקוד כלשהו . /? 5 V בכל שלב נוסיף קשת בעלת משקל מינימלי , המחברת את העץ לקדקוד שלא שייך לעץ . כך גדל העץ הפורש עד שהוא מכיל את כל קדקודי הגרף . G בדומה לאלגוריתם של קרוסקל , גם האלגוריתם של פרים הוא אלגוריתם חמדן , כי בכל צעד הוא מוסיף קשת בעלת משקל קטן ככל האפשר . ניתן להוכיח שאסטרטגיה כזו של בניית עץ פורש מבטיחה שבתום האלגוריתם , E יכיל קשתות המהוות עץ פורש מינימלי . כאמור , מטרתנו למצוא עץ המכיל את כל קדקודי הגרף . לשם פיקוח על כך נשתמש בתור , Q כך ש : V- Q מייצג את קבוצת הקדקודים אשר טופלו ושנמצאים בעץ הפורש , ואילו Q מייצג את קבוצת הקדקודים שעדיין לא טופלו ושאינם נמצאים בעץ הפורש . מאחר שבתחילת האלגוריתם אף קדקוד של הגרף הנתון לא טופל , כל הקדקודים יהיו בתור , ובתום האלגוריתם התור Q יישאר ריק , כיוון שכל הקדקודיס חייבים להיות בעץ הפורש . עבור כל קדקוד , v נשמור בתור Q את , K [ v ] אשר יכיל את המשקל המינימלי מבין משקלי הקשתות המחברות את הקדקוד v לקדקודים השייכים לעץ . כי < - 00 ברור בתחילת האלגוריתם . A V ] ^ בנוסף , עבור כל קדקוד v נשמור מידע נוסף \ P [ v ] שהנו ההורה של v בעת בניית עץ פורש . כלומר P [ v ] מציין את ההורה של ע . הסימן P נבע מהסיבה P [ v ] -v מייצג הורה של קדקוד * משפט 6 . 3 . 4 . 1 לאחר הרצת האלגוריתם של קרו 0 קל על הגרף G = ( V , E ) מתק"ם : א . מספר הצעדים באלגוריתם של קרו 0 קל הוא M - 1 לכל היותר . ב . אם אלגוריתם מ 0 ת"ם לאחר / 77 איטרציות , אזי : אם /| - 1 ן | -ודו , אזי , T = ( V , E ) הנו yvrt הפורש המינימלי של . G אחרת < / V \ - 1 ) ל , (/ 7 הגרף G לא מכיל עץ פורש . משפט זה ניתן ללא הוכחה .
|
|