Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым. Навед...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2008 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101552 |
| 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: | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859726926952792064 |
|---|---|
| author | Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. |
| author_facet | Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. |
| citation_txt | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым.
Наведено результати оцінки кількості основних ребер при побудові GL-моделей, що відображують реакцію відмовостійкої багатомодульної системи на появу відмов, з мінімальною кількістю втрачених ребер, а також граничні оцінки числа додаткових ребер при трансформації базових GL-моделей до небазових.
The main edge number estimates are given for base GL-models construction with minimum failed edges number which reflect reaction of failure-resistance multi-module system for failure occurrence. The boundary estimates of additional edges number are given to transform base GL-models to non-base.
|
| first_indexed | 2025-12-01T11:23:14Z |
| format | Article |
| fulltext |
ÓÄÊ 519.718
À. Ì. Ðîìàíêåâè÷, ä-ð òåõí. íàóê,
Â. À. Ðîìàíêåâè÷, êàíä. òåõí. íàóê, È. Â. Ìàéäàíþê, àñïèðàíò
Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû
«Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò»
(Óêðàèíà, 03056, Êèåâ, ïð-ò Ïîáåäû, 37,
òåë.: (044) 4549032, E-mail romankev@scs.ntu-kpi.kiev.ua)
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð
GL-ìîäåëåé ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ
ìíîãîïðîöåññîðíûõ ñèñòåì â ïîòîêå îòêàçîâ
(Ñòàòüþ ïðåäñòàâèë ä-ð òåõí.íàóê Â. Ã. Òîöåíêî)
Ïðèâåäåíû îöåíêè ÷èñëà îñíîâíûõ ðåáåð ïðè ïîñòðîåíèè áàçîâûõ GL-ìîäåëåé, îòîáðà-
æàþùèõ ðåàêöèþ îòêàçîóñòîé÷èâîé ìíîãîìîäóëüíîé ñèñòåìû íà ïîÿâëåíèå îòêàçîâ, ñ
ìèíèìàëüíûì ÷èñëîì òåðÿåìûõ ðåáåð, à òàêæå ãðàíè÷íûå îöåíêè ÷èñëà äîïîëíèòåëüíûõ
ðåáåð ïðè òðàíñôîðìàöèè áàçîâûõ GL-ìîäåëåé ê íåáàçîâûì.
Íàâåäåíî ðåçóëüòàòè îö³íêè ê³ëüêîñò³ îñíîâíèõ ðåáåð ïðè ïîáóäîâ³ GL-ìîäåëåé, ùî
â³äîáðàæóþòü ðåàêö³þ â³äìîâîñò³éêî¿ áàãàòîìîäóëüíî¿ ñèñòåìè íà ïîÿâó â³äìîâ, ç ì³í³ìàëü-
íîþ ê³ëüê³ñòþ âòðà÷åíèõ ðåáåð, à òàêîæ ãðàíè÷í³ îö³íêè ÷èñëà äîäàòêîâèõ ðåáåð ïðè
òðàíñôîðìàö³¿ áàçîâèõ GL-ìîäåëåé äî íåáàçîâèõ.
Ê ë þ ÷ å â û å ñ ë î â à: îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû, ãðàôû, ìîäåëè.
Øèðîêîå ðàñïðîñòðàíåíèå ñëîæíûõ ìíîãîìîäóëüíûõ ñèñòåì, óñòîé÷èâûõ ê
îòêàçàì íåêîòîðûõ ìîäóëåé, òðåáóåò àíàëèçà ïîâåäåíèÿ ñèñòåìû â ïîòîêå
îòêàçîâ ðàçëè÷íîé êðàòíîñòè (ò. å. îïðåäåëåíèÿ åå ðåàêöèè íà îòêàç íåêî-
òîðîãî ÷èñëà ìîäóëåé), â ÷àñòíîñòè ïðè îöåíêå åå íàäåæíîñòè [1]. Ñðåäè
ìíîæåñòâà ðàçëè÷íûõ ìîäåëåé, àäåêâàòíî îòîáðàæàþùèõ ýòó ðåàêöèþ, íàè-
áîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èëè GL-ìîäåëè [2], îòëè÷àþùèåñÿ îòíîñè-
òåëüíîé ïðîñòîòîé ôîðìèðîâàíèÿ è óäîáñòâîì èñïîëüçîâàíèÿ.
Ïðè ðàçðàáîòêå, àíàëèçå è òðàíñôîðìàöèè ðåêîíôèãóðèðóåìûõ îòêà-
çîóñòîé÷èâûõ ìíîãîìîäóëüíûõ ñèñòåì (ÎÌÑ), â îñîáåííîñòè ñèñòåì óïðàâ-
ëåíèÿ ñëîæíûìè îáúåêòàìè, GL-ìîäåëü, ñîîòâåòñòâóþùàÿ òàêîé ñèñòåìå,
èíîãäà ïîëó÷àåòñÿ äîñòàòî÷íî ñëîæíîé.  ñâÿçè ñ ýòèì ïðàêòè÷åñêèé èíòåðåñ
ïðåäñòàâëÿåò ðàñ÷åò ïàðàìåòðîâ ìîäåëè íà ïåðâûõ ýòàïàõ ïðîåêòèðîâàíèÿ
ÎÌÑ, à òàêæå îïðåäåëåíèå ñëîæíîñòè òðàíñôîðìàöèè óæå ñîçäàííîé
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 59
���������
�
��������
� �������
ìîäåëè ïðè ïðåîáðàçîâàíèè ñàìîé ñèñòåìû. Îò ñëîæíîñòè ìîäåëè çàâèñèò
âðåìÿ âûïîëíåíèÿ ñòàòèñòè÷åñêèõ ýêñïåðèìåíòîâ ñ íåé è, ñëåäîâàòåëüíî,
òî÷íîñòü ðàñ÷åòà íàäåæíîñòè ÎÌÑ.
Áóäåì îïðåäåëÿòü ÷èñëî îñíîâíûõ ðåáåð â áàçîâîé GL-ìîäåëè, ïðåäëî-
æåííîé â [3]. Ýòà ìîäåëü ñðàâíèòåëüíî ïðîñòà è òåðÿåò äâà ðåáðà ïðè ïîÿâ-
ëåíèè «ëèøíåãî» îòêàçà. Çàòåì îïðåäåëèì ãðàíè÷íûå îöåíêè ÷èñëà äîïîëíè-
òåëüíûõ ðåáåð ïðè ðåêîíôèãóðàöèè áàçîâîé GL-ìîäåëè ê íåáàçîâîé.
×èñëî îñíîâíûõ ðåáåð.  GL-ìîäåëè [2] ïîâåäåíèÿ ÎÌÑ â ïîòîêå
îòêàçîâ ðàáîòîñïîñîáíîñòè ñèñòåìû ïîñòàâëåíà â ñîîòâåòñòâèå ñâÿçíîñòü
íåîðèåíòèðîâàííîãî öèêëè÷åñêîãî ãðàôà, íàëè÷èå (èëè îòñóòñòâèå) ðåáåð
êîòîðîãî îïðåäåëÿåòñÿ çíà÷åíèÿìè áóëåâûõ ôóíêöèé, ïðèñâîåííûõ ðåá-
ðàì ãðàôà. Àðãóìåíòû ôóíêöèé îòîáðàæàþò ñîñòîÿíèå ìîäóëåé (îòêàç —
«0», èñïðàâåí — «1») ñèñòåìû. ÎÌÑ, ñîñòîÿùóþ èç n ýëåìåíòîâ (ìîäóëåé)
è ñîõðàíÿþùóþ ðàáîòîñïîñîáíîñòü â ñëó÷àå îòêàçà íå áîëåå, ÷åì m ëþáûõ
åå ìîäóëåé (0 � m � n), îáîçíà÷èì K m n( , ) è íàçîâåì áàçîâîé. Åé ñîîò-
âåòñòâóåò áàçîâàÿ GL-ìîäåëü, êîòîðóþ äëÿ ïðîñòîòû âîñïðèÿòèÿ â äàëü-
íåéøåì áóäåì òàêæå îáîçíà÷àòü K m n( , ). Ðåáåðíûå ôóíêöèè ôîðìèðóþòñÿ
òàêèì îáðàçîì, ÷òî äëÿ áàçîâîé ìîäåëè K m n( , ) ïîÿâëåíèå âåêòîðîâ ñ
÷èñëîì íóëåé (îòêàçîâ â ñèñòåìå), íå ïðåâûøàþùåì âåëè÷èíû m, ïðèâî-
äèò ê èñ÷åçíîâåíèþ íå áîëåå, ÷åì îäíîãî ðåáðà.  äðóãèõ ñëó÷àÿõ â ãðàôå
èñ÷åçàþò äâà è áîëåå ðåáåð, è îí òåðÿåò ñâÿçíîñòü. Ìîäåëü, ïðåäëîæåííàÿ
â [3], òåðÿåò ìèíèìàëüíîå ÷èñëî ðåáåð ïðè ïîÿâëåíèè âåêòîðîâ ñ ÷èñëîì
íóëåâûõ êîìïîíåíò, ïðåâûøàþùèì m, à ïðè ïîÿâëåíèè âåêòîðà ñ m + 1
íóëåâîé êîìïîíåíòîé èç ìîäåëè èñêëþ÷àþòñÿ ðîâíî äâà ðåáðà.
Ðàññìîòðèì çàäà÷ó îïðåäåëåíèÿ ÷èñëà r ðåáåð GL-ìîäåëè, ïîñòðîåí-
íîé ïî ýòîìó ìåòîäó. Àëãîðèòì ôîðìèðîâàíèÿ ðåáåðíûõ ôóíêöèé ìîäåëè
ÎÌÑ îñíîâàí íà îïåðàöèè ñêëåèâàíèÿ. Ïðèâåäåì íåñêîëüêî îñíîâíûõ åãî
ïîëîæåíèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è.
Îáîçíà÷èì ÷åðåç �K m n( , ) ìíîæåñòâî ðåáåðíûõ ôóíêöèé GL-ìîäåëè
K m n( , ). Êàæäûé ýëåìåíò èç �K m n( , ) ïðèñâîåí òîëüêî îäíîìó ðåáðó ìîäå-
ëè. Ïðîöåññ ïîëó÷åíèÿ ýëåìåíòîâ �K m n( , ) ìîæíî ïðåäñòàâèòü â âèäå
ðåêóðñèâíîãî ñîîòíîøåíèÿ:
� �� � � � �K m n K m i n K i n( , ) ( ,[ / ]) ( , ] / [)
1 1 1 1 1
2 2 , (1)
ãäå i = 0 ... m1, n1 > m1, m i n
1 1
2� � [ / ], i n�] / [
1
2 ; [ ]x — öåëàÿ ÷àñòü îò õ; ] x [—
îêðóãëåíèå äî áëèæàéøåãî áîëüøåãî öåëîãî. Íà ïåðâîì øàãå àëãîðèòìà
âìåñòî ïåðåìåííûõ m1 è n1 ïîäñòàâëÿåì ðåàëüíûå çíà÷åíèÿ m è n, íà
ïîñëåäóþùèõ, åñëè ýòî âîçìîæíî, — ñîîòâåòñòâóþùèå çíà÷åíèÿ ïðåäû-
äóùåãî øàãà èç ïðàâîé ÷àñòè ñîîòíîøåíèÿ (1).
 [3] äîêàçàíî, ÷òî äèçúþíêòèâíîå âûðàæåíèå âèäà
� � � �K m p n K p n( ,[ / ]) ( , ] / [)
1 1 1
2 2 , (2)
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
60 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
ãäå 0 < p < m1; n1 > m1; m p n
1 1
2� � [ / ]; p n�] / [
1
2 , ïîääàåòñÿ ñïåöèàëüíûì
ïðåîáðàçîâàíèÿì è â êîíå÷íîì èòîãå ìîæåò áûòü çàïèñàíî â âèäå îäíîé
áóëåâîé ðåáåðíîé ôóíêöèè, ò.å. ñîîòâåòñòâóþùåå ìíîæåñòâî �K áóäåò
ñîñòîÿòü èç îäíîãî ýëåìåíòà. Çàìåòèì, ÷òî â âûðàæåíèÿõ (1) è (2) îïåðà-
öèþ äèçúþíêöèè ñëåäóåò îòíîñèòü íå ê ñàìèì ìíîæåñòâàì, à ê ïàðàì
ýëåìåíòîâ (ôóíêöèé) ðàçíûõ ìíîæåñòâ âèäà �K .
Ìíîæåñòâî �K m n( , )
1 1
, ãäå m n
1 1
� , íå òðåáóåò ïðåäñòàâëåíèÿ â âèäå (2) è
äàëüíåéøåãî ïðåîáðàçîâàíèÿ: îíî ñîñòîèò òîëüêî èç îäíîé ôóíêöèè. Ïîíÿò-
íî, ÷òî ðàññìàòðèâàòü äâèæåíèå â ãëóáèíó íà ñëåäóþùåì øàãå ðåêóðñèè ïî
(1) öåëåñîîáðàçíî òîëüêî äëÿ äèçúþíêöèé âèäà � � �K m n K n( ,[ / ]) ( , ] / [)
1 1 1
2 0 2
èëè � � �K n K m n( ,[ / ]) ( , ] / [)0 2 2
1 1 1
, ò. å. ïðè ãðàíè÷íûõ çíà÷åíèÿõ ïåðåìåí-
íîé i, èáî òîëüêî â ýòîì ñëó÷àå íåîáõîäèì äàëüíåéøèé ðåêóðñèâíûé ñïóñê
äëÿ îïðåäåëåíèÿ �K m n( , ). Ñëåäóåò çàìåòèòü, ÷òî ìíîæåñòâî �K m n( , )
1 1
ïóñòî ïðè m1 = 0, è ïðè ïîñëåäóþùèõ âûêëàäêàõ óïîìèíàíèå î íåì áóäåì
îïóñêàòü.
Ïîñëå âûïîëíåíèÿ âñåõ ïðåîáðàçîâàíèé âèäà (1) è (2) áóäóò ïîëó÷åíû
âñå ìíîæåñòâà òèïà �K , äëÿ êîòîðûõ íå íóæíû èëè íåâîçìîæíû äàëü-
íåéøèå ïðåîáðàçîâàíèÿ. Äëÿ ïîëó÷åíèÿ èñêîìîãî �K m n( , ) âûïîëíÿåì
îáúåäèíåíèå ýëåìåíòîâ ýòèõ ìíîæåñòâ.
Òåïåðü âîçâðàòèìñÿ ê ðåøåíèþ ïîñòàâëåííîé çàäà÷è. Äîêàæåì ñëå-
äóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå.
r = n – m + 1.
Äëÿ óïðîùåíèÿ äîêàçàòåëüñòâà ïðîöåññ ïîëó÷åíèÿ ýëåìåíòîâ �K m n( , )
ïî (1) ïðåäñòàâèì â âèäå äåðåâà. Äëÿ óäîáñòâà ïîìåñòèì â óçëû äåðåâà
ìíîæåñòâà �K m n( , )
1 1
, äëÿ êîòîðûõ ïðèìåíèìà îïåðàöèÿ (1) è êîòîðûå íå
âõîäÿò â ñîñòàâ äèçúþíêöèé òèïà (2), ãäå n m
1 1
� . Âåðøèíû äåðåâà ñîîò-
âåòñòâóþò ýëåìåíòàì ìíîæåñòâà �K m n( , ), ò. å. ðåáðaì èñõîäíîé GL-ìîäåëè ñ
èõ ôóíêöèÿìè, ñëåäîâàòåëüíî, ÷èñëî âåðøèí äåðåâa â òî÷íîñòè ðàâíî
÷èñëó ðåáåð ìîäåëè. Äèçúþíêöèè (2) ïðèïèøåì âåðøèíàì (âåðøèíà íå
èìååò èñõîäÿùèõ äóã). Ïîìåñòèì â âåðøèíû äåðåâà òàêæå ìíîæåñòâà
�K m n( , )
1 1
, ãäå m n
1 1
� , íå âõîäÿùèå â ñîñòàâ äèçúþíêöèè (2). Ïðèìåð
òàêîãî äåðåâà ïðèâåäåí íà ðèñ. 1.
 äàííîì ïðèìåðå �K ( , )3 9 , �K ( , )3 5 , �K ( , )3 4 ïîìåùåíû â óçëàõ, âñå
äèçúþíêòèâíûå âûðàæåíèÿ òèïà (2) ïðèñâîåíû âåðøèíàì è �K ( , )3 3 òàêæå
îòîáðàæàåòñÿ êàê âåðøèíà. Íàïîìíèì, ÷òî êàæäàÿ âåðøèíà ñîäåðæèò ìíî-
æåñòâî �K , ìîùíîñòü êîòîðîãî ðàâíà åäèíèöå. Äåðåâî ïîçâîëÿåò óïðîñòèòü
ïðîöåäóðó îïðåäåëåíèÿ ÷èñëà r.
Ñëåäóÿ îïåðàöèè (1) â ãëóáèíó, ïîñëåäîâàòåëüíî íà êàæäîì ýòàïå
äåëèì âåëè÷èíó n íà äâà, ïîëó÷àÿ çíà÷åíèÿ ïåðåìåííûõ n1 íà ñîîòâåòñò-
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 61
âóþùåì ýòàïå. Òàêèì îáðàçîì, n ni
i
1
2� [ / ]ëèáî n ni
i
1
2�] / [, ãäå i — íîìåð
ýòàïà (óðîâíÿ). Ïóñòü (k + 1) = max (i), ò. å. íà óðîâíå (k + 1) óçëû
îòñóòñòâóþò. Ïîñêîëüêó k-é óðîâåíü ýòî ìàêñèìàëüíûé óðîâåíü, èìåþ-
ùèé óçëû, ìîæíî çàïèñàòü m n mk
� �/2 2 . Ðàçäåëèâ ýòî íåðàâåíñòâî íà m è
óìíîæèâ íà 2
k
, ïîëó÷èì 2 2
1k kn m� �
�
/ , èëè 2 2 22
1k n m k
� �
�log ( / )
, îòêóäà
k n m� [log ( / )]
2
. Èñõîäÿ èç (1), ìîæíî çàìåòèòü, ÷òî èç êàæäîãî óçëà, íàõî-
äÿùåãîñÿ íà óðîâíå ãëóáèíîé i < k, âûõîäèò m + 1 âåòâü, è êàæäûé òàêîé
óçåë èìååò ðîâíî m – 1 èíöèäåíòíóþ âåðøèíó. Íà êàæäîì òàêîì óðîâíå
áóäåò 2
i
óçëîâ. Ëåãêî îïðåäåëèòü îáùåå ÷èñëî âåðøèí r*
íà óðîâíÿõ
ãëóáèíîé ìåíüøåé k:
r mi
i
k
*
( )� �
�
�
2 1
1
1
.
Ïîíÿòíî, ÷òî íà îäíîì è òîì æå óðîâíå â ðàçëè÷íûõ óçëàõ (îáîçíà-
÷åííûõ �K m n( , )
1 1
), çíà÷åíèÿ âåëè÷èí n1 îòëè÷àþòñÿ íå áîëåå ÷åì íà åäèíèöó.
Îáîçíà÷èì ÷åðåç nm ìåíüøåå èç çíà÷åíèé n1 íà k-ì óðîâíå, à ÷åðåç nx —
áîëüøåå. Î÷åâèäíî, ÷òî n nm
k
� [ / ]2 , à n nx
k
�] / [2 . Ïóñòü
� � �{ / }n nk
2
� � �[ / ]n n nk k
m
k
2 2 2 , ãäå {x/y} — îñòàòîê îò öåëî÷èñëåííîãî äåëåíèÿ.
ßñíî, ÷òî
ðàâíî ÷èñëó óçëîâ �K m n( , )
1 1
, â êîòîðûõ n nx1
� , à ( )2
k
�
—
÷èñëó óçëîâ �K m n( , )
1 1
, â êîòîðûõ n nm1
� . Ïîñêîëüêó óçåë k-ãî óðîâíÿ ìîæåò
áûòü èíöèäåíòåí òîëüêî âåðøèíàì (k + 1)-ãî óðîâíÿ, àíàëèçèðóÿ (1), ìîæíî
çàìåòèòü, ÷òî ÷èñëî òàêèõ âåðøèí îïðåäåëÿåòñÿ êàê (n m
1 1
1� � ). Ñëåäîâà-
òåëüíî, îáùåå ÷èñëî âåðøèí, èíöèäåíòíûõ âñåì óçëàì �K m nx( , )
1
, ðàâíî
( )n mx � �
1
1 . Àíàëîãè÷íî îáùåå ÷èñëî âåðøèí, èíöèäåíòíûõ âñåì óçëàì
�K m nm( , )
1
, ðàâíî ( ) ( )2 1
k
mn m� � �
. Ñëåäîâàòåëüíî, îáùåå ÷èñëî âåðøèí
âî âñåì äåðåâå:
r m n m n mi
x
k
m
i
k
� � � � � � � � � �
�
�
2 1 1 2 1
1
1
( ) ( ) ( ) ( )
� � � � � � � � � � �( )( ) ( ) ( ) ( )2 1 1 1 2 1
k
x
k
mm n m n m
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
62 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
K�(3,9)
K�(3,4)
K�(3,5) K�(2,3)� �K (1,2)
K�(2,2)� �K (1,2)
K�(1,2)� K’(2,2)
K�(3,3)
K�(1,3)� �K (2,2)
K�(1,4) � K’ (2,5)
K�(2,4) K� ’ (1,5)
Íóëåâîé óðîâåíü Âòîðîé óðîâåíüÏåðâûé óðîâåíü
Ðèñ. 1. Äåðåâî äëÿ �K ( , )3 9
� � � � � � � � � � � � � �2 2 1 2 2 2
k k
x
k
m
k k
mm m n m n m n m
� � � � �
n n n mx
k
m m2 1. (3)
Ïîñêîëüêó n nx
k
�] / [2 , à n nm
k
� [ / ]2 , n nx m� ëèøü â ñëó÷àå, êîãäà n k
/2 —
öåëîå ÷èñëî, èíà÷å n nx m� �1.  óðàâíåíèè (3) nx óìíîæàåòñÿ íà êîýôôè-
öèåíò
, ðàâíûé íóëþ, êîãäà n k
/2 — öåëîå. Íà îñíîâàíèè èçëîæåííîãî
ìîæíî âûïîëíèòü çàìåíó n nx m� �1:
r n m n n n n n mx
k
m m m
k
m m� � � � � � � � � � � �
1 2 2 1
� � � �
2 1
k
mn m .
Ïîäñòàâèâ
� �n nm
k
2 , ïîëó÷èì r n n n m n mk
m
k
m� � � � � � � �2 2 1 1. Óòâåðæ-
äåíèå äîêàçàíî.
Îöåíêà ÷èñëà äîïîëíèòåëüíûõ ðåáåð ïðè ïðåîáðàçîâàíèè GL-
ìîäåëè. Áàçîâàÿ ÎÌÑ ïðîäîëæàåò ôóíêöèîíèðîâàòü ïðè ïîÿâëåíèè îòêà-
çîâ, êðàòíîñòü êîòîðûõ íå ïðåâûøàåò çàäàííóþ. Îäíàêî ðåàëüíî ÎÌÑ
ìîæåò ïðîäîëæàòü ôóíêöèîíèðîâàòü è ïðè ïîÿâëåíèè îòêàçîâ áîëåå âûñî-
êîé êðàòíîñòè, ÷òî äîëæíî áûòü àäåêâàòíî îòîáðàæåíî íà GL-ìîäåëè. Â
ïîäîáíûõ ñëó÷àÿõ íåîáõîäèìî ðåøàòü çàäà÷ó ïðåîáðàçîâàíèÿ ìîäåëè
áàçîâîé ÎÌÑ ê ìîäåëè íåáàçîâîé ÎÌÑ. Ïîÿâëåíèå ñîîòâåòñòâóþùèõ
âåêòîðîâ ñîñòîÿíèÿ ñèñòåìû ïðèâåäåò ê èñ÷åçíîâåíèþ êàêèõ-òî îñíîâíûõ
ðåáåð áàçîâîé GL-ìîäåëè. Áóäåì ðàññìàòðèâàòü ñëó÷àé èñ÷åçíîâåíèÿ
òîëüêî ïàðû îñíîâíûõ ðåáåð (â ñîîòâåòñòâèè ñ ðàññóæäåíèÿìè, èçëîæåí-
íûìè âûøå) ïðè ïîÿâëåíèè îäíîãî òàêîãî âåêòîðà, õîòÿ ðåàëüíî èñ÷åçíóòü
ìîæåò áîëüøåå ÷èñëî îñíîâíûõ ðåáåð (ýòî çàâèñèò îò àëãîðèòìà ôîðìèðî-
âàíèÿ ðåáåðíûõ ôóíêöèé äëÿ ìîäåëè). Ïîíÿòíî, ÷òî èñ÷åçíîâåíèå ïàðû
ðåáåð âåäåò ê ïîòåðå ñâÿçíîñòè ãðàôà áàçîâîé ìîäåëè. Îäíèì èç ïóòåé
îáåñïå÷åíèÿ àäåêâàòíîñòè ìîäåëè (ò.å. ñîõðàíåíèÿ ñâÿçíîñòè ãðàôà) äëÿ
óêàçàííûõ ñëó÷àåâ ÿâëÿåòñÿ ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð ñî ñâîèìè
ôóíêöèÿìè [4].
Îáîçíà÷èì L ìíîæåñòâî ïàð ðåáåð, ïðè èñêëþ÷åíèè êîòîðûõ íåîáõî-
äèìî îáåñïå÷èòü ñâÿçíîñòü ãðàôà, à åãî ìîùíîñòü îáîçíà÷èì l. Êàæäàÿ
ïàðà ñîîòâåòñòâóåò îäíîìó èç âåêòîðîâ ñîñòîÿíèÿ ñèñòåìû. Â äàëüíåéøåì
äëÿ êðàòêîñòè ñîõðàíåíèå ñâÿçíîñòè ãðàôà ïðè èñ÷åçíîâåíèè ïàð ðåáåð (èç
ìíîæåñòâà L) áóäåì íàçûâàòü áëîêèðîâêîé ìíîæåñòâà L, èëè ïðîñòî
áëîêèðîâêîé.
 ñîîòâåòñòâèè ñ àëãîðèòìîì, îïèñàííûì â [4], ðåáðà ãðàôà èñõîäíîé
GL-ìîäåëè ðàçáèâàåì íà äâà èëè áîëåå íåïóñòûõ, íåïåðåñåêàþùèõñÿ
S-ïîäìíîæåñòâà: â îäíîì S-ïîäìíîæåñòâå ïðèñóòñòâóþò òîëüêî òàêèå
ðåáðà, âûáîðêà ïî äâà êîòîðûõ íå ñîâïàäàåò íè ñ îäíèì ýëåìåíòîì èç
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 63
ìíîæåñòâà L. Îäíèì èç âàæíûõ êðèòåðèåâ ðàçáèåíèÿ ãðàôà íà S-ïîäìíî-
æåñòâà ÿâëÿåòñÿ èõ ìèíèìàëüíîå ÷èñëî. Çàòåì ïðîâîäèì äîïîëíèòåëüíûå
ðåáðà â ñîîòâåòñòâèè ñ ðàçáèåíèåì ãðàôà íà S-ïîäìíîæåñòâà. Ôàêòè÷åñêè
ðàçáèåíèå ìíîæåñòâà ðåáåð ãðàôà íà S-ïîäìíîæåñòâà îïðåäåëÿåò ÷èñëî è
ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð, êîòîðûå îáåñïå÷èâàþò ñîõðàíåíèå
ñâÿçíîñòè ãðàôà ïðè èñ÷åçíîâåíèè îïðåäåëåííûõ ïàð ðåáåð. Ïîñêîëüêó
ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð ôàêòè÷åñêè îïðåäåëÿåòñÿ ðàçáèåíèåì
ãðàôà íà S-ïîäìíîæåñòâà, áóäåì ñ÷èòàòü, ÷òî S-ïîäìíîæåñòâà áëîêèðóþò
ïàðû ðåáåð èç ìíîæåñòâà L. Ïóñòü p — ÷èñëî S-ïîäìíîæåñòâ, à èõ ìîù-
íîñòè îáîçíà÷èì ñîîòâåòñòâåííî s1, s2, ..., sp. Ñîãëàñíî ìåòîäó, ïðåäëîæåí-
íîìó â [4], ÷èñëî äîïîëíèòåëüíûõ ðåáåð n = ] p/2 [.
Íà ýòàïå ïðîåêòèðîâàíèÿ ìîäåëè è âíåñåíèÿ â íåå èçìåíåíèé ðàç-
ðàáîò÷èêó íåîáõîäèìî çíàòü ãðàíè÷íûå çíà÷åíèÿ ÷èñëà ââîäèìûõ äëÿ
îáåñïå÷åíèÿ àäåêâàòíîñòè ìîäåëè äîïîëíèòåëüíûõ ðåáåð. Èíòåðåñ òàêæå
ïðåäñòàâëÿåò ïðåäåëüíîå ÷èñëî âåêòîðîâ, áëîêèðóåìûõ ñ ïîìîùüþ çàäàí-
íîãî ÷èñëà äîïîëíèòåëüíûõ ðåáåð. Ñôîðìóëèðóåì ñëåäóþùóþ çàäà÷ó:
îïðåäåëèòü ãðàíèöû p (÷èñëî S-ïîäìíîæåñòâ), èñõîäÿ èç çàäàííûõ
çíà÷åíèé r è l ;
îïðåäåëèòü ãðàíèöû äëÿ l ïðè çàäàííûõ p è r .
Ïîíÿòíî, ÷òî çíà÷åíèå l ìîæåò êîëåáàòüñÿ â ïðåäåëàõ îò åäèíèöû (íå
ïóñòîå ìíîæåñòâî L) äî C r
2
(êàê ïåðåáîð âñåâîçìîæíûõ ïàð ðåáåð), à
çíà÷åíèå p — â ïðåäåëàõ îò åäèíèöû (ïðè ïóñòîì ìíîæåñòâå L) äî r, êîãäà
êàæäîå ðåáðî çàäàeò îäíî S-ïîäìíîæåñòâî (â ýòîì ñëó÷àå l = C r
2
).
Îñíîâíûå îïðåäåëåíèÿ. Ïóñòü ñóùåñòâóþò âñå âîçìîæíûå êîìáèíàöèè
ïî l ïàð ðåáåð 1
2
� �l C r èñõîäíîé GL-ìîäåëè: k1, k2, …, kCr
2
. Êàæäàÿ êîìáè-
íàöèÿ ki ïîòðåáóåò äëÿ ðåøåíèÿ çàäà÷è áëîêèðîâêè ñâîåãî îïòèìàëüíîãî
ðàçáèåíèÿ ìíîæåñòâà ðåáåð GL-ìîäåëè íà pi S-ïîäìíîæåñòâ.
Îïðåäåëåíèå 1. Âåëè÷èíà pmax (l) åñòü ìàêñèìàëüíîå çíà÷åíèå èç pi,
pmin(l) — ìèíèìàëüíîå èç pi, ò. å. âåðõíÿÿ ãðàíèöà pmax(l) — ýòî òàêîå ÷èñëî
S-ïîäìíîæåñòâ, êîòîðîå ñïîñîáíî áëîêèðîâàòü ëþáîé íàáîð ýëåìåíòîâ
ìíîæåñòâà L ìîùíîñòüþ l, âûïîëíÿÿ óñëîâèå ìèíèìàëüíîñòè ÷èñëà S-ïîä-
ìíîæåñòâ. Ïóñòü pmin (l) — ìèíèìàëüíîå ÷èñëî S-ïîäìíîæåñòâ, îáåñïå÷è-
âàþùåå âîçìîæíîñòü áëîêèðîâêè õîòÿ áû îäíîãî íàáîðà èç l ïàð ðåáåð,
ïðè÷åì äîáàâëåíèå õîòÿ áû îäíîãî ýëåìåíòà â ìíîæåñòâî L îäíîçíà÷íî
ïîòðåáîâàëî áû ðàçáèåíèÿ íà áîëüøåå, ÷åì pmin (l), ÷èñëî S-ïîäìíîæåñòâ.
Ñóùåñòâóþò âñå âîçìîæíûå ðàçáèåíèÿ
1 2
, ,..., t ðåáåð èñõîäíîé
GL-ìîäåëè íà p S-ïîäìíîæåñòâ. Êàæäîå ðàçáèåíèå
i ÿâëÿåòñÿ îïòèìàëü-
íûì äëÿ îñóùåñòâëåíèÿ áëîêèðîâàíèÿ ðàçëè÷íûõ ìíîæåñòâ ïàð ðåáåð,
ñðåäè êîòîðûõ èìååòñÿ íàèáîëüøåå ïî ìîùíîñòè, âêëþ÷àþùåå �li ïàð, è
íàèìåíüøåå, âêëþ÷àþùåå ��li ïàð.
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
64 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
Îïðåäåëåíèå 2. Ìàêñèìàëüíîå èç �li îáîçíà÷èì lmax (p), à ìèíèìàëüíîå
èç ��li — lmin (p), ò. å. lmax (p) — ýòî ìàêñèìàëüíîå ÷èñëî ïàð ðåáåð, äëÿ
áëîêèðîâêè êîòîðûõ äîñòàòî÷íî ðàçáèåíèÿ ãðàôà íà p S-ïîäìíîæåñòâ;
lmin (p) — òàêîå ìèíèìàëüíîå çíà÷åíèå ìîùíîñòè ìíîæåñòâà L, äëÿ áëîêè-
ðîâêè êîòîðîãî òðåáóåòñÿ ðàçáèåíèå ðåáåð ãðàôà íà p S-ïîäìíîæåñòâ. Ýòî
òàêàÿ êîìáèíàöèÿ èç l ïàð, ÷òî óäàëåíèå õîòÿ áû îäíîãî ýëåìåíòà èç
ìíîæåñòâà L ïîòðåáîâàëî áû ìåíåå ÷åì p S-ïîäìíîæåñòâ (ñ ó÷åòîì òðåáî-
âàíèÿ ìèíèìàëüíîñòè ê èõ ÷èñëó).
Âçàèìíàÿ îáðàòèìîñòü ãðàíè÷íûõ ôóíêöèé. Ïîêàæåì, ÷òî ïðè
îñóùåñòâëåíèè îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâà ðåáåð GL-ìîäåëè íà
S-ïîäìíîæåñòâà [4] ãðàíè÷íûå ôóíêöèè pmin(l) è lmax(p) ÿâëÿþòñÿ âçàèìíî
îáðàòíûìè.
Ïóñòü l l p*
max
*
( )� , ò.å. ñðåäè âñåõ îïòèìàëüíûõ ðàçáèåíèé ðåáåð ãðà-
ôà íà p* S-ïîäìíîæåñòâ ñóùåñòâóåò òàêîå, êîòîðîå áëîêèðóåò ìíîæåñòâî
ïàð ðåáåð, èìåþùåå íàèáîëüøóþ ìîùíîñòü, ðàâíóþ l*
. Ïîíÿòíî, ÷òî åñëè
çàäàíî êàêîå-òî ìíîæåñòâî ïàð ðåáåð L, âêëþ÷àþùåå l*
ïàð, òî äëÿ åãî
áëîêèðîâàíèÿ ïîíàäîáèòñÿ íå ìåíåå ÷åì p* S-ïîäìíîæåñòâ.  òî æå âðåìÿ
ñóùåñòâóåò òàêîå ìíîæåñòâî p l
min
*
( ) ìîùíîñòüþ l*
ïàð, äëÿ êîòîðîãî ðàç-
áèåíèå íà p* S-ïîäìíîæåñòâ îêàçûâàåòñÿ äîñòàòî÷íûì. Ñëåäîâàòåëüíî, â
òî÷êàõ ïðîñòðàíñòâà (p*
, l*
) çíà÷åíèÿ ôóíêöèé p l
min
*
( ) è l p
max
*
( ) ñîâ-
ïàäàþò. Ïîäîáíûå ðàññóæäåíèÿ ñïðàâåäëèâû äëÿ ëþáûõ çíà÷åíèé l è p, à
çíà÷èò, ýòè ôóíêöèè ÿâëÿþòñÿ âçàèìíî îáðàòíûìè. Ïðîâåäÿ àíàëîãè÷íûå
ðàññóæäåíèÿ îòíîñèòåëüíî äðóãîé ïàðû ãðàíè÷íûõ ôóíêöèé, ïðèõîäèì ê
âûâîäó, ÷òî ôóíêöèè l p
min
( ) è p l
max
( ) òàêæå âçàèìíî îáðàòíû.
Íà îñíîâàíèè èçëîæåííîãî ìîæíî ñäåëàòü âûâîä î òîì, ÷òî äëÿ ïîèñ-
êà ãðàíè÷íûõ ôóíêöèé äîñòàòî÷íî íàéòè òîëüêî äâå èç íèõ, îïðåäåëÿÿ
äðóãèå êàê âçàèìíî îáðàòíûå.
Íèæíÿÿ ãðàíèöà l. Ââåäåì ïîíÿòèå V-ãðàôà [4]. Ýòî íåîãðàô, â êîòî-
ðîì âåðøèíàì ñîîòâåòñòâóþò ðåáðà èñõîäíîãî ãðàôà GL-ìîäåëè, à ðåáðà
ïðîâîäÿòñÿ â ñîîòâåòñòâèè ñ ïàðàìè ìíîæåñòâà L. Ñëåäóåò çàìåòèòü, ÷òî
ïðàâèëüíàÿ ðàñêðàñêà âåðøèí V-ãðàôà, êàê ïîêàçàíî â [4], îïðåäåëÿåò
ðàçáèåíèå èñõîäíîãî ãðàôà íà S-ïîäìíîæåñòâà, ïðè÷åì ðåáðà, èìåþùèå
îäèí öâåò, âõîäÿò â îäíî S-ïîäìíîæåñòâî. Íà ðèñ. 2 ïðèâåäåí ïðèìåð
V-ãðàôà, åãî ðàñêðàñêè è ñîîòâåòñòâóþùåãî ðàçáèåíèÿ ìíîæåñòâà ðåáåð
èñõîäíîãî ãðàôà ìîäåëè íà S-ïîäìíîæåñòâà äëÿ r = 8.
Äîïóñòèì, p — õðîìàòè÷åñêîå ÷èñëî V-ãðàôà, êîòîðûé áóäåì ñòðîèòü,
èñõîäÿ èç GL-ìîäåëè ÎÌÑ. Ïîñêîëüêó l ðàâíî ÷èñëó ðåáåð V-ãðàôà, äëÿ
ðåøåíèÿ ïîñòàâëåííîé çàäà÷è äîñòàòî÷íî îïðåäåëèòü ìèíèìàëüíîå ÷èñëî
ðåáåð, ôîðìèðóþùèõ V-ãðàô, òðåáóþùèé p êðàñîê äëÿ ïðàâèëüíîé ðàñ-
êðàñêè ñâîèõ âåðøèí. Èçâåñòíî, ÷òî õðîìàòè÷åñêîå ÷èñëî íå ìåíüøå
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 65
÷èñëà âåðøèí â êëèêå ãðàôà, ò. å. â ìàêñèìàëüíî ïîëíîì ïîäãðàôå. Ñëåäî-
âàòåëüíî, äîñòàòî÷íî âûáðàòü òàêîå ÷èñëî ðåáåð, êîòîðîå â îïòèìàëüíîì
ñëó÷àå çàäàâàëî áû ïîëíûé ïîäãðàô, ñîñòîÿùèé èç p âåðøèí. Òàêèì
îáðàçîì, çàäà÷à ñâåäåíà ê îïðåäåëåíèþ ÷èñëà ðåáåð ïîëíîãî ãðàôà, èìåþ-
ùåãî p âåðøèí, à çíà÷èò, èñêîìàÿ ãðàíèöà èìååò âèä
l p
p p
min
( )
( )
�
�1
2
.
Ïîñêîëüêó l p
min
( )è p l
max
( )— âçàèìíî îáðàòíûå ôóíêöèè, ïðåäñòàâèâ
l êàê àðãóìåíò ôóíêöèè p, ðåøèâ êâàäðàòíîå óðàâíåíèå, ëåãêî îïðåäåëÿåì,
âåðõíþþ ãðàíèöó ÷èñëà S-ïîäìíîæåñòâ:
p l
l
max
( ) �
� �1 1 8
2
.
(4)
Âåðõíÿÿ ãðàíèöà l. Äëÿ ïîèñêà ãðàíèöû l p
max
( ) âíîâü îáðàòèìñÿ ê
V-ãðàôó, ðåáðà êîòîðîãî ñîîòâåòñòâóþò ýëåìåíòàì ìíîæåñòâà L. Îïðå-
äåëèì, êàêîâà äîëæíà áûòü ñòðóêòóðà V-ãðàôà ñ ìàêñèìàëüíûì ÷èñëîì
ðåáåð, ÷òîáû îí ïðè ýòîì îñòàâàëñÿ p-ðàñêðàøèâàåìûì. Ðàçîáüåì âåð-
øèíû èñêîìîãî V-ãðàôà (îíè ñîîòâåòñòâóþò ðåáðàì GL-ìîäåëè) íà p
ãðóïï è ïðîâåäåì âñå âîçìîæíûå ðåáðà ìåæäó âåðøèíàìè èç ðàçëè÷íûõ
ãðóïï. Ïîíÿòíî, ÷òî òàêîé ãðàô ÿâëÿåòñÿ p-ðàñêðàøèâàåìûì, ïîñêîëüêó
âåðøèíû, âõîäÿùèå â îäíó ãðóïïó, îïðåäåëÿþò âíóòðåííå óñòîé÷èâîå
ìíîæåñòâî. Îäíàêî ïðè ýòîì, â çàâèñèìîñòè îò ñïîñîáà ðàçáèåíèÿ, âîç-
ìîæíîå ÷èñëî ðåáåð, ñîõðàíÿÿ ñâîéñòâî p-ðàñêðàøèâàåìîñòè, áóäåò ðàç-
ëè÷íûì. Äëÿ ðåøåíèÿ çàäà÷è äîñòàòî÷íî âûáðàòü ìîùíîñòè ãðóïï òàêè-
ìè, ÷òîáû ÷èñëî ðåáåð V-ãðàôà áûëî ìàêñèìàëüíûì. Ïîñêîëüêó âñå
âåðøèíû, âõîäÿùèå â îäíó ãðóïïó, èìåþò îäèí öâåò, ñîîòâåòñòâóþùèå èì
ðåáðà â GL-ìîäåëè, áóäóò ïðèíàäëåæàòü îäíîìó S-ïîäìíîæåñòâó. Èñõîäÿ
èç ýòîãî, ìíîæåñòâî L ñëåäóåò ôîðìèðîâàòü êàê ìíîæåñòâî ïàð { , }R RS
w
S
q
i j
,
ãäå w = 1 .. si , q = 1 .. sj , i = 1 .. p – 1, j = (i + 1) .. p; RS
w
i
— ðåáðî èç Si-ïîäìíî-
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
66 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
S
5
1,2
4 3 S2
S
3
S
4
1
5
4
3
2
L =({1, 3},{1, 4} ,
{1, 5},{3, 4},
{3,5},{4, 5})
Ðèñ. 2. Ïîñòðîåíèå V-ãðàôà è ñîîòâåòñòâóþùèõ S-ïîäìíîæåñòâ
æåñòâà. Íàéäåì òàêèå çíà÷åíèÿ s1, s2, …, sp, ïðè êîòîðûõ ìîùíîñòü ìíî-
æåñòâà L áóäåò ìàêñèìàëüíîé.
Î÷åâèäíî, ÷òî1 1� � � �s r pi , ãäå i = 1 ... p. Ïóñòü èìåþòñÿ S1, S2, … ...,
Sp-ïîäìíîæåñòâà è ñîîòâåòñòâóþùèå ìîùíîñòè s1, s2, ..., sp. Èñõîäÿ èç
ñêàçàííîãî âûøå, ìîæíî çàïèñàòü ñëåäóþùåå:
l s s s C C C C C Cp S S S S Spmax
( , ,..., ) ( ... ) (
1 2
1 1 1 1 1
1 2 3 2
� � � � � S SC
p3
1 1
� � �... ) ...
... ( ... ) ...
( )
� � � � � � � �
�
�
C C s s s s s s s sS S p P P i j
i
p p1
1 1
1 2 3 1
, j
j i
p
�
�
1
.
(5)
Çàìåòèì, ÷òî
s s s s rP i
i
p
1 2
1
� � � � �
�
... .
Îïðåäåëèì çíà÷åíèÿ àðãóìåíòîâ si, ïðè êîòîðûõ ôóíêöèÿ lmax(s1, s2, ...
..., sp) ïðèìåò ìàêñèìàëüíîå çíà÷åíèå. Ýòî ïðîèçîéäåò ïðè s s s
1 2 3
� � � ...
... /� �s r pP . Äåéñòâèòåëüíî,
l s s s s s
s
p i j
i j
j i
p i
i
p
max
,
( , ,..., )
1 2
1
1
2
� �
�
�
�
�
�
�
�
�
�
�
�
si
i
p
2
1
2
.
Îòñþäà ñëåäóåò, ÷òî l s s spmax
( , , ..., )
1 2
äîñòèãàåò ìàêñèìóìà, êîãäà çíà-
÷åíèå si
i
p
2
1�
ìèíèìàëüíî. Ïóñòü � �s r p/ , òîãäà si ìîæíî ïðåäñòàâèòü êàê
s si i� � �( )� , ãäå � i
i
p
�
�
1
0, � i is� , i = 1, ..., p. Âûïîëíèì ïðåîáðàçîâàíèÿ:
s s s si
i
p
i
p
i
i
p
i
p
i
i
p
2
1 1
2
1
2
1 1
2
� � � � �
� �� � � � � �( ) ( )� � � �i
i
p
ip s2 2
1
2
� � �
�
( ) .
Ïîñêîëüêó� i
2
0� , ñóììà si
i
p
2
1�
ïðèìåò ìèíèìàëüíîå çíà÷åíèå ïðè� i
2
0� , ò. å.
êîãäà s s r pi � � � / , ÷òî è òðåáîâàëîñü äîêàçàòü. Ïîäñòàâèâ â (4) çíà÷åíèå
s r pi � / , i = 1, 2, …, p , ïîëó÷èì
l r p
r p
pmax
( , )
( )
�
�
2
2
1
.
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 67
Ñëåäóåò çàìåòèòü, ÷òî çíà÷åíèÿ ýòîé ôóíêöèè ÿâëÿþòñÿ äåéñòâèòåëü-
íûìè ÷èñëàìè, íî íà ñàìîì äåëå ôóíêöèÿ lmax äîëæíà ïðèíèìàòü íàòó-
ðàëüíûå çíà÷åíèÿ. Ïîñêîëüêó s s sp1 2
, ,..., òàêæå ìîãóò ïðèíèìàòü òîëüêî
íàòóðàëüíûå çíà÷åíèÿ, s
r
p
i �
�
�
�
�
�
�
ëèáî s
r
p
i �
�
�
�
�
�
�
�1. Ïóñòü s
r
p
1
�
�
�
�
�
�
�
, à îñòàëü-
íûå s sp2
, ..., ðàâíû ëèáî
r
p
�
�
�
�
�
�
�1, ëèáî
r
p
�
�
�
�
�
�
, ÷òî îïðåäåëÿåòñÿ îñòàòêîì
r
p
�
�
�
�
�
�
,
êîòîðûé îáîçíà÷èì
.Ó÷èòûâàÿ, ÷òî s ri
i
p
�
�
1
, à òàêæå òîò ôàêò, ÷òî âçàèì-
íîå ðàñïîëîæåíèå S-ïîäìíîæåñòâ îäíî îòíîñèòåëüíî äðóãîãî íå èìååò
çíà÷åíèÿ, ìîæíî ñ÷èòàòü, ÷òî
s s s
r
p
p1 2
, , ...,
�
�
�
�
�
�
�
�
, s s
r
p
p p�
�
�
�
�
�
�
�
�
�
, ..., 1.
Ïîäñòàâèâ íîâûå çíà÷åíèÿ àðãóìåíòîâ â ôîðìóëó (5) è óïðîñòèâ åå,
ïîëó÷èì
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
l r p C
r
p
C
r
p
Cpmax
( , )
2
2
2
2
1
1 C
r
p
r
p
p�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
1
1
�
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
p p r
p
r
p
p
( )
( )
1
2
1 2 1
2
2
.
Ñ ïîìîùüþ ýòîé ôîðìóëû íàõîäèì òî÷íûå çíà÷åíèÿ.  ðåçóëüòàòå äîñ-
òàòî÷íî áîëüøîãî ÷èñëà ýêñïåðèìåíòîâ óñòàíîâëåíî, ÷òî ñðåäíåå çíà÷å-
íèå àáñîëþòíîé ïîãðåøíîñòè çàâèñèò îò çíà÷åíèÿ r:
� � !l r p l r p r
max max
( , ) ( , ) ,00386 .
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
68 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
l
P
min
(l)
1 3 5 7 9 11 13 15 17 19 21 23 25 27
Pmax (l)
7
5
3
1
0
p
Ðèñ. 3. Ãðàíèöû P l
min
( ) è P l
max
( ) äëÿ ñëó÷àÿ r� 8
Äàëåå â ðàñ÷åòàõ áóäåì èñïîëüçîâàòü ôóíêöèþ l r p
max
( , ), òàê êàê îíà
íå ñîäåðæèò öåëî÷èñëåííîãî äåëåíèÿ è, ñëåäîâàòåëüíî, áîëåå ïðîñòà â
ïðèìåíåíèè. Ïîñêîëüêó l p
max
( ) è p l
min
( ) — ôóíêöèè âçàèìíî îáðàòíûå,
ïðåäñòàâèâ l êàê àðãóìåíò ôóíêöèè p, ëåãêî îïðåäåëèì íèæíþþ ãðàíèöó
÷èñëà S-ïîäìíîæåñòâ:
p l r
r
r l
min
( , ) �
�
2
2
2
.
(6)
Ïîëó÷åííûå âûøå ðåçóëüòàòû ìîæíî ïðåäñòàâèòü â âèäå íåðàâåíñòâ:
r
r l
p r l
l2
2
2
1 1 8
2�
� �
� �
( , ) ;
p p
l p r
p p r
p
r
p
p
( )
( , )
( )
( )
�
� �
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
1
2
1
2
1 2 12
2
.
Ãðàíèöû ÷èñëà S-ïîäìíîæåñòâ, âû÷èñëåííûå äëÿ êîíêðåòíîãî ïðè-
ìåðà ïî ôîðìóëàì (4) è (6), ïîêàçàíû íà ðèñ. 3. Íàéäåííûå ãðàíèöû íå
ÿâëÿþòñÿ íàòóðàëüíûìè ÷èñëàìè, ïîýòîìó îêðóãëèì íèæíþþ ãðàíèöó â
ñòîðîíó ìåíüøåãî öåëîãî ÷èñëà, à âåðõíþþ — â ñòîðîíó áîëüøåãî, ÷òîáû
íå ïîòåðÿòü èõ âîçìîæíûå çíà÷åíèÿ:
r
r l
p r l
l2
2
2
1 1 8
2�
�
�
�
�
�
�
� �
� ��
�
�
�
�
�
( , ) .
Ñëåäóåò çàìåòèòü, ÷òî ïîëó÷åííàÿ ôîðìóëà (6) äëÿ íèæíåé ãðàíèöû
÷èñëà S-ïîäìíîæåñòâ ñîâïàäàåò ñ ðåçóëüòàòàìè, ïðèâåäåííûìè â ðàáîòå
[5] äëÿ íèæíåé ãðàíèöû õðîìàòè÷åñêîãî ÷èñëà ïðîèçâîëüíîãî ãðàôà, ÷òî
ïîäòâåðæäàåò ïðàâèëüíîñòü äàííûõ ðàññóæäåíèé.
Âûâîäû. Ïîëó÷åííûå ðåçóëüòàòû äàþò âîçìîæíîñòü îöåíèòü ñëîæ-
íîñòü GL-ìîäåëè ðàçðàáàòûâàåìîé ÎÌÑ íà ðàííèõ ñòàäèÿõ ïðîåêòèðî-
âàíèÿ. Åå ñëîæíîñòü çàâèñèò îò ÷èñëà ìîäóëåé ñèñòåìû, ñòåïåíè îòêàçî-
óñòîé÷èâîñòè, à òàêæå îò ìíîæåñòâà âåêòîðîâ ñîñòîÿíèÿ ÎÌÑ, êîòîðûå
îòëè÷àþò ìîäåëü ïðîåêòèðóåìîé ñèñòåìû îò áàçîâîé. Ïîëó÷åííûå îöåíêè
ìîãóò ïîìî÷ü ðàçðàáîò÷èêó çàðàíåå îïðåäåëèòü ðåñóðñû (âû÷èñëèòåëüíûå
è âðåìåííûå), íåîáõîäèìûå äëÿ ðàñ÷åòà íàäåæíîñòè ÎÌÑ ñ òðåáóåìîé
òî÷íîñòüþ.
The main edge number estimates are given for base GL-models construction with minimum
failed edges number which reflect reaction of failure-resistance multi-module system for failure
occurrence. The boundary estimates of additional edges number are given to transform base
GL-models to non-base.
Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 69
1. Õàð÷åíêî Â. Ñ., Æèõàðåâ Â. ß., Èëþøêî Â. Ì., Íå÷èïîðóê Í. Â. Ìíîãîâåðñèîííûå
ñèñòåìû, òåõíîëîãèè, ïðîåêòû. — Õàðüêîâ : Íàöèîíàëüíûé àýðîêîñìè÷åñêèé óí-ò
«Õàðüêîâñêèé àâèàöèîííûé èí-ò», 2003. — 486 ñ.
2. Ðîìàíêåâè÷ À. Ì., Êàðà÷óí Ë. Ô., Ðîìàíêåâè÷ Â. À. Ãðàôî-ëîãè÷åñêèå ìîäåëè äëÿ
àíàëèçà ñëîæíûõ îòêàçîóñòîé÷èâûõ âû÷èñëèòåëüíûõ ñèñòåì//Ýëåêòðîí. ìîäåëèðîâà-
íèå. — 2001. — 23, ¹ 1. — Ñ. 102—111.
3. Ðîìàíêåâè÷ Â. À., Ïîòàïîâà Å. Ð., Áàõòàðè Õåäàÿòîëëàõ, Íàçàðåíêî Â. Â. GL-ìîäåëü
ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ ìíîãîïðîöåññîðíûõ ñèñòåì ñ ìèíèìàëüíûì ÷èñëîì
òåðÿåìûõ ðåáåð // ³ñíèê ÍÒÓÓ «Êϲ». ²íôîðìàòèêà, óïðàâë³ííÿ òà îá÷èñëþâàëüíà
òåõí³êà. — 2006. — ¹ 45. — Ñ. 93—100.
4. Ðîìàíêåâè÷ À. Ì., Èâàíîâ Â.Â., Ðîìàíêåâè÷ Â.À. Àíàëèç ÎÌÑ ñî ñëîæíûì ðàñïðå-
äåëåíèåì îòêàçîâ íà îñíîâå öèêëè÷åñêîé GL-ìîäåëè// Ýëåêòðîí. ìîäåëèðîâàíèå. —
2004. — 26, ¹ 5. — Ñ. 67—81.
5. Geller D. P. Problem 5713// American Mathematical Monthly. — 1970. —Vol. 77, ¹ 1. —
Ð. 85.
Ïîñòóïèëà 19.04.07
ÐÎÌÀÍÊÅÂÈ× Àëåêñåé Ìèõàéëîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð êàô. ñïåöèàëèçèðîâàííûõ
êîìïüþòåðíûõ ñèñòåì ÍÒÓÓ «ÊÏÈ». Â1961 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò.
Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ñàìîïðîâåðÿåìûå ñõåìû, ïñåâäîñëó÷àéíîå òåñòèðîâàíèå
öèôðîâîé àïïàðàòóðû, îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû.
ÐÎÌÀÍÊÅÂÈ× Âèòàëèé Àëåêñååâè÷, êàíä. òåõí. íàóê, äîöåíò êàô. ñïåöèàëèçèðîâàííûõ
êîìïüþòåðíûõ ñèñòåì ÍÒÓÓ «ÊÏÈ». â 1996 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò.
Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìîäåëè ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ ìíîãîïðîöåññîðíûõ
ñèñòåì, ðàñ÷åò íàäåæíîñòè.
ÌÀÉÄÀÍÞÊ Èâàí Âèêòîðîâè÷, àñïèðàíò êàô. ñïåöèàëèçèðîâàííûõ êîìïüþòåðíûõ ñèñòåì
ÍÒÓÓ «ÊÏÈ».  2007 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäî-
âàíèé — îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû.
À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê
70 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-101552 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-01T11:23:14Z |
| publishDate | 2008 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. 2016-06-04T19:16:37Z 2016-06-04T19:16:37Z 2008 Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101552 519.718 Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым. Наведено результати оцінки кількості основних ребер при побудові GL-моделей, що відображують реакцію відмовостійкої багатомодульної системи на появу відмов, з мінімальною кількістю втрачених ребер, а також граничні оцінки числа додаткових ребер при трансформації базових GL-моделей до небазових. The main edge number estimates are given for base GL-models construction with minimum failed edges number which reflect reaction of failure-resistance multi-module system for failure occurrence. The boundary estimates of additional edges number are given to transform base GL-models to non-base. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Точность, надежность, диагностика Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов Boundary Estimates of Edge Number for GL-models of Behavior of Failure-resistance Multi-processor Systems in Failure Flow Article published earlier |
| spellingShingle | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. Точность, надежность, диагностика |
| title | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| title_alt | Boundary Estimates of Edge Number for GL-models of Behavior of Failure-resistance Multi-processor Systems in Failure Flow |
| title_full | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| title_fullStr | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| title_full_unstemmed | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| title_short | Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| title_sort | граничные оценки числа ребер gl-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов |
| topic | Точность, надежность, диагностика |
| topic_facet | Точность, надежность, диагностика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101552 |
| work_keys_str_mv | AT romankevičam graničnyeocenkičislareberglmodeleipovedeniâotkazoustoičivyhmnogoprocessornyhsistemvpotokeotkazov AT romankevičva graničnyeocenkičislareberglmodeleipovedeniâotkazoustoičivyhmnogoprocessornyhsistemvpotokeotkazov AT maidanûkiv graničnyeocenkičislareberglmodeleipovedeniâotkazoustoičivyhmnogoprocessornyhsistemvpotokeotkazov AT romankevičam boundaryestimatesofedgenumberforglmodelsofbehavioroffailureresistancemultiprocessorsystemsinfailureflow AT romankevičva boundaryestimatesofedgenumberforglmodelsofbehavioroffailureresistancemultiprocessorsystemsinfailureflow AT maidanûkiv boundaryestimatesofedgenumberforglmodelsofbehavioroffailureresistancemultiprocessorsystemsinfailureflow |