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

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

ראשית נתרגם את השאלה לדרישות מדויקות מעט יותר. השאלה, למעשה, מבקשת לבדוק האם קיימת זרימה ברשת כך שיתקיימו הדברים הבאים:

  1. הזרימה היוצאת מ היא .
  2. מתקיימות הווריאציות הבאות של זרימה חוקית:
    1. (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; .
    2. (סימטריה הפכית) הזרימה הישירה מצומת לצומת היא מינוס הזרימה הישירה מצומת

לצומת ;‏ .

    1. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים ו, הצומת אינו אוגר או מייצר זרם; .(שים לב שרק הדרישה השלישית השתנתה.)

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

גרף הפתרון.
גרף הפתרון.

בגרף החדש, כל קשת מהצורה בעלת הקיבול , וכל קשת מהצורה בעלת הקיבול .

נבדוק בגרף החדש האם יש זרימה מלבגודל .



משפט:

יש פתרון לבעיה החדשה \Leftrightarrow יש פתרון לבעיה המקורית.



הוכחה: (⇐) נניח שיש פתרון לבעיה החדשה (כלומר, אכן יש זרימה שגודלה ). נתבונן בחתך הבא:

חתך בפתרון.
חתך בפתרון.

מה נוכל לראות מחתך זה וממגבלות הזרימה? מצד אחד, גודל הזרימה כאן הוא

מצד שני, מגבלת קיבול החתך על זרימת החתך אומרת כי

מכאן קל לראות שבהכרח, לכל ,