לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי


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


כדאי לדעת:

נחלק את החומר שנלמד בזרימה לשלשה חלקים:


כדאי לדעת:

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



מימוש C++

boost::edmunds_karp_max_flow, boost::push_relabel_max_flow

הבעיה

[עריכה]

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



דוגמה:

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

  1. לקשת קיבול . לכן יכולה להזרים ליטר לשניה בקשת זו.
  2. לקשת קיבול . לכן יכולה להזרים ליטר לשניה בקשת זו.
  3. אין קשת מ ל. לכן אינה יכולה להזרים ישירות שום נוזל ל.נניח צומת מקור , וצומת בור .
בעיית הזרימה.
בעיית הזרימה.

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

הפתרון האופטימאלי.
הפתרון האופטימאלי.

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


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

[עריכה]

רשת זרימה

[עריכה]

הגדרה:

רשת זרימה היא:

  1. גרף מכוון
  2. השמת קיבולים ; לכל שני צמתים ,‏ יש קיבול
  3. צומת מקור וצומת בור




דוגמה:

ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):

  1. הקיבולים הם:
    • לכל צירוף אחר של ו,‏ .
  2. צומת המקור הוא , וצומת הבור הוא .


זרימה חוקית

[עריכה]

הגדרה:

ברשת זרימה, זרימה חוקית היא קביעת ערך לכל שני צמתים , כך שיתקיימו התנאים הבאים:

  1. (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; .
  2. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים ו, הצומת אינו אוגר או מייצר זרם; .
  3. (סימטריה הפכית) הזרימה הישירה מצומת לצומת היא מינוס הזרימה הישירה מצומת לצומת ;‏ .


כדאי לדעת:

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




דוגמה:

ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):

  1. אפשר לוודא שהזרימה הראשונה שראינו (התרשים השני שבדף זה), בה ,‏ וכו', היא אכן זרימה חוקית.
  2. הזרימה בה , עבור כל שני צמתים -‏ גם היא זרימה חוקית.




דוגמה:

ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה), הזרימה בתרשים הבא אינה חוקית.

זרימה לא חוקית.
זרימה לא חוקית.

בין היתר:

  1. , דבר שסותר את מגבלת הקיבול.
  2. , ‏דבר שסותר את שימור הזרם.


גודל הזרימה

[עריכה]

הגדרה:

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




דוגמה:

בזרימה הראשונה שראינו (התרשים השני שבדף זה), גודל הזרימה הוא .‏



כדאי לדעת:

אפשר לחשוב על הגדרות אחרות לגודל הזרימה, כמו סכום הזרימות שנכנסות ל,‏ לדוגמה. בסוף

נושא זה יהיה עליך לדעת להוכיח שהגדרות אלו שקולות.

קלט ופלט

[עריכה]

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

הקלט

[עריכה]

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

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


לשם הנוחות, בשאר החומר בנושא נגדיר Capacities[u][v].



דוגמה:

בגרף הקודם שראינו:





שימו לב:

מתאר כמה אפשר להזרים מ ל. באופן כללי, אין שום קשר בין ו.

הפלט

[עריכה]

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



דוגמה:

בגרף הקודם שראינו:





שימו לב:

מתאר כמה מזרימים מ

ל. אנו נבחר בפרשנות שבה, לפי ההגדרה, .


הפרק הקודם:
אלגוריתם Floyd-Warshall
זרימה - הגדרות הפרק הבא:
זרימה שיורית וחתכים