Sieci Transportowe

Definicja

Siecią transportową nazywamy graf zorientowany (P, U), gdzie P
jest zbiorem wierzchołków grafu natomiast U zbiorem łuków
(zbiorem par uporządkowanych), bez pętli, w którym określone są
trzy funkcje:

funkcja pojemności:

k : U → R

+

∪ {0}, k((p

i

, p

j

)) = k

i ,j

­ 0,

maksymalna ilość tego, co może być przesłane łukiem
(p

i

, p

j

).

funkcja kosztów:

l : U → R, k((p

i

, p

j

)) = k

i ,j

, koszt przesłania

jednostki łukiem, czas przebycia łuku, długość łuku
(p

i

, p

j

).

funkcja zapotrzebowania:

d : P → R.

Sieci Transportowe

Niech p

i

∈ P wówczas, jeżeli

d (p

i

) > 0:

wówczas, p

i

nazywamy wyjściem, punktem

docelowym, natomiast d (p

i

) nazywamy

zapotrzebowaniem w punkcie p

i

.

d (p

i

) = 0:

wówczas, p

i

nazywamy punktem tranzytowym.

d (p

i

) < 0:

wówczas, p

i

nazywamy wejściem, punktem

początkowym, natomiast d (p

i

) nazywamy zapasem w

punkcie p

i

.

Sieci Transportowe

Zbiór wyjść oznaczamy przez S , zbiór wejść E .

Sieci Transportowe

Definicja

Siecią zredukowaną nazywamy sieć która ma tylko jedno wejście
p

0

i jedno wyjście p

n

.

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

Zagadnienie znajdowania najkrótszej drogi w grafie. Algorytm
Forda. Łuk będzie reprezentował drogę pomiędzy wierzchołkami
grafu. Wartość nad łukiem (p

i

, p

j

) będzie oznaczała długość drogi

pomiędzy wierzchołkami p

i

oraz p

j

.

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

Algorytm Forda I

1

Każdemu wierzchołkowi p

i

przyporządkować wartość u

i

następująco:

u

0

= 0, oraz

u

i

= −∞, dla i = 1, 2, 3, . . . , n.

2

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez u

i

− l

i ,j

.

3

Gdy żadna modyfikacja nie jest już możliwa, to dla każdego
łuku (p

i

, p

j

) ∈ U mamy u

i

− u

j

¬ l

i ,j

oraz dla każdego

wierzchołka p

k

i

6= p

0

istnieje co najmniej jeden wierzchołek

p

k

j

taki, że (p

k

j

, p

k

i

) ∈ U oraz

u

k

j

− u

k

i

= l

k

j

,k

i

.

(1)

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

Algorytm Forda II

4

Zaczynając od p

n

wyznaczyć ciąg

α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

],

który wskazuje najkrótszą drogę, a dla każdego łuku tej drogi
zachodzi (1). Dodając równania (1) odpowiadające łukom z
drogi α otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

Najkrótsza droga α ma długość, która wynosi −u

n

.

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

Twierdzenie

Dla każdej sieci transportowej powyższego zagadnienia można
zdefiniować sieć zredukowaną, równoważną wyjściowej.

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

p

1

5

p

2

7

3

p

3

9

p

4

p

5

d (p

1

) < 0, d (p

2

) < 0, d (p

3

) < 0

d (p

4

) > 0, d (p

5

) > 0

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

p

0

0

0

0

p

1

5

p

2

7

3

p

3

9

p

4

p

5

d (p

0

) < 0

d (p

1

) = 0, d (p

2

) = 0, d (p

3

) = 0

Sieci Transportowe

Zagadnienie znajdowania najkrótszej drogi w grafie

p

0

0

0

0

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

0

0

d (p

0

) < 0

d (p

1

) = 0, d (p

2

) = 0, d (p

3

) = 0

d (p

6

) > 0

d (p

4

) = 0, d (p

5

) = 0

