Teoria grafow i sieci - temat nr 5.pdf

(380 KB) Pobierz
Microsoft Word - Teoria grafow i sieci - temat nr 5.doc
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 5: Sieci, drogi ekstremalne w sieciach
1
SIECI, drogi ekstremalne w sieciach
1. Sieć :
{} { } J
S
= ξ
G
,
i
i
=
1
I
,
Ψ
j
j
=
1
gdzie:
G =〈 W , U , P 〉 - graf
ξ
i
:
W
→
X
i
,
i
=
1
I
Ψ
j
:
U
→
Y
j
,
j
=
1
J
ajczęściej: X i = R , Y j = R
2. Sieć stochastyczna (losowa):
9 bez zależności ξ i oraz Ψ j od czasu:
[ ]
() ( )
∨
ξ
i
:
W
→
0
i
∈
{ }
1 …
,
I
ξ
w
=
Pr
A
i
w
gdzie :
A w – pewne zdarzenie losowe dotyczące
wierzchołka w , np. A w ≡ wierzchołek w jest
sprawny (działa) ;
lub (i)
[ ]
() ( )
∨
Ψ
j
:
U
→
0
{ }
Ψ
u
=
Pr
A
j
∈
1 …
,
J
j
u
gdzie:
A u – pewne zdarzenia losowe dotyczące
gałęzi u , np. A u ≡ gałąź u jest sprawna;
A u ≡ długość gałęzi u wynosi l u , itp.
9 z zależnością ξ i oraz Ψ j od czasu :
[ ]
( ) ( )
∨
i
ξ
:
W
×
T
→
0
i
∈
{ }
1 …
,
I
w
,
t
=
Pr
A
,
T
⊂
R
+
∪
{ 0
i
w
,
t
gdzie:
A w,t – pewne zdarzenie losowe dotyczące
wierzchołka w i chwili t , np. A w,t ≡
wierzchołek w jest sprawny do chwili t, itp.
T – zbiór opisujący czas;
ξ
381467118.013.png
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 5: Sieci, drogi ekstremalne w sieciach
2
a)
b)
Sieć drogowa (a) i jej model grafowo-sieciowy (b)
( funkcja l opisana na gałęziach może mieć interpretację odległości )
381467118.014.png 381467118.015.png
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 5: Sieci, drogi ekstremalne w sieciach
3
Problem drzewa ekonomicznego
Dla danej sieci
S
=
G
,
∅
,
{} R
l
,
l
:
U
→
wyznaczyć taki karkas
T =
W
, P
U
*
*
grafu
G
=
W
,
U
,
P
, aby
L
( ) ( )
T
*
= min
L
T
T ∈
gdzie:
T – zbiór wszystkich karkasów grafu G ;
() ( )
L
T
=
∈
l
u
- koszt karkasu.
u
U
( T
)
Algorytm Prim’a (wyznaczania karkasu najtańszego)
1. Wybieramy dowolny x ∈ W i wśród gałęzi incydentnych z nim
wybieramy gałąź u I (nie pętlę) o najmniejszej wartości l(u I ) .
Tworzymy podgraf częściowy
G
I
=
W
I
,
U
I
,
P
I
zawierający
u I i wierzchołki incydentne z u I .
Podstawiamy:
G
II
:=
W
|
W
I
,
U
II
,
P
II
-
podgraf,
W /
II
:=
W
I
.
2. Wśród
gałęzi
u ∈ U
takich, że
, wybieramy gałąź
o najmniejszej wartości l(u) . Gałąź tą dołączamy do U I :
{ }
x
u
,
y
∈
P
∨
y
,
u
,
x
∈
P
,
x
∈
W
I
,
y
∈
W
II
W
I
:
=
W
I
∪
y
;
W
II
:
=
W
II
\
{ }
y
. Postępowanie kończymy,
gdy W II = ∅ . Wówczas
T :
*
G
I
.
PRZYKŁAD
Wybieramy
wierzchołek np. 3
1.
2.1
2.2
2.3
5
2
G
I
≡
3
G 1
I
≡
1
I
G 2
≡
1
1
G
≡
3
3
3
3
2
5
2
1
3
7
1
I
G 3
≡
3
1
5
4
5
1
5
4
5
4
2
2
4
8
G
II
≡
1
II
G 2
≡
II
G 2
≡
G
II
∅≡ ,
,
∅
∅
5
2
2
3
4
4
I
T 3
* =
*
381467118.016.png 381467118.001.png 381467118.002.png
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 5: Sieci, drogi ekstremalne w sieciach
4
Algorytm Kruskala
1. W zbiorze U wybieramy gałąź (nie pętlę) o najmniejszej
wartości l(u). Tworzymy podgraf częściowy
G
I
=
W
I
,
U
I
,
P
I
złożony z tej gałęzi i wierzchołków z nią incydentnych.
2. Spośród niewybranych gałęzi, nie tworzących łańcuchów
cyklicznych z podgrafem G I , wybieramy gałąź o najmniejszym
l(u) i dołączamy ją do G I wraz z wierzchołkami incydentnymi.
Za każdym razem przy wyborze następnej, najtańszej gałęzi,
wyliczamy liczbę cyklomatyczną powstającego grafu
częściowego i gałąź włączamy do zbioru gałęzi karkasu Ù
wyliczona liczba cyklomatyczna jest równa zeru. Postępowanie
kończymy, gdy W I = W . Wówczas
T :
*
G
I
.
DROGI EKSTREMALNE W SIECIACH SKIEROWANYCH
UWAGA : dotyczy tylko dróg prostych.
Sieć standardowa dla problemu dróg ekstremalnych:
{}
S
=
G
,∅
,
l
gdzie:
l : U → R
l(u) – „koszt” gałęzi u ∈ U ;
U(µ(x p ,x k ) ) – zbiór gałęzi drogi µ(x p ,x k ) z wierzchołka
p do x k ;
( ) ( )
( )
F
µ
(
x
p
,
x
k
)
=
∑
l
u
- „koszt” drogi µ(x p ,x k ) .
u
∈
U
µ
(
x
p
,
x
k
)
Definicja problemu wyznaczania drogi ekstremalnej:
w sieci S znaleźć taką drogę
µ
* ∈
D ,
( )
p
x
k
, dla której
F
( )
µ
*
(
x
p
,
x
k
)
=
min
F
( )
µ
(
x
p
,
x
k
)
p
k
p
k
µ ∈
(
x
,
x
)
D
(
x
,
x
)
lub
F
( )
µ
*
(
x
p
,
x
k
)
=
max
F
( )
µ
(
x
p
,
x
k
)
µ ∈
(
x
p
,
x
k
)
D
(
x
p
,
x
k
)
gdzie ( )
D ,
x
k
- zbiór wszystkich dróg prostych w G z x p do x k .
p
381467118.003.png
dr inż. Z. Tarapata, Teoria grafów i sieci, Temat nr 5: Sieci, drogi ekstremalne w sieciach
5
S jest cykliczna?
T
Rodzaj ekstremalizacji
min
max
N
l
≥
0
?
T
N
l
≤
0
?
T
Długości dróg cykl.>=0 ?
N
T
Długości dróg cykl.<=0 ?
N
T
Programowanie
dynamiczne
Programowanie
całkowitoliczbowe
pełny przegląd
Metoda dendrytów
dróg ekstremalnych
Sieci acykliczne – programowanie dynamiczne
µ
*
( )
x
p
,
x
k
=
?
w
G
I
=
W
,
U
I
,
P
I
x Ω - zbiór wierzchołków osiągalnych z x p w G I ;
( )
p
x Π - zbiór wierzchołków, z których w G I osiągalny jest x k ;
k
( ) ( )
= - zbiór wierzchołków, które mogą
wystąpić w ( )
Ω
x
p
∩
Π
x
k
x ,µ ; X = ∅ ⇒ nie istnieje ( )
p
x
k
x ,µ ;
p
x
k
G ,
=
,
U
P
- podgraf generowany przez X ⊂ W ;
WW … - warstwy w G;
0 , , ,
x
p
∈ ;
W
x
k
∈
W
K
0
K
X
dop
i
=
W
i
∩
X
- zbiór tzw. stanów dopuszczalnych w i -tym
etapie;
U dop
()
x
=
u
∈
U
:
∨
x
,
u
,
y
∈
P
y
∈
X
- zbiór
tzw. sterowań dopuszczalnych dla stanu x ∈ X;
( m - liczba łuków w drodze µ ;
N
( )
X
381467118.004.png 381467118.005.png 381467118.006.png 381467118.007.png 381467118.008.png 381467118.009.png 381467118.010.png 381467118.011.png 381467118.012.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin