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

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

1. הזרימה היוצאת מ$\displaystyle s_{i}$ היא $\displaystyle x_{i}$.
2. מתקיימות הווריאציות הבאות של זרימה חוקית:
   1. (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; $\displaystyle \forall _{u,v\in V}f_{u,v}\leq c_{u,v}$.
   2. (סימטריה הפכית) הזרימה הישירה מצומת $\displaystyle u$לצומת $\displaystyle v$היא מינוס הזרימה הישירה מצומת

$\displaystyle v$לצומת $\displaystyle u$;‏ $\displaystyle \forall _{u,v\in V}f_{u,v}=-f_{v,u}$.

1. 1. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים $\displaystyle s_{1},\ldots ,s_{m}$ו$\displaystyle t$, הצומת אינו אוגר או מייצר זרם; $\displaystyle \forall _{u\in V\setminus \{s_{1},\cdots ,s_{m},t\}}\sum _{v\in V}f_{u,v}=0$.(שים לב שרק הדרישה השלישית השתנתה.)

נבנה, לכן, גרף חדש. נוסיף בו שני צמתים $\displaystyle s$ו$\displaystyle t$, ועוד מספר קשתות. הגרף החדש מתואר להלן:

גרף הפתרון.

בגרף החדש, כל קשת מהצורה $\displaystyle (s,s_{i})$בעלת הקיבול $\displaystyle x_{i}$, וכל קשת מהצורה $\displaystyle (t_{j},t)$בעלת הקיבול $\displaystyle \infty$.

נבדוק בגרף החדש האם יש זרימה מ$\displaystyle s$ל$\displaystyle t$בגודל $\displaystyle \sum _{i=1}^{m}[x_{i}]$.

משפט: יש פתרון לבעיה החדשה \Leftrightarrow יש פתרון לבעיה המקורית.

הוכחה: (⇐) נניח שיש פתרון לבעיה החדשה (כלומר, אכן יש זרימה שגודלה $\displaystyle \sum _{i=1}^{m}[x_{i}]$). נתבונן בחתך הבא:

חתך בפתרון.

מה נוכל לראות מחתך זה וממגבלות הזרימה? מצד אחד, גודל הזרימה כאן הוא $\displaystyle \sum _{i=1}^{m}[f_{s,s_{i}}]=\sum _{i=1}^{m}[x_{i}].$

מצד שני, מגבלת קיבול החתך על זרימת החתך אומרת כי $\displaystyle \sum _{i=1}^{m}[f_{s,s_{i}}]\leq \sum _{i=1}^{m}[c_{s,s_{i}}]=\sum _{i=1}^{m}[x_{i}].$

מכאן קל לראות שבהכרח, לכל $\displaystyle i$, $\displaystyle f_{s,s_{i}}=x_{i}.$