מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה שיורית וחתכים

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

תבנית:הארה

תבנית:הארה

הרשת השיורית

הרשת השיורית הנה רשת זרימה המתארת כמה עוד אפשר להזרים.

הגדרה

נניח רשת זרימה על גרף $G=(V,E)$,‏ וכן זרימה חוקית עליה $\{f_{u,v}\}$. הרשת השיורית מתארת כמה עוד אפשר להזרים ישירות בין שני צמתים, ומוגדרת כך. לוקחים כל זוג צמתים $u,v\in V$, ומגדירים להם את הקיבול השיורי, המתאר כמה עוד אפשר להזרים ישירות מ$u$ ל$v$. פורמלית: $c_{u,v}^f=c_{u,v}-f_{u,v}$.

גרף הרשת השיורית, $G^f=(V,E^f)$ מורכב מצמתי הגרף המקורי, ומהקשתות שקיבוליהן השיורי חיובי. לבסוף, צומת המקור והבור הם אלה מהרשת המקורית.

מסלול משפר

הגדרה

תבנית:מבנה תבנית

גודל זרימה ומסלולים משפרים

באופן לא מפתיע, מסלולים משפרים מצביעים כיצד להגביר את גודל הזרימה ברשת:

עד עתה ראינו שאם ברשת השיורית קיים מסלול משפר, אפשר להגדיל את הזרימה. האם הכוון ההפוך מתקיים? במילים אחרות, האם נכון בהכרח שאם ברשת השיורית אין מסלול משפר, אז אי אפשר להגדיל את הזרימה? התשובה היא כן - הכוון ההפוך גם הוא מתקיים. כדי להבין מדוע, נזדקק לחתכי S-T - מושג שכעת נראה.

חתכי S-T

הגדרה

תבנית:מבנה תבנית

{{הערה|1 = חתך S-T יכול להכיל גם קשתות מצומת ב$T$ לצומת ב$S$. חשוב להבין מההגדרות מהו קיבול החתך וזרימת החתך במקרים כאלה.

זרימה וחתכי S-T

ראשית נראה בשלושת המשפטים הבאים שגודל זרימת החתך מגביל את גודל הזרימה.

תבנית:משפט

להלן הוכחה של המשפט השני מבין השניים.

משילוב שני המשפטים הקודמים, קל לראות את המשפט הבא:

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

תבנית:משפט

תבנית:הוכחה

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס