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

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

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

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

מימוש C++ boost::edmunds_karp_max_flow, boost::push_relabel_max_flow

הבעיה

נתונים גרף מכוון $\displaystyle G=(V,E)$, טבלת קיבולים לקשתות $\displaystyle E$, צומת מקור $\displaystyle s\in V$ כלשהו, וצומת בור $\displaystyle t\in V$ כלשהו. בהינתן צומת $\displaystyle v\in V$ כלשהו, רוצים לדעת מה זרימת המקסימום מ$\displaystyle s$ ל$\displaystyle t$.

דוגמה: בגרף שבתרשים הבא, המספר המצויין על כל קשת הוא קיבולו: לקשת $\displaystyle (1,2)$ קיבול $\displaystyle 1$. לכן $\displaystyle 1$ יכולה להזרים $\displaystyle 1$ ליטר לשניה בקשת זו. לקשת $\displaystyle (2,3)$ קיבול $\displaystyle 10$. לכן $\displaystyle 2$ יכולה להזרים $\displaystyle 10$ ליטר לשניה בקשת זו. אין קשת מ$\displaystyle 1$ ל$\displaystyle 7$. לכן $\displaystyle 1$ אינה יכולה להזרים ישירות שום נוזל ל$\displaystyle 7$.נניח צומת מקור $\displaystyle s=1$, וצומת בור $\displaystyle t=4$. בעיית הזרימה. התרשים הבא מראה את זרימת המקסימום: המספר בסוגריים בכל קשת מציין כמה ליטר לשניה מזרימים בה. כך, לדוגמה, בקשת $\displaystyle (1,6)$ מזרימים $\displaystyle 2$ ליטר לשניה. הפתרון האופטימאלי. סך הזרימה היא $\displaystyle 3$, כי בכל יחידת זמן מזרימים $\displaystyle 3$ ליטר לשניה מ1 ל$\displaystyle 4$. אפשר לבדוק שאין אפשרות לעשות יותר מכך.

הגדרות מדוייקות לבעיה

רשת זרימה

הגדרה: רשת זרימה היא: גרף מכוון $\displaystyle G=(V,E)$ השמת קיבולים $\displaystyle \{c_{u,v}\}$; לכל שני צמתים $\displaystyle u,v\in V$,‏ יש קיבול $\displaystyle c_{u,v}\geq 0$ צומת מקור $\displaystyle s\in V$ וצומת בור $\displaystyle t\in V$

דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה): הקיבולים הם: $\displaystyle c_{1,2}=1$ $\displaystyle c_{1,6}=20$ $\displaystyle c_{2,3}=10$ $\displaystyle c_{6,5}=34$ $\displaystyle c_{6,7}=1$ $\displaystyle c_{7,3}=3$ $\displaystyle c_{7,5}=4$ $\displaystyle c_{3,4}=3$ $\displaystyle c_{5,4}=1$ לכל צירוף אחר של $\displaystyle u$ ו$\displaystyle v$,‏ $\displaystyle c_{u,v}=0$. צומת המקור הוא $\displaystyle s=1$, וצומת הבור הוא $\displaystyle t=4$.

זרימה חוקית

הגדרה: ברשת זרימה, זרימה חוקית היא קביעת ערך $\displaystyle f_{u,v}$ לכל שני צמתים $\displaystyle u,v\in V$, כך שיתקיימו התנאים הבאים: (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; $\displaystyle \forall _{u,v\in V}f_{u,v}\leq c_{u,v}$. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים $\displaystyle s$ ו$\displaystyle t$, הצומת אינו אוגר או מייצר זרם; $\displaystyle \forall _{u\in V\setminus \{s,t\}}\sum _{v\in V}f_{u,v}=0$. (סימטריה הפכית) הזרימה הישירה מצומת $\displaystyle u$ לצומת $\displaystyle v$ היא מינוס הזרימה הישירה מצומת $\displaystyle v$ לצומת $\displaystyle u$;‏ $\displaystyle \forall _{u,v\in V}f_{u,v}=-f_{v,u}$.

כדאי לדעת: סטודנטים להנדסה יזהו דמיון בין שני החוקים האחרונים לחוקי קירקהוף.

דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה): אפשר לוודא שהזרימה הראשונה שראינו (התרשים השני שבדף זה), בה $\displaystyle f_{1,2}=1,f_{1,6}=2$,‏ וכו', היא אכן זרימה חוקית. הזרימה בה $\displaystyle f_{u,v}=0$, עבור כל שני צמתים $\displaystyle u,v\in V$ -‏ גם היא זרימה חוקית.

דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה), הזרימה בתרשים הבא אינה חוקית. זרימה לא חוקית. בין היתר: $\displaystyle f_{1,2}=5000>c_{1,2}=1$, דבר שסותר את מגבלת הקיבול. $\displaystyle f_{2,1}+f_{2,3}=-5000+10\neq 0$, ‏דבר שסותר את שימור הזרם.

גודל הזרימה

הגדרה: ברשת זרימה, נניח שמצאנו זרימה חוקית $\displaystyle \{f_{u,v}\}$‏ (המתאימה מספר לכל זוג צמתים $\displaystyle u,v\in V$ לפי התנאים שראינו). נאמר שגודל הזרימה הוא $\displaystyle \sum _{u\in V}f_{s,u}$. במילים אחרות, גודל הזרימה הוא סכום הזרימות שיוצאות מ$\displaystyle s$.

דוגמה: בזרימה הראשונה שראינו (התרשים השני שבדף זה), גודל הזרימה הוא $\displaystyle f_{1,2}+f_{1,6}=1+2=3$.‏

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

קלט ופלט

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

הקלט

נניח שקיבולי הקשתות נתונות ע"י טבלת עלויות. באופן דומה למה שראינו במסלולים זולים לכלל הזוגות, לא נניח שמדובר בטבלת ערבול, אלא נניח שCapacities היא מטריצה שלה כניסה Capacities[u][v] לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil, כבטבלת ערבול). הערך Capacities[u][v], הנו:

1. קיבול הקשת מu לv, אם יש קשת כזו.
2. $\displaystyle 0$ אם אין קשת כזו.

לשם הנוחות, בשאר החומר בנושא נגדיר $\displaystyle c_{u,v}=$ Capacities[u][v].

דוגמה: בגרף הקודם שראינו: $\displaystyle c_{1,6}=20$ $\displaystyle c_{7,5}=4$ $\displaystyle c_{6,1}=0$ $\displaystyle c_{1,4}=0$

שימו לב: $\displaystyle c_{u,v}$ מתאר כמה אפשר להזרים מ$\displaystyle u$ ל$\displaystyle v$. באופן כללי, אין שום קשר בין $\displaystyle c_{u,v}$ ו$\displaystyle c_{v,u}$.

הפלט

נרצה פלט שמתאר כמה זורם בכל קשת. באופן כללי יש יש יותר מדרך אחת הגיונית לעשות זאת; אנו נבחר בדרך שייתכן שתיראה שרירותית בתחילה. נניח שהפלט הוא Flows, שהיא מטריצה שלה כניסה Flows[u][v] לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil, כבטבלת ערבול). הערך Flows[u][v] מתאר כמה זורם מ$\displaystyle u$ ל$\displaystyle v$, שהוא, עפ"י ההגדרה, מינוס מה שזורם מ$\displaystyle v$ ל$\displaystyle u$. לשם הנוחות, בשאר החומר בנושא נגדיר $\displaystyle f_{u,v}=$ Flows[u][v].

דוגמה: בגרף הקודם שראינו: $\displaystyle f_{1,2}=1$ $\displaystyle f_{1,6}=2$ $\displaystyle f_{1,7}=0$ $\displaystyle f_{2,1}=-1$

שימו לב: $\displaystyle f_{u,v}$ מתאר כמה מזרימים מ$\displaystyle u$ ל$\displaystyle v$. אנו נבחר בפרשנות שבה, לפי ההגדרה, $\displaystyle f_{u,v}=-f_{v,u}$.

הפרק הקודם: אלגוריתם Floyd-Warshall

זרימה - הגדרות

הפרק הבא: זרימה שיורית וחתכים