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

שאלה זו מובילה משיטת Ford-Fulkerson לאלגוריתם Ford-Fulkerson.

הגדרה: שיטת Ford-Fulkerson בהינתן רשת הזרימה: ראשית קבע את זרימת האפס (כלומר הזרימה המשייכת לכל קשת זרימה 0). (זו בוודאי זרימה חוקית.) כל עוד יש מסלול משפר ברשת השיורית, שפר את הזרימה דרך מסלול זה.

נתונה רשת זרימה שבה גרף $\displaystyle G=(V,E)$.

הגדרה: נאמר שרשת זרימה היא שלמה אם הקיבול $\displaystyle c_{u,v}$ הוא מספר שלם לכל $\displaystyle u,v\in V$. נאמר שזרימה היא שלמה אם הזרימה $\displaystyle f_{u,v}$ היא מספר שלם לכל $\displaystyle u,v\in V$.

1. נתונה רשת זרימה שלמה. האם כל זרימה מירבית היא בהכרח שלמה? אנא הוכח או הראה דוגמה נגדית.
2. אנא הראה ששיטת Ford-Fulkerson פועלת מספר סופי של איטרציות במקרה של רשת זרימה שלמה.
3. בהנתן רשת זרימה שלמה, האם בהכרח קיימת זרימה מירבית שהיא שלמה? אנא הוכח או הראה דוגמה נגדית.