מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 11/תשובות

1

את התשובה נפריד לשני חלקים: זיהוי מעגלים שליליים, ומציאת ארביטראז'.

זיהוי מעגלים שליליים

כידוע, אם יש מעגל שלילי בגרף, המושג מסלול זול ביותר איננו כלל מוגדר (אין מסלול סופי שהוא הזול ביותר). בפרט, אלגוריתם Floyd-Warshall לא יחזיר את התשובה הנכונה.

עם זאת, קל לחזור על ההוכחה של אלגוריתם Floyd-Warshall ולהווכח בנכונות הטענה הבאה. אם יש מעגל שלילי, האלגוריתם יחזיר מטריצה שבה יש לפחות מספר שלילי אחד באלכסון המטריצה (מעגל שלילי פירושו שאפשר להגיע מצומת לעצמו במחיר קטן מ0).

מציאת ארביטראז'

נבנה גרף חדש שבו הצמתים מתאימים למטבעות השונים, והקשתות מתארות המרות בין המטבעות. אם אפשר להמיר מטבע אחד למטבע שני ביחס $\displaystyle p$, אז נייחס מחיר $\displaystyle \log(1/p)$ לקשת. נשים לב שאם יש ארביטראז', אז קיימת סדרת המרות המקיימת $\displaystyle p_{1}\cdot p_{2}\cdots p_{k}>1$. תנאי זה שקול לתנאי $\displaystyle \log \left(1/p_{1}\right)+\log \left(1/p_{2}\right)+\cdots +\log \left(1/p_{k}\right)=\log \left(1/(p_{1}\cdot p_{2}\cdots p_{k})\right)<\log(1)=0$. התנאי לארביטראז' בטבלה, לכן, שקול לתנאי למעגל שלילי בגרף החדש.

2

נניח שמצאנו זרימה חוקית כלשהי, המתאימה $\displaystyle f_{u,v}$ לכל שני צמתים $\displaystyle u,v\in V$. נניח גם שברשת השיורית יש מסלול משפר בעל קיבול $\displaystyle k$. נסמן מסלול זה כ$\displaystyle u_{1}\rightarrow u_{2}\rightarrow \ldots \rightarrow u_{m}$. נשים לב ש$\displaystyle u_{1}=s$ ו$\displaystyle u_{m}=t$. מכאן נוכל להסיק את הדברים הבאים:

1. מספר הקשתות הנכנס ל$\displaystyle s$ במסלול זה קטן ב1 ממספר הקשתות היוצאות ממנו.
2. מספר הקשתות היוצא מ$\displaystyle t$ במסלול זה קטן ב1 ממספר הקשתות הנכנסות אליו.
3. לכל צומת אחר המופיע במסלול, מספר הקשתות הנכנס אליו במסלול שווה בדיוק למספר הקשתות היוצא ממנו.

שימו לב: ודא שלא הנחת במובלע שכל צומת מופיע בדיוק פעם אחת בדיוק במסלול. זה רק מקרה פרטי (שאמנם מתאים למקרה הכללי המתואר בשלושת הכללים הקודמים).

נקח את הזרימה החוקית, נזרים עוד $\displaystyle k$ יחידות בכל קשת במסלול המשפר, ונראה מה קורה לזרימה.

1. לאחר השיפור, הזרימה הישירה בין שני צמתים היא $\displaystyle f_{u,v}$ אם $\displaystyle (u,v)$ אינו שייך למסלול המשפר, ו$\displaystyle f_{u,v}+k$ אם $\displaystyle (u,v)$ שייך למסלול המשפר. במקרה השני חייב להתקיים $\displaystyle c_{u,v}-f_{u,v}\geq k$, משום שאם לא כן, לא ייתכן שקיבול המסלול היה $\displaystyle k$. לכן בהכרח $\displaystyle f_{u,v}+k\leq c_{u,v}$.
2. הסימטריה ההפכית אינה מופרת, משום שבחרנו בפרשנות לפיה אם אנו מזרימים עוד $\displaystyle k$ יחידות מ$\displaystyle u$ ל$\displaystyle v$, מזרימים פחות $\displaystyle k$ יחידות מ$\displaystyle v$ ל$\displaystyle u$.
3. שימור הזרם אינו מופר. נקח צומת $\displaystyle v\in V\ \{s,t\}$ שנמצא על המסלול. לפי טענה 3 למעלה, אם $\displaystyle (u,v)$ במסלול (עבור $\displaystyle u$ כלשהו), אז גם $\displaystyle (v,w)$ במסלול (עבור $\displaystyle w$ כלשהו). אך זה אומר שהזרימה מהצומת החוצה אינה משתנה, כי $\displaystyle f_{u,v}+k-(f_{v,w}+k)=f_{u,v}+f_{w,v}$.

מה קורה לגודל הזרימה? נתבונן ב$\displaystyle \sum _{v\in V}[f_{s,v}]$. עפ"י טענה 1 למעלה, גודל זה גדל ב$\displaystyle k$ בדיוק.

3

1

התרשים הבא מראה דוגמה נגדית לטענה.