Sieci Transportowe

Zadanie

p

0

5

2

1

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

4

1

Sieci Transportowe

Zadanie

l

0,1

= 5

l

1,4

= 5

l

3,5

= 9

l

0,2

= 2

l

2,4

= 7

l

4,6

= 4

l

0,3

= 1

l

2,5

= 3

l

5,6

= 1

Sieci Transportowe

Zadanie

p

1

p

2

p

3

p

4

p

5

u

0

0

0

u

1

−∞

− 5

u

2

−∞

− 2

u

3

−∞

− 1

u

4

−∞

− 10

u

5

−∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

1

p

2

p

3

p

4

p

5

u

0

0

0

u

1

−∞

− 5

u

2

−∞

− 2

u

3

−∞

− 1

u

4

−∞

− 10

u

5

−∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

p

0

5

2

1

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

4

1

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

u

1

−∞

− 5

u

2

−∞

− 2

u

3

−∞

− 1

u

4

−∞

− 10

u

5

−∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

u

1

−∞

− 5

u

2

−∞

− 2

u

3

−∞

− 1

u

4

−∞

− 10

u

5

−∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

0

, p

1

)

(p

0

, p

2

)

(p

0

, p

3

)

u

0

= 0

u

0

= 0

u

0

= 0

u

1

= −∞

u

2

= −∞

u

3

= −∞

l

0,1

= 5

l

0,1

= 2

l

0,1

= 1

u

0

− u

1

> l

0,1

u

0

− u

2

> l

0,2

u

0

− u

3

> l

0,3

0 − (−∞) > 5

0 − (−∞) > 2

0 − (−∞) > 1

TAK

TAK

TAK

u

1

= u

0

− l

0,1

u

2

= u

0

− l

0,2

u

3

= u

0

− l

0,3

u

1

= 0 − 5

u

2

= 0 − 2

u

3

= 0 − 1

u

1

= −5

u

2

= −2

u

3

= −1

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

p

0

5

2

1

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

4

1

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

1

, p

4

)

u

1

= −5

u

4

= −∞

l

1,4

= 5

u

1

− u

4

> l

1,4

0 − (−∞) > 5

TAK

u

4

= u

1

− l

1,4

u

4

= −5 − 5

u

4

= −10

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

p

0

5

2

1

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

4

1

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

u

1

−∞

− 5

− 5

u

2

−∞

− 2

− 2

u

3

−∞

− 1

− 1

u

4

−∞

− ∞

− 10

u

5

−∞

− ∞

− ∞

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

2

, p

4

)

(p

2

, p

5

)

u

2

= −2

u

2

= −2

u

4

= −10

u

5

= −∞

l

2,4

= 7

l

2,5

= 3

u

2

− u

4

> l

2,4

u

2

− u

5

> l

2,5

−2 − (−10) > 7

−2 − (−∞) > 3

TAK

TAK

u

4

= u

2

− l

2,4

u

5

= u

2

− l

2,5

u

4

= −2 − 7

u

5

= −2 − 3

u

4

= −9

u

5

= −5

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

u

5

−∞

− ∞

− ∞

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

u

5

−∞

− ∞

− ∞

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

3

, p

5

)

u

3

= −1

u

5

= − − 5

l

3,5

= 9

u

3

− u

5

> l

3,5

−1 − (−5) > 9

NIE

p

0

5

2

1

p

1

5

p

2

7

3

p

3

9

p

4

p

5

p

6

4

1

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

− 9

u

5

−∞

− ∞

− ∞

− 5

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

− 9

u

5

−∞

− ∞

− ∞

− 5

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

4

, p

6

)

u

4

= −9

u

6

= −∞

l

4,6

= 4

u

4

− u

6

> l

4,6

−9 − (−∞) > 4

TAK

u

6

= u

4

− l

4,6

u

6

= −9 − 4

u

6

= −13

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

− 9

