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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה צמתים:

  1. צמתים , אחד לכל סטודנט
  2. צמתים , אחד לכל חברה
  3. צומת מקור וצומת בור

נגדיר כ את Length(W).

בגרף יש קשתות:

  1. קשת אחת לכל איבר בW בעלת קיבול 1
  2. קשת מ לכל בעלת קיבול 1
  3. קשת מכל ל בעלת קיבול
.
.

כעת נריץ את אלגוריתם Ford-Fulkerson. נחזיר כתשובה כל זוג שעבורו קיבלנו .



משפט:

האלגוריתם מחזיר תשובה נכונה.



הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות מ ל יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

.
.

נניח שיש קשת בין ל. בהכרח הקשת מזרימה 1. מצד שני, הקשת המזרימה מ ל מזרימה גם היא 1. משימור הזרם נובע אם כן שאין קשת אחרת היוצאת מ.טענה כמעט זהה מראה שאין קשת אחרת הנכנסת ל. ברור גם שקשת זו היתה שייכת לגרף המקורי. מכאן נובע שהמערך המוחזר W' אכן משייך אחת לאחת סטודנט לחברה, ואינו ממציא שיוכים שלא הופיעו במקור. קל גם לראות שכל חברה אינה מעסיקה יותר סטודנטים מיכולתה. קל לראות שאם יש התאמה גדולה יותר, אז אפשר להגיע לזרימה גדולה יותר מהמושגת כאן, וזאת בסתירה לנכונות Ford-Fulkerson.



משפט:

סיבוכיות האלגוריתם .



הוכחה: אם משתמשים ברשימת שכנויות, אז בניית הגרף החדש היא .כבר ראינו בניתוח אלגוריתם Ford-Fulkerson, שסיבוכיותו לינארית במספר הקשתות כפול גודל הזרימה המירבית. מספר הקשתות כאן הוא , והזרימה המירבית היא