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

נניח שמצאנו זרימה חוקית כלשהי, המתאימה $\displaystyle f_{u,v}$ לכל שני צמתים $\displaystyle u,v\in V$. נניח גם שברשת השיורית יש מסלול משפר בעל קיבול $\displaystyle k$. נסמן מסלול זה כ$\displaystyle u_{1}\rightarrow u_{2}\rightarrow \ldots \rightarrow u_{m}$. נשים לב ש$\displaystyle u_{1}=s$ ו$\displaystyle u_{m}=t$. מכאן נוכל להסיק את הדברים הבאים:

1. מספר הקשתות הנכנס ל$\displaystyle s$ במסלול זה קטן ב1 ממספר הקשתות היוצאות ממנו.
2. מספר הקשתות היוצא מ$\displaystyle t$ במסלול זה קטן ב1 ממספר הקשתות הנכנסות אליו.
3. לכל צומת אחר המופיע במסלול, מספר הקשתות הנכנס אליו במסלול שווה בדיוק למספר הקשתות היוצא ממנו.

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

נקח את הזרימה החוקית, נזרים עוד $\displaystyle k$ יחידות בכל קשת במסלול המשפר, ונראה מה קורה לזרימה.

1. לאחר השיפור, הזרימה הישירה בין שני צמתים היא $\displaystyle f_{u,v}$ אם $\displaystyle (u,v)$ אינו שייך למסלול המשפר, ו$\displaystyle f_{u,v}+k$ אם $\displaystyle (u,v)$ שייך למסלול המשפר. במקרה השני חייב להתקיים $\displaystyle c_{u,v}-f_{u,v}\geq k$, משום שאם לא כן, לא ייתכן שקיבול המסלול היה $\displaystyle k$. לכן בהכרח $\displaystyle f_{u,v}+k\leq c_{u,v}$.
2. הסימטריה ההפכית אינה מופרת, משום שבחרנו בפרשנות לפיה אם אנו מזרימים עוד $\displaystyle k$ יחידות מ$\displaystyle u$ ל$\displaystyle v$, מזרימים פחות $\displaystyle k$ יחידות מ$\displaystyle v$ ל$\displaystyle u$.
3. שימור הזרם אינו מופר. נקח צומת $\displaystyle v\in V\ \{s,t\}$ שנמצא על המסלול. לפי טענה 3 למעלה, אם $\displaystyle (u,v)$ במסלול (עבור $\displaystyle u$ כלשהו), אז גם $\displaystyle (v,w)$ במסלול (עבור $\displaystyle w$ כלשהו). אך זה אומר שהזרימה מהצומת החוצה אינה משתנה, כי $\displaystyle f_{u,v}+k-(f_{v,w}+k)=f_{u,v}+f_{w,v}$.

מה קורה לגודל הזרימה? נתבונן ב$\displaystyle \sum _{v\in V}[f_{s,v}]$. עפ"י טענה 1 למעלה, גודל זה גדל ב$\displaystyle k$ בדיוק.