− 9

u

5

−∞

− ∞

− ∞

− 5

− 5

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

− 9

− 9

u

5

−∞

− ∞

− ∞

− 5

− 5

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

2008-03-06

Sieci Transportowe

Zadanie

Dla każdego łuku (p

i

, p

j

) ∈ U, dla którego u

i

− u

j

> l

i ,j

zastąpić u

j

przez

u

i

− l

i ,j

.

(p

5

, p

6

)

u

5

= −5

u

6

= −14

l

5,6

= 1

u

5

− u

6

> l

5,6

−5 − (−14) > 1

TAK

u

6

= u

5

− l

5,6

u

6

= −5 − 1

u

6

= −6

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

u

0

0

0

0

0

0

0

0

u

1

−∞

− 5

− 5

− 5

− 5

− 5

− 5

u

2

−∞

− 2

− 2

− 2

− 2

− 2

− 2

u

3

−∞

− 1

− 1

− 1

− 1

− 1

− 1

u

4

−∞

− ∞

− 10

− 9

− 9

− 9

− 9

u

5

−∞

− ∞

− ∞

− 5

− 5

− 5

− 5

u

6

−∞

− ∞

− ∞

− ∞

− ∞

− 14

− 6

Sieci Transportowe

Zadanie

Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p

i

, p

j

) ∈ U mamy u

i

− u

j

¬ l

i ,j

oraz dla każdego wierzchołka

p

k

i

6= p

0

istnieje co najmniej jeden wierzchołek p

k

j

taki, że

(p

k

j

, p

k

i

) ∈ U oraz

u

k

j

− u

k

i

= l

k

j

,k

i

.

p

0

, 0

p

1

, −5

5

p

2

, −2

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

Sieci Transportowe

Zadanie

Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p

i

, p

j

) ∈ U mamy u

i

− u

j

¬ l

i ,j

oraz dla każdego wierzchołka

p

k

i

6= p

0

istnieje co najmniej jeden wierzchołek p

k

j

taki, że

(p

k

j

, p

k

i

) ∈ U oraz

u

k

j

− u

k

i

= l

k

j

,k

i

.

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p

i

, p

j

) ∈ U mamy u

i

− u

j

¬ l

i ,j

oraz dla każdego wierzchołka

p

k

i

6= p

0

istnieje co najmniej jeden wierzchołek p

k

j

taki, że

(p

k

j

, p

k

i

) ∈ U oraz

u

k

j

− u

k

i

= l

k

j

,k

i

.

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Zaczynając od p

n

wyznaczyć ciąg α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

], który

wskazuje najkrótszą drogę, a dla każdego łuku tej drogi zachodzi
(1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Zaczynając od p

n

wyznaczyć ciąg α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

], który

wskazuje najkrótszą drogę, a dla każdego łuku tej drogi zachodzi
(1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Zaczynając od p

n

wyznaczyć ciąg α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

], który

wskazuje najkrótszą drogę, a dla każdego łuku tej drogi zachodzi
(1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Zaczynając od p

n

wyznaczyć ciąg α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

], który

