О гомоморфизме компонентной сети Петри
В виде компонентной сети Петри (CN-сети) рассмотрена редуцированная модель Петри параллельной распределенной системы для установления степени адекватности двух моделей (детальной модели Петри N и компонентной модели Петри CN) одной и той же исследуемой параллельной распределенной системы. Вводятся п...
Saved in:
| Date: | 2014 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/115732 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О гомоморфизме компонентной сети Петри / Е.А. Лукьянова // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 36-44 . — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-115732 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1157322017-04-12T03:02:30Z О гомоморфизме компонентной сети Петри Лукьянова, Е.А. Кибернетика В виде компонентной сети Петри (CN-сети) рассмотрена редуцированная модель Петри параллельной распределенной системы для установления степени адекватности двух моделей (детальной модели Петри N и компонентной модели Петри CN) одной и той же исследуемой параллельной распределенной системы. Вводятся понятия отношения χ компоненты и областей отношения компоненты. Установлен сюръективный гомоморфизм исследуемых моделей N и CN и изоморфизм сети N / χ — фактор-модели N по отношению χ и CN-сети. У вигляді компонентної мережі Петрі (CN-мережі) розглянуто редуковану модель Петрі паралельної розподіленої системи для встановлення ступеня адекватності двох моделей (детальної моделі Петрі N і компонентної моделі Петрі CN) однієї і тієї ж досліджуваної паралельної розподіленої системи. Вводяться поняття відношення χ компоненти і областей відношення компоненти. Встановлено сюр’єктивний гомоморфізм досліджуваних моделей N і CN та ізоморфізм мережі N / χ — фактор-моделі N у відношенні χ і CN-мережі. We analyze a reduced Petri net model of a parallel distributed system as a component Petri net (CN-net) to determine the adequacy of two models (a detailed Petri model N and a component Petri model CN) of the same parallel distributed system under study. The concepts of relation of a component and relation χ areas of components are introduced. The surjective homomorphism of the N and CN models and the isomorphism of net N /χ , factor-model N with respect to the relation χ, and CN-net are determined. 2014 Article О гомоморфизме компонентной сети Петри / Е.А. Лукьянова // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 36-44 . — Бібліогр.: 18 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/115732 004.021:004.312.4 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Лукьянова, Е.А. О гомоморфизме компонентной сети Петри Кибернетика и системный анализ |
| description |
В виде компонентной сети Петри (CN-сети) рассмотрена редуцированная модель Петри параллельной распределенной системы для установления степени адекватности двух моделей (детальной модели Петри N и компонентной модели Петри CN) одной и той же исследуемой параллельной распределенной системы. Вводятся понятия отношения χ компоненты и областей отношения компоненты. Установлен сюръективный гомоморфизм исследуемых моделей N и CN и изоморфизм сети N / χ — фактор-модели N по отношению χ и CN-сети. |
| format |
Article |
| author |
Лукьянова, Е.А. |
| author_facet |
Лукьянова, Е.А. |
| author_sort |
Лукьянова, Е.А. |
| title |
О гомоморфизме компонентной сети Петри |
| title_short |
О гомоморфизме компонентной сети Петри |
| title_full |
О гомоморфизме компонентной сети Петри |
| title_fullStr |
О гомоморфизме компонентной сети Петри |
| title_full_unstemmed |
О гомоморфизме компонентной сети Петри |
| title_sort |
о гомоморфизме компонентной сети петри |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/115732 |
| citation_txt |
О гомоморфизме компонентной сети Петри / Е.А. Лукьянова // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 36-44 . — Бібліогр.: 18 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT lukʹânovaea ogomomorfizmekomponentnojsetipetri |
| first_indexed |
2025-07-08T09:17:42Z |
| last_indexed |
2025-07-08T09:17:42Z |
| _version_ |
1837069775868526592 |
| fulltext |
ÓÄÊ 004.021: 004.312.4
Å.À. ËÓÊÜßÍÎÂÀ
Î ÃÎÌÎÌÎÐÔÈÇÌÅ ÊÎÌÏÎÍÅÍÒÍÎÉ ÑÅÒÈ ÏÅÒÐÈ
Àííîòàöèÿ. Â âèäå êîìïîíåíòíîé ñåòè Ïåòðè (CN-ñåòè) ðàññìîòðåíà ðåäóöèðîâàííàÿ ìî-
äåëü Ïåòðè ïàðàëëåëüíîé ðàñïðåäåëåííîé ñèñòåìû äëÿ óñòàíîâëåíèÿ ñòåïåíè àäåêâàòíî-
ñòè äâóõ ìîäåëåé (äåòàëüíîé ìîäåëè Ïåòðè N è êîìïîíåíòíîé ìîäåëè Ïåòðè CN) îäíîé
è òîé æå èññëåäóåìîé ïàðàëëåëüíîé ðàñïðåäåëåííîé ñèñòåìû. Ââîäÿòñÿ ïîíÿòèÿ îòíîøå-
íèÿ � êîìïîíåíòû è îáëàñòåé îòíîøåíèÿ êîìïîíåíòû. Óñòàíîâëåí ñþðúåêòèâíûé ãîìî-
ìîðôèçì èññëåäóåìûõ ìîäåëåé N è CN è èçîìîðôèçì ñåòè N / � — ôàêòîð-ìîäåëè N ïî
îòíîøåíèþ � è CN-ñåòè.
Êëþ÷åâûå ñëîâà: ñåòü Ïåòðè, êîìïîíåíòíàÿ ñåòü Ïåòðè, êëàññû ýêâèâàëåíòíîñòè, îòíî-
øåíèå êîìïîíåíòû, îáëàñòè îòíîøåíèÿ êîìïîíåíòû, ãîìîìîðôèçì.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ ðåàëüíûå òåõíè÷åñêèå è ïðîãðàììíûå ñèñòåìû, èñïîëüçóå-
ìûå äëÿ ðåøåíèÿ çàäà÷ ïðèêëàäíîãî õàðàêòåðà è óñòàíîâëåíèÿ ñïîñîáîâ
óïðàâëåíèÿ, çíà÷èòåëüíî óñëîæíèëèñü è òðåáóþò íàõîæäåíèÿ áîëåå ýêîíîìè÷-
íûõ è áîëåå íàäåæíûõ ìåòîäîâ ïðîâåðêè ïðàâèëüíîñòè èõ ôóíêöèîíèðîâàíèÿ.
Òðàäèöèîííûì è åñòåñòâåííûì ïîäõîäîì ê âîïðîñàì âåðèôèêàöèè ïàðàëëåëü-
íûõ ðàñïðåäåëåííûõ ñèñòåì ÿâëÿåòñÿ èõ ìîäåëèðîâàíèå ñåòÿìè Ïåòðè [1, 2].
Ñëîæíîñòü ïðîöåäóðû âåðèôèêàöèè òàêèõ ñèñòåì çàâèñèò îò ðàçìåðîâ èõ
ìîäåëåé: ÷åì ìåíüøå ðàçìåð ìîäåëè, òåì ïðîùå åå âåðèôèöèðîâàòü. Âîçìîæ-
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
� Å.À. Ëóêüÿíîâà, 2014
íîñòü äîñêîíàëüíîé ñòðóêòóðíîé õàðàêòåðèçàöèè ôóíäàìåíòàëüíûõ àñïåêòîâ ïà-
ðàëëåëüíûõ âû÷èñëåíèé ÿâëÿåòñÿ îñíîâíûì äîñòîèíñòâîì ôîðìàëèçìà ñåòåé
Ïåòðè, êîòîðûé ïîçâîëÿåò ïîëó÷àòü êà÷åñòâåííûå ìîäåëè èññëåäóåìûõ ñèñòåì.
Îäíàêî ââèäó áîëüøîé ñëîæíîñòè ìíîãèõ ðåàëüíûõ ðàñïðåäåëåííûõ ñèñòåì äå-
òàëèçàöèÿ ïðè èõ ìîäåëèðîâàíèè ÷àñòî ïðèâîäèò ê èññëåäîâàíèþ ñåòåé, ðàçìåðû
êîòîðûõ ïðè èõ ôîðìàëüíîì àíàëèçå ìîãóò ïðèâåñòè ê äîïîëíèòåëüíûì âû-
÷èñëèòåëüíûì çàòðàòàì.  ðåçóëüòàòå óìåíüøàåòñÿ âîçìîæíîñòü èñïîëüçîâà-
íèÿ ïîëíîé (äîñêîíàëüíîé) ìîäåëè äëÿ èññëåäîâàíèÿ ðåàëüíûõ ñèñòåì [3, 4].
Ïîýòîìó ïðè èññëåäîâàíèè ñëîæíûõ ñèñòåì èõ ìîäåëè ÷àñòî çàìåíÿþò áîëåå
ïðîñòûìè, ÷òîáû àíàëèçèðîâàòü ñâîéñòâà íå íà äîñêîíàëüíîé ìîäåëè, à íà óïðî-
ùåííîé (ðåäóöèðîâàííîé). Îñíîâíîå óñëîâèå äîïóñòèìîñòè òàêîé çàìåíû çà-
êëþ÷àåòñÿ â òîì, ÷òîáû ïîëó÷åííàÿ óïðîùåííàÿ (ðåäóöèðîâàííàÿ) ìîäåëü îòðà-
æàëà ôóíêöèîíèðîâàíèå èññëåäóåìîé ñèñòåìû, à çíà÷èò, îáëàäàëà âñåìè òåìè
ñâîéñòâàìè, êîòîðûìè îáëàäàåò èñõîäíàÿ äîñêîíàëüíàÿ ìîäåëü.
Ïîñòðîåíèå áîëåå ïðîñòîé ìîäåëè òðåáóåò íàëè÷èÿ èíñòðóìåíòà, ïîçâîëÿþùå-
ãî îñóùåñòâëÿòü ïåðåõîä îò èñõîäíîé äîñêîíàëüíîé (äåòàëüíîé) ìîäåëè ê ðåäóöè-
ðîâàííîé. Â íàñòîÿùåå âðåìÿ äëÿ íàõîæäåíèÿ ïðàâèëüíîãî ïåðåõîäà îò ñëîæíîé
(äîñêîíàëüíîé) ìîäåëè óñòàíàâëèâàåòñÿ âîçìîæíîñòü âçàèìîñâÿçåé ìåæäó ðàçëè÷-
íûìè ñåìàíòè÷åñêèìè ìîäåëÿìè ïàðàëëåëèçìà [5–7].  äàííîì íàïðàâëåíèè óñïåø-
íî èñïîëüçóþòñÿ ìåòîäû òåîðèè êàòåãîðèé è ÷àñòè÷íûõ îòîáðàæåíèé [8–10]. Ïðè
ýòîì õàðàêòåðèçàöèÿ ïîâåäåíèÿ ñåòåé Ïåòðè ïðåäñòàâëÿåòñÿ â âèäå òàêèõ ñîîòâå-
òñòâóþùèõ îðèåíòèðîâàííûõ ãðàôîâ è êîíñòðóêöèé, êàê, íàïðèìåð, ñèñòåìû ïåðå-
õîäîâ, ñåòè-ïðîöåññû, ñèñòåìû ïåðåõîäîâ ñ íåçàâèñèìîñòüþ, àñèíõðîííûå ñèñòå-
ìû ïåðåõîäîâ, ñòðóêòóðû ñîáûòèé, ÷àñòè÷íî-óïîðÿäî÷åííûå ìíîæåñòâà.
Ïðèìåíèì ïîíÿòèå ìîðôèçìà ìîäåëåé äëÿ òî÷íîãî îïèñàíèÿ âçàèìîñâÿçè ìåæ-
äó ìîäåëüþ ïàðàëëåëüíîé ðàñïðåäåëåííîé ñèñòåìû, ïðåäñòàâëåííîé â âèäå äåòàëü-
íîé ìîäåëè Ïåòðè, è åå óïðîùåíèåì — êîìïîíåíòíîé ñåòüþ Ïåòðè. Êîíñòðóèðî-
âàíèå êîìïîíåíòíîé ñåòè Ïåòðè [11, 12] ìîæíî ðàññìàòðèâàòü êàê îäèí èç ìåòîäîâ
ïðåîáðàçîâàíèÿ äîñêîíàëüíîé (äåòàëüíîé) ìîäåëè Ïåòðè, êîòîðûé ïîçâîëÿåò ïîëó-
÷èòü ðåäóöèðîâàííóþ ìîäåëü çíà÷èòåëüíî ìåíüøèõ ðàçìåðîâ [13]. Ðåäóöèðîâàíèå
çàêëþ÷àåòñÿ â èíêàïñóëÿöèè ó÷àñòêîâ äåòàëüíîé ìîäåëè Ïåòðè (ñîñòàâíûõ êîìïî-
íåíò [12]) â ñîîòâåòñòâóþùèå âåðøèíû êîìïîíåíòíîé ñåòè Ïåòðè.
Öåëü äàííîé ñòàòüè — èçó÷åíèå ñâÿçåé ìîäåëåé: äåòàëüíîé ìîäåëè Ïåòðè N
è êîìïîíåíòíîé CN-ìîäåëè èññëåäóåìîé ïàðàëëåëüíîé ðàñïðåäåëåííîé ñèñòå-
ìû, óñòàíîâëåíèå ñòåïåíè ìîðôèçìà ìåæäó íèìè äëÿ îáîñíîâàíèÿ íà ìîäåëüíîì
óðîâíå àäåêâàòíîñòè äâóõ ìîäåëåé îäíîé è òîé æå èññëåäóåìîé ïàðàëëåëüíîé
ðàñïðåäåëåííîé ñèñòåìû.
1. ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Ðàññìîòðèì äåòàëüíóþ ìîäåëü Ïåòðè N è êîìïîíåíòíóþ CN-ìîäåëü ïàðàë-
ëåëüíîé ðàñïðåäåëåííîé ñèñòåìû, ïðåäñòàâëÿþùèå îðèåíòèðîâàííûå ãðàôû
ñ äâóìÿ òèïàìè âåðøèí, ñîåäèíåííûõ ìåæäó ñîáîé äóãàìè, ïðè ýòîì êàæäàÿ
äóãà ñîåäèíÿåò âåðøèíû ðàçíûõ òèïîâ. Äåòàëüíàÿ ìîäåëü Ïåòðè N îïèñûâà-
åòñÿ óïîðÿäî÷åííîé ïÿòåðêîé: N P T F W M� ( , , , , )0 , ãäå P T� — êîíå÷íîå
ìíîæåñòâî âåðøèí, F P T T P� � �� — îòíîøåíèå èíöèäåíòíîñòè ìåæäó
ìåñòàìè (âåðøèíàìè èç ìíîæåñòâà P) è ïåðåõîäàìè (âåðøèíàìè èç ìíîæåñòâà T),
W F N: \� { }0 è M P N0 : � — ñîîòâåòñòâåííî ôóíêöèè êðàòíîñòè äóã è íà-
÷àëüíîé ðàçìåòêè. Äåòàëüíàÿ ìîäåëü ïðåäñòàâëÿåò ñîáîé îáûêíîâåííóþ ñåòü
Ïåòðè, äîñêîíàëüíî ìîäåëèðóþùóþ ïðîöåññû èññëåäóåìîé ñèñòåìû. Êîìïî-
íåíòíàÿ ìîäåëü (CN-ìîäåëü èëè CN-ñåòü), ïðåäëîæåííàÿ â [14], — ýòî íàáîð
CN P T F W M� � � � � �( , , , , )0 , ãäå P P P' � 1 2� — êîíå÷íîå ìíîæåñòâî ìåñò (P1 —
êîíå÷íîå ìíîæåñòâî êîìïîíåíò-ìåñò, P2 — êîíå÷íîå ìíîæåñòâî ìåñò ñåòåé
Ïåòðè, îñòàâøèõñÿ ïîñëå âûäåëåíèÿ êîìïîíåíò-ìåñò), T T T' � 1 2� — êîíå÷íîå
ìíîæåñòâî ïåðåõîäîâ, ñîñòîÿùåå èç ïîäìíîæåñòâ T1 è T2 (ñîîòâåòñòâåííî
ìíîæåñòâî êîìïîíåíò-ïåðåõîäîâ è ìíîæåñòâî ïåðåõîäîâ â ñìûñëå ïåðåõîäîâ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 37
ñåòåé Ïåòðè, îñòàâøèõñÿ ïîñëå âûäåëåíèÿ êîìïîíåíò-ïåðåõîäîâ), � �F
� �� � �� �P T T P� — îòíîøåíèå èíöèäåíòíîñòè ìåæäó ìåñòàìè è ïåðåõîäàìè,
� � �W F N: \ { }0 — ôóíêöèÿ êðàòíîñòè äóã, �M 0 — íà÷àëüíàÿ ðàçìåòêà ñåòè.
Êîìïîíåíòíàÿ ñåòü ïðåäñòàâëÿåò ñîáîé ñåòü Ïåòðè, â êîòîðîé â îòëè÷èå îò äå-
òàëüíîé ìîäåëè N âûäåëåííûå ñîñòàâíûå êîìïîíåíòû àêêóìóëèðîâàíû â êîìïî-
íåíòû-ìåñòà Cp è êîìïîíåíòû-ïåðåõîäû Ct. (Ôîðìàëüíûå îïðåäåëåíèÿ ñîñòàâíûõ
êîìïîíåíò Cp è Ct äàíû â ðàáîòå [12].)
Îòìåòèì îñîáåííîñòè îïðåäåëåíèÿ ñîñòàâíûõ êîìïîíåíò. Òàê, êîìïîíåí-
òà-ìåñòî ïðåäñòàâëÿåò ó÷àñòîê ñåòè, ìîäåëèðóþùèé íåêîòîðûé îäíîòèïíûé ïðî-
öåññ äåòàëüíîé ìîäåëè èññëåäóåìîé ñèñòåìû, íà÷èíàþùèéñÿ è çàêàí÷èâàþùèéñÿ
ìåñòîì (ìåñòàìè). Âõîäíûå è âûõîäíûå ìåñòà êîìïîíåíòû Cp, êàê ýëåìåíòà
CN-ñåòè, íå èìåþò ñîîòâåòñòâåííî âõîäÿùèõ è èñõîäÿùèõ äóã, à ñàìà êîìïîíåíòà
Cp â CN-ñåòè ïðåäñòàâëÿåòñÿ ìåñòîì è èìååò âõîäÿùèå è èñõîäÿùèå äóãè.
Àíàëîãè÷íî êîìïîíåíòà-ïåðåõîä ïðåäñòàâëÿåò ó÷àñòîê ñåòè, ìîäåëèðóþùèé íåêî-
òîðûé îäíîòèïíûé ïðîöåññ èññëåäîâàíèÿ, íà÷èíàþùèéñÿ è çàêàí÷èâàþùèéñÿ ïåðå-
õîäîì (ïåðåõîäàìè). Íà÷àëüíûå è çàêëþ÷èòåëüíûå ïåðåõîäû êîìïîíåíòû Ct, êàê
ýëåìåíòà CN-ñåòè, íå èìåþò ñîîòâåòñòâåííî âõîäÿùèõ è èñõîäÿùèõ äóã, êîìïîíåí-
òà Ct â CN-ñåòè ïðåäñòàâëÿåòñÿ ïåðåõîäîì è èìååò âõîäÿùèå è èñõîäÿùèå äóãè.
Äëÿ èëëþñòðàöèè êîìïîíåíòíîé ñåòè íà ðèñ. 1,à ïîêàçàíà CN-ñåòü èç ðàáî-
òû [15], ìîäåëèðóþùàÿ àëãîðèòìè÷åñêóþ ñõåìó êðèïòîãðàôè÷åñêîãî ïðîòîêîëà
Äèôôè-Õýëëìà. Îíà ïîçâîëÿåò ïîëó÷àòü äâóì ñòîðîíàì îáùèé ñåêðåòíûé êëþ÷,
ïðåäíàçíà÷åííûé äëÿ îáìåíà êîíôèäåíöèàëüíîé èíôîðìàöèåé. Òàêàÿ CN-ñåòü
â êà÷åñòâå ñîñòàâíûõ êîìïîíåíò ñîäåðæèò îäèíàêîâûå êîìïîíåíòû-ïåðåõîäû
T1
* , T2
* , T3
* , T4
* , âíóòðåííÿÿ ñòðóêòóðà êîòîðûõ îäèíàêîâà (ðèñ. 1,á). Ýòè êîìïî-
íåíòû ìîäåëèðóþò îäèí ïðîöåññ (íî ñ ðàçíûìè äàííûìè) ñîçäàíèÿ êëþ÷à ïî
ôîðìóëå q nxmod ( ), ãäå x — ñëó÷àéíîå ÷èñëî îäíîãî èç ïîëüçîâàòåëåé; n è q —
áîëüøèå ïðîñòûå ÷èñëà, èçâåñòíûå îáîèì ïîëüçîâàòåëÿì. Íà ðèñ. 1,á ïåðåõîäû t1
è t4 ñîîòâåòñòâóþò ââîäó äàííûõ x, n è q; ïåðåõîäû t2 è t3 — âû÷èñëåíèþ çíà÷å-
íèÿ q x , ïåðåõîäû t5 è t6 ñîîòâåòñòâóþò âû÷èñëåíèþ çíà÷åíèÿ q nxmod ( ), ïåðåõî-
äû t7 è t8 — âûâîäó äàííûõ. Ïðè ýòîì â ñàìîé CN-ñåòè (ðèñ. 1,à) ïåðåõîäû t1 è
t2 ñîîòâåòñòâóþò ââîäó äàííûõ, êîìïîíåíòû T1
* è T2
* — âû÷èñëåíèþ ïî âûøåó-
êàçàííîé ñõåìå ïðîìåæóòî÷íûõ êëþ÷åé ñîîòâåòñòâåííî äëÿ ïåðâîãî è âòîðîãî
ïîëüçîâàòåëåé. Êîìïîíåíòû T3
* è T4
* , èñïîëüçóÿ ïîëó÷åííûå äàííûå îò âû÷èñëå-
íèé, ñìîäåëèðîâàííûõ êîìïîíåíòàìè T1
* è T2
* ïî òîé æå ñõåìå, ñîîòâåòñòâóþò
âû÷èñëåíèÿì îáùåãî ñåêðåòíîãî êëþ÷à äëÿ äâóõ ïîëüçîâàòåëåé, ó÷àñòâóþùèõ â
ïðîöåññå îáìåíà êîíôèäåíöèàëüíîé èíôîðìàöèåé.
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
Ðèñ. 1. Êîìïîíåíòíàÿ ñåòü Ïåòðè ñ êîìïîíåíòàìè-ïåðåõîäàìè T1
*, T2
*, T3
*, T4
* (à) è âíóòðåííÿÿ
ñòðóêòóðà ýòèõ îäèíàêîâûõ êîìïîíåíò (á)
à á
Ñðåäè âûäåëåííûõ ñîñòàâíûõ êîìïîíåíò ìîãóò áûòü êàê îäèíàêîâûå, òàê
è îäíîòèïíûå. Â ðàáîòàõ [11, 16] îïðåäåëåíû ïîíÿòèÿ îäèíàêîâûõ è îäíîòèïíûõ
ñîñòàâíûõ êîìïîíåíò êîìïîíåíòíîé ñåòè Ïåòðè. Îòìåòèì, ÷òî îäèíàêîâûå ñî-
ñòàâíûå êîìïîíåíòû ìîäåëèðóþò îäèíàêîâûå ïðîöåññû, è ìîäåëè ýòèõ êîìïî-
íåíò ïîëíîñòüþ ñîâïàäàþò. Îäíîòèïíûå èëè îòíîñÿùèåñÿ ê îäíîìó òèïó ñîñòàâ-
íûå êîìïîíåíòû ìîäåëèðóþò îäíîòèïíûå ïðîöåññû è îòëè÷àþòñÿ òîëüêî
êîëè÷åñòâîì îäèíàêîâûõ ïàðàëëåëüíûõ ïðîöåññîâ.
Çàìå÷àíèå 1. Ó÷èòûâàÿ îñîáåííîñòè îïðåäåëåíèÿ îäèíàêîâûõ è îäíîòèï-
íûõ ñîñòàâíûõ êîìïîíåíò, åñòåñòâåííî îáîçíà÷àòü â îäèíàêîâûõ è îäíîòèïíûõ
ñîñòàâíûõ êîìïîíåíòàõ îäèíàêîâûìè ñèìâîëàìè ñîîòâåòñòâóþùèå ìåñòà è ïå-
ðåõîäû è îäèíàêîâûìè ñèìâîëàìè ñîîòâåòñòâóþùèå ìåñòà è ïåðåõîäû â îäèíà-
êîâûõ ïàðàëëåëüíûõ ïðîöåññàõ.
Íà ðèñ. 2 ïîêàçàíû îäíîòèïíûå ñîñòàâíûå êîìïîíåíòû — êîìïîíåíòû-ìåñ-
òà CN-ñåòè èç [11], ÿâëÿþùåéñÿ ìîäåëüþ ñõåìû äâèæåíèÿ æåëåçíîäîðîæíîãî
òðàíñïîðòà (ÄÆÒ) äëÿ æåëåçíîäîðîæíîãî óçëà, êîòîðûé îáåñïå÷èâàåò âçàèìî-
äåéñòâèå è ñîãëàñîâàííóþ ðàáîòó ñïåöèàëèçèðîâàííûõ ñòàíöèé. Ýòè êîìïîíåí-
òû ìîäåëèðóþò ÄÆÒ òðåõ òóïèêîâûõ ñòàíöèé, ïðèíèìàþùèõ è îòïðàâëÿþùèõ
ïîåçäà â îäíîì íàïðàâëåíèè. Òàê, íà ðèñ. 2, à, á ïîêàçàíû êîìïîíåíòû, ìîäåëè-
ðóþùèå ÄÆÒ ñòàíöèé ñ îäíîé âõîäíîé êîëååé è ñîîòâåòñòâåííî ñ òðåìÿ è ïÿòüþ
âíóòðåííèìè ïóòÿìè, íà ðèñ. 2, â ïîêàçàíà êîìïîíåíòà, ìîäåëèðóþùàÿ ÄÆÒ
ñòàíöèè ñ äâóìÿ âõîäíûìè êîëåÿìè è ïÿòüþ âíóòðåííèìè ïóòÿìè. Ýòè êîìïî-
íåíòû îòëè÷àþòñÿ îäíà îò äðóãîé òîëüêî êîëè÷åñòâîì îäèíàêîâûõ ïàðàëëåëü-
íûõ ïðîöåññîâ: â êîìïîíåíòå íà ðèñ. 2, á — íà ýòàïå ñðàáàòûâàíèÿ III, â êîìïî-
íåíòå íà ðèñ. 2, â – íà ýòàïàõ ñðàáàòûâàíèÿ I–IV. Ïðè ýòîì â êîìïîíåíòàõ ìåñòî
p3 è ïåðåõîä b ìîäåëèðóþò ôóíêöèîíèðîâàíèå îäíîé êîëåè, ïåðåõîäû a è c —
âõîä è âûõîä ïîåçäîâ ñî ñòàíöèè ïî îäíîé êîëåå, ìåñòî p4 îáåñïå÷èâàåò èñêëþ÷å-
íèå êîíêóðåíöèè äëÿ ïîåçäîâ íà âõîäå è âûõîäå ñî ñòàíöèè, ìåñòà p2 è p5 ìîäå-
ëèðóþò ñîîòâåòñòâåííî óñëîâèÿ íàëè÷èÿ ïîåçäîâ äëÿ âõîäà è âûõîäà ñî ñòàíöèè.
ÎÁËÀÑÒÈ ÎÒÍÎØÅÍÈß ÊÎÌÏÎÍÅÍÒÛ
Îáîçíà÷èì NCk
( , , , )k n�1 2 � ñîñòàâíûå êîìïîíåíòû êîìïîíåíòíîé ñåòè Ïåò-
ðè âíå çàâèñèìîñòè îò òèïà êîìïîíåíòû (êîìïîíåíòû-ìåñòà èëè êîìïîíåí-
òû-ïåðåõîäà). Ñ îäíîé ñòîðîíû, ñîñòàâíàÿ êîìïîíåíòà NCk
â CN-ñåòè ïðåä-
ñòàâëÿåòñÿ ëèáî ìåñòîì Pk
* , ëèáî ïåðåõîäîì Tk
* : { }P T CNk k
* *, � . Ñ äðóãîé ñòî-
ðîíû, ýòà æå êîìïîíåíòà NCk
äëÿ äåòàëüíîé ìîäåëè N èññëåäóåìîé ñèñòåìû
ïðåäñòàâëÿåòñÿ ó÷àñòêîì ýòîé ñåòè, ïðè ýòîì N NCk
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 39
Ðèñ. 2. Îäíîòèïíûå êîìïîíåíòû-ìåñòà (ìåñòà è ïåðåõîäû îáîçíà÷åíû ñîãëàñíî çàìå÷àíèþ 1)
áà â
Îïðåäåëåíèå 1. Îòíîøåíèåì êîìïîíåíòû íàçîâåì îòíîøåíèå �, ðàññìàò-
ðèâàåìîå íà ìíîæåñòâå âåðøèí äåòàëüíîé ìîäåëè Ïåòðè N è óäîâëåòâîðÿþùåå
ñëåäóþùèì óñëîâèÿì:
1) äëÿ êàæäîé âåðøèíû a N� è îòíîøåíèÿ � âûïîëíÿåòñÿ a a� ;
2) äëÿ äâóõ âåðøèí a N� , b N� è îòíîøåíèÿ � âûïîëíÿåòñÿ a b� , åñëè a è
b NCk
� — âåðøèíû îäíîé ñîñòàâíîé êîìïîíåíòû NCk
.
Êàæäóþ âåðøèíó ñåòè N , íå âîøåäøóþ íè â îäíó èç ñîñòàâíûõ êîìïîíåíò
NCk
, ìîæíî ðàññìàòðèâàòü êàê êîìïîíåíòó, ñîñòîÿùóþ èç îäíîé âåðøèíû, ÷òî íå
ïðîòèâîðå÷èò îïðåäåëåíèÿì ñîñòàâíûõ êîìïîíåíò, äàííûì â [12], è îïðåäåëåíèþ 1.
Íàçîâåì òàêóþ êîìïîíåíòó åäèíè÷íîé êîìïîíåíòîé è îáîçíà÷èì NCei
(i m�
1, , ).
Î÷åâèäíî, îòíîøåíèå �, ðàññìàòðèâàåìîå íà ìíîæåñòâå âåðøèí äåòàëüíîé
ìîäåëè Ïåòðè N , ðåôëåêñèâíî, ñèììåòðè÷íî, òðàíçèòèâíî, ÿâëÿåòñÿ îòíîøåíèåì
ýêâèâàëåíòíîñòè. Òîãäà êîìïîíåíòû N NCk
( , , , ,k n ei�1 2 � ) ïðåäñòàâëÿþò
ñîáîé êëàññû ýêâèâàëåíòíîñòè îòíîøåíèÿ �. Òàêîé êëàññ áóäåì íàçûâàòü
îáëàñòüþ îòíîøåíèÿ êîìïîíåíòû NCk
.
Ìíîæåñòâî âåðøèí ñåòè N ñ îòíîøåíèåì ýêâèâàëåíòíîñòè � ïðåäñòàâëÿåò
îáúåäèíåíèå íåïåðåñåêàþùèõñÿ îáëàñòåé îòíîøåíèÿ êîìïîíåíòû, êîòîðûå îá-
ðàçóþò ðàçáèåíèå ìíîæåñòâà âåðøèí ñåòè N . Äëÿ îáëàñòè îòíîøåíèÿ êîìïîíåí-
òû N NCk
âûïîëíÿþòñÿ óñëîâèÿ:
1) � �a b N a bCk
, : � , ïðè ýòîì î÷åâèäíî, ÷òî åñëè êîìïîíåíòà åäèíè÷íàÿ
( )k ei� , òî b a� ;
2) � � �
� � �a N a N b N a bC Ck k
: : ( )� .
Òåîðåìà 1. Îáëàñòè îòíîøåíèÿ îäíîòèïíûõ ñîñòàâíûõ êîìïîíåíò NCi
è
NC j
ñîâïàäàþò, â ïðîòèâíîì ñëó÷àå îíè íå èìåþò îáùèõ ýëåìåíòîâ.
Äîêàçàòåëüñòâî. Ðàññìîòðèì îäíîòèïíûå ñîñòàâíûå êîìïîíåíòû NCi
è
NC j
, êîòîðûå îòëè÷àþòñÿ òîëüêî êîëè÷åñòâîì îäèíàêîâûõ ïàðàëëåëüíûõ ïðî-
öåññîâ. Âåðøèíû ýòèõ êîìïîíåíò èìåþò îáîçíà÷åíèÿ ñîãëàñíî çàìå÷àíèþ 1; îò-
ìåòèì, ÷òî NCi
— êîìïîíåíòà ñ ìåíüøèì ÷èñëîì îäèíàêîâûõ ïàðàëëåëüíûõ
ïðîöåññîâ. Ïóñòü âåðøèíà x — ïðîèçâîëüíûé ýëåìåíò îáëàñòè îòíîøåíèÿ êîì-
ïîíåíòû NCi
. Ýòî îçíà÷àåò, ÷òî x íàõîäèòñÿ â îòíîøåíèè � ñ ëþáîé âåðøèíîé â
êîìïîíåíòå NCi
. Ó÷èòûâàÿ, ÷òî NCi
è NC j
— îäíîòèïíûå ñîñòàâíûå êîìïîíåí-
òû, òàêàÿ âåðøèíà x èìååòñÿ è â êîìïîíåíòå NC j
, è ñîãëàñíî çàìå÷àíèþ 1 íèêà-
êèõ äðóãèõ ïàð x y� äëÿ âñÿêîé âåðøèíû y NC j
� (êðîìå ïàð x y� äëÿ ëþáîé âåð-
øèíû y NCi
� ) â îáëàñòè îòíîøåíèÿ êîìïîíåíòû NC j
íå ïîÿâèòñÿ. Ñëåäîâàòåëü-
íî, îáëàñòè îòíîøåíèÿ êîìïîíåíò NCi
è NC j
ñîâïàäàþò.
Ïðåäïîëîæèì òåïåðü, ÷òî âåðøèíà a NCi
� è a NCj� . Òîãäà a íàõîäèòñÿ
â îòíîøåíèè � ñ ëþáîé âåðøèíîé â êîìïîíåíòå NCi
(ïóñòü âåðøèíîé b) è ñ ëþ-
áîé âåðøèíîé èç NC j
(ïóñòü âåðøèíîé ñ). Îòñþäà â ñèëó ñèììåòðè÷íîñòè è
òðàíçèòèâíîñòè îòíîøåíèÿ ýêâèâàëåíòíîñòè � èìååò ìåñòî b c� è, çíà÷èò, îá-
ëàñòè îòíîøåíèÿ îäíîòèïíûõ êîìïîíåíò NCi
è NC j
ìîãóò òîëüêî ñîâïàäàòü.
ÝÏÈÌÎÐÔÈÇÌ ÄÅÒÀËÜÍÎÉ È ÊÎÌÏÎÍÅÍÒÍÎÉ ÑÅÒÅÉ ÏÅÒÐÈ
ÏÀÐÀËËÅËÜÍÎÉ ÐÀÑÏÐÅÄÅËÅÍÍÎÉ ÑÈÑÒÅÌÛ
CN-ìîäåëü ÿâëÿåòñÿ ðåçóëüòàòîì íåêîòîðîãî ïðåîáðàçîâàíèÿ � ìîäåëè N .
Ïðåîáðàçîâàíèå � ìîäåëè N , íà ìíîæåñòâå âåðøèí êîòîðîé çàäàíî îòíîøåíèå
�, â CN-ìîäåëü óäîâëåòâîðÿåò ñëåäóþùèì óñëîâèÿì.
1�. Åñëè ñîñòàâíàÿ êîìïîíåíòà NCk
— êîìïîíåíòà-ìåñòî, òî äëÿ ëþáûõ ýëå-
ìåíòîâ a b N a b a b PC kk
, : ( ) ( ) *
� � � �� � � .
2�. Åñëè ñîñòàâíàÿ êîìïîíåíòà NCk
— êîìïîíåíòà-ïåðåõîä, òî äëÿ ëþáûõ
ýëåìåíòîâ a b N a b a b TC kk
, : ( ) ( ) *
� � � �� � � .
3�. Åñëè NCei
— ìåñòî p ñåòè N , òî âûïîëíÿåòñÿ ðàâåíñòâî � ( )p p� ; âåðíî è
îáðàòíîå.
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
4�. Åñëè NCei
— ïåðåõîä t ñåòè N , òî âûïîëíÿåòñÿ ðàâåíñòâî � ( )t t� ; âåðíî
è îáðàòíîå.
Ïîêàæåì, ÷òî îòîáðàæåíèå � � N CN� ÿâëÿåòñÿ ñþðúåêòèâíûì ãîìîìîð-
ôèçìîì, ò.å. ýïèìîðôèçìîì.
Òåîðåìà 2. Ïðåîáðàçîâàíèå � ìîäåëè N , íà ìíîæåñòâå âåðøèí êîòîðîé çàäàíî
îòíîøåíèå êîìïîíåíòû �, â CN-ìîäåëü ÿâëÿåòñÿ ñþðúåêòèâíûì îòîáðàæåíèåì.
Äîêàçàòåëüñòâî. Ïðè ïîñòðîåíèè êîìïîíåíòíîé ñåòè âûäåëåííûå â ñåòè N
ñîñòàâíûå êîìïîíåíòû îôîðìëÿþòñÿ â âèäå êîìïîíåíò-ìåñò Pk
* è êîìïîíåíò-ïå-
ðåõîäîâ Tk
* ( , , , )k n�1 2 � , âåðøèíû êîòîðûõ íàõîäÿòñÿ â îòíîøåíèè êîìïîíåí-
òû �. Ðàññìàòðèâàåìîå ïðåîáðàçîâàíèå îñóùåñòâëÿåòñÿ â ðåçóëüòàòå îòîáðàæå-
íèÿ � : N CN� . Îòîáðàæåíèå � óäîâëåòâîðÿåò óñëîâèÿì 1 4�� �, ñîãëàñíî êîòî-
ðûì êàæäîé âåðøèíå äåòàëüíîé ìîäåëè N ñòàâèòñÿ â ñîîòâåòñòâèå âåðøèíà
êîìïîíåíòíîé ñåòè (CN-ìîäåëè) òàê, ÷òîáû êàæäàÿ âåðøèíà ãðàôà CN-ìîäåëè
ñòàëà îáðàçîì õîòÿ áû îäíîé âåðøèíû ãðàôà ìîäåëè N . Ñëåäîâàòåëüíî, îòîáðà-
æåíèå � ÿâëÿåòñÿ ñþðúåêòèâíûì îòîáðàæåíèåì ìíîæåñòâà âåðøèí ìîäåëè N íà
ìíîæåñòâî âåðøèí CN-ìîäåëè.
Íà ìíîæåñòâå âåðøèí ðàññìàòðèâàåìîé ñåòè N çàäàíû äâà áèíàðíûõ îòíî-
øåíèÿ: F — îòíîøåíèå èíöèäåíòíîñòè è � — îòíîøåíèå êîìïîíåíòû. Ïîñëå
âûäåëåíèÿ â ñåòè N ñîñòàâíûõ êîìïîíåíò NCk
( , , , ; )k n ei�1 2 � , âûÿâëåíèÿ îá-
ëàñòåé êîìïîíåíòû è ïîñòðîåíèÿ êîìïîíåíòíîé ñåòè íà ìíîæåñòâå âåðøèí
CN-ñåòè îïðåäåëÿþòñÿ ñëåäóþùèå áèíàðíûå îòíîøåíèÿ:
1) îòíîøåíèå èíöèäåíòíîñòè �F , êîòîðîå óñòàíàâëèâàåòñÿ ìåæäó ðàçíî-
èìåííûìè îáëàñòÿìè êîìïîíåíò ìîäåëè N èëè (÷òî òî æå ñàìîå) ìåæäó ýëåìåí-
òàìè (ìåñòàìè è ïåðåõîäàìè) CN-ñåòè;
2) îòíîøåíèå êîìïîíåíòû �� , êîòîðîå óñòàíàâëèâàåòñÿ íà ìíîæåñòâå âåð-
øèí êîìïîíåòíîé ìîäåëè Ïåòðè CN èëè (÷òî òî æå ñàìîå) íà ìíîæåñòâå êîìïî-
íåíò NCk
( , , , ; )k n ei�1 2 � , ÿâëÿþùèõñÿ ïî ïîñòðîåíèþ CN-ñåòè åå âåðøèíàìè;
ïðè ýòîì äëÿ êàæäîé âåðøèíû a CN� âûïîëíÿåòñÿ a a�� .
Ñëåäîâàòåëüíî, íà ìíîæåñòâå âåðøèí äåòàëüíîé è êîìïîíåíòíîé ñåòåé äåéñòâó-
þò ñîîòâåòñòâóþùèå îòíîøåíèÿ: îòíîøåíèÿ èíöèäåíòíîñòè F , �F è îòíîøåíèÿ
êîìïîíåíò �, �� . Ïðè ýòîì ñóùåñòâóåò «ñîãëàñîâàííîñòü» îòíîøåíèé èíöèäåíò-
íîñòè F è �F è îòíîøåíèé êîìïîíåíò � è �� . Ðàññìîòðèì âñå âîçìîæíûå ñëó÷àè.
1. Ïóñòü a è b — âåðøèíû ñåòè N , êîòîðûå íå ïîïàëè íè â îäíó èç ñîñòàâ-
íûõ êîìïîíåíò NCk
( , , , )k n�1 2 � , è èìååò ìåñòî aFb (âåðøèíà a íàõîäèòñÿ â îò-
íîøåíèè èíöèäåíòíîñòè F ñ âåðøèíîé b). Òîãäà êàæäàÿ òàêàÿ âåðøèíà ÿâëÿåòñÿ
ñîîòâåòñòâóþùåé åäèíè÷íîé êîìïîíåíòîé NCei
è ñîãëàñíî ïîñòðîåíèþ
CN-ñåòè, ñåòè N è óñëîâèÿì 3�, 4� ïðåîáðàçîâàíèÿ � ìîæíî ñâèäåòåëüñòâîâàòü î
«ñîãëàñîâàííîñòè» ñîâïàäåíèÿ îòíîøåíèé èíöèäåíòíîñòè F è F ' äëÿ ñìåæíûõ
âåðøèí ñåòè, íå ïîïàâøèõ íè â îäíó èç ñîñòàâíûõ êîìïîíåíò. Ïîýòîìó åñëè äëÿ
òàêèõ âåðøèí a è b ñåòè N åñòü ñîåäèíÿþùàÿ èõ äóãà â N , òî è äëÿ âåðøèí
� ( )a a� è� ( )b b� CN-ñåòè åñòü ñîåäèíÿþùàÿ èõ äóãà â CN. Ñëåäîâàòåëüíî, èìå-
åò ìåñòî � �( ) ' ( )a F b (îáðàç âåðøèíû a íàõîäèòñÿ â îòíîøåíèè èíöèäåíòíîñòè F '
ñ îáðàçîì âåðøèíû b), à çíà÷èò, âûïîëíÿåòñÿ ñëåäîâàíèå � � �( ) ( ) ' ( )aFb a F b
.
2. Ïóñòü âåðøèíû a b N, � è íàõîäÿòñÿ â îòíîøåíèè èíöèäåíòíîñòè F , ïðè
ýòîì âåðøèíà b Cp� (b — ýëåìåíò íåêîòîðîé êîìïîíåíòû-ìåñòà Cp), à âåðøè-
íà a ëèáî: �1 ) íå ïðèíàäëåæèò íèêàêîé êîìïîíåíòå, ëèáî: �2 ) ïðèíàäëåæèò íåêî-
òîðîé äðóãîé êîìïîíåíòå (â äàííîì ñëó÷àå òîëüêî êîìïîíåíòå-ïåðåõîäà Ct).
Âñëåäñòâèå èíöèäåíòíîñòè âåðøèí a è b â ñëó÷àå �1 âåðøèíà a — ïåðåõîä, à âåð-
øèíà b — ìåñòî, ÿâëÿþùååñÿ íà÷àëüíûì (âõîäíûì) ìåñòîì êîìïîíåíòû Cp. Ñîã-
ëàñíî óñëîâèÿì 4� è 1� ïðåîáðàçîâàíèÿ � èìååì, ÷òî � ( )à à� — ïåðåõîä,
� ( ) *b Pk� — ìåñòî CN-ñåòè. Ñëåäîâàòåëüíî, â CN-ñåòè âûïîëíÿåòñÿ � �( ) ' ( )a F b .
 ñëó÷àå �2 âåðøèíà a — ïåðåõîä, ÿâëÿþùèéñÿ çàêëþ÷èòåëüíûì (âûõîäíûì) ïå-
