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

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

כדאי לדעת: נחלק את החומר שנלמד בזרימה לשלשה חלקים: בזרימה - הגדרות נגדיר מספר מושגים הנדרשים להגדרת הבעיה, כמו זרימה חוקית וגודל הזרימה. בזרימה שיורית וחתכים נעסוק במסלולים משפרים ברשת השיורית וחתכי S-T, ונראה מדוע מספיק לבדוק האם קיים מסלול משפר. באלגוריתמי זרימה נעסוק (מעט) בדרכים יעילות למצוא מסלול משפר.

כדאי לדעת: בספר הקורס, הפרק "Maximum Flow" (תתי פרקים 1 ו2) מכסה נושא זה.

הרשת השיורית

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

הגדרה

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

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

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

מסלול משפר

הגדרה

הגדרה: נניח שברשת שיורית יש מסלול מ$\displaystyle s$ ל$\displaystyle t$ על פני קשתות בעלי קיבול (שיורי) חיובי ממש. נאמר שהמסלול הוא מסלול משפר לזרימה ברשת המקורית.

דוגמה: בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. לזרימה זו מתאימה הרשת השיורית המוצגת ב-B ‏.C מראה מסלול משפר, כלומר מסלול מ$\displaystyle s$ ל$\displaystyle t$ ברשת השיורית על פני קשתות בעלי קיבול (שיורי) חיובי ממש. מסלול משפר.

דוגמה: בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. B מראה את הרשת השיורית. קל לראות שאין מסלול משפר מ$\displaystyle s$ ל$\displaystyle t$ ברשת השיורית, כלומר מסלול על פני קשתות בעלי קיבול (שיורי) חיובי ממש. אין מסלול משפר ברשת השיורית.

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

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

משפט: נניח שברשת השיורית יש מסלול משפר, וקיבול המינימום בגרף השיורי לאורך המסלול הוא $\displaystyle c$. אז אפשר להגדיל את הזרימה ברשת המקורית ב$\displaystyle c$ על ידי הזרמה נוספת במסלול המשפר.

דוגמה: כפי שראינו, בתרשים הבא, A מראה רשת זרימה וזרימה חוקית עליה. לזרימה זו מתאימה הרשת השיורית המוצגת בB ‏.C מראה מסלול משפר, כלומר מסלול מ$\displaystyle s$ ל$\displaystyle t$ ברשת השיורית על פני קשתות בעלי קיבול (שיורי) חיובי ממש. מסלול משפר. במסלול המשפר כל הקשתות בעלי קיבול (שיורי) לפחות 1, ואכן, קל להווכח שאפשר להגדיל את הזרימה בA ב1.

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

חתכי S-T

הגדרה

הגדרה: ברשת זרימה, חתך S-T הוא חלוקה של $\displaystyle V$ לשתי קבוצות (זרות) $\displaystyle S$ ו$\displaystyle T$, כך ש: $\displaystyle s\in S,t\in T$ $\displaystyle S\bigcap T=\emptyset ,S\bigcup T=V$קשת $\displaystyle (u,v)$ חוצה את החתך מ$\displaystyle S$ ל$\displaystyle T$ אם $\displaystyle u\in S$ ו$\displaystyle v\in T$.

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

דוגמה: להלן מספר חתכי S-T לרשת זרימה שכבר ראינו: A בתרשים הבא מראה את החתך $\displaystyle S=\{s\},T=V\ -\{s\}$. גודל קיבול החתך הוא 21, וגודל זרימת החתך הוא 3. B בתרשים הבא מראה את החתך $\displaystyle S=V\ -\{t\},T=\{t\}$. גודל קיבול החתך הוא 4 וגודל זרימת החתך הוא 3. C בתרשים הבא מראה את החתך $\displaystyle S=\{1,2,6\},T=\{3,4,5,7\}$.גודל קיבול החתך הוא 45 וגודל זרימת החתך הוא 3. גודל זרימת חתך וקיבול חתך.

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

דוגמה: להלן חתך S-T אחר לגרף מהדוגמה הקודמת. גודל קיבול החתך הוא 23, וגודל זרימת החתך הוא 4 (ודא שהנך מבין מדוע).(*גודל זרימת החתך הוא 3) גודל זרימת חתך וקיבול חתך עם קשתות מt לs.

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

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

משפט: לכל חתך S-T, גודל זרימת החתך הוא לכל היותר גודל קיבול החתך.

משפט: לכל חתך S-T, גודל זרימת החתך הוא בדיוק גודל הזרימה.

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

הוכחה: ההוכחה היא באינדוקציה על $\displaystyle |S|$.

(בסיס האינדוקציה) כאשר $\displaystyle |S|=1$ הטענה ברורה, כי פשוט $\displaystyle S=\{s\}$.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל $\displaystyle S$ כך ש$\displaystyle |S|=i-1$, ונראה שהיא נכונה גם לכל $\displaystyle S$ כך ש$\displaystyle |S|=i$.

