Teoremo pri maksimuma-fluo kaj minimuma-tranĉo

En optimumigo, la teoremo pri maksimuma-fluo kaj minimuma-tranĉo asertas, ke la maksimuma fluo en flureto trairanta de la fonto ĝis la dreno egalas al la sumo de pezoj de la minimuma tranĉo, t.e. aro da eĝoj kun la plej malgranda sumo de pezoj tiaj, ke se forigantaj, malligas la fonton kaj la drenon.

La teoremo pri maksimuma-fluo kaj minimuma-tranĉo estas malĝenerala kazo de dueca teoremo por linia programado kaj per ĝi oni povas devenigi teoremo de Menger kaj la teoremo de König.

Difino kaj asertoj

N = (V, E) estu orientita grafeo kun verticoj s, la fonto, kaj t ∈ V, la dreno.

Fluo estu funkcio $f:E\to \mathbb {R} ^{+}$, signita kiel $f_{uv}$ aŭ $f(u,v)$. Kapablon ankaŭ estu funkcio $c:E\to \mathbb {R} ^{+}$, signita kiel $c_{uv}$ aŭ $c(u,v)$. Kapablo reprezentas la maksimuman fluon, kiu povas traflui tra la eĝo.

Jenaj regulojn devas sekvi al fluoj:

1. Kapabla limo:

$\forall (u,v)\in E:\qquad f_{uv}\leq c_{uv}$

2. Konservado de fluo:

$\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}.$

La tutan fluon oni povas kalkulas jene

$|f|=\sum \nolimits _{v:(s,v)\in E}f_{sv},$

kie s estas la fonto kaj la kalkulo sumas la fluon de la fonto ĝis la dreno.

La problemo de fluo-maksimumigo celas maksimumigi $|f|$, t.e. la fluon de fonto ĝis dreno.

Minimuma tranĉo

s-t-tranĉo $C=(S,T)$ estas iu dividado de V tia, ke s ∈ S kaj t ∈ T. La tranĉeĝaro de C estas la eĝaro jena

$\{(u,v)\in E\ :\ u\in S,v\in T\}.$

Klare, se oni forigus ĉiujn eĝojn en la tranĉeĝaro, $|f|$ iĝas 0.

Oni difinas kapablon de s-t-tranĉo kiel

$c(S,T)=\sum \nolimits _{(u,v)\in (S\times T)\cap E}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},$

kie $d_{ij}=1$ se $i\in S$ kaj $j\in T$, 0 alie.

La problemo de minimuma s-t-tranĉo celas minimumigi c(S, T), t.e. trovi iu tranĉo S kaj T kies kapablo estu minimuma.

Aserto

La teoremo pri maksimuma-fluo kaj minimuma-tranĉo asertas, ke la solvoj al la du antaŭmenciitaj problemoj samas. T.e. la maksimuma s-t-fluo egalas al la minimuma kapablo inter ĉiuj s-t-tranĉoj.

Ekzemplo

Grafeo, kies fluo egalas al kapablo de s-t-tranĉo

La dekstra bildo montras reton kun tuta fluo 7. La verticoj blankaj kaj grizaj estas subgrafeo S kaj T de la s-t-tranĉo, kies tranĉeĝaron oni montras per strekaj eĝoj. Klare la kapalo de la tranĉo estas ankaŭ 7, same al la maksimuma fluo, kiel la teoremo asertas.