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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

קפיצה אל: ניווט, חיפוש

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

תוכן עניינים

1 זרימה אפשרית ברשת זרימה נתונה
- 1.1 שאלה
- 1.2 תשובה
2 קיום מסלול משפר והגדלת גודל הזרימה
- 2.1 שאלה
- 2.2 תשובה
3 קשתות משפרות בכוונים שונים
- 3.1 שאלה
- 3.2 תשובה

[עריכה] זרימה אפשרית ברשת זרימה נתונה

[עריכה] שאלה

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

[עריכה] תשובה

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

[עריכה] קיום מסלול משפר והגדלת גודל הזרימה

[עריכה] שאלה

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

שימו לב:

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

[עריכה] תשובה

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

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

שימו לב:

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

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

לאחר השיפור, הזרימה הישירה בין שני צמתים היא $\displaystyle f_{u, v}$ אם $\displaystyle (u, v)$ אינו שייך למסלול המשפר, ו $\displaystyle f_{u, v} + k$ אם $\displaystyle (u, v)$ שייך למסלול המשפר. במקרה השני חייב להתקיים $\displaystyle c_{u, v} - f_{u, v} \ge k$ , משום שאם לא כן, לא ייתכן שקיבול המסלול היה $\displaystyle k$ . לכן בהכרח $\displaystyle f_{u, v} + k \le c_{u, v}$ .
הסימטריה ההפכית אינה מופרת, משום שבחרנו בפרשנות לפיה אם אנו מזרימים עוד $\displaystyle k$ יחידות מ $\displaystyle u$ ל $\displaystyle v$ , מזרימים פחות $\displaystyle k$ יחידות מ $\displaystyle v$ ל $\displaystyle u$ .
שימור הזרם אינו מופר. נקח צומת $\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}$ .