Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.2.Sieciiichreprezentacjagraficzna
13
Przykładgrafudwudzielnegoprzedstawiononarys.2.3.Węzłyróżnychtypów
oznaczonoodmiennymikolorami.
x2
xi
x3
x4
Rys.2.3.Grafdwudzielny
Wszystkiepojęciaprzedstawionewtympodrozdzialemożnazdefiniowaćanalo-
giczniedlagrafówbezłukówwielokrotnych.
2.2.Sieciiichreprezentacjagraficzna
Jakjużwspomniałemnapoczątkudotegorozdziału,sieciPetriegosąprzedstawia-
nejakografydwudzielne.Wwiększościklassieciomawianychwtejksiążcenie
mogąwystępowaćłukiwielokrotneidefinicjetakichklassiecisąopartenagrafach
skierowanych,przedstawionychjakoparyG=(V,A).Grafyzłukamiwielokrot-
nymisłużądoopisugrafówosiągalności(zob.rozdz.5)orazsiecikolorowanych
(zob.rozdz.10).
Definicja2.7.UporządkowanątrójkępostaciN=(P,T,A)nazywamysiecią,jeżelisąspełnione
warunki:
(1)Pjestniepustymzbioremmiejsc.
(2)Tjestniepustymzbioremprzejść(tranzycji),takimżeP∩T=∅.
(3)A⊆(P×T)∪(T×P)jestzbioremłukówsieci.
DlasieciniskiegopoziomuzbiórAnazywanyjestrównieżrelacjąprzepływu.
ł
Będziemyodtądrozważaćtylkosieciskończone,tzn.takie,którychzbiorymiejsc
iprzejśćsązbioramiskończonymi.
Dlasieciprzyjmujesięnastępującąinterpretację.Siećprzedstawiasięjakograf
dwudzielnyG=(V,A),któregowęzłamisąelementyzbiorówPiT,tzn.V=
P∪T,łukamizaś,paryrelacjiA.Etykietyłukówniemająbezpośredniegozwiązku
