WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
PRZEPA
YWY W SIECIACH
" SieciÄ… nazywamy parÄ™ uporzÄ…dkowanÄ… S = ( D, c) ,
gdzie: D = ( V, A ) jest grafem skierowanym,
c : A R+ jest funkcją, która przyporządkowuje łukowi
(u, v) liczbÄ™ rzeczywistÄ… nieujemnÄ… c(u, v), nazywanÄ…
przepustowością łuku;
w grafie D wyróżnione są dwa wierzchołki s, t "V (s `" t)
nazywane: s  z
ródłem , a t  ujściem sieci.
Przykład sieci
x
6 3
3 1
2 2
s v z t
1 2
3 3
y
Czasami wygodnie jest zdefiniować funkcjÄ™ c na caÅ‚ym zbiorze V × V
i wtedy przyjmujemy, że c(u, v) = 0 dla (u, v) " (V × V) \ A
" Przepływem z s do t w sieci S nazywamy funkcję
f : A R+ , spełniającą następujące warunki:
1. 0 d" f (u, v) d" c (u, v) dla każdego (u, v) " A
2. f (v,u) - f (u,v) = 0 dla każdego v " V \ {s, t}
" "
+ -
u"V (v) u"V (v)
(warunek zachowania przepływu)
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 1 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
Przykład przepływu w sieci
x
3 (3)
5 (6)
2 (3) 0 (1)
1 (2) 1 (2)
s v z t
1 (1) 1 (2)
3 (3)
3 (3)
y
f (s, x) = 5 d" 6 = c (s, x), f (x, t) = 3 d" 3 = c (x, t) itd.
f (x,u) - f (u, x) = ( f (x, t) + f (x, v))  ( f (s, x) + f (z, x)) =
" "
+ -
u"V (x) u"V (x)
= (3 + 2)  (5 + 0) = 5  5 = 0 itd.
" Wartością przepływu f nazywamy liczbę W( f ) daną wzorem:
W ( f ) = f (s,u) - f (u,s)
" "
+ -
u"V (s) u"V (s)
Z warunku zachowania przepływu wynika, że
W ( f ) = f (u,t) - f (t,u)
" "
- +
u"V (t) u"V (t)
Przykład wyznaczania wartości przepływu w sieci
W(f ) = f (s, x) + f (s, y) - f (s, v) = 5 + 3 - 1 = 7
lub
W(f ) = f (x, t) + f (z, t) + f (y, t) = 3 + 1 + 3 = 7
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 2 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
" Przekrojem sieci, który odpowiada niepustemu podzbiorowi
wierzchoÅ‚ków sieci U ‚" V ( U `" " ), nazywamy zbiór Å‚uków
PU = A )" ( U × ( V \ U) ) = { (u, v) " A : u " U, v " V \ U }
Przykład przekroju sieci
x
3
5
2 0
1 1
s v z t
1
1
3
3
y
U
Podzbiór wierzchołków U = { s, v, y }
(jego uzupełnienie do V to V \ U = { x, z, t })
i odpowiadający mu przekrój sieci: PU = { (s, x), (y, z), (y, t) }
" Przepływem przez przekrój PU nazywamy liczbę
f (U, V \ U) = f (u,v)
"
(u,v)"PU
Przykład wyznaczania przepływu przez przekrój sieci
Dla przekroju sieci PU = { (s, x), (y, z), (y, t) }
przepływ przez ten przekrój wynosi
f ({s, v, y}, ({x, t, z}) = f (s, x) + f (y, z) + f (y, t) = 5 + 1 + 3 = 9
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 3 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
Lemat
JeÅ›li s " U i t " V \ U dla pewnego podzbioru U ‚" V , to dla
dowolnego przepływu f z s do t zachodzi równość
W(f ) = f (U, V \ U) - f (V \ U, U) ,
Gdzie f (U, V \ U) jest przepływem przez przekrój PU ,
a f (V \ U, U) jest przepływem przez przekrój PV \ U .
Dowód
Z definicji wartości przepływu:
W ( f ) = f (s,u) - f (u,s),
" "
+ -
u"V (s) u"V (s)
a z warunków zachowania przepływu w wierzchołkach v " U \ {s}:
0 = f (v,u) - f (u,v) .
" "
+ -
u"V (v) u"V (v)
Zsumujmy stronami wszystkie równania:
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
W ( f ) = f (s,u) + f (s,u)÷Å‚ - f (u, s) + f (u, s)÷Å‚
" " " "
ìÅ‚ ìÅ‚
ìÅ‚u"V (s))"U u"V (s))"(V \U ) ÷Å‚ ìÅ‚u"V - -
÷Å‚
+ +
(s))"U u"V (s))"(V \U )
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚
0 = f (v,u) + f (v,u) + f (v,u)÷Å‚ +
" " "
ìÅ‚
ìÅ‚u"V (v))"{s} u"V (v))"(U \{s}) u"V (v))"(V \U ) ÷Å‚
+ + +
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚
- f (u,v) + f (u,v) + f (u,v)÷Å‚ dla v " U \ {s}
" " "
ìÅ‚
ìÅ‚u"V - - -
÷Å‚
(v))"{s} u"V (v))"(U \{s}) u"V (v))"(V \U )
íÅ‚ Å‚Å‚
Otrzymamy równanie:
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚÷Å‚
ìÅ‚
ìÅ‚
Å‚uki z s do v"U \{s}
W ( f ) = f (s,u) - f (u,v)÷Å‚÷Å‚ +
" " "
ìÅ‚
ìÅ‚ ÷Å‚
ìÅ‚u"V -
÷Å‚
ìÅ‚u"V +
v"U \{s}
(s))"U (v))"{s}
íÅ‚ Å‚Å‚÷Å‚
íÅ‚ Å‚Å‚
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 4 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚
ìÅ‚
Å‚uki z v"U \{s} do s
+ f (v,u)÷Å‚ - f (u, s)÷Å‚ +
" " "
ìÅ‚
ìÅ‚
ìÅ‚u"V (v))"{s} ÷Å‚ u"V -
÷Å‚
ìÅ‚v"U \{s}íÅ‚ + ÷Å‚
(s))"U
Å‚Å‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚÷Å‚
ìÅ‚
ìÅ‚
łuki w obrębie U \{s}
+ f (v,u) - f (u,v)÷Å‚÷Å‚ +
" " "
ìÅ‚
ìÅ‚ ÷Å‚
ìÅ‚u"V (v))"(U \{s}) u"V -
÷Å‚
ìÅ‚v"U \{s}íÅ‚ +
(v))"(U \{s})
Å‚Å‚÷Å‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚÷Å‚
ìÅ‚
ìÅ‚
Å‚uki z v"U do u"V \U
+ f (s,u) + f (v,u)÷Å‚÷Å‚ +
" " "
ìÅ‚
ìÅ‚
ìÅ‚u"V (v))"(V \U ) ÷Å‚
÷Å‚
ìÅ‚u"V + +
v"U \{s}
(s))"(V \U )
íÅ‚ Å‚Å‚÷Å‚
íÅ‚ Å‚Å‚
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚÷Å‚
ìÅ‚
ìÅ‚
Å‚uki z u"V \U do v"U
- f (u, s) + f (u,v)÷Å‚÷Å‚
" " "
ìÅ‚
ìÅ‚ ÷Å‚
ìÅ‚u"V -
÷Å‚
ìÅ‚u"V -
v"U \{s}
(s))"(V \U ) (v))"(V \U )
íÅ‚ Å‚Å‚÷Å‚
íÅ‚ Å‚Å‚
Trzy pierwsze składniki redukują się do 0 i pozostaje
W ( f ) = f (v,u) - f (u,v) = f (U ,V \U )- f (V \U ,U )
" "
(v,u)"PU (u,v)"PV \U
Przykład ilustrujący lemat
V \ U
x
3
5 2
0
1
s v z t
1
1
1
3 3
y
U
Podzbiór wierzchołków: U = { s, y, z },
odpowiadający mu przekrój sieci: PU = {(s, x), (y, t), (z, x), (z, t)}
i przepływ przez ten przekrój f ({s, y, z}, {v, x, t}) = 5 + 3 + 0 + 1 = 9
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 5 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
V \ U
x
3
5 2
0
1
s v z t
1
1
1
3 3
y
U
Podzbiór wierzchołków: V \ U = { v, x, t },
odpowiadający mu przekrój sieci: PV \ U = {(v, s), (v, y)}
i przepływ przez ten przekrój f ({v, x, t}, {s, y, z}) = 1 + 1 = 2 ;
7 = W(f ) = f ({s, y, z}, {v, x, t}) - f ({v, x, t}, {s, y, z}) = 9 - 2 = 7
" PrzepustowoÅ›ciÄ… przekroju PU dla U ‚" V nazywamy liczbÄ™
C(PU) =
"c(u,v)
(u,v)"PU
Przykład wyznaczania przepustowości przekroju
x
3
6
3 1
2 2
s v z t
2
1
3
3
y
U
C(P{s, v, y}) = c(s, x) + c(y, z) + c(y, t) = 6 + 2 + 3 = 11
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 6 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
Lemat
Dla dowolnego przepływu f z s do t w sieci S oraz przekroju PU ,
wyznaczonego przez podzbiór U ‚" V , dla którego s"U i t"V \ U,
zachodzi nierówność
W(f ) d" C(PU),
Dowód
Dla ustalonego przepływu f i zbioru U z twierdzenia wynika
W(f ) = f (U, V \ U) - f (V \ U, U) d" f (U, V \ U)
Z definicji przepływu wynika, że f (U, V \ U) d" C(PU)
" Minimalnym przekrojem sieci pomiędzy z
ródłem i ujściem
nazywamy taki przekrój PU , dla którego przepustowość jest
najmniejsza ze wszystkich przekrojów sieci odpowiadających
takim podzbiorom U ‚" V, że s " U i t " V \ U.
Zatem dla każdego przepływu w sieci jego wartość nie jest większa
od przepustowości minimalnego przekroju.
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 7 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
Przykład wyznaczania minimalnego przekroju sieci
x
6 3
3 1
2 2
s v z t
1 2
3 3
y
Przekroje sieci pomiędzy s i t odpowiadają wszystkim zbiorom postaci
{s} *" A , gdzie A jest podzbiorem {v, x, y, z}:
U1 = {s}, U2 = {s, v}, U3 = {s, v, x}, U4 = {s, x},
U5 = {s, x, y}, U6 = {s, v, x, y}, U7 = {s, v, y}, U8 = {s, y},
U9 = {s, y, z}, U10 = {s, v, y, z}, U11 = {s, v, x, y, z}, U12 = {s, x, y, z},
U13 = {s, x, z}, U14 = {s, v, x, z}, U15 = {s, v, z}, U16 = {s, z}.
(C(PUi )) = (9, 10, 7, 9, 11, 8, 11, 11, 12, 12, 8, 11, 11, 9, 13, 12)
i=1,...,16
Wartość minimalna w tym ciągu to 7 = C(P{s,v,x})
U3
x
3
6
3 1
2 2
s v z t
1
2
3
3
y
Podzbiór U3 = {s, v, x} wyznacza minimalny przekrój PU3 pomiędzy
z
ródłem i ujściem o przepustowości C( PU3 ) = 7.
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 8 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
Zatem przepływ:
x
3 (3)
5 (6)
2 (3) 0 (1)
1 (2) 1 (2)
s v z t
1 (1) 1 (2)
3 (3)
3 (3)
y
o wartości 7 jest przepływem o maksymalnej wartości w tej sieci.
Czy w każdej sieci można znalez
ć przepływ o wartości równej
przepustowości minimalnego przekroju?
TAK
Twierdzenie (Ford i Fulkerson, 1955)
W każdej sieci maksymalna wartość przepływu ze z
ródła do ujścia jest
równa przepustowości minimalnego przekroju pomiędzy z
ródłem
i ujściem.
Dla danej sieci S = (D, c), gdzie D = (V, A) jest grafem skierowanym
rozważmy drogę prostą P = (v1, & , vk) w pochodnym grafie
niekierowanym G(D).
Drodze P odpowiada ciąg łuków (a1, & , ak-1), w którym ai " A
dla i = 1, & , k-1 oraz ai = (vi, vi+1) albo ai = (vi+1, vi).
A
uk ai w przypadku ai = (vi, vi+1) nazywamy Å‚ukiem zgodnym z
kierunkiem od v1 do vk , a w przypadku ai = (vi+1, vi) Å‚ukiem
niezgodnym z tym kierunkiem.
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 9 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
" Dla danego przepływu f w sieci S oraz drogi prostej P ciąg
(a1, & , ak-1) nazywamy ścieżką z v1 do vk powiększającą
przepływ f, jeśli dla każdego łuku ai zgodnego z kierunkiem od
v1 do vk zachodzi f (ai) < c(ai), a dla każdego łuku ai
niezgodnego z kierunkiem od v1 do vk zachodzi f (ai) > 0.
Jeżeli dla danego przepływu f istnieje w sieci ścieżka z s do t
powiększająca ten przepływ, to wartość przepływu przez sieć można
zwiÄ™kszyć o pewnÄ… wartość µ > 0, definiujÄ…c nowy przepÅ‚yw f 2 , w
którym f 2 (a) = f (a) + µ , dla każdego Å‚uku a zgodnego z kierunkiem
od s do t, oraz f 2 (a) = f (a) - µ , dla każdego Å‚uku a niezgodnego z tym
kierunkiem.
NajwiÄ™ksza możliwa wartość µ jest równa minimum z różnic pomiÄ™-
dzy przepustowością i wartością przepływu dla łuków zgodnych z
kierunkiem z s do t oraz z wartości przepływu dla łuków niezgodnych.
Przykłady ścieżek powiększających przepływy w sieci
x
4 (6)
2 (3)
1 (1)
3 (3)
0 (2)
2 (2)
z
s v t
1 (1) 1 (2)
3 (3)
3 (3)
y
W( f ) = 5
Ciąg łuków ((s, x), (z, x), (z, t)) odpowiada drodze P = (s, x, z, t) w G(D).
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 10 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
A
uki (s, x) i (z, t) sÄ… zgodne z kierunkiem od s do t, a Å‚uk (z, x) jest
niezgodny z tym kierunkiem.
x
4 (6)
2 (3)
1 (1)
3 (3)
0 (2)
2 (2)
z
s v t
1 (1) 1 (2)
3 (3)
3 (3)
y
W( f ) = 5
Ciąg łuków ((s, x), (z, x), (z, t)) jest ścieżką z s do t powiększającą
przepływ f :
c(s, x) - f (s, x) = 6 - 4 = 2 i c(z, t) - f (z, t) = 2 - 0 = 2,
czyli dla łuków zgodnych z kierunkiem od s do t zachodzi f (a) < c(a);
f (z, x) = 1 > 0 dla Å‚uku niezgodnego z tym kierunkiem.
Można zatem zwiÄ™kszyć wartość przepÅ‚ywu w sieci przyjmujÄ…c µ = 1;
nowe wartości przepływów przez łuki ze ścieżki wyniosą wtedy:
f 2 (s, x) = f (s, x) + 1 = 4 + 1 = 5, f 2 (z, x) = f (z, x) - 1 = 1 - 1 = 0
f 2 (z, t) = f (z, t) + 1 = 0 + 1 = 1; W( f 2 ) = W( f ) + 1 = 5 + 1= 6
x
5 (6)
2 (3)
0 (1)
3 (3)
1 (2)
2 (2)
z
s v t
1 (1) 1 (2)
3 (3)
3 (3)
y
W( f 2 ) = 6
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 11 / 12
WYŻSZA SZKOA
A INFORMATYKI STOSOWANEJ I ZARZ
DZANIA WIT
x
5 (6) 2 (3)
0 (1)
3 (3)
2 (2)
1 (2)
z
s v t
1 (1) 1 (2)
3 (3)
3 (3)
y
W( f 2 ) = 6
Ciąg łuków ((v, s), (x, v), (x, t)) jest ścieżką z s do t powiększającą
przepływ f 2 : c(x, t) - f 2 (x, t) = 3 - 2 = 1 ,
czyli dla Å‚uku zgodnego z kierunkiem od s do t zachodzi f 2 (a) < c(a);
f 2 (v, s) = 2 > 0 i f 2 (x, v) = 3 > 0
dla łuków niezgodnych z tym kierunkiem.
Można zatem zwiÄ™kszyć wartość przepÅ‚ywu w sieci przyjmujÄ…c µ = 1;
nowe wartości przepływów przez łuki ze ścieżki wyniosą wtedy:
f 2 2 (v, s) = f 2 (v, s) - 1 = 2 - 1 = 1, f 2 2 (x, v) = f 2 (x, v) - 1 = 3 - 1 = 2
f 2 2 (x, t) = f 2 (x, t) + 1 = 2 + 1 = 3; W( f 2 2 ) = W( f 2 ) + 1 = 6 + 1= 7
x
5 (6)
3 (3)
0 (1)
2 (3)
1 (2)
1 (2)
z
s v t
1 (1) 1 (2)
3 (3)
3 (3)
y
W( f 2 2 ) = 7
Twierdzenie
Przepływ f w sieci S jest maksymalny wtedy i tylko wtedy, kiedy nie
istnieje dla niego ścieżka powiększająca ze z
ródła s do ujścia t.
MATEMATYKA DYSKRETNA (14) J.Sikorski Strona 12 / 12