משפט זרימה־מקסימלית חתך־מינימלי

מתוך ויקיפדיה, האנציקלופדיה החופשית

בתורת הגרפים, משפט זרימה-מקסימלית חתך-מינימלי (Max-flow min-cut) עוסק בזרימה המקסימלית שניתן להעביר ברשת זרימה. המשפט אומר את הדבר הבא:

• כמות הזרימה המקסימלית שניתן להעביר ברשת זרימה שווה לקיבול המינימלי של חתך ברשת.

[עריכה] תיאור פורמלי

בהינתן רשת זרימה עם פונקציית קיבול , חתך ברשת הזרימה הוא חלוקה של צומתי הרשת לשתי קבוצות זרות כך שאחת מהן מכילה את המקור והשנייה את הבור: .

קיבול של חתך מוגדר באמצעות סכום הקיבולים של הקשתות שמחברות בין שתי הקבוצות של החתך:

משפט זרימה-מקסימלית חתך-מינימלי אומר כי שלושת התנאים הבאים שקולים, עבור זרימה :

1. היא זרימה מקסימלית ברשת הזרימה.
2. הגרף השיורי של רשת הזרימה עבור הזרימה לא מכיל מסלולי שיפור.
3. כמות הזרימה שווה לקיבול של חתך כלשהו: .

[עריכה] הוכחה

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

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

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

הגרירה של 3 את 1 היא מיידית שכן קל להראות שערך של כל זרימה קטן מקיבולו של כל חתך בגרף.