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

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

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

פתרון: **רעיון:** בהינתן זרימה-חוקית $f$, כל צלע $e$ יכולה "לוותר" על עד $f(e)-c(e)$ יחידות זרימה מבלי להפר את החסם התחתון $f(e)\ge c(e)$. נמקסם את הכמות שנוריד מ-$f$ (כזרימת $s\rightsquigarrow t$) באמצעות זרימה מרבית ברשת מתאימה. **האלגוריתם:** 1. בנה גרף $G'$ עם אותם קדקודים וצלעות, אך עם קיבולות (עליונות, רגילות) $c'(e)=f(e)-c(e)\ge 0$ לכל צלע. 2. הרֵץ אדמונדס-קארפ על $G'$ ומצא זרימה מרבית $f'$. 3. החזר $f''(e)=f(e)-f'(e)$ לכל צלע $e$. **נכונות.** *ראשית, $f''$ חוקית.* שימור-זרימה: $f$ ו-$f'$ שתיהן מקיימות שימור בכל קדקוד $v\ne s,t$, ולכן גם הפרשן $f''=f-f'$: $$\sum_{(u,v)\in E} f''(u,v)=\sum_{(u,v)\in E}\big(f(u,v)-f'(u,v)\big)=\sum_{(v,w)\in E}\big(f(v,w)-f'(v,w)\big)=\sum_{(v,w)\in E} f''(v,w).$$ חסם תחתון: $f'(e)\le c'(e)=f(e)-c(e)$, ולכן $f''(e)=f(e)-f'(e)\ge f(e)-\big(f(e)-c(e)\big)=c(e)$. אז $f''$ מקיימת את שני התנאים. *שנית, $f''$ מזערית.* נניח בשלילה שקיימת זרימה-חוקית קטנה יותר. אזי ניתן להוריד מ-$f$ עוד יחידת זרימה במסלול $s\rightsquigarrow t$ מעבר למה ש-$f'$ כבר הורידה, כלומר קיים מסלול-שיפור בגרף-השיורי של $G'$ ל-$f'$ — בסתירה לכך ש-$f'$ מקסימלית. $\blacksquare$ **זמן ריצה:** בניית $G'$ ב-$\Theta(|E|)$ והרצת אדמונדס-קארפ — סה"כ כזמן ריצת אדמונדס-קארפ.