מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה - הגדרות
דף זו הוא הראשון משלשה העוסק באלגוריתמים למציאת זרימת המקסימום בגרף מכוון המתאר "רשת צינורות".
כדאי לדעת: נחלק את החומר שנלמד בזרימה לשלשה חלקים:
|
כדאי לדעת: בספר הקורס, הפרק "Maximum Flow" (תתי פרקים 1 ו2) מכסה נושא זה. |
מימוש C++ |
הבעיה
עריכהנתונים גרף מכוון , טבלת קיבולים לקשתות , צומת מקור כלשהו, וצומת בור כלשהו. בהינתן צומת כלשהו, רוצים לדעת מה זרימת המקסימום מ ל .
דוגמה: בגרף שבתרשים הבא, המספר המצויין על כל קשת הוא קיבולו:
התרשים הבא מראה את זרימת המקסימום: המספר בסוגריים בכל קשת מציין כמה ליטר לשניה מזרימים בה. כך, לדוגמה, בקשת מזרימים ליטר לשניה. סך הזרימה היא , כי בכל יחידת זמן מזרימים ליטר לשניה מ1 ל . אפשר לבדוק שאין אפשרות לעשות יותר מכך. |
הגדרות מדוייקות לבעיה
עריכהרשת זרימה
עריכה
הגדרה: רשת זרימה היא:
|
דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):
|
זרימה חוקית
עריכה
הגדרה: ברשת זרימה, זרימה חוקית היא קביעת ערך לכל שני צמתים , כך שיתקיימו התנאים הבאים:
|
כדאי לדעת: סטודנטים להנדסה יזהו דמיון בין שני החוקים האחרונים לחוקי קירקהוף. |
דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):
|
דוגמה: ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה), הזרימה בתרשים הבא אינה חוקית. בין היתר:
|
גודל הזרימה
עריכה
הגדרה: ברשת זרימה, נניח שמצאנו זרימה חוקית (המתאימה מספר לכל זוג צמתים לפי התנאים שראינו). נאמר שגודל הזרימה הוא . במילים אחרות, גודל הזרימה הוא סכום הזרימות שיוצאות מ . |
דוגמה: בזרימה הראשונה שראינו (התרשים השני שבדף זה), גודל הזרימה הוא . |
כדאי לדעת: אפשר לחשוב על הגדרות אחרות לגודל הזרימה, כמו סכום הזרימות שנכנסות ל , לדוגמה. בסוףנושא זה יהיה עליך לדעת להוכיח שהגדרות אלו שקולות. |
קלט ופלט
עריכהלאחר שראינו את ההגדרות המדוייקות לבעיה, ברור מה אנו מנסים לפתור מבחינה מתמטית. עם זאת, בקורס זה אנו לרוב עוסקים באלגוריתמים בעלי קלט ופלט מוגדרים על ידי טיפוסים בפסוודו-קוד. נעסוק בכך כעת.
הקלט
עריכהנניח שקיבולי הקשתות נתונות ע"י טבלת עלויות. באופן דומה למה שראינו במסלולים זולים לכלל הזוגות, לא נניח שמדובר בטבלת ערבול, אלא נניח שCapacities
היא מטריצה שלה כניסה Capacities[u][v]
לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil
, כבטבלת ערבול). הערך Capacities[u][v]
, הנו:
- קיבול הקשת מ
u
לv
, אם יש קשת כזו. - אם אין קשת כזו.
לשם הנוחות, בשאר החומר בנושא נגדיר Capacities[u][v]
.
דוגמה: בגרף הקודם שראינו:
|
שימו לב: מתאר כמה אפשר להזרים מ ל . באופן כללי, אין שום קשר בין ו . |
הפלט
עריכהנרצה פלט שמתאר כמה זורם בכל קשת. באופן כללי יש יש יותר מדרך אחת הגיונית לעשות זאת; אנו נבחר בדרך שייתכן שתיראה
שרירותית בתחילה. נניח שהפלט הוא Flows
, שהיא מטריצה שלה כניסה Flows[u][v]
לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil
,
כבטבלת ערבול). הערך Flows[u][v]
מתאר כמה זורם מ
ל , שהוא, עפ"י ההגדרה, מינוס מה שזורם מ ל .
לשם הנוחות, בשאר החומר בנושא נגדיר Flows[u][v]
.
דוגמה: בגרף הקודם שראינו:
|
שימו לב: מתאר כמה מזרימים מל . אנו נבחר בפרשנות שבה, לפי ההגדרה, . |
הפרק הקודם: אלגוריתם Floyd-Warshall |
זרימה - הגדרות | הפרק הבא: זרימה שיורית וחתכים |