نظریه جریان بیشینه برش کمینه

قضیۀ جریان-بیشینه برش-کمینه در بهینه‌سازی شبکه نشان می‌دهد که دو مسئلۀ جریان بیشینه و برش کمینه دوگانه‌ی یکدیگرند. به سخنی دیگر، این قضیه نشان می‌دهد که یافتن جریانی بیشینه میان یک گره‌ی چشمه (سرِ جریان) و یک گره‌ی چاه (تهِ جریان) هم‌ارز است با یافتن برشی کمینه برای چشمه و چاه. اگر در گرافی باسو، برچسب‌های یال‌های گراف نمایندهٔ گنجایش یال‌ها باشند، جریان بیشینه به دنبال یافتن بیشترین جریانی است که می‌توان از گره‌ای به گره‌ای دیگر فرستاد به گونه‌ای که از هر یالی جریانی کم‌تر یا برابر با گنجایش یال بگذرد. گرهٔ سر جریان را چشمه و گرهٔ ته جریان را چاه می‌نامیم. در پرسمان برش کمینه، برچسب یک یال نمایندهٔ هزینه‌ای است که باید برای برداشتن یا بریدن آن یال پرداخت. برش در یک گراف برای دو گرهٔ چشمه و چاه تعریف می‌شود. برش بریدن یال‌هایی از گراف است به گونه‌ای که این گراف را به دو بخش ناهمبند بِبُرد که در هر کدام از این بخش‌ها تنها یکی از گره‌های چشمه یا چاه جای دارند. هم‌چنین، هزینهٔ برش برابر است با جمع هزینه‌های بریدن یال‌ها. برش کمینه برشی است که کم‌ترین هزینه را داشته باشد. قضیۀ جریان-بیشینه برش-کمینه نشان می‌دهد که یافتن جریان بیشینه هم‌ارز است با یافتن برشی کمینه.

تعریف‌ها و استاتمان‌ها

فرض کنید که ${\displaystyle N=(V,E)}$ شبکه‌ای با گره‌های ${\displaystyle V}$ و یال‌های ${\displaystyle E}$ است. هم‌چنین ${\displaystyle s}$ چشمه است و ${\displaystyle t}$ چاه.

جریان بیشینه

تعریف: گنجایش یال نگاشتی است ${\displaystyle c:E\rightarrow R_{+}}$ که با ${\displaystyle c_{uv}}$ یا ${\displaystyle c(u,v)}$ نمایانیده می‌شود. گنجایش یک یال بیش‌ترین جریانی است که می‌تواند از یال بگذرد.

تعریف: جریان نگاشتی است ${\displaystyle f:E\rightarrow R_{+}}$ که با ${\displaystyle f_{uv}}$ یا ${\displaystyle f(u,v)}$ نشان داده می‌شود. گنجایش یک یال بیش‌ترین جریانی است که می‌تواند از یال بگذرد. برای جریان دو قید وجود دارد:

1. قید گنجایش: جریان در هر یال باید کم‌تر از گنجایش یال باشد. ${\displaystyle \forall (u,v)\in E:\qquad f_{uv}\leq c_{uv}}$
2. ًقید پایستگی جریان: برای هر گره به جز چشمه و چاه، اندازهٔ جریان‌هایی که به گره درمی‌آید باید برابر باشد با اندازهٔ جریان‌هایی که از گره بیرون می‌آید. از چشمه جریان تنها بیرون می‌آید و به چاه جریان تنها درمی‌آید. ${\displaystyle \forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{u:(v,u)\in E\}}f_{vu}.}$

تعریف: اندازهٔ جریان گرهٔ ${\displaystyle s}$ برابر است با ${\displaystyle |f|=\sum \nolimits _{v\in V}f_{sv},}$.

پرسمان جریان بیشینه ${\displaystyle |f|}$ را بیشینه می‌کند. به سخنی دیگر بیشترین جریان را از چشمه به چاه می‌رساند.

قضیه اصلی

این قضیه که ل. ر. فورد (لستر رندالف فورد) و د. ر. فالکرسون (دلبرت ری فالکرسون) آن را در سال ۱۹۵۶ (میلادی) ثابت کردند به شرح زیر است:

برای هر شبکه ماکزیمم(val(f برابر گنجایش مینیمم روی تمام چشمه-چاه برش‌های ممکن است.^[۱]

اثبات

اثبات با استفاده از بررسی مسیرهای افزایشی انجام می‌شود.^[۱]

الگوریتم و پیاده‌سازی کامپیوتری

برای پیدا کردن بیشترین جریان (و معادلا کمترین برش) می‌توان از الگوریتم فورد-فالکرسون استفاده کرد. هائو و اورلین [۱۹۹۲] روشی ارائه کردند تا با استفاده از الگوریتم گولدنبرگ و تارژان [۱۹۸۸] بتوان برش مینیم را پیدا کرد که الگوریتمی با ${\displaystyle O(|V||E|+V^{2}log|V|)\ }$ است.^[۲] هم اکنون الگوریتم‌های سریعتری نیز ارائه شده‌است.^[۳]

منابع

1. West, Douglas Brent (1996). Introduction to graph theory. Upper Saddle River, NJ: Prentice Hall. p. 162. ISBN 0-13-227828-6. OCLC 32921996.
2. A Simple Min-Cut Algorithm
3. A faster algorithm for finding the minimum cut in a graph