شبکه پسماند

شبکه پسماند

تعریف

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

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

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

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

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

مثال

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

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

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

منابع

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