Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.3.Własnościstrukturalnesieci
15
2.3.Własnościstrukturalnesieci
Wtympodrozdzialeograniczymynaszerozważaniadotakichsieci,którychgraf
jestgrafemspójnym.Wprzypadkusieci,którychgrafyniesąspójne,ichposzcze-
gólnefragmentymożnarozważaćniezależnie.
NiechdanabędziesiećN=(P,T,A).Zewzględunacharakterpołączeńelementów
sieciwyróżniasiękilkatypówsieci.
Definicja2.8.Paręwęzłówxiynazywamyciasnąpętlą,jeżeliwęzełyjestjednocześniewęzłem
wejściowymiwyjściowymwęzłax,tzn.jeżeli(x,y)∈Ai(y,x)∈A.SiećN
nazywamyczystą,jeżeliniezawieraciasnychpętli.
ł
Definicja2.9.SiećNnazywamyprostą,jeżeliróżnejejwęzłymająróżnezbiorywejściowelub
wyjściowe,tzn.:
∀x,y∈V:x±y⇒(In(x)±In(y)∨Out(x)±Out(y)).
(2.6)
ł
Definicja2.10.SiećNnazywamymaszynąstanową,jeżelikażdejejprzejściemadokładniejed-
nomiejscewejścioweidokładniejednomiejscewyjściowe,tzn.,gdyjestspełniony
warunek2:
∀t∈T:IIn(t)I=i∧IOut(t)I=i.
(2.7)
SiećNnazywamygrafemsynchronizacji,jeżelikażdejejmiejscemadokładnie
jednoprzejściewejścioweidokładniejednoprzejściewyjściowe,tzn.,gdyjest
spełnionywarunek:
∀p∈P:IIn(p)I=i∧IOut(p)I=i.
(2.8)
ł
Jeślidodatkowografsiecijestgrafemsilniespójnym,tomówimyosilniespójnej
maszyniestanowejlubsilniespójnymgrafiesynchronizacji.
Maszynastanowaigrafsynchronizacjisąpojęciamidualnymi.Grafdualnydo
maszynystanowejN(tzn.sieć,którapowstajezsieciN,gdymiejscazostaną
2
SymbolIXIoznaczamoczbioruX.