משתמש:Amire80/ארגז חול

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