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

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

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

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

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

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

רשת זרימה מורכבת מגרף \ G=(V,E), משני צמתים מיוחדים - המקור (Source) \ s\isin V והבור (Sink) \ t\isin 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\isin S,t\isin T.

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

\ c(S,T)=\sum_{u\isin S,v\isin T}c(u,v)

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

  1. אנטי-סימטריה: \ f(u,v)=-f(v,u)
  2. שמירה על אילוץ הקיבול: \ f(u,v)\le c(u,v)
  3. שימור הזרימה: לכל \ u\ne s,t מתקיים: \ \sum_{v\in V}f(u,v)=0

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

עבור רשת זרימה \ G=(V,E) עם פונקציית קיבול \ c וזרימה חוקית \ f:V\times V\to\mathbb{R} הגרף השיורי הוא רשת זרימה עם אותה קבוצת צמתים וקשתות כך שהקיבול של קשת (u,v) הוא c(u,v) -f(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 היא מיידית שכן קל להראות שהערך של כל זרימה קטן או שווה לקיבולו של כל חתך בגרף.

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