Teoria grafow i sieci - temat nr 6

[ Pobierz całość w formacie PDF ]
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 6:
Przepływy w sieciach
1
PRZEPŁYWY W SIECIACH SKIEROWANYCH
Sieć standardowa
dla przepływów:
S =
〈
G,
{
a
}
,
{
c
}〉
gdzie:
G =
〈
W,Γ
〉
- graf Berge’a

1, d la źródło
0, dla
xs
=
ax
()
=


−
x st
xt
≠
,

1, d la
=
od pływ
s
≠
t
!!!
0
≤
c(x,y)
<
∞
przepustowość łuku (x,y)
Definicja przepływu
f
:
f
: U
→
R
( ) ( )
1.
x
,
∧
∈
y
U
0
≤
f
x
,
y
≤
c
x
,
y
2.
x
∧
W
∑
f
( )
x
,
y
−
∑
f
( ) ( )()
z
,
x
=
a
x
⋅
v
f
y
∈
()
x
−
()
z
∈
x
tzw. wartość przepływu
Przepływ maksymalny
f
*
:
v
( )
( )
f
*
= max
v
f
f
∈
F
zbiór wszystkich przepływów w S
gdzie:
() ( ) ( )
()
v
f
=
∑ ∑
∈
f
s
,
y
−
f
z
,
s
y
()
s
z
∈
−
1
s
∈
1
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 6:
Przepływy w sieciach
2
Przekrój rozdzielający
P
(źródło
s
od odpływu
t
):
P
=
{〈
x,y
〉∈
U : x
∈
W
1
∧
y
∈
W
2
}
gdzie:
W = W
1
∪
W
2
; W
1
∩
W
2
=
∅
;
P
≡
(W
1
,W
2
)
s
∈
W
1
;
t
∈
W
2
Przepustowość przekroju (rozdzielającego)
P
:
C
() ( )
P
=
∑
∈
c
x
,
y
x
,
y
P
Przekrój minimalny (rozdzielający):
C
( )
( )
P
*
= min
C
P
P
∈
P
zbiór wszystkich możliwych przekrojów w
S
.
TWIERDZENIE F-F (FORD’A - FULKERSON’A)
Wartość maksymalnego przepływu
v(f
*
)
jest równa
przepustowości minimalnego przekroju rozdzielającego
C(P
*
).
Łańcuch powiększalny
(przy jakimś przepływie
f
):
Każdy taki łańcuch
Ł(s,t),
łączący źródło
s
z odpływem
t
, że
każdy jego
łuk zgodny
z kierunkiem od
s
do
t
jest nienasycony,
a każdy
łuk przeciwny
– niewyschnięty, tzn. jeśli
t
x
0
=
s
,
x
1
,
x
2
,
…
,
x
n
−
,
1
x
tworzy łańcuch, wtedy
( ) ( )
( )
=
∀

x
i
−
1
,
x
i
∈
U
⇒
f
x
i
−
1
,
x
i
<
c
x
i
−
1
,
x
i
∧



∧
x
,
x
∈
U
⇒
f
x
,
x
>
0
i
=
1
n

i
i
−
1
i
i
−
1

