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

במסגרת הפקה של סרט קולנוע עלינו ללהק שחקנים מבין השחקנים $A_1, A_2, \ldots, A_n$, ולבחור משקיעים מבין המשקיעים $I_1, I_2, \ldots, I_m$. ידוע לנו השכר המדויק $W_i$ של שחקן $A_i$ (לכל $1 \leq i \leq n$), וסכום ההשקעה המדויק $P_k$ של משקיע $I_k$ (לכל $1 \leq k \leq m$). עבור כל זוג של שחקן-משקיע ידוע לנו האם הם בקשר של "נאמנות": שחקן $A_i$ ישתתף בסרט רק אם כל המשקיעים להם הוא נאמן ישתתפו במימון, ובדומה, משקיע $I_k$ ישקיע בסרט רק אם כל השחקנים להם הוא נאמן ילוהקו למשחק. (מעבר לכך אין אילוצים נוספים, ובפרט, איננו מחויבים ללהק מספר מסוים של שחקנים, או לגייס מספר מסוים של משקיעים). בחירה חוקית של שחקנים ומשקיעים הינה בחירה שמקיימת את אילוצי הנאמנות. בבעיית ההפקה מחפשים בחירה חוקית כך שיתקבל רווח מרבי, כשהרווח הינו סך כל המימון מן המשקיעים פחות סך כל המשכורות לשחקנים. בשאלה זו נפתור את בעיית ההפקה בעזרת בנייה של רשת זרימה, כך שהזרימה המרבית ברשת תגדיר את הפתרון האופטימלי לבעיית ההפקה. מעבר לקדקודי המקור והיעד, יהיו ברשת קדקוד יחיד לכל שחקן, וקדקוד יחיד לכל משקיע. המפתח לפתרון נכון הינו התשובה לשאלה הבאה: אילו צלעות/קיבול ות יש להגדיר בין קדקודי-משקיעים לבין קדקודי-שחקנים ברשת, כך שזרימה מרבית תגדיר (בפרט) פתרון חוקי לבעיית ההפקה. ענו על 3 הסעיפים הבאים. שימו לב: סעיף (ג) מופיע בעמוד הבא. (הנכם רשאים להניח שהרווח המרבי חיובי ממש. אין צורך לנתח יעילות). (א) מהן הצלעות ברשת ומהן הקיבולות שלהן? (ב) מדוע זרימה מרבית ברשת מגדירה בחירה חוקית של שחקנים ומשקיעים? (ג) הוכיחו שזרימה מרבית ברשת מגדירה בחירה אופטימלית של שחקנים ומשקיעים.

רמז: ניתן למדל את בעיית מקסום הרווח כבעיית חתך מינימלי ברשת זרימה. חשבו כיצד לייצג את הרווחים והעלויות כקיבולים של צלעות שייחתכו, ואת האילוצים כצלעות שלא ניתן לחתוך.

פתרון: נבנה רשת זרימה באופן הבא, אשר פתרון בעיית הזרימה המרבית בה יפתור את בעיית ההפקה. **(א) בניית הרשת: צלעות וקיבולות** הרשת $G=(V,E)$ תכלול את הרכיבים הבאים: 1. **קודקודים**: קודקוד מקור $s$ וקודקוד בור $t$. לכל שחקן $A_i$ (עבור $i=1, \ ext{...}, n$) נוסיף קודקוד $v_i$. לכל משקיע $I_k$ (עבור $k=1, \text{...}, m$) נוסיף קודקוד $u_k$. 2. **צלעות רווח (מהמקור)**: לכל משקיע $I_k$, נוסיף צלע $(s, u_k)$ עם קיבול $c(s, u_k) = P_k$. צלעות אלו מייצגות את ההשקעה הפוטנציאלית של כל משקיע. 3. **צלעות עלות (אל הבור)**: לכל שחקן $A_i$, נוסיף צלע $(v_i, t)$ עם קיבול $c(v_i, t) = W_i$. צלעות אלו מייצגות את השכר שיש לשלם לכל שחקן אם ילוהק. 4. **צלעות אילוצים (בין שחקנים למשקיעים)**: צלעות אלו יאכפו את אילוצי הנאמנות. הקיבול שלהן יהיה אינסופי ($\\infty$) כדי למנוע מצב שבו בחירה אינה חוקית. * אם שחקן $A_i$ נאמן למשקיע $I_k$, נוסיף צלע $(v_i, u_k)$ עם קיבול $c(v_i, u_k) = \infty$. צלע זו מבטיחה שאם נבחר בשחקן $A_i$, נהיה חייבים לבחור גם במשקיע $I_k$. * אם משקיע $I_k$ נאמן לשחקן $A_i$, נוסיף צלע $(u_k, v_i)$ עם קיבול $c(u_k, v_i) = \infty$. צלע זו מבטיחה שאם נבחר במשקיע $I_k$, נהיה חייבים לבחור גם בשחקן $A_i$. **(ב) מדוע זרימה מרבית מגדירה בחירה חוקית** לפי **משפט זרימה-מרבית חתך-מינימלי**, ערך הזרימה המרבית ברשת שווה לקיבול של החתך המינימלי המפריד בין $s$ ל-$t$. יהי $(S, T)$ חתך $s-t$ מינימלי כלשהו ברשת, כאשר $s \in S$ ו-$t \in T$. החתך מגדיר בחירה של שחקנים ומשקיעים באופן הבא: * שחקן $A_i$ נבחר אם ורק אם הקודקוד המתאים לו, $v_i$, נמצא בקבוצה $S$. * משקיע $I_k$ נבחר אם ורק אם הקודקוד המתאים לו, $u_k$, נמצא בקבוצה $S$. כדי שהבחירה תהיה **חוקית**, עליה לקיים את כל אילוצי הנאמנות. נראה שבניית הרשת שלנו מבטיחה זאת. קיבול החתך המינימלי חייב להיות סופי (בהינתן שהרווח המרבי חיובי, סך ההשקעות סופי). חתך בעל קיבול סופי אינו יכול לחצות צלע עם קיבול אינסופי. לכן: * אם שחקן $A_i$ נאמן למשקיע $I_k$, קיימת צלע $(v_i, u_k)$ עם קיבול $\infty$. אם נבחר ב-$A_i$ (כלומר $v_i \in S$), לא ייתכן ש-$I_k$ לא ייבחר (כלומר $u_k \in T$), כי אז החתך יחצה את הצלע האינסופית. מכאן שאם $v_i \in S$, בהכרח גם $u_k \in S$. האילוץ מתקיים. * באופן דומה, אם משקיע $I_k$ נאמן לשחקן $A_i$, קיימת צלע $(u_k, v_i)$ עם קיבול $\infty$. אם נבחר ב-$I_k$ (כלומר $u_k \in S$), לא ייתכן ש-$A_i$ לא ייבחר (כלומר $v_i \in T$). מכאן שאם $u_k \in S$, בהכרח גם $v_i \in S$. האילוץ מתקיים. לסיכום, כל חתך $s-t$ סופי ברשת (ובפרט חתך מינימלי) מגדיר בחירה חוקית של שחקנים ומשקיעים. $\blacksquare$ **(ג) הוכחה שהבחירה היא אופטימלית** נראה כי הבחירה המוגדרת על ידי חתך מינימלי משיאה את הרווח. יהי $(S, T)$ חתך $s-t$ כלשהו המגדיר בחירה חוקית. ה**רווח** של בחירה זו הוא סך ההשקעות מהמשקיעים שנבחרו פחות סך המשכורות לשחקנים שנבחרו: $$ \text{Profit}(S,T) = \sum_{k: u_k \in S} P_k - \sum_{i: v_i \in S} W_i $$ קיבול החתך $(S,T)$, המסומן $C(S,T)$, הוא סכום הקיבולים של הצלעות $(x,y)$ כך ש-$x \in S$ ו-$y \in T$. מכיוון שהחתך מגדיר בחירה חוקית, הוא אינו חוצה צלעות עם קיבול אינסופי. הצלעות היחידות שנחתכות הן: 1. צלעות $(s, u_k)$ עבורן $s \in S$ ו-$u_k \in T$. אלו הם המשקיעים ש**לא נבחרו**. 2. צלעות $(v_i, t)$ עבורן $v_i \in S$ ו-$t \in T$. אלו הם השחקנים ש**נבחרו**. לכן, קיבול החתך הוא: $$ C(S,T) = \sum_{k: u_k \in T} P_k + \sum_{i: v_i \in S} W_i $$ נסמן את סך ההשקעות הפוטנציאליות ב-$P_{\text{total}} = \sum_{k=1}^m P_k$. נשים לב כי $\sum_{k: u_k \in S} P_k = P_{\text{total}} - \sum_{k: u_k \in T} P_k$. נציב זאת בנוסחת הרווח: $$ \text{Profit}(S,T) = \left( P_{\text{total}} - \sum_{k: u_k \in T} P_k \right) - \sum_{i: v_i \in S} W_i = P_{\text{total}} - \left( \sum_{k: u_k \in T} P_k + \sum_{i: v_i \in S} W_i \right) $$ קיבלנו את הקשר הישיר בין הרווח לקיבול החתך: $$ \text{Profit}(S,T) = P_{\text{total}} - C(S,T) $$ מכיוון ש-$P_{\text{total}}$ הוא ערך קבוע שאינו תלוי בבחירה, **מקסום הרווח** שקול ל**מינמום קיבול החתך** $C(S,T)$. אלגוריתם למציאת זרימה מרבית מוצא למעשה חתך מינימלי, אשר כפי שהראנו מגדיר בחירה חוקית. לכן, הבחירה המוגדרת על ידי החתך המינימלי היא **בחירה אופטימלית** המשיאה את הרווח. $\blacksquare$