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

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

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

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|}$ را بیشینه می‌کند. به سخنی دیگر بیشترین جریان را از چشمه به چاه می‌رساند.