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

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

המשפט הוא מקרה פרטי של הדואליות של תכנון ליניארי ומכליל את משפט מנגר הקובע כי גרף הוא k-קשיר אם ורק אם בין כל שני קודקודים בגרף קיימים k מסלולים זרים בקודקודים והוא k-קשיר-קשתות אם ורק אם בין כל שני קודקודים בגרף קיימים k מסלולים זרים בקשתות.

תיאור פורמלי

רשת זרימה מורכבת מגרף $\ G=(V,E)$ , משני צמתים מיוחדים - המקור (Source) $\ s\in V$ והבור (Sink) $\ t\in V$ , ומפונקציית קיבול $\ c:V\times V\to \mathbb {R} ^{+}\cup \left\{\infty \right\}$ שמתאימה לכל זוג צמתים את כמות הזרימה המקסימלית שיכולה לעבור מהראשון שבהם אל השני (ויכולה להיות אינסופית, כלומר ללא הגבלה). אם לא קיימת קשת מ- $\ u$ אל $\ v$ , מניחים כי $\ c(u,v)=0$ .

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

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

\ c(S,T)=\sum _{u\in S,v\in T}c(u,v)

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

פונקציית זרימה $\ f:V\times V\to \mathbb {R}$ מתאימה לכל זוג צמתים $\ (u,v)$ את כמות הזרימה מ- $\ u$ אל $\ v$ (לכיוון יש חשיבות), כך שמתקיימים התנאים הבאים:

אנטי-סימטריה: $\ f(u,v)=-f(v,u)$
שמירה על אילוץ הקיבול: $\ f(u,v)\leq c(u,v)$
שימור הזרימה: לכל $\ u\neq s,t$ מתקיים: $\ \sum _{v\in V}f(u,v)=0$

הערך של זרימה היא הזרימה נטו שיוצאת מן המקור, כלומר $\ |f|=\sum _{v\in V}f(s,v)$ .

עבור רשת זרימה $\ G=(V,E)$ עם פונקציית קיבול $\ c$ וזרימה חוקית $\ f:V\times V\to \mathbb {R}$ הגרף השיורי הוא רשת זרימה עם אותה קבוצת צמתים וקשתות כך שהקיבול של קשת (u,v) הוא $c(u,v)-f(u,v)$ .

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

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

הוכחה

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

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

קל לראות שקיבול החתך $\ (S,T)$ שווה לכמות הזרימה: אם $\ u\in S,v\in 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.