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

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

בתורת הגרפים, משפט זרימה-מקסימלית חתך-מינימלי (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:

  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 היא מיידית שכן קל להראות שערך של כל זרימה קטן מקיבולו של כל חתך בגרף.

שפות אחרות