דף זו הוא השני משלשה העוסק באלגוריתמים למציאת זרימת המקסימום בגרף מכוון המתאר "רשת צינורות". בסוף זרימה - הגדרות ראינו כיצד להגדיר במדויק רשת זרימה, זרימה חוקית, וגודל זרימה. בדף זה נראה רעיון כללי המאפשר לנו למצא זרימה חוקית בעלת גודל מירבי בהנתן רשת זרימה.
נניח רשת זרימה על גרף , וכן זרימה חוקית עליה . הרשת השיורית מתארת כמה עוד אפשר להזרים ישירות בין שני צמתים, ומוגדרת כך. לוקחים כל זוג צמתים , ומגדירים להם את הקיבול השיורי, המתאר כמה עוד אפשר להזרים ישירות מ ל. פורמלית:
.
גרף הרשת השיורית, מורכב מצמתי הגרף המקורי, ומהקשתות שקיבוליהן השיורי חיובי. לבסוף, צומת המקור והבור הם אלה מהרשת המקורית.
הגדרה:
בהינתן רשת זרימה , ,
ו, וזרימה חוקית עליה , אז הרשת השיורית היא הרשת בעלת אותו הגרף וצמתי המקור והבור, והקיבולים (הנקראים קיבולים שיוריים).
נניח שברשת שיורית יש מסלול מ ל על פני קשתות בעלי קיבול (שיורי) חיובי ממש. נאמר שהמסלול הוא מסלול משפר לזרימה ברשת המקורית.
דוגמה:
בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. לזרימה זו מתאימה הרשת השיורית המוצגת ב-B .C מראה מסלול משפר, כלומר מסלול מ ל ברשת השיורית על פני קשתות בעלי קיבול (שיורי) חיובי ממש.
מסלול משפר.
דוגמה:
בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. B מראה את הרשת השיורית. קל לראות שאין מסלול משפר מ ל ברשת השיורית, כלומר מסלול על פני קשתות בעלי קיבול (שיורי) חיובי ממש.
באופן לא מפתיע, מסלולים משפרים מצביעים כיצד להגביר את גודל הזרימה ברשת:
משפט:
נניח שברשת השיורית יש מסלול משפר, וקיבול המינימום בגרף השיורי לאורך המסלול הוא . אז אפשר להגדיל את הזרימה ברשת המקורית ב על ידי הזרמה נוספת במסלול
המשפר.
דוגמה:
כפי שראינו, בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. לזרימה זו מתאימה הרשת השיורית המוצגת בB .C מראה מסלול משפר, כלומר מסלול מ ל ברשת השיורית על פני קשתות בעלי קיבול (שיורי) חיובי ממש.
מסלול משפר.
במסלול המשפר כל הקשתות בעלי קיבול (שיורי) לפחות 1, ואכן, קל להווכח שאפשר להגדיל את הזרימה בA ב1.
עד עתה ראינו שאם ברשת השיורית קיים מסלול משפר, אפשר להגדיל את הזרימה. האם הכוון ההפוך מתקיים? במילים אחרות, האם נכון בהכרח שאם ברשת השיורית אין מסלול משפר, אז אי אפשר להגדיל את הזרימה? התשובה היא כן - הכוון ההפוך גם הוא מתקיים. כדי להבין מדוע, נזדקק לחתכי S-T - מושג שכעת נראה.
ראשית נראה בשלושת המשפטים הבאים שגודל זרימת החתך מגביל את גודל הזרימה.
משפט:
לכל חתך S-T, גודל זרימת החתך הוא לכל היותר גודל קיבול החתך.
משפט:
לכל חתך S-T, גודל זרימת החתך הוא בדיוק גודל הזרימה.
להלן הוכחה של המשפט השני מבין השניים.
הוכחה: ההוכחה היא באינדוקציה על .
(בסיס האינדוקציה) כאשר הטענה ברורה, כי פשוט .
(מעבר האינדוקציה) נניח שהטענה נכונה לכל כך ש, ונראה שהיא נכונה גם לכל כך ש.
נקח חתך S-T כלשהו שבו , ונבחר איזשהו . נציין את שכניו של כך: שכניו של ב הם , ושכניו של ב הם . A בתרשים הבא מראה את החתך, את , ואת שכניו (שים לב שיתכנו עוד צמתים שאינם מופיעים בתרשים). נגדיר כ את גודל זרימת החתך.
מעבר האינדוקציה.
כעת נייצר חתך אחר, ע"י זאת שנעביר את מ ל, כמוראה בB בתרשים הקודם. נגדיר כ את גודל זרימת החתך החדש. נשים לב לשני דברים:
משילוב שני המשפטים הקודמים, קל לראות את המשפט הבא:
משפט:
לכל חתך S-T, גודל הזרימה הוא לכל היותר גודל קיבול החתך.
כזכור, רעיון החתכים נועד להוכיח את הטענה שיכולת שיפור גודל הזרימה היא בדיוק היכולת למצוא מסלול משפר בגרף השיורי. כעת נוכל להוכיח זאת (ואף יותר מכך) במשפט הבא.
כדאי לדעת:
המשפט הבא ידוע כמשפט Max-Flow Min-Cut, וייתכן מאד שהוא המשפט המפורסם ביותר בתורת הגרפים.
משפט: Max-Flow Min-Cut
הטענות הבאות שקולות:
הזרימה היא בעלת גודל מירבי.
אין מסלול משפר ברשת השיורית .
קיים חתך S-T שבו גודל הזרימה הוא בדיוק גודל קיבול החתך.
הוכחה: כבר הראנו מקודם שאם יש מסלול משפר בגרף הרשת השיורית, אז אפשר להגדיל את גודל הזרימה.
נניח שאין מסלול משפר בגרף הרשת השיורית. נגדיר שתי קבוצות כך: מוגדרת כקבוצת הצמתים שיש מסלול מ אליהם בגרף הרשת השיורית, ו מוגדרת כשאר הצמתים - . מהבניה ברור ש, ולכן זהו חתך S-T. נניח שקיימים המקיימים . אז על פי ההגדרה, , דבר שסותר את הנחתנו ש. לכן בחתך זה, גודל קיבול החתך שווה לגודל זרימת החתך. מצד שני, הראינו מקודם שלכל חתך, גודל זרימת החתך הוא בדיוק גודל הזרימה.
כבר הראנו מקודם שלכל חתך S-T, גודל הזרימה חסום ע"י גודל קיבול החתך. לכן, אם מצאנו זרימה שגודלה הוא גודל קיבול חתך כלשהו, זו בהכרח זרימת המקסימום.