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

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

פתרון: השאלה, כפי שנוסחה, מתארת בעיה של **זרימה עם דרישות** (flow with demands), כאשר לכל קשת יש חסם תחתון על הזרימה. נתונה רשת $G=(V,E)$ עם מקור $s$ ובור $t$, ולכל קשת $e \in E$ נתון ערך $c(e)>0$ המשמש **דרישה** על הזרימה באותה קשת. "זרימה-חוקית" $f$ היא פונקציה $f:E\to\mathbb{R}$ המקיימת שני תנאים: 1. **שימור זרימה:** לכל צומת $v \in V \setminus \{s,t\}$, מתקיים $\sum_{(u,v)\in E} f(u,v) = \sum_{(v,w)\in E} f(v,w)$. 2. **עמידה בדרישות:** לכל קשת $e \in E$, מתקיים $f(e) \ge c(e)$. המטרה היא לקבוע האם קיימת זרימה חוקית ברשת. ניתן לפתור בעיה זו על ידי **רדוקציה** לבעיית **זרימה מקסימלית** סטנדרטית. **שלב 1: הגדרת זרימת העודפים** נגדיר פונקציית זרימה חדשה, $f': E \to \mathbb{R}_{\ge 0}$, המייצגת את "העודף" מעל הדרישה המינימלית: $f'(e) = f(e) - c(e)$ מכיוון ש- $f(e) \ge c(e)$, אנו יודעים כי $f'(e) \ge 0$, וזוהי דרישת אי-השליליות הסטנדרטית בזרימה. **שלב 2: ניתוח חוק שימור הזרימה** נציב את הביטוי עבור $f(e)$ בחוק שימור הזרימה עבור צומת $v \in V$ (לשם הפשטות, נניח שהחוק חל על כל הצמתים, כולל $s,t$, מה שמוביל לבעיית **סירקולציה עם דרישות**): $\sum_{(u,v)\in E} (f'(u,v) + c(u,v)) = \sum_{(v,w)\in E} (f'(v,w) + c(v,w))$ $\sum_{(u,v)\in E} f'(u,v) + \sum_{(u,v)\in E} c(u,v) = \sum_{(v,w)\in E} f'(v,w) + \sum_{(v,w)\in E} c(v,w)$ נסדר מחדש את המשוואה כדי לבודד את הזרימה $f'$: $\sum_{(v,w)\in E} f'(v,w) - \sum_{(u,v)\in E} f'(u,v) = \sum_{(u,v)\in E} c(u,v) - \sum_{(v,w)\in E} c(v,w)$ נגדיר את **עודף הדרישה** בכל צומת $v \in V$ בתור: $D(v) = \sum_{(u,v)\in E} c(u,v) - \sum_{(v,w)\in E} c(v,w)$ $D(v)$ מייצג את ההפרש בין סך הדרישות הנכנסות לצומת $v$ לסך הדרישות היוצאות ממנו. **שלב 3: בניית רשת זרימה חדשה** נבנה רשת זרימה חדשה $G'=(V', E')$ באופן הבא: 1. **צמתים:** $V' = V \cup \{s', t'\}$ (נוסיף מקור-על $s'$ ובור-על $t'$). 2. **קשתות וקיבולים:** * כל קשת מקורית $e=(u,v) \in E$ קיימת גם ב-$E'$. מכיוון שלא נתון חסם עליון על הזרימה, הקיבול שלה יהיה אינסופי: $c'(e) = \infty$. * לכל צומת $v \in V$ עם **עודף דרישה חיובי** ($D(v) > 0$), נוסיף קשת מהמקור החדש $s'$ אל $v$, עם קיבול $c'(s', v) = D(v)$. צמתים אלה צריכים "לקבל" זרימה כדי להתאזן. * לכל צומת $v \in V$ עם **עודף דרישה שלילי** ($D(v) < 0$), נוסיף קשת מ-$v$ אל הבור החדש $t'$, עם קיבול $c'(v, t') = -D(v)$. צמתים אלה צריכים "לשלוח" זרימה כדי להתאזן. **שלב 4: פתרון הבעיה** נשים לב כי $\sum_{v \in V} D(v) = 0$, ולכן סך הקיבולים של הקשתות היוצאות מ-$s'$ שווה לסך הקיבולים של הקשתות הנכנסות ל-$t'$. קיימת זרימה חוקית $f$ ברשת המקורית $G$ **אם ורק אם** הזרימה המקסימלית ברשת $G'$ מהמקור $s'$ לבור $t'$ **מרווה** את כל הקשתות היוצאות מ-$s'$. כלומר, אם ערך הזרימה המקסימלית שווה ל- $\sum_{v: D(v)>0} D(v)$. **הסבר:** אם מצאנו זרימה $f'$ ב-$G'$ שמרווה את כל הקשתות מ-$s'$, זה אומר שסיפקנו לכל צומת $v$ עם $D(v)>0$ בדיוק $D(v)$ יחידות זרימה, וניקזנו מכל צומת $v$ עם $D(v)<0$ בדיוק $-D(v)$ יחידות זרימה. כתוצאה מכך, בגרף המקורי (ללא $s', t'$), הזרימה $f'$ מקיימת את חוק שימור הזרימה המתוקן בכל צומת $v \in V$. כעת, נוכל להגדיר את הזרימה החוקית $f(e) = f'(e) + c(e)$ בגרף המקורי, והיא תקיים את כל הדרישות. $\blacksquare$