שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - זרימה ברשתות

שאלה 3 – זרימה (תיקון של זרימה-מרבית נתונה) נתונה רשת-זרימה: גרף מכוון $(V, E)$ עם מקור $s$ ויעד $t$, ועם קיבולות שלמות $c(e) \geq 0$ לכל $e \in E$. נתונה זרימה-מרבית $f$ ברשת, שהתקבלה מהרצה של אלגוריתם Ford–Fulkerson, ונתונה צלע מסוימת $e^* \in E$. הציגו אלגוריתם שרץ בזמן לינארי למציאת זרימה מרבית ברשת, המתקבלת מהקטנת הקיבולת של $e^*$ ב-$1$. (הניחו שבכל הצלעות הקיבולות קטנות כך שחיבור/חיסור/השוואה של קיבולת/זרימה הינן פעולות אלמנטריות המתבצעות בזמן $\Theta(1)$.) ___________________________________________________________________1 ___________________________________________________________________2 __________________________________________________________________3 ___________________________________________________________________4 ___________________________________________________________________5 __________________________________________________________________6 ___________________________________________________________________7 ___________________________________________________________________8 ___________________________________________________________________9 __________________________________________________________________10 __________________________________________________________________11 _________________________________________________________________12 __________________________________________________________________13 __________________________________________________________________14 __________________________________________________________________15

רמז: נתחו את המצב לפי הזרימה על הצלע $e^*$. אם הזרימה שווה לקיבולת, בדקו בגרף השיורי אם ניתן למצוא מסלול חלופי ליחידת הזרימה שיש להסיט, או שחייבים להקטין את ערך הזרימה הכולל.

