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

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