נקח חתך S-T כלשהו שבו $\displaystyle |S|=i>1$, ונבחר איזשהו $\displaystyle u\in T\setminus \{t\}$. נציין את שכניו של $\displaystyle u$ כך: שכניו של $\displaystyle u$ ב$\displaystyle S$ הם $\displaystyle \{v_{1},\ldots ,v_{m}\}\subseteq S$, ושכניו של $\displaystyle u$ ב$\displaystyle T$ הם $\displaystyle \{w_{1},\ldots ,v_{w}\}\subseteq S$.‏ A בתרשים הבא מראה את החתך, את $\displaystyle u$, ואת שכניו (שים לב שיתכנו עוד צמתים שאינם מופיעים בתרשים). נגדיר כ$\displaystyle |f_{A}|$ את גודל זרימת החתך.

מעבר האינדוקציה.

כעת נייצר חתך אחר, ע"י זאת שנעביר את $\displaystyle u$ מ$\displaystyle T$ ל$\displaystyle S$, כמוראה בB בתרשים הקודם. נגדיר כ$\displaystyle |f_{B}|$ את גודל זרימת החתך החדש. נשים לב לשני דברים:

1. בהכרח $\displaystyle |f_{A}|=|f_{B}|$:
   1. מהתרשימים קל לראות שמתקיים $\displaystyle |f_{A}|-\sum _{i=1}^{m}[f_{v_{i},u}]+\sum _{j=1}^{n}[f_{u,w_{j}}]=|f_{B}|$.
   2. מזרימה הופכית אנו יודעים ש$\displaystyle \sum _{i=1}^{m}[f_{v_{i},u}]=-\sum _{i=1}^{m}[f_{u,v_{i}}],$, ולכן $\displaystyle |f_{A}|+\sum _{i=1}^{m}[f_{u,v_{i}}]+\sum _{j=1}^{n}[f_{u,w_{j}}]=|f_{B}|$
      .
   3. משימור הזרימה אנו יודעים ש $\displaystyle \sum _{i=1}^{m}[f_{u,v_{i}}]+\sum _{j=1}^{n}[f_{u,w_{j}}]=0$
      .
2. בתרשים B, בהכרח $\displaystyle |S|=i$, וזאת משום שהעברנו את $\displaystyle u$ ל$\displaystyle S$.

קל להשלים מכאן את מעבר האינדוקציה.

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

משפט: לכל חתך S-T, גודל הזרימה הוא לכל היותר גודל קיבול החתך.

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

כדאי לדעת: המשפט הבא ידוע כמשפט Max-Flow Min-Cut, וייתכן מאד שהוא המשפט המפורסם ביותר בתורת הגרפים.

משפט: Max-Flow Min-Cut הטענות הבאות שקולות: הזרימה $\displaystyle \{f_{u,v}\}$ היא בעלת גודל מירבי. אין מסלול משפר ברשת השיורית $\displaystyle G^{f}$. קיים חתך S-T שבו גודל הזרימה הוא בדיוק גודל קיבול החתך.

הוכחה: $\displaystyle (1\Rightarrow 2)$ כבר הראנו מקודם שאם יש מסלול משפר בגרף הרשת השיורית, אז אפשר להגדיל את גודל הזרימה.

$\displaystyle (2\Rightarrow 3)$ נניח שאין מסלול משפר בגרף הרשת השיורית. נגדיר שתי קבוצות כך: $\displaystyle S$ מוגדרת כקבוצת הצמתים שיש מסלול מ$\displaystyle s$ אליהם בגרף הרשת השיורית, ו$\displaystyle T$ מוגדרת כשאר הצמתים - $\displaystyle V\ -S$. מהבניה ברור ש$\displaystyle s\in S,t\in T$, ולכן זהו חתך S-T. נניח שקיימים $\displaystyle u\in S,v\in V$ המקיימים $\displaystyle f_{u,v}<c_{u,v}$. אז על פי ההגדרה, $\displaystyle (u,v)\in G^{f}$, דבר שסותר את הנחתנו ש$\displaystyle v\notin S$. לכן בחתך זה, גודל קיבול החתך שווה לגודל זרימת החתך. מצד שני, הראינו מקודם שלכל חתך, גודל זרימת החתך הוא בדיוק גודל הזרימה.

$\displaystyle (3\Rightarrow 1)$ כבר הראנו מקודם שלכל חתך S-T, גודל הזרימה חסום ע"י גודל קיבול החתך. לכן, אם מצאנו זרימה שגודלה הוא גודל קיבול חתך כלשהו, זו בהכרח זרימת המקסימום.

הפרק הקודם: זרימה - הגדרות

זרימה שיורית וחתכים תרגילים

הפרק הבא: אלגוריתמי זרימה