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

קשת שיורית נעלמת ומופיעה

שאלה

נתונה רשת זרימה כלשהי. מנסים למצוא זרימה מירבית בעזרת שיטת Ford-Fulkerson. נזכר שהרשת השיורית משתנה בכל אירטציה.

אנא הוכח או הפרך את הטענה הבאה. אם באיטרציה i נעלמת הקשת $\displaystyle e$ מגרף הרשת השיורית, אז $\displaystyle e$ לא תופיע בגרפי הרשתות השיוריות באיטרציות לאחר $\displaystyle i$.

תשובה

הטענה אינה נכונה.

נתבונן ברשת שבתרשים הבא:

הרשת המקורית.

הרשת השיורית זהה בשלב זה לרשת המקורית. נניח שמשפרים ראשית דרך המסלול $\displaystyle s\rightarrow u\rightarrow v\rightarrow t$. הרשת השיורית נראית כך:

לאחר שיפור ראשון.

שים לב שהקשת $\displaystyle (u,v)$ נעלמה מהרשת השיורית. $\displaystyle (u,v)$ נעלמה מהרשת השיורית. כעת נניח שמשפרית דרך המסלול $\displaystyle s\rightarrow v\rightarrow u\rightarrow t$. אז הרשת השיורית נראית כך:

לאחר שיפור נוסף.

שים לב שהקשת $\displaystyle (u,v)$ חזרה לרשת השיורית.

זרימה מירבית בקיבולים מוגבלי שורש

שאלה

נתונה רשת זרימה שבה גרף $\displaystyle G=(V,E)$. נתון שהחתך הקטן ביותר (מבחינת גודל הקיבול) הוא $\displaystyle {\sqrt {|E|}}$.

1. נתון שכל אחד מקיבולי הרשת הוא מספר שלם. אנא הצע שיטה יעילה למציאת הזרימה המירבית.
2. אנא חזור על הסעיף הקודם, אך עתה אל תניח שכל אחד מהקיבולים הוא מספר שלם.

תשובה

1. נריץ את אלגוריתם Edmonds-Karp, אך ננתח אותו בצורה עדינה יותר, תוך לקיחה בחשבון שכל אחד מהקיבולים הוא מספר שלם, ושאנו יודעים את גודל קיבול החתך הקטן ביותר. עפ"י המשפט המשפט Max-Flow Min-Cut ונתוני השאלה, אנו יודעים שגודל הזרימה המירבית כאן הוא $\displaystyle {\sqrt {|E|}}$. מנתוני השאלה גם קל לראות שכל איטרציה משפרת את הזרימה בלפחות יחידה אחת. מכאן נובע שיש לכל היותר $\displaystyle {\sqrt {|E|}}$ איטרציות. כל איטרציה מפעילה את אלגוריתם BFS, שבמקרה כאן יעבוד בזמן $\displaystyle \Theta (|E|)$. הסיבוכיות הכללית, לכן, היא $\displaystyle \Theta ({\sqrt {|E|}}\cdot |E|)$
2. גם הפעם נריץ את אלגוריתם Edmonds-Karp, אך לא נוכל לחזור על הניתוח שבסעיף הקודם (מדוע?). כל שנוכל לטעון הוא שהסיבוכיות היא $\displaystyle O(|E|^{2}\cdot |V|)$.

שיטת Ford-Fulkerson ברשת זרימה שלמה

שאלה

שאלה זו מובילה משיטת Ford-Fulkerson לאלגוריתם Ford-Fulkerson.

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

נתונה רשת זרימה שבה גרף $\displaystyle G=(V,E)$.

הגדרה: נאמר שרשת זרימה היא שלמה אם הקיבול $\displaystyle c_{u,v}$ הוא מספר שלם לכל $\displaystyle u,v\in V$. נאמר שזרימה היא שלמה אם הזרימה $\displaystyle f_{u,v}$ היא מספר שלם לכל $\displaystyle u,v\in V$.

1. נתונה רשת זרימה שלמה. האם כל זרימה מירבית היא בהכרח שלמה? אנא הוכח או הראה דוגמה נגדית.
2. אנא הראה ששיטת Ford-Fulkerson פועלת מספר סופי של איטרציות במקרה של רשת זרימה שלמה.
3. בהנתן רשת זרימה שלמה, האם בהכרח קיימת זרימה מירבית שהיא שלמה? אנא הוכח או הראה דוגמה נגדית.

תשובה

1

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

דוגמה נגדית.

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

2

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

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

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

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

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

3

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

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

רשת זרימה שלמה

שאלה

נתונה רשת זרימה שבה גרף $\displaystyle G=(V,E)$.

הגדרה: נאמר שרשת זרימה היא שלמה אם הקיבול $\displaystyle c_{u,v}$ הוא מספר שלם לכל $\displaystyle u,v\in V$. נאמר שזרימה היא שלמה אם הזרימה $\displaystyle f_{u,v}$ היא מספר שלם לכל $\displaystyle u,v\in V$.

אנא הוכח או הפרך כל אחת מהטענות הבאות.

