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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

קיבול של חתך מוגדר באמצעות סכום הקיבולים של הקשתות שמחברות בין שתי הקבוצות של החתך: $\ c(S,T)=\sum_{u\isin S,v\isin T}c(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\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.