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 , signita kiel  aŭ . Kapablon ankaŭ estu funkcio , signita kiel  aŭ . Kapablo reprezentas la maksimuman fluon, kiu povas traflui tra la eĝo.

Jenaj regulojn devas sekvi al fluoj:
 1. Kapabla limo:

 2. Konservado de fluo:


La tutan fluon oni povas kalkulas jene

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

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

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

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

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

kie  se  kaj , 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 
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.

Kategorio:Grafeteorio
Kategorio:Matematikaj teoremoj
Kategorio:Optimumigo