WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

PRZEPŁ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 – ź 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 ≤ f ( u, v) ≤ 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)

GRAFY i SIECI (6)

J.Sikorski

Strona 1 / 12

WYŻSZA SZKOŁ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 ≤ 6 = c ( s, x), f ( x, t) = 3 ≤ 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

GRAFY i SIECI (6)

J.Sikorski

Strona 2 / 12

WYŻSZA SZKOŁ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

5

3

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 ∈

)

U

P

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

GRAFY i SIECI (6)

J.Sikorski

Strona 3 / 12

WYŻSZA SZKOŁ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:













W ( f ) = 

∑ f ( s, u) − ∑ 

∑ f ( u, v) +

łuki z s do v∈ U \{ s}



+



−



 ∈

u V ( s)∩ U

∈

v U {

\ }

s  ∈

u V ( v)∩{ }

s



GRAFY i SIECI (6)

J.Sikorski

Strona 4 / 12

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

















+  ∑ 

∑ f ( v, u) −

∑ f u

( , s)  +

łuki z v∈ U \{ s} do s





+



−



 ∈

v U s

{

\ } ∈

u V ( v)∩ s

{ }



∈

u V ( s)∩ U















+  ∑ 

∑ f ( v, u) −

∑ f ( u, v) +

łuki w obrębie U \{ s}





+

−



 ∈

v U {

\ }

s  ∈

u V ( v)∩( U {

\ }

s )

∈

u V ( v)∩( U {

\ }

s ) 













+ 

∑ f ( s, u) + ∑ 

∑ f ( v, u) +

łuki z v∈ U do u∈ V \ U



+



+



 ∈

u V ( s)∩( V \ U )

∈

v U {

\ }

s  ∈

u V ( v)∩( V \ U ) 













− 

∑ f ( u, s) + ∑ 

∑ f ( u, v)

łuki z u∈ V \ U do v∈ U



−



−



 ∈

u V ( s)∩( V \ U )

∈

v U {

\ }

s  ∈

u V ( 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) P

∈

( u, v)∈

U

V

P \ U

Przykład ilustrują cy lemat

V

\ U

x

5

2

3

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

GRAFY i SIECI (6)

J.Sikorski

Strona 5 / 12

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

V

\ U

x

5

2

3

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 ∈

)

U

P

Przykład wyznaczania przepustowoś ci przekroju

x

6

3

3

1

2

2

s

v

z

t

1

2

3

3

y

U

C( P{ s, v, y}) = c( s, x) + c( y, z) + c( y, t) = 6 + 2 + 3 = 11

GRAFY i SIECI (6)

J.Sikorski

Strona 6 / 12

WYŻSZA SZKOŁ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 ) ≤ 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) ≤ f ( U, V \ U) Z definicji przepływu wynika, że f ( U, V \ U) ≤ C( PU)

• Minimalnym przekrojem sieci pomiędzy ź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.

GRAFY i SIECI (6)

J.Sikorski

Strona 7 / 12

WYŻSZA SZKOŁ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}: U 1 = { s},

U 2 = { s, v},

U 3 = { s, v, x},

U 4 = { s, x},

U 5 = { s, x, y}, U 6 = { s, v, x, y}, U 7 = { s, v, y}, U 8 = { s, y},

U 9 = { s, y, z}, U 10 = { s, v, y, z}, U 11 = { s, v, x, y, z}, U 12 = { s, x, y, z}, U 13 = { s, x, z}, U 14 = { s, v, x, z}, U 15 = { s, v, z}, U 16 = { s, z}.

( C( UP

= (9, 10, 7, 9, 11, 8, 11, 11, 12, 12, 8, 11, 11, 9, 13, 12)

i ) i

,

1

= ... 1

, 6

Wartość minimalna w tym ciągu to 7 = C( {

P s, v, }

x )

U 3

x

3

6

3

1

2

2

s

v

z

t

1

2

3

y

3

Podzbiór U 3 = { s, v, x} wyznacza minimalny przekrój U

P pomiędzy

3

źródłem i ujściem o przepustowości C( U

P ) = 7.

3

GRAFY i SIECI (6)

J.Sikorski

Strona 8 / 12

WYŻSZA SZKOŁ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 znaleźć 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 źródła do ujścia

jest równa przepustowości minimalnego przekroju pomiędzy źródłem

i ujściem.

Dla danej sieci S = ( D, c), gdzie D = ( V, A) jest grafem skierowanym rozważmy drogę prostą P = ( v 1, …, vk) w pochodnym grafie

niekierowanym G( D).

Drodze P odpowiada ciąg łuków ( a 1, …, ak−1), w którym ai ∈ A dla i = 1, …, k−1 oraz ai = ( vi, vi+1) albo ai = ( vi+1, vi).

Łuk ai w przypadku ai = ( vi, vi+1) nazywamy łukiem zgodnym z

kierunkiem od v 1 do vk , a w przypadku ai = ( vi+1, vi) łukiem

niezgodnym z tym kierunkiem.

GRAFY i SIECI (6)

J.Sikorski

Strona 9 / 12

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

• Dla danego przepływu f w sieci S oraz drogi prostej P ciąg ( a 1, …, ak−1) nazywamy ś cież ką z v 1 do vk powię kszają cą

przepływ f, jeśli dla każdego łuku ai zgodnego z kierunkiem od v 1 do vk zachodzi f ( ai) < c( ai), a dla każdego łuku ai niezgodnego z kierunkiem od v 1 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 ′, w

którym f ′( a) = f ( a) + ε , dla każdego łuku a zgodnego z kierunkiem od s do t, oraz f ′( 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)

2 (2)

0 (2)

s

v

z

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).

GRAFY i SIECI (6)

J.Sikorski

Strona 10 / 12

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

Ł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)

2 (2)

0 (2)

s

v

z

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 ′( s, x) = f ( s, x) + 1 = 4 + 1 = 5, f ′( z, x) = f ( z, x) − 1 = 1 − 1 = 0

f ′( z, t) = f ( z, t) + 1 = 0 + 1 = 1; W( f ′) = W( f ) + 1 = 5 + 1= 6

x

5 (6)

2 (3)

0 (1)

3 (3)

2 (2)

1 (2)

s

v

z

t

1 (1)

1 (2)

3 (3)

3 (3)

y

W( f ′) = 6

GRAFY i SIECI (6)

J.Sikorski

Strona 11 / 12

WYŻSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

x

5 (6)

2 (3)

0 (1)

2 (2)

3 (3)

1 (2)

s

v

z

t

1 (1)

1 (2)

3 (3)

3 (3)

y

W( f ′) = 6

Ciąg łuków (( v, s), ( x, v), ( x, t)) jest ścieżką z s do t powiększającą przepływ f ′:

c( x, t) − f ′( x, t) = 3 − 2 = 1 , czyli dla łuku zgodnego z kierunkiem od s do t zachodzi f ′( a) < c( a); f ′( v, s) = 2 > 0 i f ′( 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 ′ ( v, s) = f ′( v, s) − 1 = 2 − 1 = 1, f ′ ( x, v) = f ′( x, v) − 1 = 3 − 1 = 2

f ′ ( x, t) = f ′( x, t) + 1 = 2 + 1 = 3; W( f ′ ) = W( f ′) + 1 = 6 + 1= 7

x

5 (6)

3 (3)

0 (1)

2 (3)

1 (2)

1 (2)

s

v

z

t

1 (1)

1 (2)

3 (3)

3 (3)

y

W( f ′ ) = 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 źródła s do ujścia t.

GRAFY i SIECI (6)

J.Sikorski

Strona 12 / 12