1. ברשת זרימה שלמה, תמיד קיימת זרימה מירבית שהיא שלמה.
2. ברשת זרימה שלמה, כל זרימה מירבית היא שלמה.
3. ברשת זרימה שלמה שכל אחד מקיבוליה קטן מ7, מספר האיטרציות של אלגוריתם Ford-Fulkerson הוא $\displaystyle O(|E|)$.
4. ברשת זרימה, לאו דוקא שלמה, שכל אחד מקיבוליה קטן מ7, מספר האיטרציות של אלגוריתם Ford-Fulkerson הוא $\displaystyle O(|E|)$.

תשובה

1

הטענה נכונה.

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

2

הטענה אינה נכונה.

להלן דוגמה נגדית.

.

ברשת הזרימה הזו, קל מאד לראות שהזרימה המירבית בגודל 1.

להלן זרימה בגודל 1 שאינה זרימה שלמה:

.

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

3

הטענה נכונה.

נתבונן בחתך כלשהו בגרף. מספר הקשתות שחוצות אותו (מ$\displaystyle S$ ל$\displaystyle T$) הוא לכל היותר $\displaystyle |E|$. על פי נתוני השאלה, כל אחד מקיבולי הקשתות קטן מ7. לכן, קיבול החתך הוא לכל היותר $\displaystyle 6|E|$. היות שהדבר נכון לכל חתך, הוא נכון גם לחתך הקטן ביותר (מבחינת גודל הקיבול). לכן, עפ"ׁי המשפט Max-Flow Min-Cut, גודל הזרימה המירבית הוא לכל היותר $\displaystyle 6|E|$. היות שכל אחד מקיבולי הקשתות הוא מספר שלם, אז כל איטרציה של אלגוריתם ford-Fulkerson תשפר את הזרימה בלפחות 1. מספר האיטרציות לכן הוא לכל היותר $\displaystyle 6|E|=O(|E|)$.

4

הטענה אינה נכונה.

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

.

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

.

נניח שהמסלול המשפר הראשון שבחרנו הוא $\displaystyle s\rightarrow u\rightarrow v\rightarrow t$ (ולכן הזרימה בסוף האיטרציה הראשונה היא בגודל $\displaystyle 1/|E|^{2}$). התרשים הבא מראה את גרף הרשת השיורית בשלב זה.

.

מתרשים זה אפשר לראות שיש כעת שיפור שגם הוא בעל גודל $\displaystyle 1/|E|^{2}$: השיפור דרך המסלול < math dir = "ltr">\displaystyle s \rightarrow v \rightarrow u \rightarrow t</math> (ולכן הזרימה בסוף האיטרציה השניה היא בגודל $\displaystyle 2/|E|^{2}$).

קל להראות (פורמלית, באינדוקציה), שאפשר לבצע $\displaystyle m$ שיפורים (בזוגות), כך שכל שיפור אי-זוגי יהיה דרך $\displaystyle s\rightarrow u\rightarrow v\rightarrow t$, כל שיפור זוגי יהיה דרך $\displaystyle s\rightarrow v\rightarrow u\rightarrow t$, וגודל הזרימה יהיה $\displaystyle m/|E|^{2}$.

היות שגודל הזרימה המירבית הוא 2, אז מספר האיטרציות $\displaystyle m$ הוא פתרון המשוואה $\displaystyle m/|E|^{2}=2$, ולכן $\displaystyle m=2\cdot |E|^{2}=\Theta (|E|^{2})$.

מערך הייצור בקונצרן אישימוטו

שאלה

קונצרן המכוניות היפני אישימוטו מעוניין להעביר את מערך הייצור שלו לישראל. הגרף הבא מתאר את המצב בישראל. הצמתים $\displaystyle s_{1},\ldots ,s_{m}$ מתארים את מיקומם של המפעלים שהקונצרן רוצה לבנות. הצמתים $\displaystyle t_{1},\ldots ,t_{n}$ מתארים נמלים (דרכם שולחים את המכוניות לחו"ל). שאר הצמתים הם צמתי ביניים. הקשתות מתארות כבישים, וקיבוליהם מתארים את מספר המכוניות ליחידת זמן שאפשר לשלוח דרכם.

נתונים המספרים $\displaystyle x_{1},\ldots ,x_{m}$, המתארים את מספר המכוניות לשעה שהקונצרן מתכנן לייצור ב$\displaystyle s_{1},\ldots ,s_{m}$. אנא מצא אלגוריתם יעיל המוצא האם המפעלים יוכלו לייצר מכוניות כך שלא ייווצר צואר בקבוק. (הנח שכל נמל מסוגל לטפל בכל כמות מכוניות ליחידת זמן).

.

תשובה

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

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}.$

יריד תעסוקה 1

שאלה

ליריד התעסוקה של האוניברסיטה הגיעו $\displaystyle m$ סטודנטים, $\displaystyle 1,\ldots m$, ו$\displaystyle n$ חברות, $\displaystyle 1,\ldots n$. נניח שכל סטודנט מוכן לעבוד בחברה אחת או יותר, וכל חברה מוכנה להעסיק סטודנט אחד או יותר, אך כל סטודנט יכול לעבוד בחברה אחת לכל היותר, וכל חברה יכולה להעסיק סטודנט אחד לכל היותר.

