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

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

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

ראו גם[עריכת קוד מקור | עריכה]