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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש
  1. נריץ את אלגוריתם Edmonds-Karp, אך ננתח אותו בצורה עדינה יותר, תוך לקיחה בחשבון שכל אחד מהקיבולים הוא מספר שלם, ושאנו יודעים את גודל קיבול החתך הקטן ביותר. עפ"י המשפט המשפט Max-Flow Min-Cut ונתוני השאלה, אנו יודעים שגודל הזרימה המירבית כאן הוא . מנתוני השאלה גם קל לראות שכל איטרציה משפרת את הזרימה בלפחות יחידה אחת. מכאן נובע שיש לכל היותר איטרציות. כל איטרציה מפעילה את אלגוריתם BFS, שבמקרה כאן יעבוד בזמן . הסיבוכיות הכללית, לכן, היא
  2. גם הפעם נריץ את אלגוריתם Edmonds-Karp, אך לא נוכל לחזור על הניתוח שבסעיף הקודם (מדוע?). כל שנוכל לטעון הוא שהסיבוכיות היא .