شبکه پسماند

شبکه پسماند

تعریف

با در اختیار داشتن شبکه شاره G و جریان f ، شبکه پسماند G_f ،متشکل از رئوس گراف و ظرفیت هر یک از آن‌ها می‌باشد. هر یال در شبکه‌ی جریان، ممکن است قادر به عبور مقدار جریان بیشتری از خود باشد. این مقدار، معادل تفاضل ظرفیت و جریان گذرنده از آن یال است. چنان‌چه این مقدار مثبت باشد، یال مورد نظر با مقدار ظرفیت پسماند خود در G_f قرار می‌گیرد. مقدار ظرفیت پسماند برای هر یال مانند (u,v) را با $c_{f}(u,v)$ نمایش داده که مقدار آن از رابطه‌ی $c_{f}(u,v)=c(u,v)-f(u,v)$ قابل محاسبه است. چنان‌چه ظرفیت یالی، برابر جریان گذرنده از آن باشد، $c_{f}(u,v)=0$ بوده و در گراف پسماند قرار نمی‌گیرد. همچنین شبکه‌ی پسماند ممکن است شامل یال‌هایی باشد که در گراف موجود نیستند. هم‌چنان که در بسیاری از الگوریتم‌ها، نیاز به افزایش مقدار جریان عبوری از یک یال وجود دارد، کاهش مقدار جریان عبوری نیز در برخی از آنها مانند الگوریتم فورد–فالکرسون مورد استفاده قرار می‌گیرد. جهت نمایش کاهش جریان عبوری مثبت $f(u,v)$ در گراف $G$، یال $(v,u)$ را با ظرفیت پسماند $c_{f}(v,u)=f(u,v)$ در $G_{f}$ قرار می‌دهیم. به طور خلاصه، مقدار ظرفیت پسماند به شکل زیر محاسبه می‌شود:

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

جریان شبکه پسماند

با استفاده از جریان در شبکه پسماند، می‌توان مقدار جریان قابل افزودن به جریان شار اصلی را محاسبه نمود. اگر شار شبکه $G$ را با $f$ و شار گذرنده از شبکه پسماند متعلق به آن یعنی $G_{f}$ را با $f'$ نمایش دهیم، $f\uparrow f'$ یک جریان افزاینده برای $f$ توسط $f'$ خواهد بود. جریان افزاینده در حقیقت یک تابع از $V\times V$ به اعداد حقیقی است که مقدار آن به شکل زیر محاسبه می‌شود:

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

مثال

در شکل روبه‌رو شبکه‌ی جریان $G$ و شبکه‌ی پسماند متعلق به آن نمایش داده شده‌اند. در حالت عادی، یال‌هایی که در آن‌ها مقدار ظرفیت پسماند برابر صفر است، در $G_{f}$ نمایش داده نمی‌شوند. مانند $(s,b)$.

شبکه جریان $G$ و شار $f$ جاری در آن

شبکه پسماند $G_{f}$ متعلق به $G$

منابع

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