משתמש: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})$ .