ðåõîäîì êîìïîíåíòû Ct. Ñîãëàñíî óñëîâèÿì 2� è 1� ïðåîáðàçîâàíèÿ � èìååì, ÷òî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 41
� ( ) *a Tk� — ïåðåõîä, à � ( ) *b Pk� — ìåñòî CN-ñåòè. Ñëåäîâàòåëüíî, â CN-ñåòè íà-
áëþäàåòñÿ � �( ) ( )a F b� . À çíà÷èò, è â ñëó÷àå 2 èìååò ìåñòî � � �( ) ( ) ( )aFb a F b
� .
3. Ïóñòü âåðøèíû a b N, � è íàõîäÿòñÿ â îòíîøåíèè èíöèäåíòíîñòè F , ïðè
ýòîì âåðøèíà b Ct� (b ÿâëÿåòñÿ ýëåìåíòîì íåêîòîðîé êîìïîíåíòû-ïåðåõîäà Ct),
à âåðøèíà a ëèáî: ��1 ) íå ïðèíàäëåæèò íèêàêîé êîìïîíåíòå, ëèáî: ��2 ) ïðèíàäëåæèò
íåêîòîðîé äðóãîé êîìïîíåíòå (çäåñü ìîæåò áûòü òîëüêî êîìïîíåíòà-ìåñòî Cp).
Òîãäà â ñëó÷àå ��1 âåðøèíà a — ìåñòî, à âåðøèíà b — ïåðåõîä, ÿâëÿþùèéñÿ íà-
÷àëüíûì (âõîäíûì) ïåðåõîäîì êîìïîíåíòû Ct, è ñîãëàñíî óñëîâèÿì 3� è 2� ïðå-
îáðàçîâàíèÿ � èìååì, ÷òî � ( )à à� — ìåñòî, � ( ) *b Tk� — ïåðåõîä CN-ñåòè, à çíà-
÷èò, â CN-ñåòè âûïîëíÿåòñÿ � �( ) ( )a F b� .  ñëó÷àå ��2 âåðøèíà a — ìåñòî, ÿâëÿþ-
ùååñÿ çàêëþ÷èòåëüíûì (âûõîäíûì) ìåñòîì êîìïîíåíòû Cp, è ñîãëàñíî
óñëîâèÿì 1� è 2� ïðåîáðàçîâàíèÿ � èìååì, ÷òî � ( ) *a Pk� — ìåñòî, à � ( ) *b Tk� —
ïåðåõîä CN-ñåòè. Ñëåäîâàòåëüíî, â CN-ñåòè âûïîëíÿåòñÿ � �( ) ' ( )a F b , à çíà÷èò, è
â ñëó÷àå 3 èìååò ìåñòî � � �( ) ( ) ( )aFb a F b
� .
Àíàëîãè÷íûé ðåçóëüòàò óñòàíàâëèâàåòñÿ è äëÿ ñëó÷àåâ 4 è 5, êîãäà âåðøèíû
à b N, � è íàõîäÿòñÿ â îòíîøåíèè èíöèäåíòíîñòè F , a Cp� (Ct), à b NCk
�
( , , , )k n�1 2 � èëè b Ct� (b NCk
� èëè b Cp� ).
6. Ïóñòü âåðøèíû a è b ñåòè N ïðèíàäëåæàò íåêîòîðîé ñîñòàâíîé êîìïîíåí-
òå NCk
. Âíå çàâèñèìîñòè îò èíöèäåíòíîñòè âåðøèí a è b ñîãëàñíî îïðåäåëåíèÿì
ñîñòàâíûõ êîìïîíåíò [12] â êîìïîíåíòå NCk
äîëæíà íàõîäèòüñÿ õîòÿ áû åùå
îäíà âåðøèíà c NCk
� , èíöèäåíòíàÿ ïî îòíîøåíèþ F ëèáî âåðøèíå a, ëèáî âåð-
øèíå b, èëè âåðøèíà a áóäåò èíöèäåíòíà ïî îòíîøåíèþ F âåðøèíå ñ, èëè âåð-
øèíà b èíöèäåíòíà ïî îòíîøåíèþ F âåðøèíå ñ. Ïðè îòîáðàæåíèè � îáðàçàìè
âñåõ ýòèõ âåðøèí, â çàâèñèìîñòè îò òèïà ñîñòàâíîé êîìïîíåíòû NCk
, ÿâëÿåòñÿ
ëèáî âåðøèíà Pk
* , ëèáî âåðøèíà Tk
* CN-ñåòè, êîòîðàÿ ñîãëàñíî ââåäåííîìó íà
ìíîæåñòâå âåðøèí CN-ñåòè îòíîøåíèþ êîìïîíåíòû �' íàõîäèòñÿ â îòíîøåíèè �'
ñàìà ñ ñîáîé. Òîãäà âåðøèíû à è b ñåòè N , ïðèíàäëåæàùèå îäíîé ñîñòàâíîé
êîìïîíåíòå NCk
è íàõîäÿùèåñÿ â îòíîøåíèè èíöèäåíòíîñòè F aFb: , íàõîäÿòñÿ
â îòíîøåíèè � �: a b è ïðè îòîáðàæåíèè � èìååò ìåñòî ñëåäîâàíèå � �( )a b
�� � �( ) ( )a b . À çíà÷èò, äëÿ ðàññìàòðèâàåìîãî ñëó÷àÿ 6 ïðè îòîáðàæåíèè �
ñ ó÷åòîì âûïîëíåíèÿ äëÿ íåãî óñëîâèé 1� è 2� èìååò ìåñòî ñëåäîâàíèå
� � � � � � � �( ) ( ) ( ) ( ) ' ( )aFb a b a b a b
�
,
ãäå � � �( ) ( )a b� ðàâíî P Pk k
* *
�� èëè T Tk k
* *
�� â çàâèñèìîñòè îò òîãî, êàêîé ñî-
ñòàâíîé êîìïîíåíòîé ÿâëÿåòñÿ êîìïîíåíòà NCk
( , , , )k n�1 2 � . Ïîëó÷åííûé
âûâîä â ñëó÷àå îòîáðàæåíèÿ îðèåíòèðîâàííûõ ãðàôîâ ñ îäíèì òèïîì âåðøèí
èíòåðïðåòèðóåòñÿ êàê ðåçóëüòàò, ïðè êîòîðîì îáðàçîì äóãè ÿâëÿåòñÿ ïåòëÿ.
Ñîãëàñíî ñëó÷àÿì 1–6 ïðè îòîáðàæåíèè � ìíîæåñòâî âåðøèí P T� äåòàëüíîé
ìîäåëè N , íà êîòîðîì îïðåäåëåíû äâà áèíàðíûõ îòíîøåíèÿ: îòíîøåíèå èíöèäåíò-
íîñòè F è îòíîøåíèå êîìïîíåíòû �, ðàñïàäàåòñÿ íà ïîïàðíî íåïåðåñåêàþùèåñÿ
ìíîæåñòâà ïðîîáðàçîâ: P T a
a P T
� �
�
�
� � �
�
�
1 ( ), ãäå �
�1 ( )a — âñå âåðøèíû ñåòè N ,
èìåþùèå îäèí è òîò æå îáðàç a â � ( )N . Ñëåäîâàòåëüíî, �
�1 ( )a — êëàññ ýêâèâà-
ëåíòíîñòè îòíîøåíèÿ �, ò.å. ïðåäñòàâëÿåò ñîáîé îáëàñòü îòíîøåíèÿ êîìïîíåíòû.
Èòàê, ïðè îòîáðàæåíèè � : N CN� êàæäûé êëàññ ýêâèâàëåíòíîñòè, ïîñòðî-
åííûé íà ìíîæåñòâå âåðøèí äåòàëüíîé ìîäåëè Ïåòðè N ïî îòíîøåíèþ êîìïî-
íåíòû �, à çíà÷èò, êàæäàÿ âåðøèíà ñîîòâåòñòâóþùåé ñîñòàâíîé êîìïîíåíòû NCk
( , , , , ; , , , )k e n i mi� �1 2 1 2� � , îòîáðàæàåòñÿ â ñîîòâåòñòâóþùóþ îäíó âåðøèíó
êîìïîíåíòíîé CN-ìîäåëè ñ ñîõðàíåíèåì óñëîâèÿ èíöèäåíòíîñòè äëÿ îáðàçîâ
âåðøèí ñåòè N . Ñëåäîâàòåëüíî, ðàññìîòðåííîå îòîáðàæåíèå � : N CN� ÿâëÿåò-
ñÿ ãîìîìîðôèçìîì äëÿ ñåòåé Ïåòðè ñ ñîñòàâíûìè êîìïîíåíòàìè. Òàêîé ïîä-
õîä îáîñíîâûâàåò ñëåäóþùóþ òåîðåìó.
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
Òåîðåìà 3. Ïóñòü íà ìíîæåñòâå âåðøèí äåòàëüíîé ìîäåëè Ïåòðè N çàäàíî
îòíîøåíèå êîìïîíåíòû �. Òîãäà îòîáðàæåíèå � : N CN� ÿâëÿåòñÿ ãîìîìîðôèç-
ìîì, ïðè êîòîðîì âûïîëíÿåòñÿ ñëåäîâàíèå
� � �( ) ( ) ( )aFb a F b
� , (1)
ãäå F è �F — ñîîòâåòñòâåííî îòíîøåíèÿ èíöèäåíòíîñòè ìîäåëåé N è CN .
 ñëó÷àå ïðèíàäëåæíîñòè âåðøèí ñåòè N îäíîé ñîñòàâíîé êîìïîíåíòå NCk
( , , , )k n�1 2 � ñëåäîâàíèå (1) ïðèíèìàåò âèä
� � � � �( ) ( ) ' ( )a b a b
, (2)
ãäå �, �� — ñîîòâåòñòâåííî îòíîøåíèÿ êîìïîíåíòû ìîäåëåé N è CN.
ÔÀÊÒÎÐ-ÌÎÄÅËÜ
 ðåçóëüòàòå ðàññìîòðåíèÿ íà ìíîæåñòâå âåðøèí äåòàëüíîé ìîäåëè Ïåòðè N
ðåôëåêñèâíîãî, ñèììåòðè÷íîãî è òðàíçèòèâíîãî îòíîøåíèÿ — îòíîøåíèÿ
êîìïîíåíòû � ìîæíî ñâèäåòåëüñòâîâàòü î ââåäåíèè ôàêòîðèçàöèè íà ìíîæåñ-
òâå âåðøèí äåòàëüíîé ìîäåëè Ïåòðè èññëåäóåìîé ñèñòåìû è ïîëó÷åíèè ñåòè
N / � — ôàêòîð-ìîäåëè ïî îòíîøåíèþ �. Â ôàêòîð-ìîäåëè N / � â ðåçóëüòàòå
îòíîøåíèÿ � âåðøèíû ñåòè N (îáëàñòè îòíîøåíèÿ êîìïîíåíò NCei
) è ó÷àñò-
êè ñåòè N (îáëàñòè îòíîøåíèÿ êîìïîíåíò NCk
( , , , )k n�1 2 � ) èíäóöèðîâàíû â
âåðøèíû íîâîé ñåòè N / �. Èìååò ìåñòî î÷åâèäíàÿ òåîðåìà.
Òåîðåìà 4. Îáðàç îòîáðàæåíèÿ � : N CN� íàõîäèòñÿ â áèåêòèâíîì ñîîò-
âåòñòâèè ñ ôàêòîð-ìîäåëüþ N / �.
Ñëåäñòâèå 1. CN-ìîäåëü èçîìîôíà ôàêòîð-ìîäåëè N / �.
ÇÀÊËÞ×ÅÍÈÅ
Óñòàíîâëåíî, ÷òî ñâÿçü ìåæäó äåòàëüíîé ñåòüþ N è êîìïîíåíòíîé CN-ìîäåëüþ
Ïåòðè, îñíîâàííàÿ íà ïðåîáðàçîâàíèè ñåòè N â CN-ñåòü, ò.å. èíêàïñóëÿöèè
ó÷àñòêîâ (ñîñòàâíûõ êîìïîíåíò NCk
( , , , )k n�1 2 � — êîìïîíåíò-ìåñò Cp è
êîìïîíåíò-ïåðåõîäîâ Ct) ñåòè N ñîîòâåòñòâåííî â ìåñòà Pk
* è ïåðåõîäû Tk
*
ñåòè CN, ÿâëÿåòñÿ ñþðúåêòèâíûì ãîìîìîðôèçìîì äëÿ ñåòåé Ïåòðè ñ ñîñòàâ-
íûìè êîìïîíåíòàìè. Ïðè ýòîì äîêàçàíî, ÷òî âûäåëåííûå ïðè êîìïîíåíòíîì
ìîäåëèðîâàíèè [11, 14] ñîñòàâíûå êîìïîíåíòû ÿâëÿþòñÿ îáëàñòÿìè îòíîøå-
íèÿ êîìïîíåíòû, êîòîðûå îáðàçóþò ðàçáèåíèå ìíîæåñòâà âåðøèí äåòàëüíîé
ìîäåëè Ïåòðè íà íåïåðåñåêàþùèåñÿ êëàññû ýêâèâàëåíòíîñòè. Ýòî ïîçâîëèëî
ïîñòðîèòü ñåòü N / � — ôàêòîð-ìîäåëü ìîäåëè N ïî îòíîøåíèþ �, èçîìîðô-
íóþ CN-ìîäåëè, ò.å. ïîëó÷èòü äëÿ èññëåäóåìîé ïàðàëëåëüíîé ðàñïðåäåëåííîé
ñèñòåìû äâå èçîìîðôíûå ìîäåëè: â âèäå CN-ñåòè è N / �-ñåòè.
Ðàññìàòðèâàåìàÿ èíêàïñóëÿöèÿ îòíîñèòñÿ ê ïðîáëåìå äåêîìïîçèöèè ñåòåé
Ïåòðè. Èçó÷àåìûé ïîäõîä ïîçâîëÿåò ðàññìàòðèâàòü ìîäåëè N è CN ñ òî÷êè çðå-
íèÿ íåêîòîðîãî îòíîøåíèÿ ïîäîáèÿ, îòâå÷àþùåãî ââåäåííîìó îòíîøåíèþ êîì-
ïîíåíòû è óñòàíîâëåííîìó ãîìîìîðôèçìó èññëåäóåìûõ ñåòåé, è íå çàâèñèò îò
ïîäõîäà, ïðåäëîæåííîãî â ðàáîòàõ [17, 18] è îñíîâàííîãî íà äåêîìïîçèöèè ñåòåé
Ïåòðè íà ôóíêöèîíàëüíûå ïîäñåòè. Èçó÷àåìûé ïîäõîä ê ïðîáëåìå äåêîìïîçè-
öèè ñåòåé Ïåòðè ìîæåò áûòü ïðèìåíåí è äëÿ èçó÷åíèÿ öâåòíûõ è ñ íåêîòîðûìè
âàðèàöèÿìè âðåìåííûõ ñåòåé Ïåòðè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê î ò î â Â . Å . Ñåòè Ïåòðè. — Ì.: Íàóêà, 1984. — 160 ñ.
2. M u r a t a T . Petri nets: Properties, analysis and applications // Proc. IEEE. — 1989. — 77, N 4. —
P. 541–580.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 43
3. E s p a r z a J . , H e l j a n k o K . Unfoldings: A partial-order approach to model checking // EATCS
Monographs in Theoret. Comput. Sci. — ISBN: 978-3-540-77425-9. — New York:
Springer-Verlag, 2008. — 172 p.
4. Ê ð û â û é Ñ . Ë . , Ì à ò â å å â à Ë . Å . Ôîðìàëüíûå ìåòîäû àíàëèçà ñâîéñòâ ñèñòåì // Êèáåð-
íåòèêà è ñèñòåìíûé àíàëèç. — 2003. — ¹ 2. — Ñ. 15–36.
5. B e d n a r c z y k M . A . , B o r z y s z k o w s k i A . M . , S o m l a R . Finite completeness of
categories of Petri nets // Fundamenta Informaticae. – 2000. — 43. — P. 21–48.
6. M e s e g u e r J . , M o n t a n a r i U . On the semantics of Petri nets // Lect. Notes Comput. Sci. —
1992. — 630. — P. 286–301.
7. M e s e g u e r J . , M o n t a n a r i U . , S a s s o n e V . Process versus unfolding semantics for Place
/ Transition Petri nets // Theoret. Comput. Sci. — 1996 — 153. — P. 71–210.
8. M a c L a n e S . Categories for the working mathematician. Graduate texts in mathematics. —
New York: Springer, 1998. — 314 p.
9. Ê î ë ì î ã î ð î â À . Í . , Ô î ì è í Ñ . Â . Ýëåìåíòû òåîðèè ôóíêöèé è ôóíêöèîíàëüíîãî àíà-
ëèçà. — 3-å èçä. — Ì.: Íàóêà, 1972. — 256 ñ.
10. Ê å ë ë è Ä æ . Ë . Îáùàÿ òîïîëîãèÿ. — 2-å èçä. — Ì.: Íàóêà, 1981. — 423 ñ.
11. Ë ó ê ü ÿ í î â à Å . À . , Ä å ð å ç à À . Â . Èññëåäîâàíèå îäíîòèïíèõ ñòðóêòóðíûõ ýëåìåíòîâ
CN-ñåòè â ïðîöåññå êîìïîíåíòíîãî ìîäåëèðîâàíèÿ è àíàëèçà ñëîæíîé ñèñòåìû ñ ïàðàëëåëèç-
ìîì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 6. — Ñ. 20–29.
12. Ë ó ê ü ÿ í î â à Å . À . Î ñòðóêòóðíûõ ýëåìåíòàõ êîìïîíåíòíîé ñåòè Ïåòðè // Ïðîáëåìè ïðî-
ãðàìóâàííÿ. — 2012. — ¹ 2–3. — Ñ. 25–32.
13. Ë ó ê ’ ÿ í î â à Î . Î . Ïðî ïðèñêîðåííÿ îá÷èñëåíü çíàõîäæåííÿ ñòðóêòóðíèõ ³íâàð³àíò³â ïðè
êîìïîíåíòíîìó àíàë³çó CN I -ìåðåæ // ³ñí. Êè¿â. íàö. óí-òó ³ì. Òàðàñà Øåâ÷åíêà.
Ñåð.: ô³ç.-ìàò. íàóêè. — 2012. — ¹ 2. — Ñ. 25–32.
14. Ë ó ê ’ ÿ í î â à Î . Î . Ïðî êîìïîíåíòíå ìîäåëþâàííÿ ñèñòåì ç ïàðàëåë³çìîì // Íàóê. çàïèñêè
ÍàÓÊÌÀ. Êîìï’þòåð. íàóêè. — 2012. — 138. — Ñ. 47–52.
15. Ë ó ê ü ÿ í î â à Å . À . , Ä å ð å ç à À .  . Îá îäíîì ïðîöåññå âåðèôèêàöèè àëãîðèòìè÷åñêèõ
ñõåì // Intern. conf. «Intellegent Informations Processing», IIP-8. — Ì.: ÌÀÊÑ Ïðåññ, 2010. —
C. 299–302.
16. Ë ó ê ’ ÿ í î â à Î . Î . Ïðî çâ’ÿçîê ìîâè CN-ìîäåë³ ç êîìïîíåíòàìè-ïåðåõîäàìè ³ ìîâè äåòàëü-
íî¿ ìîäåë³ Ïåòð³ ïàðàëåëüíî¿ ðîçïîä³ëåíî¿ ñèñòåìè // ³ñí. Êè¿â. íàö. óí-òó ³ì. Òàðàñà Øåâ-
÷åíêà. Ñåð.: ô³ç.-ìàò. íàóêè. — 2012. — ¹ 4. — Ñ. 145–150.
17. Ç à é ö å â Ä . À . Äåêîìïîçèöèÿ ñåòåé Ïåòðè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2004. —
¹ 5. — Ñ. 131–140.
18. Ç à é ö å â Ä . À . Êîìïîçèöèîííûé àíàëèç ñåòåé Ïåòðè // Òàì æå. — 2006. — ¹ 1. —
Ñ. 143–154.
Ïîñòóïèëà 19.07.2013
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
|