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

נתונה רשימה של $n_1$ גברים, של $n_2$ נשים ושל $m$ שדכנים. עבור כל שדכן $1\le i\le m$ נתונה רשימת הגברים והנשים המוכרים לו, ונתונה מגבלת עומס $1\le B_i\le n_1,n_2$: שדכן מספר $i$ יכול לשדך באופן חוקי בין כל גבר ואשה המוכרים לו, כל עוד מספר הזוגות הכולל שהוא משדך אינו עולה על $B_i$. ברצוננו למצוא שידוך מרבי (מספר מרבי של זוגות גבר-אשה, כאשר כל אדם משתתף בזוג אחד לכל היותר). נביט באלגוריתם הבא: בונים רשת-זרימה עם הצלעות הבאות בלבד: **(א)** המקור $s$ מחובר לכל שדכן $i$ בצלע עם קיבולת $B_i$; **(ב)** כל שדכן מחובר בצלע עם קיבולת $1$ לכל הגברים שהוא מכיר; **(ג)** כל גבר מחובר בצלע עם קיבולת $1$ לכל אישה שקיים שדכן המכיר את שניהם; **(ד)** כל אישה מחוברת בצלע עם קיבולת $1$ ליעד $t$. גודל הזרימה המרבית ברשת מוחזר כגודל השידוך המרבי. **הוכיחו שהאלגוריתם המוצע שגוי**, על-ידי הצגת דוגמה שבה גודל הזרימה החוקית המרבית שונה מגודל השידוך המרבי.

רמז: חפשו היכן הבנייה לא אוכפת ש**גבר** ישתתף בזוג אחד בלבד. גבר יחיד המוכר לשני שדכנים (עם שתי נשים שונות) נותן זרימה $2$ אך שידוך $1$.

פתרון: האלגוריתם שגוי משום שאין ברשת שום אילוץ המגביל **גבר** יחיד להשתתף בזוג אחד בלבד — זרימה יכולה לעבור דרך אותו גבר מספר פעמים. **דוגמה נגדית.** גבר יחיד $g$ ($n_1=1$), שתי נשים $a,b$ ($n_2=2$), ושני שדכנים $S_1,S_2$ עם $B_1=B_2=1$. השדכן $S_1$ מכיר את $g$ ואת $a$; השדכן $S_2$ מכיר את $g$ ואת $b$ (כלומר $g$ מוכר לשני השדכנים). - **הזרימה החוקית המרבית $=2$:** המסלול $s\to S_1\to g\to a\to t$ (זרימה $1$) יחד עם $s\to S_2\to g\to b\to t$ (זרימה $1$) — סה"כ $2$ יחידות זרימה, חוקיות בכל הקיבולות. שימו לב ש-$2$ יחידות עוברות דרך הקדקוד $g$. - **השידוך המרבי $=1$:** יש רק גבר אחד $g$, והוא יכול להיות משודך לאישה אחת בלבד. לכן הזרימה המרבית $=2\ne 1=$ השידוך המרבי, והאלגוריתם מחזיר תוצאה שגויה. **התיקון:** יש לפצל כל גבר לשני קדקודים $g_{\text{in}}\to g_{\text{out}}$ עם צלע פנימית בקיבולת $1$ (וכן לפצל כל שדכן כדי לאכוף את $B_i$ בין הגברים לנשים), כך שדרך כל גבר תעבור לכל היותר יחידת זרימה אחת. $\blacksquare$