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

זרימה אפשרית ברשת זרימה נתונה

שאלה

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

זרימה אפשרית בגרף נתון.

תשובה

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

קיום מסלול משפר והגדלת גודל הזרימה

שאלה

נניח שברשת השיורי יש מסלול משפר. אנא הוכח בצורה מדויקת שאפשר להגדיל את הזרימה.

שימו לב: שים לב שאתה אכן מוכיח את טענתך. השתמש בהגדרות הזרימה החוקית וגודל הזרימה.

תשובה

נניח שמצאנו זרימה חוקית כלשהי, המתאימה $\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$ בדיוק.

קשתות משפרות בכוונים שונים

שאלה

בגרף שבתרשים הבא, $\displaystyle s=1$, ‏ $\displaystyle t=4$, ‏ והמספר בכל קשת מציין את קיבול הקשת.

מה זה פשוט - חבל על הזמן.

1. אנא מצא זרימה חוקית כך שברשת השיורית אין קשתות הפונות שמאלה.
2. אנא מצא זרימה חוקית כך שברשת השיורית יש לפחות קשת אחת הפונה שמאלה.

תשובה

בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון שמאל.

אין קשתות לשמאל.

בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון ימין.

אין קשתות לימין.

בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו יש קשתות הן לכוון שמאל והן לכוון ימין.

יש קשתות לכל הכוונים.