פתרון: האלגוריתם המוצע מנתח את מצב הזרימה על הצלע $e^*=(u,v)$ שקיבולתה הוקטנה, ופועל בהתאם. זמן הריצה הנדרש הוא לינארי בגודל הגרף, $O(|V|+|E|)$. ראשית, נבדוק את ערך הזרימה $f(e^*)$ על הצלע $e^*$ ברשת המקורית. 1. **מקרה א': $f(e^*) < c(e^*)$** במקרה זה, מכיוון שהזרימה והקיבולות שלמות, מתקיים $f(e^*) \leq c(e^*) - 1 = c'(e^*)$. כלומר, הזרימה $f$ עומדת במגבלת הקיבולת החדשה על הצלע $e^*$. מכיוון שלא שינינו קיבולות של צלעות אחרות, הזרימה $f$ היא **זרימה חוקית** גם ברשת החדשה. ערך הזרימה הכולל נותר $|f|$. מאחר שהקיבולות ברשת החדשה קטנות או שוות לאלו שברשת המקורית, ערך הזרימה המרבית החדשה לא יכול להיות גדול מ-$|f|$. לכן, $f$ היא **זרימה מרבית** גם ברשת החדשה. בדיקה זו מתבצעת בזמן $O(1)$. 2. **מקרה ב': $f(e^*) = c(e^*)$** במקרה זה, הזרימה $f$ אינה חוקית ברשת החדשה כי $f(e^*) = c(e^*) > c(e^*) - 1 = c'(e^*)$. עלינו למצוא זרימה מרבית חדשה. ערך הזרימה המרבית החדשה יכול להיות $|f|$ או $|f|-1$. נשתמש במשפט מרכזי בתורת הזרימה: **צלע רוויה $(u,v)$ (כלומר, $f(u,v) = c(u,v)$) נמצאת על חתך מינימום כלשהו אם ורק אם אין מסלול מהצומת $u$ לצומת $v$ בגרף השיורי $G_f$**. נבנה את הגרף השיורי $G_f$ ונשתמש ב-BFS או DFS כדי לבדוק אם קיים מסלול מ-$u$ ל-$v$. * **תת-מקרה 2א': קיים מסלול $P$ מ-$u$ ל-$v$ ב-$G_f$.** לפי המשפט, הצלע $e^*$ אינה חלק מאף חתך מינימום ברשת המקורית. לכן, הקיבולת של כל חתך מינימום מקורי נשארת $|f|$ גם לאחר הקטנת הקיבולת של $e^*$. מכאן שערך הזרימה המרבית החדשה הוא $|f|$. כדי למצוא זרימה זו, עלינו לתקן את הזרימה $f$ שהפכה ללא חוקית. נגדיר תחילה "קדם-זרימה" $f_{temp}$ על ידי הפחתת הזרימה על $e^*$: $f_{temp}(e^*) = f(e^*) - 1$, ו-$f_{temp}(e) = f(e)$ לכל $e \neq e^*$. ב-$f_{temp}$ נוצר **עודף זרימה** של 1 בצומת $u$ ו**מחסור בזרימה** של 1 בצומת $v$. כדי לתקן זאת, "נעביר" את יחידת הזרימה הבעייתית מ-$u$ ל-$v$ דרך המסלול $P$ שמצאנו בגרף השיורי. כלומר, נבצע **הגדלת זרימה (augmentation)** של 1 לאורך המסלול $P$ על גבי $f_{temp}$. הזרימה החדשה $f'$ שתתקבל תהיה חוקית, ערכה יהיה $|f|$, ולכן היא זרימה מרבית. מציאת המסלול ועדכון הזרימה לוקחים זמן $O(|V|+|E|)$. * **תת-מקרה 2ב': לא קיים מסלול מ-$u$ ל-$v$ ב-$G_f$.** לפי המשפט, הצלע $e^*$ נמצאת על חתך מינימום $(S,T)$ כלשהו ברשת המקורית. קיבולת חתך זה הייתה $c(S,T)=|f|$. ברשת החדשה, קיבולת אותו חתך היא $c'(S,T) = c(S,T) - 1 = |f|-1$. מכאן שערך הזרימה המרבית החדשה הוא לכל היותר $|f|-1$. נוכל להשיג זרימה בערך זה, ולכן זהו הערך החדש. כדי לבנות את הזרימה החדשה, עלינו "לבטל" יחידת זרימה אחת שעברה במסלול $s \leadsto u \to v \leadsto t$. פעולה זו שקולה לביצוע הגדלת זרימה של 1 בגרף השיורי $G_f$ במסלול מהיעד למקור, $t \leadsto s$, שעובר דרך הצלע $(v,u)$ (הצלע האחורית ל-$e^*$). מסלול כזה מורכב ממסלול $P_1$ מ-$u$ ל-$s$ וממסלול $P_2$ מ-$t$ ל-$v$. קיום מסלולים כאלה מובטח מ**משפט פירוק הזרימה**, שכן זרם חיובי עבר מ-$s$ ל-$u$ וכן מ-$v$ ל-$t$ (כחלק ממסלולי זרימה שונים). האלגוריתם יפעל כך: 1. מצא מסלול $P_{u \to s}$ מ-$u$ ל-$s$ ב-$G_f$ באמצעות BFS/DFS. 2. מצא מסלול $P_{t \to v}$ מ-$t$ ל-$v$ ב-$G_f$ באמצעות BFS/DFS. 3. הגדר את הזרימה החדשה $f'$ כתוצאה של הגדלת הזרימה $f$ ביחידה אחת לאורך המסלול המורכב $P_{t \to v} \to (v,u) \to P_{u \to s}$. הזרימה $f'$ היא זרימה חוקית ברשת החדשה, ערכה הוא $|f|-1$, ולכן היא זרימה מרבית. שלב זה דורש שתי הרצות של אלגוריתם חיפוש, ולכן זמן הריצה הוא $O(|V|+|E|)$. לסיכום, בכל המקרים, האלגוריתם מוצא זרימה מרבית חדשה בזמן ריצה לינארי. $\blacksquare$