wskazuje najkrótszą drogę, a dla każdego łuku tej drogi zachodzi
(1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Zaczynając od p

n

wyznaczyć ciąg α = [p

n

, p

k

1

, . . . , p

k

l

, p

0

], który

wskazuje najkrótszą drogę, a dla każdego łuku tej drogi zachodzi
(1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy

0 − u

n

= l

0,k

l

+ l

k

l

,k

l −1

+ · · · + l

k

1

,n

= l (α).

p

0

, 0

5

2

1

p

1

, −5

5

p

2

, −2

7

3

p

3

, −1

9

p

4

, −9

p

5

, −5

p

6

, −6

4

1

Sieci Transportowe

Zadanie

Znaleźć maksymalny przepływ w sieci zredukowanej (P, U).

1

Przyporządkować wierzchołkowi p

0

znak (−, ∞).

2

Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków
p

i

o znaku (p

l

, α

i

). Każdemu wierzchołkowi p

j

, który jeszcze

nie został zaznaczony i dla którego r

i ,j

> 0 oraz [p

i

, p

j

] ∈ U

przypisać znak (p

i

, α

j

), gdzie α

j

= min{α

i

, r

i ,j

}. Jeżeli

wierzchołkowi p

j

można przypisać różne znaki, to wybrać

dowolną z możliwości (najlepiej tą, dla której wartość α

j

jest

największa). Kontynuować znakowanie aż do chwili, gdy:

1

otrzymuje wierzchołek p

n

, wówczas przechodzimy do punktu 3;

2

wierzchołek p

n

nie ma znaku i nie można już przyporządkować

znaku żadnemu innemu wierzchołkowi, wówczas przechodzimy
do punktu 4.

Sieci Transportowe

Zadanie

3

Zmienić przepływ następująco: zaczynając od p

n

wyznaczyć

ciąg σ = [p

0

, . . . , p

n

], w którym każdy wierzchołek jest

znakiem dla następnego. Pomniejszyć o α

n

pojemności

rezydualne r

i ,j

łuków (p

i

, p

j

) ∈ σ oraz powiększyć o α

n

pojemności rezydualne r

j ,i

. Wrócić do punktu 1.

4

Układ wartości r

i ,j

dla (p

i

, p

j

) ∈ U stanowi przepływ

maksymalny.

Sieci Transportowe

Zadanie

Znaleźć maksymalny przepływ w sieci poniżej.

p

0

8

9

3

p

1

9

p

2

9

8

p

5

4

p

4

p

3

p

6

9

15

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

1

x

.9

2

x

.8

.9

3

x

.15

4

x

.9

5

.4

x

6

x

Sieci Transportowe

Zadanie

Przyporządkować wierzchołkowi p

0

znak (−, ∞).

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

2

x

.8

.9

3

x

.15

4

x

.9

5

.4

x

6

x

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.

8

.9

.3

(−,

∞

)

1

x

.9

(p

0

, 8)

2

x

.8

.9

3

x

.15

4

x

.9

5

.4

x

6

x

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.

8

.9

.3

(−,

∞

)

1

x

.9

(p

0

, 8)

2

x

.8

.9

3

x

.15

4

x

.9

5

.4

x

6

x

2008-03-06

Sieci Transportowe

Zadanie

Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków p

i

o znaku

(p

l

, α

i

). Każdemu wierzchołkowi p

j

, który jeszcze nie został zaznaczony i

dla którego r

i ,j

> 0 oraz [p

i

, p

j

] ∈ U przypisać znak (p

i

, α

j

), gdzie

α

j

= min{α

i

, r

i ,j

}.

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.

9

.3

(−,

∞

)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

4

x

.9

5

.4

x

6

x

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-,

4

x

.9

5

.4

x

6

x

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-,

4

x

.9

-,

5

.4

x

6

x

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.

3

(−,

∞

)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-,

4

x

.9

-,

5

.4

x

(p

0

, 3)

6

x

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-,

4

x

.9

-,

5

.4

x

(p

0

, 3)

6

x

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.

8

.9

(p

0

,

9

)

3

x

.15

-, (p

2

, 8)

4

x

.9

-,

5

.4

x

(p

0

, 3)

6

x

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.

9

(p

0

,

9

)

3

x

.15

-, (p

2

, 8)

4

x

.9

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

x

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

x

.9

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

x

-,(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

x

.9

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

x

-,(p

4

,

9

)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

x

.9

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

x

-,(p

4

, 9)

[p

0

, p

2

, p

4

, p

6

]

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

x

.9 0

/

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

-,(p

4

, 9)

[p

0

, p

2

,

p

4

,

p

6

]

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

x

.8

.9 0

/

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

9

x

.9 0

/

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

-,(p

4

, 9)

[p

0

,

p

2

,

p

4

, p

6

]

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.9 0

/

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

9

x

.8

.9 0

/

(p

0

, 9)

3

x

.15

-, (p

2

, 8)

4

9

x

.9 0

/

-, (p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

-,(p

4

, 9)

[

p

0

,

p

2

, p

4

, p

6

]

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

1

x

.9

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

3

x

.15

(p

2

, 8)

4

9

x

.0

(p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

3

x

.15

(p

2

, 8)

4

9

x

.0

(p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

3

x

.15

(p

2

, 8)

4

9

x

.0

(p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-,

3

x

.15

(p

2

, 8)

4

9

x

.0

(p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-,

3

x

.15

(p

2

, 8)

-,

4

9

x

.0

(p

2

, 9)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-,

3

x

.15

(p

2

, 8)

-,

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-,

3

x

.15

(p

2

, 8)

-,

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-,

3

x

.15

(p

2

, 8)

-,

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-, (p

4

, 8)

3

x

.15

(p

2

, 8)

-,

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-, (p

4

, 8)

3

x

.15

(p

2

, 8)

-, (p

2

, 8)

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

-,

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-, (p

4

, 8)

3

x

.15

(p

2

, 8)

-, (p

2

, 8)

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-, (p

4

, 8)

3

x

.15

(p

2

, 8)

-, (p

2

, 8)

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

9

x

(p

4

, 9)

-, (p

3

, 8)

[p

0

, p

1

, p

4

, p

2

, p

3

, p

6

]

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8

.0

(p

0

, 9)

-, (p

4

, 8)

3

x

.15 7

/

(p

2

, 8)

-, (p

2

, 8)

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8 0

/

.0

(p

0

, 9)

-, (p

4

, 8)

3

8

x

.15 7

/

(p

2

, 8)

-, (p

2

, 8)

4

9

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9

(p

0

, 8)

(p

0

, 8)

2

9

x

.8 0

/

.0 8

/

(p

0

, 9)

-, (p

4

, 8)

3

8

x

.15 7

/

(p

2

, 8)

-, (p

2

, 8)

4

9 1

/

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8

.0

.3

(−, ∞)

(−, ∞)

1

x

.9 1

/

(p

0

, 8)

(p

0

, 8)

2

9

x

.8 0

/

.0 8

/

(p

0

, 9)

-, (p

4

, 8)

3

8

x

.15 7

/

(p

2

, 8)

-, (p

2

, 8)

4

8

9 1

/

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.8 0

/

.0

.3

(−, ∞)

(−, ∞)

1

8

x

.9 1

/

(p

0

, 8)

(p

0

, 8)

2

9

x

.8 0

/

.0 8

/

(p

0

, 9)

-, (p

4

, 8)

3

8

x

.15 7

/

(p

2

, 8)

-, (p

2

, 8)

4

8

9 1

/

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

-, (p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.0

.0

.3

(−, ∞)

(−, ∞)

1

8

x

.1

(p

0

, 8)

(p

0

, 8)

2

9

x

.0

.8

(p

0

, 9)

(p

4

, 8)

3

8

x

.7

(p

2

, 8)

(p

2

, 8)

4

8

1

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

(p

3

, 8)

Sieci Transportowe

Zadanie

p

0

p

1

p

2

p

3

p

4

p

5

p

6

0

x

.0

.0

.3

(−, ∞)

(−, ∞)

(−, ∞)

1

8

x

.1

(p

0

, 8)

(p

0

, 8)

2

9

x

.0

.8

(p

0

, 9)

(p

4

, 8)

3

8

x

.7

(p

2

, 8)

(p

2

, 8)

4

8

1

x

.0

(p

2

, 9)

(p

1

, 8)

5

.4

x

(p

0

, 3)

(p

0

, 3)

6

8

9

x

(p

4

, 9)

(p

3

, 8)