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

1

התרשים הבא מראה דוגמה נגדית לטענה.

דוגמה נגדית.

בגרף זה כל הקיבולים שלמים (כל אחד מהם הוא 1). הזרימות מתוארות בסוגריים, ולא כולן שלמות. קל לראות שהזרימה מירבית, מפני שגודל הזרימה (שהוא 1) הוא בדיוק גודל קיבול החתך בין 4 ל5.

2

נראה באינדוקציה ששיטת Ford-Fulkerson תזרים יחידות שלמות במקרה זה.

הוכחה: בכל איטרציה מוצאים מסלול משפר ברשת השיורית, ומשפרים דרכו. האינדוקציה היא על מספר האיטרציה.

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

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

היות שהזרימה היא שלמה, אז כל איטרציה של Ford-Fulkerson תשפר את הזרימה ב1 לפחות. מספר האיטרציות, לכן, חסום.

3

הטענה נכונה, והיא נובעת מהסעיף הקודם.

שיטת Ford-Fulkerson תפעל בזמן סופי במקרה זה, והיא תזרים זרימה שלמה. כשהשיטה עצרה את פעולתה, לא היה מסלול משפר ברשת השיורית. כבר למדנו שנובע מכך שהזרימה היא מירבית.