Síť
Síť je čtveřice ( )ctsGN ,,,= kde ( )AVG ,= je prostý orientovaný graf
a každé orientované hraně ( )vu, je přiřazeno nezáporné číslo, které se
nazývá kapacita hrany ( )vu, , formálně ( ) 0, ≥vuc . Pro orientovanou
hranu ( ) Avu ∉, předpokládáme ( ) 0, =vuc . V síti jsou dále vyznačeny
dva speciální uzly: zdrojový uzel s a cílový uzel t. Dále budeme bez
újmy na obecnosti předpokládat, že každý uzel leží na nějaké
(orientované) cestě z uzlu s do uzlu t.
Příklad sítě
s t
10
16
8
24
11
7
15 18
14
Tok v síti
Tok v síti ( )ctsGN ,,,= je zobrazení RVVf →×: splňující
následující podmínky:
1. f u ,v≤cu ,v,∀ u ,v∈V
2. f u ,v=− f u ,v ,∀ u ,v∈V
3. ∑
v∈V
f u ,v=0,∀u∈V −{s ,t}
Příklad toku v síti
Zde jsou kapacity hran vyznačeny červeně a hodnoty f u ,v modře.
Absence hodnoty značí f u ,v=0
10
15
20
18
5
16
12
s
t14
- 14
-12
12
2
- 2
-2
2
12
-12
● ( )vuf , se nazývá tok z uzlu u do uzlu v.
●
∣f ∣=∑
u∈V
f s ,u se nazývá hodnota toku f
● ∑
u∈V
f u ,v se nazývá tok do uzlu v
●
∑
u∈V
f v ,u se nazývá tok z uzlu v
● ∑
u∈V
f u ,v0
f u ,v se nazývá kladný tok do uzlu v
● ∑
u∈V
f v ,u0
f v ,u se nazývá kladný tok z uzlu v
Následující tvrzení jsou snadným důsledkem definice:
● ( ) ( ) ( ) VuuufVuuufuuf ∈=⇒∈−= ,0,,,, , čili tok z uzlu do
téhož uzlu je nulový.
●
∑
u∈V
f u ,v=,∀ u∈V −{s ,t} , čili celkový tok do každého uzlu
různého od počátečního a cílového je nulový.
● Pokud mezi uzly u, v neexistuje hrana, potom ( ) ( ) 0,, == uvfvuf .
Sumační formalizmus
Pro množiny uzlů X ,Y ⊆V bude symbol f  X ,Y  znamenat
∑
u∈X
∑
v∈Y
f u ,v
Někdy budeme vynechávat složené závorky {,} pro označení množin.
Například ve vzorci ( ) ( )VsfsVsf ,, =− , značí sV − množinu { }sV − .
Lemma 1
Nechť N =G , s ,t ,c je síť, G=V , A prostý orientovaný graf,
X ,Y , Z⊆V a f tok v síti N, potom platí
(1) f  X ,Y =− f Y , X 
(2) f  X , X =0
(3) f  X ∪Y , Z = f  X ,Z  f Y , Z if X ∩Y =∅
Budeme řešit následující úlohu:
Pro zadanou siť N =G , s ,t ,c najděte tok
f max v síti N, který má maximální hodnotu,
čili, ∣f max∣≥∣ f ∣ pro každý f v síti N.
Ford-Fulkersonova metoda
Tato metoda spočívá na třech základních pojmech:
zbytková síť,
vylepšující cesta
řez
Začneme s nulovým tokem, čili f u ,v=0,∀u ,v∈V . Každou iterací
najdeme vylepšující cestu, která zvětší aktuální tok, což je cesta z
počátečního do cílového uzlu, podél které se podaří “protlačit”
dodatečný tok. Iterace probíhají dokud se nám daří nacházet vylepšující
cesty. Výsledný tok pak bude maxiální.
Zbytková kapacita, zbytková síť
Nechť ( )ctsGN ,,,= je síť a f tok v této síti. Pro každou dvojici uzlů
Vvu ∈, , definujeme zbytkovou kapacitu
c f u , v=cu ,v− f u ,v
vzhledem k toku f. Dále definujeme zbytkovou síť vzhledem k toku f
N f =G f , s ,t ,c f  ,
kde
G f =V , Af 
a
Af ={u ,v∈V ×V |c f u ,v0}
Lemma 2
Nechť ( )ctsGN ,,,= je síť a f tok v této síti. Nechť N f =G f , s ,t ,c f 
je zbytková síť vzhledem k toku f a nechť f je tok v síti N f . Potom
zobrazení ( ) RVVff →×+ : takové, že
( )( ) ( ) ( )vufvufvuff ,,, +=+
je tokem v síti N.
Vylepšující cesta
Je-li dána síť ( )ctsGN ,,,= a tok f v ní definovaný, vylepšující cesta
je jakákoliv (orientovaná) cesta z počátečního uzlu s do cílového uzlu t
ve zbytkové síti N f =G f , s ,t ,c f 
Z definice zbytkové sítě plyne, že každá orientovaná hrana ( )vu, ve
vylepšující cestě zvyšuje tok z uzlu u do uzlu v při zachování podmínky
1 z definice toku.
Kapacita vylepšující cesty
Je-li dána síť ( )ctsGN ,,,= s tokem f , a je-li p vylepšující cesta ve
zbytkové síti N f =G f , s ,t ,c f  , definujeme kapacitu vylepšující
cesty p vzhledem k toku f
cf  p=min {c f u ,v | hrana u ,v je obsažena v cestě p}
Lemma 3
Nechť ( )ctsGN ,,,= je síť s tokem f a nechť p je vylepšující cesta ve
zbytkové síti N f =G f , s ,t ,c f  . Definujme zobrazení f p :V ×V  R
následovně:
f u ,v=c f  p jestliže hrana u ,v je v cestě p
(*) f u ,v=−c f  p jestliže hrana u ,v je v cestě p
f u ,v=0 jinak.
Potom f p je tok v síti N f s hodnotou ∣f p∣=c f  p
Důsledek 4
Nechť ( )ctsGN ,,,= je síť, f tok v této síti a p vylepšující cesta ve
zbytkové síti N f =G f , s ,t ,c f  . Nechť je definováno zobrazení
f p :V ×V  R jako v Lemma 3. Potom zobrazení
f :V ×V  R , f u ,v= f u ,v f p u ,v je tokem v síti N a platí
∣f ∣=∣f ∣∣ f p∣∣ f ∣ .
Při realizaci Ford-Fulkersonova
algoritmu neustále zvyšujeme
aktuální tok dokud dokážeme nalézt
vylepšující cestu. Nyní dokážeme, že
tok je maximální právě tehdym když
už žádná vylepšující cesta ve
zbytkové síti neexistuje. Je to
důsledkem toho, že maximální tok se
rovná minimálnímu řezu.
Řez v síti, tok řes řez, kapacita řezu
Řez ( )TS, v síti ( )ctsGN ,,,= je každý rozklad množiny uzlů V na
podmnožiny S a SVT −= takové, že Ss ∈ a Tt ∈ .
Tok přes řez ( )TS, v síti N při daném toku f je číslo ( )TSf , .
Kapacita řezu ( )TS, v síti N je číslo ( )TSc , .
Zatímco tok přes řez může zahrnovat i záporné hodnoty toku mezi uzly,
kapacita řezu je vždy součet kladných hodnot.
Lemma 5
Nechť je dána síť ( )ctsGN ,,,= s tokem f nechť ( )TS, je řez v síti N.
Potom platí, že tok přes řez ( )TS, se rovná hodnotě toku f , čili
( ) fTSf =, .
Důkaz:
Podle Lemma 1 (3) můžeme psát f S ,T = f S ,V − f S ,S  a podle
Lemma 1 (2) platí f S ,T = f S ,V  Opět podle Lemma 1 (3)
můžeme psát f S ,V = f s ,V  f S−s ,V  . Dále platí
f S−s ,V =∑
u∈S
u≠s
∑
v∈V
f u ,v . Avšak ∑
v∈V
f u ,v=0 pro u≠s podle
podmínky 3 z definice toku. Tedy f S ,T = f s ,V =∣ f ∣
Jednoduchým důsledkem Lemma 5 je to, že hodnota toku se rovná
celkovému toku do cílového uzlu. Další důsledek ukazuje, jak je možno
použít kapacity k nalezení horního odhadu pro hodnotu toku.
Důsledek 6
Hodnota každého toku v síti ( )ctsGN ,,,= je menší nebo rovna kapacitě
každého řezu v síti N.
Důkaz:
Nechť ( )TS, je řez. Podle Lemma 5 a podmínky 1 z definice toku platí
∣f ∣= f S ,T =∑
u∈S
∑
v∈T
f u ,v≤∑
u∈S
∑
v∈T
cu ,v=cS ,T 
Věta 7 (o maximálním toku a minimálním řezu)
Nechť ( )ctsGN ,,,= je síť s tokem f . Pak jsou následující tvrzení
ekvivalentní:
(1) f je a maximální tok v síti N
(2) ve zbytkové síti N f =G f , s ,t ,c f  nejsou žádné vylepšující cesty
(3) je-li ( )TS, řez v síti N s minimální kapacitou, platí ( )TScf ,=
Důkaz:
( ) ( )21 ⇒ : Nechť f je maximální tok v síti N a předpokládejme, že v
G f existuje vylepšující cesta. Potom podle Důsledku 4 suma toků
f  f p kde f p je definováno vztahem (*) je tok v síti N s hodnotou
větší než f , což je spor s tím, že f je maximální tok.
( ) ( )32 ⇒ : Nechť neexistuje vylepšující cesta v Nf . Neexistuje
tedyorientovaná cesta v grafu G f , z počátečního uzlu s do cílového
uzlu t. Definujme množiny S, T takto:
S={u∈V | v grafu G f existuje cesta z uzlu s do uzlu u} , SUT −=
Rozklad ( )TS, je řezem neboť Ss ∈ a St ∉ , protože v grafu Gf
neexistuje cesta z uzlu s do uzlu t. Pro každé dva uzly ( ) TvSuvu ∈∈ ,,,
platí ( ) ( )vucvuf ,, = , protože jinak by platilo u ,v∈Af a tedy Sv ∈ .
Proto podle Lemma 5 platí ( ) ( )TScTSff ,, == .
( ) ( )13 ⇒ : Podle důsledku 6 platí ( )TScf ,≤ pro každý řez ( )TS, . Proto
ze vztahu ( )TScf ,= plyne, že f je maximální tok.
SCHÉMA FORD FULKERSONOVA ALGORITMU
1. Položíme [ ] 0, =vuf , [ ] 0, =uvf pro každé dva uzly u ,v∈V
2. Vypočítáme zbytkové kapacity c f u , v=cu ,v− f u ,v .
Vytvoříme zbytkovou síť N f =G f , s ,t ,c f  , kde G f =V , Af  a
Af ={u ,v∈V ×V |cu ,v0}
3. Pokud neexistuje orientovaná cesta p v grafu Gf mezi počátečním a
cílovým uzlem, algorithms končí a poslední tok f je maximální. Jinak
nalezneme takovou orientovanou cestu a označíme ji p.
4. Vypočítáme c f  p=min {c f u ,v | hrana u ,v je v cestě p}
Pro každou dvojici uzlů ( )vu, z cesty p spočítáme:
f u ,v= f u ,vc f  p, f v ,u= f v ,u−c f  p . Přejdeme na 2.
Příklad
Najděte maximální tok v síti s počátečním uzlem s a cílovým uzlem t.
s t
16
13
12
14
9 7
20
4
10 4
Řešení – 1. iterace
Hodnota toku = 0 Zbytková síť
Modrá vylepšující cesta s kapacitou 4
s t
16
13
12
14
9 7
20
4
10 4
s t
16
13
12
14
9 7
20
4
10 4
s t
Řešení – 2. iterace:
Hodnota Toku = 4 Zbytková síť
Modrá vylepšující cesta s kapacitou 7
s t
16
13
12
14
9 7
20
4
10 4
s t
12
13
8
10
5
7
20
4
10 4
4
-4
-4
4
4
4
-4
-4
-4
4
4
4
4
Řešení – 3. iterace:
Hodnota toku = 11 Zbytková síť
Modrá vylepšující cesta s kapacitou 8
s t
16
13
12
14
9 7
20
4
10 4
s t
5
13
8
11
5
7
13
4
3 11
11
-11
-4
4
11
4
-4
-11
-4
11
4
3
7
4
-7
7
-7
7
-7
4
7
Řešení – 4. iterace:
Hodnota toku = 19 Zbytková síť
Modrá vylepšující cesta s kapacitou 4
s t
16
13
12
14
9 7
20
4
10 4
12
s t
5
5
11
5
7
15
4
113
11 -12
4
11
4
-4
-11
-4
11
4
3
-1 1
7
-7
15
-15
12
5
8
-11
-8 8
Řešení – 5. iterace:
Hodnota toku = 23 Zbytková síť
Ve zbytkové síti neexistuje vylepšující cesta, hodnota toku je maximální.
s t
16
13
12
14
9 7
20
4
10 4
12
s t
5
1
11
9
7
1
4
113
11 -12
11
4
-11
-4
11
3
-1 1
7
-7
19
-19
12
19
12
-11
-12 12