Vidi fonton por Teoremo pri maksimuma-fluo kaj minimuma-tranĉo

En [[Optimumigo (matematiko)|optimumigo]], la '''teoremo pri maksimuma-fluo kaj minimuma-tranĉo''' asertas, ke la maksimuma fluo en [[flureto]] trairanta de ''la''[[Glosaro de grafeteorio|'' fonto'']] ĝis la [[Glosaro de grafeteorio|''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 problemo|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 <math>f: E\to \mathbb{R}^+</math>, signita kiel <math>f_{uv}</math> aŭ <math>f(u,v)</math>. '''Kapablon''' ankaŭ estu funkcio <math>c: E\to \mathbb{R}^+</math>, signita kiel <math>c_{uv}</math> aŭ <math>c(u,v)</math>. Kapablo reprezentas la maksimuman fluon, kiu povas traflui tra la eĝo.

Jenaj regulojn devas sekvi al fluoj:
: 1. Kapabla limo:
:: <math>\forall (u,v)\in E: \qquad  f_{uv} \le c_{uv}</math>
: 2. Konservado de fluo:
:: <math>\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}.</math>

La '''tutan fluon''' oni povas kalkulas jene
: <math>|f| = \sum\nolimits_{v: (s,v)\in E} f_{sv},</math>
kie s estas la fonto kaj la kalkulo sumas la fluon de la fonto ĝis la dreno.

La [[fluo-maksimumigo|problemo de fluo-maksimumigo]] celas maksimumigi <math>|f|</math>, t.e. la fluon de fonto ĝis dreno.

=== Minimuma tranĉo ===
'''s-t-tranĉo''' <math>C = (S,T)</math> estas iu dividado de V tia, ke ''s'' ∈ ''S'' kaj ''t'' ∈ ''T''.
La '''tranĉeĝaro''' de C estas la eĝaro jena
: <math> \{ (u, v) \in E \ : \ u \in S, v \in T \}.</math>
Klare, se oni forigus ĉiujn eĝojn en la tranĉeĝaro, <math>|f|</math> iĝas 0.

Oni difinas '''kapablon''' de ''s-t-tranĉo'' kiel
: <math>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},</math>
kie <math>d_{ij} = 1</math> se <math>i \in S</math> kaj <math>j \in T</math>, 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 ==
[[Dosiero:max-flow min-cut example.svg|frame|dekstra|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.

[[Kategorio:Grafeteorio]]
[[Kategorio:Matematikaj teoremoj]]
[[Kategorio:Optimumigo]]