מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה

דף זו הוא השלישי (מתוך שלשה דפים) העוסק באלגוריתמים למציאת זרימת המקסימום בגרף מכוון המתאר "רשת צינורות". בדפים הקודמים מצאנו תנאים (מספיקים והכרחיים) למציאת זרימה מקסימלית. בדף זה נעסוק בשיטות ואלגוריתמים המשתמשים בתנאים אלה כדי למצוא זרימה מקסימלית.

שיטת Ford-Fulkerson

שיטת Ford-Fulkerson מתבססת על הרעיונות הבאים:

1. מסלולים משפרים מאפשרים למעשה לקבוע את זרימת המקסימום:
   1. ראינו בגודל זרימה ומסלולים משפרים שכל עוד מוצאים מסלול משפר בגרף הרשת השיורית, אפשר לשפר את הזרימה.
   2. ראינו בזרימה וחתכי S-T שאם אי אפשר למצוא מסלול משפר בגרף הרשת השיורית, אי אפשר לשפר את הזרימה.
2. קל לבנות את הרשת השיורית ולמצוא מסלול בה (או לחלופין, להיווכח שאין מסלול כזה). אם כי לא נתעמק בזאת, לא קשה לראות שאפשר לעשות זאת בסיבוכיות $O(E)$.שתי נקודות אלו מובילות לרעיון הבא, הידוע כשיטת Ford -Fulkerson:

מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/הגדרת שיטת Ford-Fulkerson

תבנית:הארה

אלגוריתם Ford-Fulkerson

אלגוריתם Ford-Fulkerson הוא פחות-או-יותר שיטת Ford-Fulkerson בהקשר רשתות זרימה שבהן הקיבולים הם מספרים שלמים:

בניגוד למקרה הכללי, כאן (כשהקיבולים הם מספרים שלמים), קל-יחסית להראות שהאלגוריתם אכן עובד, ולנתח את סיבוכיותו:

תבנית:הוכחה

אלגוריתם Edmonds-Karp

אלגוריתם Edmonds-Karp הוא פחות-או-יותר שיטת Ford-Fulkerson, אך תוך ציון כיצד יש לבחור מסלול שיפור בגרף הרשת השיורית:

תבנית:שימו לב

תבנית:משפט

להלן "הוכחת נפנופי-ידיים":

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס