מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/יריד תעסוקה 1/תשובה

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\displaystyle m+n+2$ צמתים:

1. צמתים $\displaystyle s_{1},\ldots s_{m}$, אחד לכל סטודנט
2. צמתים $\displaystyle t_{1},\ldots t_{n}$, אחד לכל חברה
3. צומת מקור $\displaystyle s$ וצומת בור $\displaystyle t$

נגדיר כ$\displaystyle w$ את Length(W).

בגרף יש $\displaystyle w+m+n$ קשתות:

1. קשת אחת לכל איבר בW
2. קשת מ$\displaystyle s$ לכל $\displaystyle s_{i}$
3. קשת מכל $\displaystyle t_{j}$ ל$\displaystyle t$קיבולי כל אחת מהקשתות הוא 1.

.

כעת נריץ את אלגוריתם Ford-Fulkerson. נחזיר כתשובה כל זוג $\displaystyle (s_{i},t_{j})$ שעבורו קיבלנו $\displaystyle f_{s_{i},t_{j}}=1$.

משפט: האלגוריתם מחזיר תשובה נכונה.

הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

.

נניח שיש קשת בין $\displaystyle s_{i}$ ל$\displaystyle t_{j}$. בהכרח הקשת מזרימה 1. מצד שני, הקשת המזרימה מ$\displaystyle s$ ל$\displaystyle s_{i}$ מזרימה גם היא 1. משימור הזרם נובע אם כן שאין קשת אחרת היוצאת מ$\displaystyle s_{i}$. טענה כמעט זהה מראה שאין קשת אחרת הנכנסת ל$\displaystyle t_{j}$. ברור גם שקשת זו היתה שייכת לגרף המקורי. מכאן נובע שהמערך המוחזר W' אכן משייך אחת לאחת סטודנט לחברה, ואינו ממציא שיוכים שלא הופיעו במקור.

נסמן כ$\displaystyle w'$ את גודל W'. מניין לנו שאין התאמה גדולה יותר? נניח בשלילה שיש כזו, ונסמן את גודלה כ$\displaystyle w''$. אבל, מכאן נובע בהכרח (בסתירה לנכונות Ford-Fulkerson) שיש זרימה בגודל $\displaystyle w''$ בגרף החדש: קל למצוא $\displaystyle w''$ קשתות מ$\displaystyle s$ לצמתי הסטודנטים, ומצמתי החברות ל$\displaystyle t$, ובדיקה פשוטה של חוקי הזרימה החוקית מראים שאם מזרימה יחידה 1 בכל אחת מקשתות אלו, אז זו אכן זרימה חוקית.

משפט: סיבוכיות האלגוריתם $\displaystyle O((m+n+w)\cdot \min\{m,n,w\})$.

הוכחה: אם משתמשים ברשימת שכנויות, אז בניית הגרף החדש היא $\displaystyle \Theta (m+n+w)$.כבר ראינו בניתוח אלגוריתם Ford-Fulkerson, שסיבוכיותו לינארית במספר הקשתות כפול גודל הזרימה המירבית. מספר הקשתות כאן הוא $\displaystyle m+n+w$, והזרימה המירבית היא $\displaystyle \min\{m,n,w\}$