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


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


כדאי לדעת:

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


כדאי לדעת:

בספר הקורס, הפרק "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
זרימה - הגדרות הפרק הבא:
זרימה שיורית וחתכים