זרימה - הגדרות ודוגמאות
רשת זרימה - גרף מכוון שבו
כל קשת היא בעלת קיבול אי שלילי (נסמן את הקיבול ב c), ברשת
הזרימה קיימים שני קודקודים מיוחדים: מקור s ובור t. אנו
מניחים שכל קודקוד שוכן על מסלול כלשהו מהמקור לבור.
זרימה - פונקציה ממשית (נסמנה
ב-f) המקיימת 3 תכונות:
1. אילוץ קיבול: הזרימה על
קשת אינה יכולה להיות גדולה מהקיבול על קשת זו.
2. סימטריה נגדית - הזרימה על קשת שווה למינוס הזרימה על
אותה הקשת בכיוון ההפוך.
3. שימור הזרימה - סכום הזרימה על כל הקשתות הסמוכות לקודקוד
מסויים שווה ל-0.
ערך הזרימה - ערך הזרימה של
פונקצית זרימה הוא סך הזרימה היוצאת מקודקוד המקור.
כאן יוצג פלאש המתאר רשתות
זרימה שונות
נבחן את בעיית הזרימה המקסימלית,
בהנתן רשת זרימה עם מקור ובור, ברצוננו למצוא את ערך הזרימה
המקסימלי ברשת.
(בעיית הזרימה המקסימלית עשויה לכלול רשת בעלת מספר מקורות
ובורות ואז ניתן לבצע רדוקציה של בעיית הזרימה המקסימלית
עם מספר מקורות ובורות לבעיית הזרימה המקסימלית עם מקור
אחד ובור אחד.
את הרדוקציה נבצע ע"י הוספת מקור על המחובר לכל המקורות
בקשתות עם קיבול אינסוף והוספת בור על המחובר מכל הבורות
בקשתות עם קיבול אינסוף.)
