שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 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(e)$ מבלי להפר את החוקיות? שימו לב שההורדה עצמה חייבת לכבד את שימור-הזרימה — לאיזו בעיה מוכרת זה מתורגם?

פתרון: **רעיון:** בהינתן זרימה-חוקית $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''$ מזערית.* תהי $g$ זרימה-חוקית כלשהי המקיימת $g\le f$, ונסמן $d=f-g$. אז $0\le d(e)\le f(e)-c(e)=c'(e)$, ו-$d$ משמרת זרימה בכל $v\ne s,t$ כהפרש שתי פונקציות משמרות — כלומר $d$ היא זרימה חוקית ב-$G'$. ממקסימליותה של $f'$ נובע $\mathrm{val}(d)\le\mathrm{val}(f')$, ולכן $\mathrm{val}(g)=\mathrm{val}(f)-\mathrm{val}(d)\ \ge\ \mathrm{val}(f)-\mathrm{val}(f')=\mathrm{val}(f'').$ נותר להיווכח שההנחה $g\le f$ אינה מגבילה: תוספת זרימה נכנסת לקדקוד $v\ne s,t$ מחייבת תוספת זהה של זרימה יוצאת, ומעגל תורם באותה מידה לכניסה וליציאה — ולכן כל תוספת נטו ברשת מקורה ב-$s$ ורק **מגדילה** את גודל הזרימה. מכאן ש-$f''$ מזערית. $\blacksquare$ **זמן ריצה:** בניית $G'$ ב-$\Theta(|E|)$ והרצת אדמונדס-קארפ — סה"כ כזמן ריצת אדמונדס-קארפ.