Teoremo pri maksimuma-fluo kaj minimuma-tranĉo

El Vikipedio, la libera enciklopedio

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[redakti | redakti fonton]

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

Fluo estu funkcio , signita kiel . Kapablon ankaŭ estu funkcio , signita kiel . 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[redakti | redakti fonton]

s-t-tranĉo estas iu dividado de V tia, ke sS kaj tT. 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[redakti | redakti fonton]

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[redakti | redakti fonton]

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.