דוגמה נגדית.

בגרף זה כל הקיבולים שלמים (כל אחד מהם הוא 1). הזרימות מתוארות בסוגריים, ולא כולן שלמות. קל לראות שהזרימה מירבית, מפני שגודל הזרימה (שהוא 1) הוא בדיוק גודל קיבול החתך בין 4 ל5.

2

נראה באינדוקציה ששיטת Ford-Fulkerson תזרים יחידות שלמות במקרה זה.

הוכחה: בכל איטרציה מוצאים מסלול משפר ברשת השיורית, ומשפרים דרכו. האינדוקציה היא על מספר האיטרציה.

(בסיס האינדוקציה) הרשת השיורית היא בתחילה רשת שלמה - קיבולי הקשתות חיוביים, והזרימה היא 0. לכן כל קיבול במסלול משפר הוא שלם. הזרימה המשפרת גם היא תהיה שלמה.

(מעבר האינדוקציה) נניח שכל הזרימות שלמות. אז שוב כל קיבול במסלול משפר הוא שלם - הקיבול השיורי הוא ההפרש בין הקיבול (שהוא שלם) לזרימה (שמהנחת האינדוקציה היא שלמה). הזרימה המשפרת גם היא תהיה שלמה.

היות שהזרימה היא שלמה, אז כל איטרציה של Ford-Fulkerson תשפר את הזרימה ב1 לפחות. מספר האיטרציות, לכן, חסום.

3

הטענה נכונה, והיא נובעת מהסעיף הקודם.

שיטת Ford-Fulkerson תפעל בזמן סופי במקרה זה, והיא תזרים זרימה שלמה. כשהשיטה עצרה את פעולתה, לא היה מסלול משפר ברשת השיורית. כבר למדנו שנובע מכך שהזרימה היא מירבית.

4

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

1. הזרימה היוצאת מ$\displaystyle s_{i}$ היא $\displaystyle x_{i}$.
2. מתקיימות הווריאציות הבאות של זרימה חוקית:
   1. (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; $\displaystyle \forall _{u,v\in V}f_{u,v}\leq c_{u,v}$.
   2. (סימטריה הפכית) הזרימה הישירה מצומת $\displaystyle u$לצומת $\displaystyle v$היא מינוס הזרימה הישירה מצומת

$\displaystyle v$לצומת $\displaystyle u$;‏ $\displaystyle \forall _{u,v\in V}f_{u,v}=-f_{v,u}$.

1. 1. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים $\displaystyle s_{1},\ldots ,s_{m}$ו$\displaystyle t$, הצומת אינו אוגר או מייצר זרם; $\displaystyle \forall _{u\in V\setminus \{s_{1},\cdots ,s_{m},t\}}\sum _{v\in V}f_{u,v}=0$.(שים לב שרק הדרישה השלישית השתנתה.)

נבנה, לכן, גרף חדש. נוסיף בו שני צמתים $\displaystyle s$ו$\displaystyle t$, ועוד מספר קשתות. הגרף החדש מתואר להלן:

גרף הפתרון.

בגרף החדש, כל קשת מהצורה $\displaystyle (s,s_{i})$בעלת הקיבול $\displaystyle x_{i}$, וכל קשת מהצורה $\displaystyle (t_{j},t)$בעלת הקיבול $\displaystyle \infty$.

נבדוק בגרף החדש האם יש זרימה מ$\displaystyle s$ל$\displaystyle t$בגודל $\displaystyle \sum _{i=1}^{m}[x_{i}]$.

משפט: יש פתרון לבעיה החדשה \Leftrightarrow יש פתרון לבעיה המקורית.

הוכחה: (⇐) נניח שיש פתרון לבעיה החדשה (כלומר, אכן יש זרימה שגודלה $\displaystyle \sum _{i=1}^{m}[x_{i}]$). נתבונן בחתך הבא:

חתך בפתרון.

מה נוכל לראות מחתך זה וממגבלות הזרימה? מצד אחד, גודל הזרימה כאן הוא $\displaystyle \sum _{i=1}^{m}[f_{s,s_{i}}]=\sum _{i=1}^{m}[x_{i}].$

מצד שני, מגבלת קיבול החתך על זרימת החתך אומרת כי $\displaystyle \sum _{i=1}^{m}[f_{s,s_{i}}]\leq \sum _{i=1}^{m}[c_{s,s_{i}}]=\sum _{i=1}^{m}[x_{i}].$

מכאן קל לראות שבהכרח, לכל $\displaystyle i$, $\displaystyle f_{s,s_{i}}=x_{i}.$

5

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\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 בעלת קיבול 1
2. קשת מ$\displaystyle s$ לכל $\displaystyle s_{i}$ בעלת קיבול 1
3. קשת מכל $\displaystyle t_{j}$ ל$\displaystyle t$ בעלת קיבול $\displaystyle P[j]$

.

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

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

הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות מ$\displaystyle s_{i}$ ל$\displaystyle t_{j}$ יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

.

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

משפט: סיבוכיות האלגוריתם $\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\}$