רשת זרימה – הבדלי גרסאות

===גרפים דו צדדיים===

[[קובץ:Matching_With_Flow.png|שמאל|מסגרת|100px|דוגמה לרשת זרימה שמתקבלת לאחר הבניה]]

 

בהינתן גרף דו צדדי המורכב משתי קבוצות צמתים <math>\ A,B</math>, כך שכל קשת היא בין צומת השייך ל-<math>\ A</math> וצומת השייך ל-<math>\ B</math>, בונים רשת זרימה כדלהלן: ראשית, מוסיפים צמתים חדשים שישמשו כמקור וכבור: <math>\ s,t</math>. כעת, מחברים בקשתות את <math>\ s</math> לכל צומתי <math>\ A</math>, ואת <math>\ t</math> לכל צומתי <math>\ B</math>. נותנים לכל הקשתות קיבולת 1. לא קשה להוכיח כי זרימת מקסימום ברשת זו משרה שידוך מקסימום בגרף המקורי, כאשר הקשתות שמשתתפות בשידוך הן אלו בהן עובר זרם.