Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
10
1.Defnicjagrafuiprzykładyzastosowań
naiteracyjnie.Kolejneczterykrokiprocedurypodziałuilustrujerys.1.8a.Proces
podziałumożebyćmodelowanyzapomocągrafu.Wierzchołkamigrafusąprosto-
kąty.Dwawierzchołkisąpołączonekrawędziąwtedy,gdyodpowiadająceimpro-
stokątymająwspólnybok.Grafykolejnychkrokówpodziałuprostokątasąpokaza-
nenarys.1.8b.
Rys.1.;.a)Podziałkwadratu;b)modelgrafowy
Łatwojestzauważyć,że:
-grafG
imaiwierzchołków;
-każdyzgrafówG
ijestpłaski,tzn.jestnarysowanynapłaszczyźniewtakispo-
sób,żejedynymiwspólnymiwierzchołkamiróżnychkrawędzimogąbyćtylkoich
końce.
Grafpokazanynarys.1.8bjesttzw.grafemmaksymalniepłaskim(p.rozdz.6).
Problem1.5.Siećradiowa
Pakietowasiećradiowa(ang.MultihopPacketRadioNetwork)składasięzpewnej
liczbykomunikującychsięzesobąstacjiradiowych.Każdazestacjimożebyćstacją
nadawczą,odbiorcząbądźpośredniczącą.Zewzględunaograniczonąmocstacji,za-
nimpakietdotrzeodwęzłapoczątkowegodokońcowego,przebywadrogęprzezwę-
złypośrednie.Węzłynadającemogąwprowadzaćzakłóceniapracysieci.Wyróżnia-
mydwatypykonfliktów:
-stacjawdanejchwilimożewykonywaćtylkojednączynność,tzn.niemoże
jednocześnienadawaćlubodbieraćwięcejniżjednejprzeznaczonejdlaniejtrans-
misji(jesttotzw.konfliktgłówny).Sytuacjakonfliktowajestzilustrowananarys.
1.9a,ponieważstacjav
2jednocześnieodbieratransmisjęodv
1inadajedov
3.Kon-
