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

فرض کنید که ${\displaystyle N=(V,E)}$

جریان بیشینه

تعریف: گنجایش یال نگاشتی است ${\displaystyle c:E\to R_{+}}$

تعریف: جریان نگاشتی است ${\displaystyle f:E\to R_{+}}$

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

تعریف: اندازهٔ جریان گرهٔ ${\displaystyle s}$

پرسمان جریان بیشینه ${\displaystyle |f|}$

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

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

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

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

• West, Douglas B. (1996). Introduction to Graph Theory (First Edition ed.). Prentice Hall, Inc. ISBN 0-13-227828-6.