W tej cz ci naszego kursu przedyskutujemy pewne przykłady zastosowa grafów
skierowanych do analizy zagadnie sieciowych, np. takich jak sie zdarze dla procesów
kolejkowania.
Zdefiniujemy pewne typy wierzchołków jakie wyst puj tylko w grafach skierowanych.
Wierzchołek grafu skierowanego nazywamy uj ciem, je li nie jest pocz tkiem adnej
kraw dzi. Na wykresie uj cia odpowiadaj punktom, z których nie wychodz adne
strzałki.
Wierzchołek grafu skierowanego nazywamy ródłem, je li nie jest on ko cem adnej
kraw dzi. Na wykresie uj cia odpowiadaj punktom, do których nie dochodz adne
strzałki.
u
t
w
z
v
Rysunek 18
x
y
Dla grafu pokazanego na Rysunku 18 wierzchołki v i y s uj ciami, a wierzchołki t i z s ródłami.
Twierdzenie. Ka dy sko czony acykliczny graf skierowany ma co najmniej jedno uj cie i
co najmniej jedno ródło.
Dowód. We my dowolny wierzchołek v1. Je li v1 jest uj ciem to koniec konstrukcji. Je li nie to z wierzchołka v1 wychodzi jaka kraw d do pewnego wierzchołka v2. Je li v2 jest uj ciem to koniec konstrukcji. Je li nie, to … i tak dalej. Otrzymujemy w ten sposób ci g
{v1, v2, v3,...} taki, e dla ka dego k ci g {v1v2v3…vk} jest drog . Poniewa graf jest acykliczny i sko czony to ka da taka droga jest acykliczna i jej długo jest ograniczona.
Musi wi c istnie droga o najwi kszej długo ci a to oznacza, e w którym momencie
osi gniemy uj cie.
29
Dowód na istnienie co najmniej jednego ródła jest analogiczne do przedstawionego.
Podamy teraz wersj twierdzenia Eulera dla grafów skierowanych.
Poniewa w grafach skierowanych kraw dzie s obiektami skierowanymi to musimy
u ci li poj cie stopnia wierzchołka.
Niech v b dzie wierzchołkiem grafu skierowanego G. Stopniem wej ciowym indeg(v)
nazywamy liczb kraw dzi grafu G, których ko cem jest wierzchołek v, a stopniem wyj ciowym outdeg(v) nazywamy liczb kraw dzi, których pocz tkiem jest v. Wtedy:
in deg( v) + out deg( v) = deg( v)
dla wszystkich wierzchołków. P tla w tym wzorze jest liczona dwukrotnie, raz przy
wej ciu i raz przy wyj ciu z wierzchołka.
Twierdzenie (Eulera dla grafów skierowanych). Załó my, e graf skierowany G jest
spójny, gdy traktujemy go jako graf nieskierowany. Wówczas istnieje zamkni ta droga
(skierowana) w grafie G, przechodz ca przez wszystkie kraw dzie grafu G wtedy i tylko
wtedy, gdy in deg( v) = out deg( v) dla ka dego wierzchołka v.
Dowód tego twierdzenia jest bardzo podobny do dowodu twierdzenia Eulera dla grafów
nieskierowanych.
Grafy skierowane z wagami.
W wielu zastosowaniach grafów skierowanych istotne jest czy dany wierzchołek v
mo na osi gn z innego wierzchołka u (czy pod aj c za strzałkami mo na si dosta z u
do v)? Na przykład przypu my, e ka dy wierzchołek grafu odpowiada pewnemu stanowi
automatu, takiemu jak POBIERZ, ODROCZ lub WYKONAJ, a kraw d od wierzchołka u
do v odpowiada temu, e automat mo e przej ze stanu u do stanu v w odpowiedzi na
pewne dostarczone dane.
Przypu my teraz, e ka de przej cie od jednego stanu do drugiego, tzn. przej cie
ka dej kraw dzi w grafie skierowanym wymaga poniesienia pewnych kosztów (np.
kosztów finansowych czy czasowych). Wa ne jest wi c pytanie o drog z u do v maj c
najmniejszy ł czny koszt, otrzymany przez dodanie kosztów wszystkich kraw dzi na tej
30
drodze. Je li wszystkie kraw dzie kosztuj tyle samo to najta sza jest droga najkrótsza. Na ogół jednak koszty kraw dzi s ró ne.
Graf skierowany z wagami, to graf skierowany bez kraw dzi wielokrotnych, w którym
ka dej kraw dzi jest przyporz dkowana pewna liczba, nazwana wag tej kraw dzi.
Szeregowanie zada .
Istniej te klasy problemów, dla których istnienie drogi minimalnej nie ma podstawowego
znaczenia. Jedna z takich klas problemów dotyczy szeregowania zada , które ma du e
znaczenie np. w przemy le czy biznesie.
Rozwa ymy teraz pewien „ artobliwy” przykład pokazuj cy kiedy szeregowanie
(kolejkowanie) zada ma zastosowanie.
Przypu my, ze chcemy przygotowa proste danie. Przepis wymaga wykonania
nast puj cych czynno ci:
a) Pokroi mi so w kawałki – 10 min.
b) Posieka cebul w kostk – 2 min.
c) Obra ziemniaki i pokroi je na wiartki – 5min.
d) Zamarynowa mi so z cebul i przyprawami – 30 min.
e) Rozgrza olej – 4 min. Usma y ziemniaki – 15 min. Podsma y kminek – 2min.
f) Usma y zamarynowane mi so – 4 min.
g) Zapiec podsma one mi so i ziemniaki – 60 min.
Ponadto
h) Ugotowa ry – 20 min.
W punkcie e) zgrupowali my 3 czynno ci poniewa musz one by wykonane po kolei.
Niektóre z innych czynno ci mog by wykonane jednocze nie je li nam kto pomaga
(powiedzmy, e mamy tylu pomocników ilu nam potrzeba).
31
Na Rysunku 19 pokazany jest graf skierowany, który przedstawia kolejno kroków i mo liwo ci działania jednoczesnego. Krojenie mi sa, siekanie cebuli, obieranie
ziemniaków i gotowanie ry u mog by wykonane w tym samym czasie.
maryno-
krojenie
wanie
siekanie
sma enie
sma enie
zapiekanie
start
Gotowanie
obieranie
ry u
Rysunek 19
Przerywane linie po krojeniu i obieraniu oznaczaj , e marynowanie mi sa i sma enie
ziemniaków nie mog si rozpocz , zanim nie zako czy si krojenie i obieranie.
Pozostałe przerywane linie maj podobne znaczenia.
Na Rysunku 20 przerysowany jest graf z Rysunku 19. W miejsce „kulinarnych” opisów
kraw dzi wprowadzili my wagi, które s czasami wykonywania poszczególnych operacji.
Wierzchołki oznaczaj etapy cz ciowego wykonania całego procesu, od lewej do prawej.
10
40
t
u
10
0
30
0
40
s
2
21
4
60
f
(4+15)
10
v
w
x
104
5
0
0
y
20
z
Rysunek 20
5
20
W tym przypadku droga minimalna od s do f ma wag 20 minut. Jednak oczywistym jest,
e potrzeba o wiele wi cej czasu na wykonanie całego procesu. Waga minimalna nic tu nie
daje.
32
Wa nym pytaniem jest: jaki jest minimalny czas potrzebny na wykonanie wszystkich
czynno ci w tym procesie?
Zbadajmy wierzchołki od lewej do prawej.
1. Rozpoczynamy w wierzchołku s w chwili 0.
2. Kiedy najwcze niej mo emy zako czy krojenie, siekanie i obieranie oraz dotrze do
wierzchołka v? Po 10 minutach, poniewa musimy poczeka na zako czenie operacji
trwaj cej 10 minut (pokrojenie), niezale nie od tego jak wcze nie zako czymy
operacje trwaj ce 2 minuty i 5 minut (odpowiednio: siekanie i obieranie). Tak naprawd 10 jest najwi ksz wag drogi od wierzchołka s do v.
3. Teraz, kiedy najwcze niej mo emy dotrze od wierzchołka v do w? Po 30 minutach (najwi ksza waga drogi od v do w). Tak wi c najkrótszym czasem, w którym mo na
si dosta z wierzchołka s do w jest 40 minut.
4. Podobnie najkrótszym czasem, w którym mo emy wykona cały proces tj. dotrze do
wierzchołka f jest 10+30+4+60=104 minuty.
W ka dym przypadku, najkrótszym czasem doj cia do danego wierzchołka jest najwi ksza
waga drogi z s do tego wierzchołka. Liczby (niewytłuszczone) wyst puj ce obok
wierzchołków podaj te czasy.
Acykliczny graf skierowany z nieujemnymi wagami, jednym ródłem i jednym uj ciem
nazywamy sieci zdarze .
Przykładem sieci zdarze jest graf na Rysunku 20.
Rozpatrzmy sie zdarze G ze ródłem s (start) i uj ciem f (finish -meta).
Dla wierzchołków u i v sieci zdarze G drog maksymaln z u do v jest droga o najwi kszej wadze, a jej wag nazywamy wag maksymaln z u do v i oznaczamy symbolem M ( u, v) .
Drog maksymaln z wierzchołka s do wierzchołka f nazywamy drog krytyczn , a ka d kraw d nale c do tej drogi nazywamy kraw dzi krytyczn .
33
(
A v), L( v) oraz S( v) okre lone na zbiorze wierzchołków V(G) i zdefiniowane poni ej s pomocne przy analizie sieci zdarze .
Je li wyjdziemy z wierzchołka s w chwili 0, to najkrótszy czas, w jakim mo emy przyby
do wierzchołka v po wykonaniu wszystkich zada poprzedzaj cych v wynosi M ( s, v) . Ten najwcze niejszy moment b dziemy oznacza (
A v) . W szczególno ci (
A f ) = M ( s, f ) jest
czasem w jakim mo emy zako czy cały proces.
Niech L( v) = M ( s, f ) − M ( v, f ) = (
A f ) − M ( v, f ) . Poniewa M ( v, f ) oznacza najkrótszy czas potrzebny do wykonania wszystkich czynno ci od v do f, to L( v) jest najpó niejszym momentem, w którym mo emy opu ci wierzchołek v i nadal wykona wszystkie
pozostałe operacje do chwili (
A f ) . Aby obliczy L( v) , mo emy posuwa si w tył od
wierzchołka f.
Rezerwa czasowa wierzchołka (zdarzenia) v
S( v) = L( v) − (
A v)
jest to maksymalny czas, w jakim wszystkie zadania zaczynaj ce si w wierzchołku v
mog nie by wykonywane, nie opó niaj c całego procesu.
Przykład. Sie zdarze z Rysunku 20 ma tylko jedn drog krytyczn : stvuwxf. Zatem czynno ci a), d), f) i g) naszego przepisu kulinarnego s krytyczne. Sie ta jest
przedstawiona jeszcze raz na Rysunku 21, przy czym droga krytyczna jest zaznaczona pogrubion lini .
10
40
t
u
10
0
30
0
2
21
40
4
60
s
f
10
v
w
x
5
0
0
y
20
z
Rysunek 21
5
20
34
Zauwa my, e gdyby wagi kraw dzi niekrytycznych zostały zmniejszone dzi ki
zwi kszeniu efektywno ci, to cały proces nadal trwałby 104 minuty. Nawet całkowite
wyeliminowanie zada niekrytycznych nie przyspieszyłoby procesu.
Warto ci funkcji A, L i S s podane w poni szej tabeli. Warto ci funkcji A s napisane
obok wierzchołków na Rysunkach 20 i 21.
s
t
u
v
w
x
y
z
f
A
0
10
40
10
40
44
5
20
104
L
0
10
40
10
40
44
10
104
104
S
0
0
0
0
0
0
5
84
0
Przykłady oblicze :
Je li wiemy, e
(
A u) = 4 ,
0 W ( u, v) = ,
0
(
A v) = 10 oraz W ( u, v) = 21 , to
(
A )
w = max 4
{ 0 + 1
,
0 0 + 2 }
1 = 40 .
Je li wiemy, e L( )
w = 4 ,
0 W ( v, )
w = 2 ,
1 L( u) = 40 oraz W ( v, )
w = 30 , to
L( v) = min 4
{ 0 − 2 ,
1 40 − 3 }
0 = 10 .
Gdzie: W ( k, m) oznacza wag kraw dzi od wierzchołka k do wierzchołka m.
Warto ci funkcji (
A v) w pierwszym wierszu s obliczane od lewej do prawej i kiedy znana
jest warto (
A f ) , warto ci L( v) w drugim wierszu s obliczane od prawej do lewej.
Zauwa my, e rezerwa czasowa wynosi 0 w ka dym wierzchołku na drodze
krytycznej. Tak jest zawsze
Poniewa S( y) = 5 , to zadanie obierania ziemniaków mo e by opó nione o 5 minut bez opó nienia całego obiadu. S( z) = 84 co oznacza, e z gotowaniem ry u mo emy (i powinni my!) poczeka około 80 minut.
Analizuj c kraw d ( v, )
w widzimy, e mogliby my opó ni to zadanie o 9 (= 30 − 2 )
1
minut, nie mo emy jednak wywnioskowa tego z rezerw czasowych. Z tego, e S( v) = 0
mo emy tylko wywnioskowa , e nie mo emy opó ni wszystkich zada zaczynaj cych
si w wierzchołku v.
35
Do bardziej szczegółowego (lokalnego) analizowania zada w sieci zdarze wprowadzimy
przydatn funkcj , rezerw czasow kraw dzi, okre lon w zbiorze kraw dzi grafu G.
Rezerwa czasowa kraw dzi (czynno ci) lub luz pełny wyra a maksymalne mo liwe
opó nienie zadania odpowiadaj cego kraw dzi ( u, v) . Wielko ta jest zdefiniowana jako: F( u, v) = L( v) − (
A u) − W ( u, v) ,
Wszystkie kraw dzie krytyczne maj rezerw czasow 0.
Twierdzenie. Niech b dzie dana sie zdarze .
a) Rezerwa czasowa kraw dzi F( u, v) jest równa 0 wtedy i tylko wtedy, gdy ( u, v) jest kraw dzi krytyczn .
b) F( u, v) ≥ ma {
x S( u), S( v }
) dla wszystkich kraw dzi sieci.
Skrócenie czasu wymaganego przez kraw d niekrytyczn nie powoduje zmniejszenia
całkowitego czasu F( u, v) potrzebnego do zako czenia procesu. Rozpoznanie kraw dzi krytycznych zwraca uwag na te operacje w procesie, w których ulepszenia mog sprawi
ró nic i w których opó nienia na pewno b d kosztowa .
36