n
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 6:
Przepływy w sieciach
3
PRZYKŁAD 1:
Sieć S wraz z funkcją C ( )
opisaną na łukach oraz funkcją f
f
)
(jedną z dopuszczalnych)
c
3
2
S
1
1
0
2
4
0
2
0
1
4
0
1
3
0
4
0
t
3
3
x
3
y
wartość funkcji c(x,y) dla łuku (x, y)
x
1
y
wartość funkcji przepływu f(x,y) dla łuku (x, y)
Zauważmy, że
przepływ
f
(opisany kolorem
zielonym
) jest
jednym z możliwych przepływów dopuszczalnych i spełnia
warunki przepływu podane wcześniej.
Jednym z możliwych
przekrojów rozdzielających
jest np.
przekrój:
gdzie:
P
1
=
{〈
s, 1
〉
,
〈
3, 4
〉
,
〈
2, t
〉}
W
1
=
{
s, 3, 2
}
, W
2
=
{
1, 4, t
}
którego
przepustowość
jest równa:
() ( )
C
P
=
∑
∈
c
x
,
y
=
3
+
3
+
1
=
7
x
,
y
P
1
Zauważmy, że przy przepływie
f
opisanym w tej chwili na S
istnieje
łańcuch powiększalny,
gdyż np. łańcuch
〈
s, 1, t
〉
charakteryzuje się tym, że każdy jego łuk zgodny z kierunkiem
od
s
do
t
(tzn.
〈
s
, 1
〉
,
〈
1,
t
〉
) jest nienasycony, bo f(s, 1) = 1< c(s, 1)
= 3 oraz f(1, t) = 1 < c (1, t) = 4, i każdy łuk przeciwny (nie ma
takich w łańcuchu
〈
s, 1, t
〉
) jest niewyschnięty.
1
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 6:
Przepływy w sieciach
4
Algorytm wyznaczania maksymalnego przepływu
Opiera się o następujące wnioski (z twierdzenia F-F):
I.
Przepływ
f
jest maksymalny
⇔
przy tym przepływie
nie istnieje
łańcuch powiększalny.
II.
Przekrój rozdzielający (W
1
, W
2
) jest minimalny
⇔
każdy
przepływ maksymalny
nasyca
wszystkie łuki
z W
1
do W
2
i
wysusza
wszystkie łuki
z W
2
do W
1
.
1.
W sieci wyznaczamy dowolny przepływ (np. f
≡
0);
2.
Cechujemy s : (-,
∞
); E(x) – cecha „prawa”.
X – zbiór wierzchołków ocechowanych i niesprawdzonych
X:=
{
s
}
4.
Wybieramy dowolny x
∈
X
a)
Dla każdego y
∈
W – nieocechowanego następnika x
sprawdzamy:
f(x,y) < c(x,y) ?
TAK – y cechujemy (x
+
, min
{
E(x), c(x,y) – f(x,y)
}
)
X:=X
∪{
y
}
NIE – kolejny y;
b)
Dla każdego
z
∈
W – nieocechowanego poprzednika x
sprawdzamy:
f(z,x) > 0 ?
TAK –
z
cechujemy (x
-
, min
{
E(x), f(z,x)
}
) , X:=X
∪{
z
}
NIE – rozpatrzyć kolejny
z
c)
X:=X\
{
x
}
. Przejdź do 3.
3.
t
∈
X ?
TAK – przejdź do 5.
NIE – X
≠
∅
?
TAK – przejdź do 4.
NIE – KONIEC, X – wyznacza W
1
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 6:
Przepływy w sieciach
5
5.
Zmiana przepływu
f
na
f
I
:
a)
Jeżeli
t
ma cechę (y
+
, E(t)), to
f
I
(y,t):= f(y,t) + E(t).
Jeżeli
t
ma cechę (y
-
, E(t)), to
f
I
(t,y):= f(t,y) – E(t).
b)
Jeżeli y ma cechę (x
+
, E(y)), to
f
I
(x,y):= f(x,y) + E(t).
Jeżeli y ma cechę (x
-
, E(y)), to
f
I
(y,x):= f(y,x) – E(t).
c)
x
≠
s ?
TAK – y:=x, przejdź do b)
NIE - przejdź do 2.
PRZYKŁAD c.d.
Wyznaczmy przepływ maksymalny dla sieci z Przykładu 1
przyjmując jako początkowy przepływ
f
≡
0.
3
2
S
3
1
0
2
Iteracja 1
y s 1 2 3 4 t
Cecha y
-,
∞
s
+
, 3 1
+
, 2 s
+
, 4 1
+
, 2 1
+
, 3
sieć po
1-szej
iteracji
4
0
2
0
3
4
0
1
3
0
4
0
t
3
3
Iteracja 2
y
3
2
S
3
1
0
2
s
1
2
3
4
t
4
3
2
0
3
4
0
1
sieć po
2-giej
iteracji
Cecha y
-,
∞
s
+
, 4 3
+
, 3 4
+
, 3
3
3
4
3
t
3
3
Iteracja 3
y
3
2
S
3
1
0
2
s
1
2
3
4
t
4
sieć po
3-ciej
iteracji
Cecha y
-,
∞
s
+
, 1
4
3
2
0
3
0
1
W
{}
{ }
()
( ) ( )
()
=
s
,
3
,
W
=
W
\
W
,
P
=
s
,
3
4
3
3
4
3
t
1
2
1
3
3
v
f
*
=
∑
f
s
,
y
−
∑
f
z
,
s
=
3
+
3
−
0
=
6
y
∈
()
s
∈
−
1
s
z
[ Pobierz całość w formacie PDF ]