Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
9
Tabela1.2.Odległościmiędzyzamkami
B
A
C
d
g
e
f
20,01
12,53
21,95
19,11
31,14
13,45
A
-
22,85
20,01
30,41
23,19
14,87
9,;5
B
-
25,00
13,00
12,16
22,85
10,05
21,95
-
C
12,53
25,00
28,18
29,55
15,03
9,;5
d
-
19,11
30,41
13,00
28,18
25,08
15,02
–
e
23,19
12,16
31,14
29,55
25,08
17,69
-
f
13,45
14,;7
10,05
15,03
15,02
17,69
g
-
Zmniejszeniezasięguprzesyłuo10%spowodujezmniejszeniezasięgunadawa-
niazdużegozamkudo18kmimałegozamkudo12,6km.Skutkujetousunięciem
zgrafuzrys.1.7akrawędzi(A,e),(e,C)oraz(g,A).Grafzusuniętymikrawędziami
jestpokazanynarys.1.7b.Wtymgrafiewierzchołekeniemożeprzesyłaćżadnej
informacji,wierzchołekfmożesiękomunikowaćjedyniezC,e,g,awierzchołekg
zC,e,f.Zatemsystemostrzeżeńniebędziedziałałprawidłowo.
Awariawęzłajestrównoważnausunięciuwęzłaorazincydentnychznimkrawędzi.
Zakładającnp.awarięwęzłag,otrzymamygrafpokazanynarys.1.7c.Wtymgrafie
komunikacjawzajemnapomiędzypozostałymiwierzchołkaminiejestmożliwa,gdyż
niemożnaprzesłaćinformacjizwęzłówf,C,edożadnegozpozostałych.
Rys.1.7.a)Grafsiecikomunikacjizamków(zasięgi14kmi20km);b)grafsiecikomunikacji
zamków(zasięgi12,6kmi18km);c)grafsiecikomunikacjizamkówpoawariiwęzłag
Problem1.4.Grafpłaski
Rozpatrzmyiteracyjnąprocedurępodziałukwadratuoustalonymboku.Kwadrat
dzielimynadwierówneczęści,np.liniąpoziomą.Wnastępnymkrokugórnypro-
stokątjestdzielonypionowąliniąnadwierówneczęści.Procedurapodziałujedne-
gozdwóchostatnioutworzonychprostokątów(górnegolubprawego)jestpowtarza-