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

שאלה 3 – רשתות זרימה (זרימה מזערית) נתונה רשת-זרימה: גרף מכוון $G = (V, E)$ עם מקור $s \in V$ ועם יעד $t \in V$ (כאשר $s \neq t$), ועם קיבולות חיוביות $c(e) > 0$ בצלעות. מובטח, שלכל זוג קדקודים $u, v$ לכל היותר אחת מבין הצלעות $(u, v)$, $(v, u)$ נמצאת בגרף. בשאלה זו "זרימה-חוקית" הינה פונקציה $f: E \to \mathbb{R}$, המקיימת את שתי הדרישות הבאות: (א) לכל קדקוד $v \neq s, t$ מתקיים $\sum_{(u,v) \in E} f(u, v) = \sum_{(v,w) \in E} f(v, w)$ (חוק שימור-הזרימה, כרגיל). (ב) לכל צלע $e \in E$ מתקיים $f(e) \geq c(e)$ (הקיבולת חוסמת בשאלה זו את הזרימה מלמטה דווקא ולא מלמעלה, בניגוד לרגיל). נניח שנתונה לכם זרימה-חוקית $f$. הציגו אלגוריתם למציאת זרימה-חוקית שגודלה מזערי. השמיטו מתשובתכם את ניתוח-היעילות.

רמז: הפכו את הבעיה לבעיית זרימה מרבית סטנדרטית. הגדירו רשת עזר חדשה שהקיבולים בה הם $c'(e) = f(e) - c(e)$ והשתמשו בזרימה המרבית ברשת זו כדי לתקן את הזרימה ההתחלתית $f$.

פתרון: האלגוריתם למציאת זרימה חוקית מינימלית מתבסס על **רדוקציה** של הבעיה לבעיית **זרימה מרבית** סטנדרטית. הרעיון המרכזי הוא להתחיל עם הזרימה החוקית הנתונה, $f$, ולנסות "להחזיר" זרימה מהיעד $t$ למקור $s$ ככל הניתן, מבלי להפר את אילוצי החוקיות. כל זרימה כזו שתנוכה מ-$f$ תקטין את ערך הזרימה הכולל. נניח ש-$f_{min}$ היא הזרימה המזערית שאנו מחפשים. ניתן לבטא אותה כהפרש בין הזרימה הנתונה $f$ לבין "זרימת תיקון" $h$, כלומר: $f_{min} = f - h$. כדי ש-$f_{min}$ תהיה חוקית, על $h$ לעמוד בתנאים מסוימים: 1. **אילוץ הקיבול התחתון**: לכל צלע $e ext{ ב- } E$, חייב להתקיים $f_{min}(e) \\