נתון מערך רצון התעסוקה W, שבו $\displaystyle r$ זוגות. אם הזוג (i, j) מופיע בW, אז המשמעות היא שסטודנט $\displaystyle i$ מוכן לעבוד בחברה $\displaystyle j$, וחברה $\displaystyle j$ מוכנה להעסיק את סטודנט $\displaystyle i$.

רוצים למצוא את השמת הסטודנטים לחברות כך שמספר רב ככל האפשר של סטודנטים יעבדו. אנא הסבר כיצד לכתוב אלגוריתם יעיל המקבל את המערך $\displaystyle W$, ומוציא מערך גדול ככל האפשר W', כך שיתקיימו התנאים הבאים:

1. אם הזוג (i, j) מופיע בW', אז הוא גם מופיע בW.
2. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו הראשון $\displaystyle i$.
3. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו השני $\displaystyle j$.

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

תשובה

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\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\}$

יריד תעסוקה 2

שאלה

ליריד התעסוקה של האוניברסיטה הגיעו $\displaystyle m$ סטודנטים, $\displaystyle 1,\ldots m$, ו$\displaystyle n$ חברות, $\displaystyle 1,\ldots n$. נניח שכל סטודנט מוכן לעבוד בחברה אחת או יותר, וכל חברה מוכנה להעסיק סטודנט אחד או יותר, אך כל סטודנט יכול לעבוד בחברה אחת לכל היותר, וכל חברה יכולה להעסיק מספר ידוע של סטודנטים, שהוא לפחות 1.

נתון מערך רצון התעסוקה W, שבו $\displaystyle r$ זוגות. אם הזוג (i, j) מופיע בW, אז המשמעות היא שסטודנט $\displaystyle i$ מוכן לעבוד בחברה $\displaystyle j$, וחברה $\displaystyle j$ מוכנה להעסיק את סטודנט $\displaystyle i$. כמו כן, נתון מערך פוטנציאל ההעסקה P, שבו $\displaystyle n$ מספרים שלמים. P[j] מתאר את מספר המשרות הפנויות בחברה $\displaystyle j$ .

רוצים למצוא את השמת הסטודנטים לחברות כך שמספר רב ככל האפשר של סטודנטים יעבדו. אנא הסבר כיצד לכתוב אלגוריתם יעיל המקבל את המערך $\displaystyle W$, ומוציא מערך גדול ככל האפשר W', כך שיתקיימו התנאים הבאים:

1. אם הזוג (i, j) מופיע בW', אז הוא גם מופיע בW.
2. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו הראשון $\displaystyle i$.
3. מספר הזוגות מהצורה (i, j) בW' בעלי אותו $\displaystyle j$, הוא לכל היותר $\displaystyle P[j]$.

תשובה

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\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\}$

מציאת מסלולים זרים

שאלה

נתונים גרף מכוון $\displaystyle G=(V,E)$, וכן שני צמתים $\displaystyle s,t\in V$.

א'

הגדרה: נאמר ששני מסלולים הם זרים בקשתות אם אין להם אף קשת משותפת. נאמר שקבוצת מסלולים היא זרה בזוגות בקשתות אם כל זוג מסלולים בה הוא של מסלולים זרים בקשתות.

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

ב'

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

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

תשובה

א'

נבנה רשת זרימה בה הגרף הוא הגרף המקורי, ולכל קשת יש קיבול 1. נריץ אלגוריתם זרימה המבטיח זרימות שלמות (כמו, לדוגמה, אלגוריתם Edmonds-Karp. קל להראות שבזרימה המירבית, כל קשת תזרים 0 או 1 (יש בדיוק שתי אפשרויות). קל להראות שהקשתות בהן יש זרימה 1 - הן בדיוק הפתרון לבעיה.

ב'

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

דוגמה: בתרשים הבא, החלק העליון מראה צומת $\displaystyle u$ בגרף המקורי. יש שלוש קשתות שנכנסות אליו, ושתי קשתות שיוצאות ממנו. התמרת הצמתים. החלק התחתון מראה את הצומת לאחר ההפרדה. הצומת הופרד לשני צמתים, $\displaystyle u_{in}$ ו$\displaystyle u_{out}$. שלוש הקשתות שנכנסו ל$\displaystyle u$ בגרף המקורי נכנסות כעת ל$\displaystyle u_{in}$; שתי הקשתות שיצאו מ$\displaystyle u$ בגרף המקורי יוצאות כעת מ$\displaystyle u_{out}$. בגרף החדש, נמתחה קשת $\displaystyle e'_{u}$ מ$\displaystyle u_{in}$ ל$\displaystyle u_{out}$.

כעת נקבע קיבולים לקשתות בגרף החדש. עבור כל קשת בגרף המקורי (לדוגמה $\displaystyle e_{2}$), נתן לה קיבול אינסוף. עבור כל קשת חדשה בגרף החדש (לדוגמה, $\displaystyle e'_{u}$), נתן לה קיבול 1.

נמשיך מכאן כבסעיף הקודם.