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

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

הבעיה

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

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

קלט ופלט

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

הקלט

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

1. קיבול הקשת מתבנית:קוד בשורה לתבנית:קוד בשורה, אם יש קשת כזו.
2. $0$ אם אין קשת כזו.

לשם הנוחות, בשאר החומר בנושא נגדיר $c_{u,v}=$ תבנית:קוד בשורה.

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

הפלט

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

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