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

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