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

הציגו דוגמה פשוטה של רשת-זרימה עם צלע $e$, המקיימת את שתי התכונות הבאות: **(א)** בהרצת Edmonds-Karp על הרשת ישנן שתי איטרציות שונות, שבהן תוספת הזרימה דרך $e$ זהה לקיבולת השיורית של $e$ (באותה איטרציה). **(ב)** הצלע $e$ מחברת בגרף המקורי בין שני קדקודים שמרחקם מהמקור $s$ שונה. לא יינתן ניקוד על דוגמה שמתאימה להרצה של Ford-Fulkerson אבל לא מתאימה להרצה של Edmonds-Karp. (כרגיל, המושג "מרחק" מתייחס למספר הצלעות במסלול הקצר ביותר.)

רמז: בנו רשת שבה כל הקיבולות שוות: מסלול ישר קצר $s\to u\to v\to t$ (דרך $e$ קדימה) ועוקפים ארוכים יותר מ-$s$ ל-$v$ ומ-$u$ ל-$t$. EK ידחוף קודם דרך $e$ קדימה, ואז — כשהמסלול הישר רווי — דרך הצלע השיורית ההפוכה של $e$; בשתי הפעמים התוספת שווה לקיבולת השיורית.

פתרון: נציג רשת שבה **כל הצלעות בעלות אותה קיבולת** $c=69$ (כל ערך חיובי זהה יתאים). הקדקודים: $s,u,v,t$ ובנוסף $a,b,p,q$; הצלע הנדונה היא $e=(u,v)$. **הצלעות (כולן בקיבולת $69$):** $$s\to u,\qquad e=u\to v,\qquad v\to t,\qquad s\to a\to b\to v,\qquad u\to p\to q\to t.$$ כלומר: מסלול ישר $s\to u\to v\to t$ באורך $3$; עוקף באורך $3$ מ-$s$ ל-$v$ דרך $a,b$; ועוקף באורך $3$ מ-$u$ ל-$t$ דרך $p,q$. **תכונה (ב):** בגרף המקורי $\text{dist}(s,u)=1$ ואילו $\text{dist}(s,v)=2$ (הקצר ביותר הוא $s\to u\to v$) — מרחקים שונים. **הרצת Edmonds-Karp (BFS בכל איטרציה):** - **איטרציה 1:** מסלול-השיפור היחיד באורך $3$ הוא $s\to u\to v\to t$ (כל שאר המסלולים באורך $\ge 4$), ולכן BFS **חייב** לבחור בו. צוואר-הבקבוק $=69$, ולכן דוחפים $69$ **דרך $e$ קדימה** — בדיוק הקיבולת השיורית של $e$ ($=69$). - **איטרציה 2:** כעת $s\to u,\ e,\ v\to t$ רוויות. הצלע היחידה היוצאת מ-$s$ עם קיבולת שיורית היא $s\to a$, ולכן מסלול-השיפור היחיד הוא $$s\to a\to b\to v\ \xrightarrow{\ \text{הצלע השיורית ההפוכה של }e\ }\ u\to p\to q\to t\qquad(\text{אורך }7),$$ העובר על הצלע השיורית ההפוכה $v\to u$. צוואר-הבקבוק $=69$, ולכן דוחפים $69$ **דרך $e$ אחורה** — שוב בדיוק הקיבולת השיורית של $e$ (הפעם של הצלע ההפוכה, $=69$), וזרימת $e$ חוזרת ל-$0$. לאחר שתי האיטרציות אין ל-$s$ אף צלע יוצאת עם קיבולת שיורית, ולכן הזרימה מרבית (בערך $138$). קיבלנו **שתי איטרציות שונות שבהן תוספת הזרימה דרך $e$ שווה לקיבולת השיורית של $e$** — תכונה (א). מאחר ששני מסלולי-השיפור הם היחידים באורכם בכל שלב, זהו בדיוק הרצף ש-Edmonds-Karp מבצע (ולא רק רצף אפשרי של Ford-Fulkerson). $\blacksquare$