شبکه پسماند

با در اختیار داشتن شبکه شاره G و جریان f ، شبکه پسماند G_f ،متشکل از رئوس گراف و ظرفیت هر یک از آن‌ها می‌باشد. هر یال در شبکه‌ی جریان، ممکن است قادر به عبور مقدار جریان بیشتری از خود باشد. این مقدار، معادل تفاضل ظرفیت و جریان گذرنده از آن یال است. چنان‌چه این مقدار مثبت باشد، یال مورد نظر با مقدار ظرفیت پسماند خود در G_f قرار می‌گیرد. مقدار ظرفیت پسماند برای هر یال مانند (u,v) را با ${\displaystyle c_f(u,v)}$

• اگر ${\displaystyle (u,v)\in E}$
  آنگاه ${\displaystyle c_f(u,v)=c(u,v)-f(u,v)}$
• اگر ${\displaystyle (u,v)\notin E}$
  آنگاه ${\displaystyle c_f(u,v)=f(v,u)}$
• در غیر این صورت ${\displaystyle c_f(u,v)=0}$

با استفاده از جریان در شبکه پسماند، می‌توان مقدار جریان قابل افزودن به جریان شار اصلی را محاسبه نمود. اگر شار شبکه ${\displaystyle G}$

• اگر ${\displaystyle (u,v)\in E}$
  آنگاه: ${\displaystyle (f\uparrow f^{\prime })(u,v)=f(u,v)+f^{\prime }(u,v)-f^{\prime }(v,u)}$
• در غیر این صورت ${\displaystyle (f\uparrow f^{\prime })(u,v)=0}$

در شکل روبه‌رو شبکه‌ی جریان ${\displaystyle G}$

• مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش
• ریاضیات گسسته و الگوریتم ها-پدیدآورنده:علی بهفروز، محمد ایزدی-ناشر:آییژ