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

בתורת הגרפים, משפט זרימה מקסימלית - חתך מינימלי (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$שאיחודן $V$ כך שאחת מהן מכילה את המקור והשנייה את הבור: $\ s\in S,t\in T$.

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

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

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

$min\ \{c(S,T):s\in S,t\in T,S\cup T=V,S\cap T=\emptyset \}$

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

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

1. אנטי-סימטריה: $\ f(u,v)=-f(v,u)$
2. שמירה על אילוץ הקיבול: $\ f(u,v)\leq c(u,v)$
3. שימור הזרימה: לכל $\ 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}$ הגרף השיורי (residual graph) הוא רשת זרימה עם אותה קבוצת צמתים וקשתות כך שהקיבול של קשת (u,v) הוא $c(u,v)-f(u,v)$.

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

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

גרסה נוספת

קיימת גם גרסה של המשפט בו ערכי הזרימה הם מספרים טבעיים (integral version), כלומר המשפט נכון גם כאשר פונקציית הזרימה היא $\ f:V\times V\to \mathbb {N}$.שאר ההגדרות והדרישות על פונקציית הזרימה נותרות בעינן. ראו גם

הוכחה

ראשית, אם $\ 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.

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

ראו גם

• בעיית זרימה

קישורים חיצוניים

• משפט זרימה מקסימלית - חתך מינימלי, באתר MathWorld (באנגלית)