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