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

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

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

תיאור פורמלי

בהינתן רשת זרימה $\ G=(V,E)$ עם פונקציית קיבול $\ c$, חתך ברשת הזרימה הוא חלוקה של צומתי הרשת לשתי קבוצות זרות $\ S,T$ כך שאחת מהן מכילה את המקור והשנייה את הבור: $\ s\isin S,t\isin T$.

קיבול של חתך מוגדר באמצעות סכום הקיבולים של הקשתות המצביעות מצומת בקבוצה $\ S$ לצומת בקבוצה $\ T$ (יש לשים לב שההגדרה אי-סימטרית):

$\ c(S,T)=\sum_{u\isin S,v\isin T}c(u,v)$

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

1. $\ f$ היא זרימה מקסימלית ברשת הזרימה.
2. הגרף השיורי של רשת הזרימה עבור הזרימה $\ f$ לא מכיל מסלולי שיפור.
3. כמות הזרימה שווה לקיבול של חתך כלשהו: $\ |f|=c(S,T)$.

הוכחה

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

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

קל לראות שקיבול החתך $\ (S,T)$ שווה לכמות הזרימה: אם $\ u\isin S, v\isin T$, אז בהכרח $\ f(u,v)=c(u,v)$, שכן אם היה מתקיים $\ f(u,v)>c(u,v)$ זו הייתה סתירה לאילוץ הקיבול של הזרימה, ואם היה מתקיים $\ f(u,v)<c(u,v)$, הרי שהקשת $\ (u,v)$ הייתה שייכת לגרף השיורי, ועל פי הגדרת החתכים שלנו, הקשת $\ (u,v)$ אינה שייכת אליו. לכן 2 גורר את 3.

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

ראו גם

• בעיית זרימה