شبکه پسماند
اگر ( u , v ) ∈ E {\displaystyle (u,v)\in E} آنگاه c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
اگر ( u , v ) ∉ E {\displaystyle (u,v)\not \in E} آنگاه c f ( u , v ) = f ( v , u ) {\displaystyle c_{f}(u,v)=f(v,u)}
در غیر این صورت c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0}
با در اختیار داشتن شبکه شاره G و جریان f ، شبکه پسماند Gf ،متشکل از رئوس گراف و ظرفیت هر یک از آن ها می باشد. هر یال در شبکه ی جریان، ممکن است قادر به عبور مقدار جریان بیشتری از خود باشد. این مقدار، معادل تفاضل ظرفیت و جریان گذرنده از آن یال است. چنان چه این مقدار مثبت باشد، یال مورد نظر با مقدار ظرفیت پسماند خود در Gf قرار می گیرد. مقدار ظرفیت پسماند برای هر یال مانند (u,v) را با c f ( u , v ) {\displaystyle c_{f}(u,v)} نمایش داده که مقدار آن از رابطه ی c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} قابل محاسبه است. چنان چه ظرفیت یالی، برابر جریان گذرنده از آن باشد، c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0} بوده و در گراف پسماند قرار نمی گیرد.همچنین شبکه ی پسماند ممکن است شامل یال هایی باشد که در گراف موجود نیستند. هم چنان که در بسیاری از الگوریتم ها، نیاز به افزایش مقدار جریان عبوری از یک یال وجود دارد، کاهش مقدار جریان عبوری نیز در برخی از آنها مانند الگوریتم فورد–فالکرسون مورد استفاده قرار می گیرد. جهت نمایش کاهش جریان عبوری مثبت f ( u , v ) {\displaystyle f(u,v)} در گراف G {\displaystyle G} ، یال ( v , u ) {\displaystyle (v,u)} را با ظرفیت پسماند c f ( v , u ) = f ( u , v ) {\displaystyle c_{f}(v,u)=f(u,v)} در G f {\displaystyle G_{f}} قرار می دهیم. به طور خلاصه، مقدار ظرفیت پسماند به شکل زیر محاسبه می شود:
با استفاده از جریان در شبکه پسماند، می توان مقدار جریان قابل افزودن به جریان شار اصلی را محاسبه نمود. اگر شار شبکه G {\displaystyle G} را با f {\displaystyle f} و شار گذرنده از شبکه پسماند متعلق به آن یعنی G f {\displaystyle G_{f}} را با f ′ {\displaystyle f'} نمایش دهیم، f ↑ f ′ {\displaystyle f\uparrow f'} یک جریان افزاینده برای f {\displaystyle f} توسط f ′ {\displaystyle f'} خواهد بود. جریان افزاینده در حقیقت یک تابع از V × V {\displaystyle V\times V} به اعداد حقیقی است که مقدار آن به شکل زیر محاسبه می شود:
در شکل روبه رو شبکه ی جریان G {\displaystyle G} و شبکه ی پسماند متعلق به آن نمایش داده شده اند. در حالت عادی، یال هایی که در آن ها مقدار ظرفیت پسماند برابر صفر است، در G f {\displaystyle G_{f}} نمایش داده نمی شوند. مانند ( s , b ) {\displaystyle (s,b)} .
اگر ( u , v ) ∈ E {\displaystyle (u,v)\in E} آنگاه c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
اگر ( u , v ) ∉ E {\displaystyle (u,v)\not \in E} آنگاه c f ( u , v ) = f ( v , u ) {\displaystyle c_{f}(u,v)=f(v,u)}
در غیر این صورت c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0}
با در اختیار داشتن شبکه شاره G و جریان f ، شبکه پسماند Gf ،متشکل از رئوس گراف و ظرفیت هر یک از آن ها می باشد. هر یال در شبکه ی جریان، ممکن است قادر به عبور مقدار جریان بیشتری از خود باشد. این مقدار، معادل تفاضل ظرفیت و جریان گذرنده از آن یال است. چنان چه این مقدار مثبت باشد، یال مورد نظر با مقدار ظرفیت پسماند خود در Gf قرار می گیرد. مقدار ظرفیت پسماند برای هر یال مانند (u,v) را با c f ( u , v ) {\displaystyle c_{f}(u,v)} نمایش داده که مقدار آن از رابطه ی c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} قابل محاسبه است. چنان چه ظرفیت یالی، برابر جریان گذرنده از آن باشد، c f ( u , v ) = 0 {\displaystyle c_{f}(u,v)=0} بوده و در گراف پسماند قرار نمی گیرد.همچنین شبکه ی پسماند ممکن است شامل یال هایی باشد که در گراف موجود نیستند. هم چنان که در بسیاری از الگوریتم ها، نیاز به افزایش مقدار جریان عبوری از یک یال وجود دارد، کاهش مقدار جریان عبوری نیز در برخی از آنها مانند الگوریتم فورد–فالکرسون مورد استفاده قرار می گیرد. جهت نمایش کاهش جریان عبوری مثبت f ( u , v ) {\displaystyle f(u,v)} در گراف G {\displaystyle G} ، یال ( v , u ) {\displaystyle (v,u)} را با ظرفیت پسماند c f ( v , u ) = f ( u , v ) {\displaystyle c_{f}(v,u)=f(u,v)} در G f {\displaystyle G_{f}} قرار می دهیم. به طور خلاصه، مقدار ظرفیت پسماند به شکل زیر محاسبه می شود:
با استفاده از جریان در شبکه پسماند، می توان مقدار جریان قابل افزودن به جریان شار اصلی را محاسبه نمود. اگر شار شبکه G {\displaystyle G} را با f {\displaystyle f} و شار گذرنده از شبکه پسماند متعلق به آن یعنی G f {\displaystyle G_{f}} را با f ′ {\displaystyle f'} نمایش دهیم، f ↑ f ′ {\displaystyle f\uparrow f'} یک جریان افزاینده برای f {\displaystyle f} توسط f ′ {\displaystyle f'} خواهد بود. جریان افزاینده در حقیقت یک تابع از V × V {\displaystyle V\times V} به اعداد حقیقی است که مقدار آن به شکل زیر محاسبه می شود:
در شکل روبه رو شبکه ی جریان G {\displaystyle G} و شبکه ی پسماند متعلق به آن نمایش داده شده اند. در حالت عادی، یال هایی که در آن ها مقدار ظرفیت پسماند برابر صفر است، در G f {\displaystyle G_{f}} نمایش داده نمی شوند. مانند ( s , b ) {\displaystyle (s,b)} .
wiki: شبکه پسماند