Представлення фрагментарних структур орієнтованими графами

Досліджено властивості фрагментарних структур і встановлено зв язок між ними та розміченими ациклічними орієнтованими графами з одним джерелом, а також встановлено відповідність класів ізоморфних фрагментарних структур нерозміченим ациклічним орієнтованим графам певного виду, які називаються допусти...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
1. Verfasser:	Кривцун, О.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Системний аналіз
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/180858
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Представлення фрагментарних структур орієнтованими графами / О.В. Кривцун // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 163-170. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-180858
record_format	dspace
spelling	irk-123456789-1808582021-10-29T21:43:17Z Представлення фрагментарних структур орієнтованими графами Кривцун, О.В. Системний аналіз Досліджено властивості фрагментарних структур і встановлено зв язок між ними та розміченими ациклічними орієнтованими графами з одним джерелом, а також встановлено відповідність класів ізоморфних фрагментарних структур нерозміченим ациклічним орієнтованим графам певного виду, які називаються допустимими графами. Визначено поняття розмірності допустимого графа та відповідних йому ізоморфних фрагментарних структур. Отримано вираз для нижньої оцінки розмірності. Доведено теорему про властивості допустимих графів. Підраховано кількості фрагментарних структур та класів ізоморфних фрагментарних структур малих розмірностей. Исследованы свойства фрагментарных структур и установлена связь между фрагментарными структурами и размеченными ациклическими ориентированными графами с одним источником, также установлено соответствие классов изоморфных фрагментарных структур неразмеченным ациклическим ориентированным графам определенного вида, которые называются допустимыми графами. Определено понятие размерности допустимого графа и соответствующих ему изоморфных фрагментарных структур. Получено выражение для нижней оценки размерности. Доказана теорема о свойствах допустимых графов. Подсчитано количество фрагментарных структур и классов изоморфных фрагментарных структур малых размерностей. In the paper, the properties of fragmentary structures are investigated and relation between fragmentary structures and marked acyclic oriented graphs with one source is established, also the correspondence of isomorphic fragmentary structure classes with unmarked acyclic oriented graphs of certain type, which are called feasible graphs, is established. The notion of the dimension of a feasible graph and its corresponding isomorphic fragmentary structures is defined. An expression for the lower-bound estimate of the dimension is obtained. A theorem on the properties of feasible graphs is proved. The number of fragmentary structures and classes of isomorphic fragmentary structures of small dimensions is calculated. 2019 Article Представлення фрагментарних структур орієнтованими графами / О.В. Кривцун // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 163-170. — Бібліогр.: 12 назв. — укр. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/180858 519.17 uk Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Системний аналіз Системний аналіз
spellingShingle	Системний аналіз Системний аналіз Кривцун, О.В. Представлення фрагментарних структур орієнтованими графами Кибернетика и системный анализ
description	Досліджено властивості фрагментарних структур і встановлено зв язок між ними та розміченими ациклічними орієнтованими графами з одним джерелом, а також встановлено відповідність класів ізоморфних фрагментарних структур нерозміченим ациклічним орієнтованим графам певного виду, які називаються допустимими графами. Визначено поняття розмірності допустимого графа та відповідних йому ізоморфних фрагментарних структур. Отримано вираз для нижньої оцінки розмірності. Доведено теорему про властивості допустимих графів. Підраховано кількості фрагментарних структур та класів ізоморфних фрагментарних структур малих розмірностей.
format	Article
author	Кривцун, О.В.
author_facet	Кривцун, О.В.
author_sort	Кривцун, О.В.
title	Представлення фрагментарних структур орієнтованими графами
title_short	Представлення фрагментарних структур орієнтованими графами
title_full	Представлення фрагментарних структур орієнтованими графами
title_fullStr	Представлення фрагментарних структур орієнтованими графами
title_full_unstemmed	Представлення фрагментарних структур орієнтованими графами
title_sort	представлення фрагментарних структур орієнтованими графами
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Системний аналіз
url	http://dspace.nbuv.gov.ua/handle/123456789/180858
citation_txt	Представлення фрагментарних структур орієнтованими графами / О.В. Кривцун // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 163-170. — Бібліогр.: 12 назв. — укр.
series	Кибернетика и системный анализ
work_keys_str_mv	AT krivcunov predstavlennâfragmentarnihstrukturoríêntovanimigrafami
first_indexed	2025-07-15T21:12:13Z
last_indexed	2025-07-15T21:12:13Z
_version_	1837748908364660736
fulltext	ÓÄÊ 519.17 Î.Â. ÊÐÈÂÖÓÍ ÏÐÅÄÑÒÀÂËÅÍÍß ÔÐÀÃÌÅÍÒÀÐÍÈÕ ÑÒÐÓÊÒÓÐ ÎÐ²ªÍÒÎÂÀÍÈÌÈ ÃÐÀÔÀÌÈ Àíîòàö³ÿ. Äîñë³äæåíî âëàñòèâîñò³ ôðàãìåíòàðíèõ ñòðóêòóð ³ âñòàíîâëåíî çâ’ÿçîê ì³æ íèìè òà ðîçì³÷åíèìè àöèêë³÷íèìè îð³ºíòîâàíèìè ãðàôàìè ç îäíèì äæåðåëîì, à òàêîæ âñòàíîâëåíî â³äïîâ³äí³ñòü êëàñ³â ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð íåðîçì³÷åíèì àöèêë³÷íèì îð³ºíòîâàíèì ãðàôàì ïåâíîãî âèäó, ÿê³ íàçèâàþòüñÿ äîïóñòèìèìè ãðàôàìè. Âèçíà÷åíî ïîíÿòòÿ ðîçì³ðíîñò³ äîïóñòèìîãî ãðàôà òà â³äïîâ³äíèõ éîìó ³çîìîðôíèõ ôðàãìåí- òàðíèõ ñòðóêòóð. Îòðèìàíî âèðàç äëÿ íèæíüî¿ îö³íêè ðîçì³ðíîñò³. Äîâåäåíî òåîðåìó ïðî âëàñòèâîñò³ äîïóñòèìèõ ãðàô³â. Ï³äðàõîâàíî ê³ëüêîñò³ ôðàã- ìåíòàðíèõ ñòðóêòóð òà êëàñ³â ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð ìàëèõ ðîçì³ðíîñòåé. Êëþ÷îâ³ ñëîâà: ôðàãìåíòàðíà ñòðóêòóðà, ÷àñòêîâî âïîðÿäêîâàíà ìíîæèíà, àöèêë³÷íèé îðãðàô, ã³ïåðêóá. ÂÑÒÓÏ Ôðàãìåíòàðí³ ñòðóêòóðè º óçàãàëüíåííÿì â³äîìèõ êîìá³íàòîðíèõ êîíñòðóê- ö³é — ìàòðî¿ä³â, ãð³äî¿ä³â, ñïàäêîâèõ ñèñòåì [1–3]. ¯õ ÷àñòî âèêîðèñòîâóþòü äëÿ ïîøóêó íàáëèæåíèõ îïòèìàëüíèõ ðîçâ’ÿçê³â íèçêè äèñêðåòíèõ îïòè- ì³çàö³éíèõ çàäà÷ [4–8], çàñòîñîâóþ÷è ôðàãìåíòàðíèé àëãîðèòì ïîáóäîâè ìàêñè- ìàëüíîãî çà âêëþ÷åííÿì ôðàãìåíòó, ÿêèé º «æàä³áíèì» àëãîðèòìîì íà ôðàãìåí- òàðí³é ñòðóêòóð³. Çã³äíî ç îçíà÷åííÿì [9, 10] ôðàãìåíòàðíà ñòðóêòóðà — öå âïî- ðÿäêîâàíà ïàðà ( , )X � , äå X — öå ñê³í÷åííà ìíîæèíà, � � { }E E En0 1, , ,� — ñ³ì’ÿ ¿¿ ï³äìíîæèí, E X i ni � �, , ,0 � , òàêå, ùî � �Ei �, Ei � �, �e Ei , E ei \ { }��. Åëåìåíòè ìíîæèíè � íàçèâàþòüñÿ äîïóñòèìèìè ôðàãìåíòàìè (ôðàã- ìåíòàìè); îäíîåëåìåíòí³ ìíîæèíè íàçèâàþòüñÿ åëåìåíòàðíèìè ôðàãìåíòàìè; ôðàãìåíò, ÿêèé íå º ï³äìíîæèíîþ æîäíîãî ³íøîãî ôðàãìåíòó, íàçèâàºòüñÿ ìàê- ñèìàëüíèì [9]. Ìíîæèíó X áóäåìî íàçèâàòè óí³âåðñàëüíîþ ìíîæèíîþ. Ç îçíà- ÷åííÿ ôðàãìåíòàðíî¿ ñòðóêòóðè ( , )X � âèïëèâàº, ùî ñ³ì’ÿ ï³äìíîæèí � çàâæäè ì³ñòèòü äîïóñòèìèé ôðàãìåíò — ïîðîæíþ ìíîæèíó (E0 �). Â³äïîâ³äíî äî îçíà÷åííÿ ôðàãìåíòàðíî¿ ñòðóêòóðè êîæåí ìàêñèìàëüíèé ôðàãìåíò ìîæíà ïîáóäóâàòè ïîñë³äîâíèì äîäàâàííÿì åëåìåíò³â, ïî÷èíàþ÷è ç ïîðîæíüî¿ ìíîæèíè, çà óìîâè, ùî íà êîæíîìó êðîö³ ïîáóäîâàíà ìíîæèíà º äî- ïóñòèìèì ôðàãìåíòîì. Òàêèé àëãîðèòì íàçèâàºòüñÿ ôðàãìåíòàðíèì. Ðåçóëüòàò ðîáîòè ôðàãìåíòàðíîãî àëãîðèòìó âèçíà÷àþòü çàäàíèì ë³í³éíèì ïîðÿäêîì íà óí³âåðñàëüí³é ìíîæèí³ X . Òàêèì ÷èíîì, áóäü-ÿêèé ìàêñèìàëüíèé ôðàãìåíò ìîæíà îïèñàòè äåÿêîþ ïåðåñòàíîâêîþ åëåìåíò³â ç X . Íåõàé A ��, x X� . Óìîâà, çà ÿêî¿ A x� �{ } �, íàçèâàºòüñÿ óìîâîþ ïðèºäíàííÿ åëåìåíòà x. Çàçíà÷èìî, ùî ôðàãìåíòàðíèé àëãîðèòì º ñâîºð³äíèì óçàãàëüíåííÿì ïîíÿòòÿ æàä³áíîãî àëãîðèòìó. Ïîêàçàíî ùî, ÿêùî ÷àñ, íåîáõ³äíèé äëÿ ïåðåâ³ðêè óìîâè ïðèºäíàííÿ, îáìåæå- íèé ïîë³íîìîì ñòåïåíÿ k , òîáòî ñòàíîâèòü O nk( ), òîä³ ÷àñîâà ñêëàäí³ñòü öüîãî ôðàãìåíòàðíîãî àëãîðèòìó ñòàíîâèòü O nk( )� 2 , äå n — ê³ëüê³ñòü åëåìåíò³â óí³âåð- ñàëüíî¿ ìíîæèíè. Òàêèì ÷èíîì, ÿêùî ³ñíóº àëãîðèòì ïîë³íîì³àëüíî¿ ñêëàäíîñò³ çà ê³ëüê³ñòþ åëåìåíò³â óí³âåðñàëüíî¿ ìíîæèíè äëÿ ïåðåâ³ðêè óìîâè ïðèºäíàííÿ, òîä³ çàäà÷ó ïîáóäîâè ìàêñèìàëüíîãî ôðàãìåíòà ðîçâ’ÿçóþòü çà ïîë³íîì³àëüíèé ÷àñ. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 163 © Î.Â. Êðèâöóí, 2019 ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×² Îçíà÷åííÿ 1. Ï³äìíîæèíè A B, ìíîæèíè X , äëÿ ÿêèõ B A x� \ { }, äå x X� , áóäåìî íàçèâàòè ïîñë³äîâíèìè ³ áóäåìî ãîâîðèòè, ùî B ñë³äóº çà A. Îçíà÷åííÿ 2. Ðîçì³òêà îð³ºíòîâàíîãî ãðàôà — öå òàêà â³äïîâ³äí³ñòü ì³æ âåð- øèíàìè ãðàôà ³ ï³äìíîæèíàìè ìíîæèíè X , çà ÿêî¿ äæåðåëó â³äïîâ³äàº ïîðîæíÿ ìíîæèíà, à ñóì³æí³ âåðøèíè â³äïîâ³äàþòü ïîñë³äîâíèì ï³äìíîæèíàì, äî òîãî æ ï³äìíîæèíà ïî÷àòêîâî¿ âåðøèíè äóãè ñë³äóº çà ï³äìíîæèíîþ ê³íöåâî¿ âåðøèíè. Áóäü-ÿêà ôðàãìåíòàðíà ñòðóêòóðà ïîðîäæóº äåÿêó ðîçì³òêó îðãðàôà. Ïðèêëàäè òàêèõ îðãðàô³â íàâåäåíî íà ðèñ. 1. Îðãðàô, çîáðàæåíèé íà ðèñ. 1, á, ïîðîäæåíèé ôðàãìåíòàðíîþ ñòðóêòóðîþ ³ç ñ³ì’ºþ � � �{ { } { } { } { }}, , , , , , ,x x x x x x x1 3 1 3 1 2 3 . Àëå íå ìîæíà ñòâåðäæóâàòè, ùî áóäü-ÿêà ðîçì³òêà â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³. Ðîçì³÷åí³ îðãðàôè íà ðèñ. 2, à, á íå â³äïîâ³äàþòü æîäí³é ôðàãìåíòàðí³é ñòðóê- òóð³. Çì³íèìî ðîçì³òêó öèõ îðãðàô³â òàê, ùîá îòðèìàòè ³çîìîðôí³ ¿ì îðãðàôè, ÿê³ â³äïîâ³äàþòü ôðàãìåíòàðíèì ñòðóêòóðàì ³ç ñ³ì’ÿìè � �� { { } { } { }, , , , ,x x x x1 2 1 3 { }}x x x1 2 3, , äëÿ îðãðàôà íà ðèñ. 3, à òà �'' � �{ { } { } { } { }}, , , , , , ,x x x x x x x5 3 1 3 1 2 3 äëÿ îðãðàôà íà ðèñ. 3, á. Ðîçãëÿíåìî òåïåð òàêó çàäà÷ó: ÿê³ ãðàôè ³ ÿê³ ðîçì³òêè ìîæóòü îïèñóâàòè ôðàãìåíòàðí³ ñòðóêòóðè? Áóäåìî íàçèâàòè ³çîìîðôíèìè ôðàãìåíòàðí³ ñòðóêòóðè, ùî îïèñóþòüñÿ ³çî- ìîðôíèìè îðãðàôàìè. ÓÌÎÂÈ Â²ÄÏÎÂ²ÄÍÎÑÒ² ÎÐÃÐÀÔ²Â ÔÐÀÃÌÅÍÒÀÐÍÈÌ ÑÒÐÓÊÒÓÐÀÌ Îçíà÷åííÿ 3. Äîïóñòèìèì ãðàôîì íàçèâàºòüñÿ íåðîçì³÷åíèé çâ’ÿçíèé îðãðàô ç îäíèì äæåðåëîì, ÿêèé â³äïîâ³äàº äåÿêîìó êëàñó F ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð òà- êèì ÷èíîì, ùî éîãî ñóì³æí³ âåðøèíè â³äïîâ³äàþòü ïîñë³äîâíèì ôðàãìåíòàì öèõ ñòðóêòóð, äî òîãî æ íàïðÿì äóãè çá³ãàºòüñÿ ç íàïðÿìîì íàñòóïíîñò³ ôðàãìåíò³â. 164 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 {x1, x2, x3} {x2} {x2, x3} {x1, x2, x3}{x1, x3, x6, x8} {x1, x3, x6} {x1, x3, x5} {x1, x3} {x1} {x1, x3} {x3} {x1} � {x1} {x1, x3} � � Ðèñ. 1. Ðîçì³÷åí³ îðãðàôè, ùî çîáðàæàþòü ôðàãìåíòàðí³ ñòðóêòóðè à á â {x1}{x1} � � {x3} {x3} {x1, x3} {x1, x3} {x1, x2, x3} {x1, x2, x3} Ðèñ. 2. ²çîìîðôí³ ðîçì³÷åí³ àöèêë³÷í³ îðãðàôè, îòðèìàí³ ç ãðàôà íà ðèñ. 1, á, ùî íå â³äïî- â³äàþòü ôðàãìåíòàðíèì ñòðóêòóðàì {x1, x3} {x5}{x1} � � {x2} {x3} {x1, x3} {x1, x2, x3} {x1, x2, x3} Ðèñ. 3. ²çîìîðôí³ ðîçì³÷åí³ àöèêë³÷í³ îðãðàôè, ùî â³äïîâ³äàþòü ³çîìîðôíèì ôðàãìåíòàðíèì ñòðóêòóðàì áà à á Ëåìà 1. ßêùî íåðîçì³÷åíèé îðãðàô ç îäíèì äæåðåëîì º äîïóñòèìèì, òîä³: 1) äæåðåëî º êîðåíåâîþ âåðøèíîþ; 2) îðãðàô º àöèêë³÷íèì; 3) äëÿ áóäü-ÿêî¿ âåðøèíè � i îðãðàôà âñ³ îð³ºíòîâàí³ øëÿõè â³ä êîðåíÿ äî ö³º¿ âåð- øèíè ìàþòü îäíàêîâó äîâæèíó li , ÿêà º íîìåðîì ÿðóñó, ÿêîìó íàëåæèòü âåðøèíà � i ; 4) íàï³âñòåï³íü çàõîäó áóäü-ÿêî¿ âåðøèíè íå ïåðåâåðøóº íîìåð ÿðóñó ö³º¿ âåðøèíè. Äîâåäåííÿ. Áåç âòðàòè çàãàëüíîñò³ ìîæíà ââàæàòè, ùî äæåðåëî ãðàôà â³äïîâ³äàº ïîðîæí³é ìíîæèí³. Îñê³ëüêè äæåðåëî ºäèíå, òî ³ñíóº øëÿõ â³ä äæåðåëà äî êîæíî¿ âåðøèíè, òîáòî äæåðåëî º êîðåíåâîþ âåðøèíîþ. Äîäàâàííÿ äóãè äî âåð- øèíè â³äïîâ³äàº äîäàâàííþ îäíîãî åëåìåíòà äî â³äïîâ³äíîãî ö³é âåðøèí³ ôðàãìåí- òà ³ îòðèìàííþ ïîñë³äîâíîãî ôðàãìåíòà. Òàêèì ÷èíîì, ê³ëüê³ñòü äóã ó áóäü-ÿêîìó øëÿõó â³ä êîðåíÿ äî çàäàíî¿ âåðøèíè çàâæäè îäíàêîâà. Çâ³äñè âèïëèâàº, ùî äîâæè- íà øëÿõó â³ä êîðåíÿ äî çàäàíî¿ âåðøèíè âèçíà÷àº ïîòóæí³ñòü ôðàãìåíòà ö³º¿ âåðøè- íè. Äóãè çàâæäè íàïðÿìëåí³ çà çðîñòàííÿì ïîòóæíîñòåé ôðàãìåíò³â, òîáòî íå ³ñíóº çâîðîòíîãî øëÿõó äî áóäü-ÿêî¿ âåðøèíè. Öå îçíà÷àº, ùî ãðàô º àöèêë³÷íèì. Äîâåäåìî ÷åòâåðòå òâåðäæåííÿ. Íåõàé âåðøèí³ � j â³äïîâ³äàº ôðàãìåíò E x xj j jk � { } 1 , ..., . Îñê³ëüêè äëÿ áóäü-ÿêî¿ ïîïåðåäíüî¿ ñóì³æíî¿ âåðøèíè øëÿõ â³ä êîðåíÿ íà îäèíèöþ ìåíøèé, òî âîíà â³äïîâ³äàº ôðàãìåíòó, ïîòóæí³ñòü ÿêîãî íà îäèíèöþ ìåíøà ³ ÿêèé ìîæíà îòðèìàòè âèëó÷åííÿì ³ç E j äåÿêîãî åëåìåíòà. ²ñíóº k ñïîñîá³â âèëó÷åííÿ îäíîãî åëåìåíòà ³ç ìíîæèíè ïîòóæí³ñòþ k. Òîìó ê³ëüê³ñòü ïîïåðåäí³õ ñóì³æíèõ âåðøèí íå ìîæå áóòè á³ëüøîþ, í³æ k, òîáòî íàï³âñòåï³íü çàõîäó âåðøèíè � j ìàº áóòè íå á³ëüøîþ, í³æ k . � Áóäåìî íàçèâàòè äàë³ íåðîçì³÷åíèé îðãðàô ç îäíèì äæåðåëîì, ÿêå º êîðå- íåì, íåðîçì³÷åíèì îðãðàôîì ç îäí³ºþ êîðåíåâîþ âåðøèíîþ. Íà ðèñ. 4 çîáðàæåíî íåðîçì³÷åí³ àöèêë³÷í³ îðãðàôè ç îäí³ºþ êîðåíåâîþ âåðøèíîþ, ÿê³ íå º äîïóñòèìèìè. Îðãðàô (äèâ. ðèñ. 4, à) íå çàäîâîëüíÿº ïåðø³é óìîâ³ ëåìè 1, òîìó ùî äâà øëÿ- õè â³ä êîðåíÿ äî ñòîêó ãðàôà ìàþòü ð³çíó äîâæèíó. Îðãðàô (äèâ. ðèñ. 4, á) íå â³äïîâ³äàº äðóã³é óìîâ³ ëåìè 1 — óñ³ øëÿõè â³ä êîðåíÿ äî ñòîêó îðãðàôà ìà- þòü äîâæèíó 2, à íàï³âñòåï³íü çàõîäó ñòîêó äîð³âíþº 3, òîáòî º á³ëüøîþ í³æ äîâæèíà øëÿõ³â. Ðîçãëÿíåìî ñê³í÷åííó ìíîæèíó X x x xm� { }1 2, , ,� , ïîòóæí³ñòü ÿêî¿ \| \|X m� . Êîæí³é ï³äìíîæèí³ A X� ìîæíà ïîñòàâèòè ó â³äïîâ³äí³ñòü òî÷êó â ïðîñòîð³ ( , , , )� � �m m mR� �1 1� , äå � i i i x A x A � � � � � � 1 0 , , , . ÿêùî ÿêùî Áóäåìî ðîçãëÿäàòè òî÷êè { }( , )� � �m m� � �1 1� ÿê âåðøèíè îð³ºíòîâàíîãî ãðàôà, ïðè÷îìó ç âåðøèíè, ùî â³äïîâ³äàº ìíîæèí³ A1, âèõîäèòü äóãà äî âåðøè- íè, ùî â³äïîâ³äàº ìíîæèí³ A2 , òîä³ ³ ò³ëüêè òîä³, êîëè A A1 2� òà \| \ \|A A2 1 1� . Äâ³éêîâèé m-âèì³ðíèé îð³ºíòîâàíèé êóá, ùî âèçíà÷àº âïîðÿäêîâàíèé áóëå- àí, º ä³àãðàìîþ Ãàññå [11]. Â³í ìàº îäíå äæåðåëî (êîðåíåâó âåðøèíó) ³ îäèí ñòîê. Íà ðèñ. 5 çîáðàæåíî îð³ºíòîâàí³ ã³ïåðêóáè ðîçì³ðíîñòåé 2 ³ 3 ðîçì³÷åí³ òàê, ùî â³äïîâ³äàþòü ä³àãðàìàì Ãàññå. Íåîáõ³äíó óìîâó òîãî, ùî íåðîçì³÷åíèé àöèêë³÷íèé îðãðàô ç îäí³ºþ êîðå- íåâîþ âåðøèíîþ º äîïóñòèìèì, íàâîäèòü òàêå òâåðäæåííÿ. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 165 Ðèñ. 4. Íåðîçì³÷åí³ àöèêë³÷í³ îðãðàôè, ÿê³ íå â³äïîâ³äàþòü ôðàãìåíòàðíèì ñòðóêòóðàì à á Ëåìà 2. Äëÿ òîãî ùîá íåðîçì³÷åíèé àöèêë³÷íèé îðãðàô ç îäí³ºþ êîðåíåâîþ âåðøèíîþ áóâ äîïóñòèìèì, íåîáõ³äíî, ùîá â³í áóâ ï³äãðàôîì äåÿêîãî îð³ºíòî- âàíîãî ã³ïåðêóáà. Äîâåäåííÿ. Ôðàãìåíòàðí³ ñòðóêòóðè º ÷àñòêîâî óïîðÿäêîâàíèìè ìíîæèíà- ìè, îòæå, ìîæóòü áóòè çîáðàæåí³ ä³àãðàìàìè Ãàññå, ÿê³, ó ñâîþ ÷åðãó, º ï³äãðà- ôàìè ã³ïåðêóá³â. Îòæå, àâòîìàòè÷íî âèêîíóþòüñÿ óìîâè ëåìè 1. � Äàë³ ï³ä ï³äãðàôîì ã³ïåðêóáà áóäåìî ðîçóì³òè îðãðàô, äëÿ ÿêîãî âèêî- íóºòüñÿ óìîâà ëåìè 2. Äîïóñòèìèé ãðàô, ùî â³äïîâ³äàº êëàñó F ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóê- òóð ( , )� X , âèçíà÷àº ñòðóêòóðó ñ³ì’¿ ï³äìíîæèí � � { }E E E En0 1 2, , , ,� , äå E Xi � , E0 � �. Âî÷åâèäü, äëÿ áóäü-ÿêî¿ ôðàãìåíòàðíî¿ ñòðóêòóðè ç F âèêî- íóºòüñÿ íåð³âí³ñòü \| \|X E i n i� �1� . Òîä³, ï³äáèðàþ÷è â³äïîâ³äíó ðîçì³òêó, çà äî- ïóñòèìèì ãðàôîì âèçíà÷èìî ì³í³ìàëüíó ïîòóæí³ñòü óí³âåðñàëüíèõ ìíîæèí öèõ ôðàãìåíòàðíèõ ñòðóêòóð, ÿêà äîð³âíþº i n iE �1� . Îçíà÷åííÿ 4. Ì³í³ìàëüíà ïîòóæí³ñòü N óí³âåðñàëüíèõ ìíîæèí ôðàãìåíòàðíèõ ñòðóêòóð ç êëàñó F íàçèâàºòüñÿ ðîçì³ðí³ñòþ äîïóñòèìîãî ãðàôà òà â³äïîâ³äíèõ éîìó ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð: N X E F i n i� � � \| \| minmin 1� . Íàïðèêëàä, ìàºìî i iE x x x � � � 1 4 1 2 3 3� \| , , \|{ } äëÿ ãðàôà íà ðèñ. 3, à, äëÿ ³çî- ìîðôíîãî éîìó ãðàôà íà ðèñ. 3, á ìàºìî i iE x x x x � � � 1 4 1 2 3 5 4� \| , , , \|{ } , òîáòî ðîçì³ðí³ñòü â³äïîâ³äíîãî íåðîçì³÷åíîãî äîïóñòèìîãî ãðàôà N � 3. Âî÷åâèäü, ðîçì³ðí³ñòü íå ìîæå áóòè ìåíøîþ çà äîâæèíó ìàêñèìàëüíîãî øëÿõó ó ãðàô³ òà íå ìîæå áóòè ìåíøîþ çà íàï³âñòåï³íü âèõîäó êîðåíåâî¿ âåðøèíè. Óçàãàëüíåí- íÿì öüîãî òâåðäæåííÿ º íåð³âí³ñòü N l p i i i� �max ( ), äå li — íîìåð ÿðóñó i-¿ âåðøèíè, pi — ¿¿ íàï³âñòåï³íü âèõîäó. Ïðèêëàäè ãðàô³â ç âèçíà÷åíèìè ðîçì³ðíîñòÿìè N � 5 íà ðèñ. 1, à òà N � 3 íà ðèñ. 1, á, â ³ íà ðèñ. 2, 3. Áóäåìî íàçèâàòè ã³ïåðêóá ðîçì³ðíîñò³ N äîñòàòí³ì ã³ïåðêóáîì äëÿ çàäàíîãî äîïóñòèìîãî ãðàôà, à ã³ïåðêóá ì³í³ìàëüíî¿ ðîçì³ðíîñò³, ï³äãðàôîì ÿêîãî º öåé äî- ïóñòèìèé ãðàô, íåîáõ³äíèì ã³ïåðêóáîì. Âî÷åâèäü, ðîçì³ðí³ñòü íåîáõ³äíîãî ã³ïåðêó- áà äîïóñòèìîãî ãðàôà º íèæíüîþ îö³íêîþ ðîçì³ðíîñò³ éîãî äîñòàòíüîãî ã³ïåðêóáà. 166 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 (0, 1, 1) (1, 1, 1) (1, 1, 0) (1, 0, 0)(0, 0, 0) (0, 0, 1) (0,1,0) (1, 0, 1) x y z (1, 0)(0, 0) (0, 1) (1, 1) x y Ðèñ. 5. Ä³àãðàìè Ãàññå íà ã³ïåðêóáàõ ðîçì³ðíîñòåé 2 (à) òà 3 (á) à á Ðîçãëÿíåìî ïðèêëàä, êîëè íåîáõ³äíèé ³ äîñòàòí³é ã³ïåðêóáè äîïóñòèìîãî ãðàôà íå çá³ãàþòüñÿ, òîáòî ìàþòü ð³çí³ ðîçì³ðíîñò³. Îðãðàô íà ðèñ. 6, à º ï³äãðà- ôîì êâàäðàòà (ã³ïåðêóáà ðîçì³ðíîñò³ 2), àëå ç äâîõ åëåìåíò³â íå ìîæíà ïîáóäóâàòè äî- ïóñòèìó ðîçì³òêó äëÿ öüîãî ãðàôà, à ç òðüîõ åëåìåíò³â — ìîæíà. Ðîçì³òêà îðãðà- ôà íà ðèñ. 6, á ³ëþñòðóº öå òâåðäæåííÿ. Òîìó ðîçì³ðí³ñòü äîñòàòíüîãî ã³ïåðêóáà äëÿ îðãðàôà íà ðèñ. 6, à äîð³âíþº 3, òîáòî äîñòàòí³ì ã³ïåðêóáîì äëÿ â³äïîâ³äíîãî êëàñó ôðàãìåíòàðíèõ ñòðóêòóð º êóá. ßê áóëî ïîêàçàíî ðàí³øå, íå áóäü-ÿêà ðîçì³òêà äîïóñòèìîãî ãðàôà óòâîðþº ãðàô, ùî â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³. Ðîçãëÿíåìî óìîâè, çà ÿêèõ ðîçì³÷åíèé ãðàô îïèñóº äåÿêó ôðàãìåíòàðíó ñòðóêòóðó. Íàñòóïíà òåîðåìà íàäàº êðèòåð³é òîãî, ùî ðîçì³÷åíèé àöèêë³÷íèé îðãðàô ç îäí³ºþ êîðåíåâîþ âåðøèíîþ â³äïîâ³äàº äåÿê³é ôðàãìåíòàðí³é ñòðóêòóð³. Òåîðåìà 1. Ðîçì³÷åíèé îðãðàô ç îäíèì äæåðåëîì îäíîçíà÷íî çàäàº ôðàã- ìåíòàðíó ñòðóêòóðó ( , )X � , ÿêùî âèêîíóþòüñÿ òàê³ óìîâè: 1) äæåðåëî â³äïîâ³äàº ïîðîæí³é ìíîæèí³; 2) áóäü-ÿê³ ñóì³æí³ âåðøèíè â³äïîâ³äàþòü ïîñë³äîâíèì ôðàãìåíòàì ³ íà- ïðÿì äóãè çá³ãàºòüñÿ ç íàïðÿìîì íàñòóïíîñò³ ôðàãìåíò³â; 3) áóäü-ÿê³ äâ³ âåðøèíè ãðàôà, ùî â³äïîâ³äàþòü ïîñë³äîâíèì ôðàãìåíòàì, º ñóì³æíèìè, ³ íàïðÿì äóãè çá³ãàºòüñÿ ç íàïðÿìîì íàñòóïíîñò³ ôðàãìåíò³â. Äîâåäåííÿ. Ïåðøà óìîâà âèïëèâàº ç òîãî, ùî ñ³ì’ÿ � ôðàãìåíòàðíî¿ ñòðóê- òóðè ( , )X � çàâæäè ì³ñòèòü ïîðîæíþ ìíîæèíó. Äðóãà óìîâà (íåîáõ³äíà): ÿêùî âåðøèíè � i , � j ñóì³æí³, òî öå îçíà÷àº, ùî ³ñíóº òàêèé åëåìåíò e X e Ei� �, , ùî E E ej i� �{ }, òîáòî E Ei j, — ïîñë³äîâí³ ôðàãìåíòè. Äîâåäåìî òðåòþ óìîâó (äîñòàòíþ): ÿêùî âåðøèíè � i , � j â³äïîâ³äàþòü ïîñë³äîâíèì ôðàãìåíòàì E Ei j, (Ei ��, E j ��), òîä³ ³ñíóº òàêèé åëåìåíò e E j� , ùî E e Ej i\ { } � , òîáòî çà îçíà÷åííÿì ôðàãìåíòàðíî¿ ñòðóêòóðè âåðøèíè � i , � j ìàþòü áóòè ç’ºäíàí³ äóãîþ. � Áóäåìî íàçèâàòè äîïóñòèìîþ ðîçì³òêó îðãðàôà ç îäíèì äæåðåëîì, ÿêà çàäî- âîëüíÿº óìîâè òåîðåìè 1. Íàâåäåìî î÷åâèäíó òåîðåìó, ùî ôîðìóëþº äîñòàòíþ óìîâó, çà ÿêî¿ íåðîçì³÷å- íèé àöèêë³÷íèé îðãðàô ç îäí³ºþ êîðåíåâîþ âåðøèíîþ º äîïóñòèìèì ãðàôîì. Òåîðåìà 2. ßêùî äëÿ íåðîçì³÷åíîãî îðãðàôà ç îäíèì äæåðåëîì ìîæíà ïî- áóäóâàòè äîïóñòèìó ðîçì³òêó, òîä³ öåé îðãðàô º äîïóñòèìèì ãðàôîì. Íåõàé º äîïóñòèìèé ãðàô, äëÿ ÿêîãî ïîáóäîâàíî äîïóñòèìó ðîçì³òêó. ßêùî äëÿ öüîãî âèêîíóºòüñÿ i n iE N � � 1� , òîä³ áóäåìî ãîâîðèòè, ùî òàêà ðîçì³òêà ì³í³ìàëüíà. ßêùî ³íäåêñè åëåìåíò³â óí³âåðñàëüíî¿ ìíîæèíè óòâîðþþòü ïîñë³äîâí³ñòü 1 2, , ,� m, m N� , íàçâåìî òàêó ðîçì³òêó íàòóðàëüíîþ. ßêùî íàéá³ëüøèé ³íäåêñ m åëåìåíò³â óí³âåðñàëüíî¿ ìíîæèíè äîð³âíþº ðîçì³ðíîñò³ N m N( )� äîïóñòèìîãî ãðàôà, òîä³ ðîçì³òêà º ì³í³ìàëüíîþ, íàòóðàëüíîþ. Íàïðèêëàä, ðîçì³òêè äîïóñòèìèõ ãðàô³â íà ðèñ. 2 íå º äîïóñòèìèìè; íà ðèñ. 1, à ðîçì³òêà ì³í³ìàëüíà, àëå íå º íàòóðàëüíîþ; íà ðèñ. 1, á, â, ðèñ. 3, à òà ðèñ. 6, á ðîçì³òêè íàòóðàëüí³, ì³í³ìàëüí³; ðîçì³òêà íà ðèñ. 3, á íå º í³ íàòóðàëüíîþ, í³ ì³í³ìàëüíîþ, àëå, ÿêùî åëåìåíò x5 çàì³íèòè x4 , âîíà ñòàíå íàòóðàëüíîþ. Óñ³ ï³äãðàôè ã³ïåðêóá³â ðîçì³ðí³ñòþ ìåíøå 3 (òîáòî òî÷êè, â³äð³çêè ³ êâàä- ðàòè) º äîïóñòèìèìè ãðàôàìè, â öüîìó ëåãêî ïåðåêîíàòèñÿ. Íà ðèñ. 7 çîáðàæåíî âñ³ òàê³ ï³äãðàôè. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 167 {x1, x3} {x2}{x1} � Ðèñ. 6. Íåðîçì³÷åíèé (à) òà ðîçì³÷åíèé (á) îðãðàôè, ùî â³äïîâ³äàþòü êëàñó ôðàãìåí- òàðíèõ ñòðóêòóð ðîçì³ðíîñò³ 3 à á Ãðàô íà ðèñ. 7, ´, õî÷à ³ º ï³äãðàôîì êâàäðàòà, â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³ ðîçì³ðí³ñò³ 3. ßêùî äâ³ éîãî âåðøèíè, ñóì³æí³ ç êîðåíåâîþ, ïîçíà÷èòè { }x1 òà { }x2 , òîä³ îñòàííÿ âåðøèíà ìàº áóòè ïîçíà÷åíà ìíîæèíîþ, ÿêà ñêëà- äàºòüñÿ ç äâîõ åëåìåíò³â: x1 ³ áóäü-ÿêîãî, îêð³ì x2 . Ðîçãëÿíåìî êâàäðàò íà ðèñ. 7, ä: ÿêùî äâ³ éîãî âåðøèíè, ñóì³æí³ ç êîðåíåâîþ, ïîçíà÷èòè { }x1 òà { }x2 , òîä³ ðîçì³òêà ñòîêó âèçíà÷àºòüñÿ îäíîçíà÷íî { }x x1 2, , òîáòî ðîçì³òêè âåðøèí, ùî íàëåæàòü øëÿõàì, ÿê³ âåäóòü äî îäí³º¿ âåðøèíè, îáìåæåí³ ìíîæèíîþ ö³º¿ âåðøèíè (äèâ. ðèñ. 1, â). Çâ³äñè âèïëèâàº òàêå òâåðäæåííÿ. Ëåìà 3. Áóäü-ÿêå îð³ºíòîâàíå äåðåâî º äîïóñòèìèì ãðàôîì. Äîâåäåííÿ. Îñê³ëüêè îð³ºíòîâàíå äåðåâî íå ìàº âåðøèí ç íàï³âñòåïåíÿìè çàõîäó á³ëüøå 1, òî ðîçì³òêè âåðøèí éîãî ð³çíèõ ã³ëîê íå îáìåæåí³ í³ÿêèìè ìíî- æèíàìè, ³ áóäóþ÷è ¿õ, ìîæíà äîäàâàòè ñê³ëüêè çàâãîäíî åëåìåíò³â äî óí³âåð- ñàëüíî¿ ìíîæèíè. Îòæå, çàâæäè ìîæíà îòðèìàòè äîïóñòèìó ðîçì³òêó. Êð³ì òîãî, öå îçíà÷àº, ùî îð³ºíòîâàí³ äåðåâà º ï³äãðàôàìè îð³ºíòîâàíèõ ã³ïåðêóá³â. � ÐÅÇÓËÜÒÀÒÈ ÄËß ÌÀËÈÕ ÐÎÇÌ²ÐÍÎÑÒÅÉ Çà ðèñ. 7 ìîæíà ï³äðàõóâàòè ê³ëüê³ñòü ³çîìîðôíèõ òà íå³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð äëÿ ðîçì³ðíîñòåé 0–2. Ðåçóëüòàò íàâåäåíî ó òàáë. 1. ²ñíóº îäèí äîïóñòè- ìèé ãðàô (äèâ. ðèñ. 7, à) ðîçì³ðíîñò³ 0 — òî÷êà, ÿêà â³äïîâ³äàº ºäèí³é ôðàãìåí- òàðí³é ñòðóêòóð³ ( , )� �{ } . Òàêîæ ³ñíóº îäèí äîïóñòèìèé ãðàô (äèâ. ðèñ. 7, á) ðîçì³ðíîñò³ 1. Îð³ºíòîâàíèé êâàäðàò º äîñòàòí³ì ã³ïåðêóáîì äëÿ òðüîõ äîïóñòèìèõ ãðàô³â (äèâ. ðèñ. 7 â, ã, ä), òîáòî ³ñíóº òðè íå³çîìîðôí³ ôðàãìåíòàðí³ ñòðóêòóðè. Âèïàäêè ç ðîçì³ðíîñòÿìè 0 (X � �) ³ 1 (X x� { }1 ) — òðèâ³àëüí³, äëÿ òàêèõ äî- ïóñòèìèõ ãðàô³â ìîæëèâà ò³ëüêè îäíà äîïóñòèìà ðîçì³òêà. Òîìó ê³ëüê³ñòü ïîïàðíî íå³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð ³ çàãàëüíà (ðàçîì ç ³çîìîðôíèìè) ê³ëüê³ñòü ôðàãìåíòàðíèõ ñòðóêòóð öèõ ðîçì³ðíîñòåé îäíàêîâ³. Çàãàëüíà ê³ëüê³ñòü ôðàãìåíòàð- íèõ ñòðóêòóð ðîçì³ðíîñò³ 2 (X x x� { }1 2, ) äîð³âíþº ÷îòèðüîì, òîáòî íà îäèíèöþ á³ëüøà í³æ ê³ëüê³ñòü ïîïàðíî íå³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð. Öå ïîÿñíþºòüñÿ òèì, ùî ãðàô íà ðèñ. 7, ã ìîæíà ðîçì³òèòè äâîìà ñïîñîáàìè, ÿê³ çîáðàæåíî íà ðèñ. 8. Çàãàëüí³ ê³ëüêîñò³ ôðàãìåíòàðíèõ ñòðóêòóð ðîçì³ðíîñòåé 3 ³ 4 áóëî ï³äðàõîâàíî çà äîïîìîãîþ êîìï’þòåðíî¿ ïðîãðàìè. Ê³ëüê³ñòü ïîïàðíî íå³çîìîðôíèõ ôðàãìåíòàð- íèõ ñòðóêòóð ðîçì³ðíîñò³ 4 äîòåïåð íå ïîðàõîâàíî. Íà ðèñ. 9 çîáðàæåíî ï³äãðàô ã³ïåðêóáà ðîçì³ðíîñò³ 3, òîáòî êóáà, ÿêèé íå º äîïóñòèìèì ãðàôîì. Ïîçíà÷èìî òðè âåðøèíè öüîãî ãðàôà, ÿê³ ñóì³æí³ ç êîðåíå- âîþ: { }x1 , { }x2 òà { }x3 . Ñòîê êóáà ìàº áóòè ïîçíà÷åíèé ìíîæèíîþ ïî- òóæíîñò³ 3. Îñê³ëüêè ³ñíóþòü øëÿõè äî ñòî- êó, ÿê³ ïðîõîäÿòü ÷åðåç òðè âæå ïî- çíà÷åí³ âåðøèíè, ðîçì³òêà ñòîêó ìàº áóòè { }x x x1 2 3, , . Öÿ îáñòàâèíà âèçíà- ÷àº ðîçì³òêè ðåøòè âåðøèí òàê, ÿê ïîêàçàíî íà ðèñ. 9. Ïîáóäîâàíà ðîçì³òêà çàäîâîëüíÿº äðóãó óìîâó òå- îðåìè 1, àëå íå çàäîâîëüíÿº òðåòþ óìîâó ö³º¿ òåîðåìè, îñê³ëüêè íå ³ñíóº äóã ì³æ âåðøèíàìè { }x2 , { }x x2 3, òà 168 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 Ðèñ. 7. Äîïóñòèì³ ãðàôè ðîçì³ðíîñòåé 0 (à), 1 (á), 2 (â, ã, ä) òà 3 (´) à á ãâ ´ ä Ò à á ë è ö ÿ 1. Ê³ëüê³ñòü ôðàãìåíòàðíèõ ñòðóêòóð ìàëèõ ðîçì³ðíîñòåé Ðîçì³ðí³ñòü ôðàãìåíòàðíèõ ñòðóêòóð, N Ê³ëüê³ñòü ôðàãìåíòàðíèõ ñòðóêòóð íå³çîìîðôíèõ ðàçîì ç ³çîìðîôíèìè 0 1 1 1 1 1 2 3 4 3 19 66 4 — 11898 ì³æ âåðøèíàìè { }x1 , { }x x1 2, , ÿê³ ïîïàðíî â³äïîâ³äàþòü ïîñë³äîâíèì ôðàãìåíòàì. Óñ³ ðîçì³òêè, ùî çàäîâîëüíÿþòü äðóãó óìîâó òåî- ðåìè 1, áóäóòü åêâ³âàëåíòí³ ïîáóäîâàí³é ç òî÷í³ñòþ äî ïîçíà÷åííÿ âåðøèí, ñóì³æíèõ ç êîðåíåâîþ, çâ³äñè âèïëèâàº, ùî äëÿ öüîãî ãðàôà íåìîæëèâî ïîáóäóâàòè äîïóñòèìó ðîçì³òêó. Îòæå, öåé ãðàô íå º äîïóñòèìèì. Áóäåìî íàçèâàòè âõ³äíèì ï³äãðàôîì âåðøèíè � ï³äãðàôà ã³ïåðêóáà òàêèé ãðàô, ùî ñêëàäàºòüñÿ ò³ëüêè ç óñ³õ øëÿõ³â â³ä êî- ðåíÿ äî ö³º¿ âåðøèíè � , à âèõ³äíèì ï³äãðà- ôîì âåðøèíè � — ãðàô, ÿêèé ñêëàäàºòüñÿ ò³ëüêè ç óñ³õ øëÿõ³â, ùî âèõîäÿòü ³ç ö³º¿ âåð- øèíè. Ï³äãðàô çàäàíîãî ï³äãðàôà ã³ïåðêóáà, ÿêèé ñêëàäàºòüñÿ ò³ëüêè ç óñ³õ øëÿõ³â â³ä êîðå- íåâî¿ âåðøèíè, ùî ìàþòü äîâæèíó l, íàçâåìî ï³äãðàôîì l-ãî ÿðóñó. Ñôîðìóëþºìî òàê³ âëàñòèâîñò³ äîïóñ- òèìèõ ãðàô³â. Òåîðåìà 3. ßêùî ãðàô º äîïóñòèìèì, òîä³: 1) óñ³ éîãî âõ³äí³ ï³äãðàôè º äîïóñòèìèìè; 2) óñ³ éîãî âèõ³äí³ ï³äãðàôè º äîïóñòè- ìèìè; 3) ï³äãðàô êîæíîãî éîãî ÿðóñó º äîïóñòèìèì. Äîâåäåííÿ. Ðîçãëÿíåìî ïåðøå òâåðäæåííÿ: âõ³äíèé ï³äãðàô âåðøèíè � j â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³, ùî óòâîðþºòüñÿ ç ïî÷àòêîâî¿ âèëó÷åííÿì âñ³õ ôðàãìåíò³â, ÿê³ íå º ï³äìíîæèíàìè ôðàãìåíòà E j âåðøèíè � j . Îòæå, â³í º äîïóñòèìèì. Ðîçãëÿíåìî äðóãå òâåðäæåííÿ: âèõ³äíèé ï³äãðàô âåðøèíè � j â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³, ÿêà óòâîðþºòüñÿ ç ïî÷àòêîâî¿ øëÿõîì ðåäóêö³¿, òîáòî ñïî÷àòêó âèëó÷àþòü âñ³ ôðàãìåíòè, ÿê³ íå ì³ñòÿòü ìíîæèíè E j . Ïîò³ì k ôðàã- ìåíò³â, ùî çàëèøèëèñÿ, ïåðåòâîðþþòüñÿ òàêèì ÷èíîì: E E Ei i j� \ , i k�1, . Îòæå, âèõ³äíèé ï³äãðàô âåðøèíè � j º äîïóñòèìèì. Äîâåäåìî òðåòº òâåðäæåííÿ: ï³äãðàô l-ãî ÿðóñó â³äïîâ³äàº ôðàãìåíòàðí³é ñòðóêòóð³, ÿêà óòâîðþºòüñÿ ç ïî÷àòêîâî¿ âèäàëåííÿì âñ³õ ôðàãìåíò³â ïîòóæíîñò³ á³ëüøå í³æ l. Îòæå, â³í º äîïóñòèìèì. � Íàñë³äîê 1. ßêùî ì³æ äâîìà âåðøèíàìè äîïóñòèìîãî ãðàôà ³ñíóº øëÿõ, òîä³ ìíîæèíà âñ³õ øëÿõ³â ì³æ öèìè äâîìà âåðøèíàìè óòâîðþº äîïóñòèìèé ãðàô. Äîâåäåííÿ. Ïîáóäóºìî âèõ³äíèé ãðàô âåðøèíè, ÿêà â³äïîâ³äàº ìåíøîìó ôðàãìåíòó. Öåé ãðàô ì³ñòèòü ³íøó âåðøèíó çà ïîáóäîâîþ. Çã³äíî ç óìîâîþ 2 òå- îðåìè 3 â³í º äîïóñòèìèì. Ç öüîãî ãðàôà ïîáóäóºìî âõ³äíèé ãðàô äðóãî¿ âåðøè- íè. Îòðèìàºìî ãðàô, ÿêèé ñêëàäàºòüñÿ ò³ëüêè ç øëÿõ³â ì³æ çàäàíèìè âåðøèíàìè, ³ çã³äíî ç óìîâîþ 1 òåîðåìè 3 â³í º äîïóñòèìèì. � ÂÈÑÍÎÂÊÈ Äîñë³äæåíî âëàñòèâîñò³ ôðàãìåíòàðíèõ ñòðóêòóð, ÿê³ äîçâîëèëè âñòàíîâèòè çâ’ÿçîê ç îð³ºíòîâàíèìè ãðàôàìè ïåâíîãî âèäó. Êîæí³é ôðàãìåíòàðí³é ñòðóêòóð³ ìîæíà ïîñòàâèòè ó â³äïîâ³äí³ñòü ðîçì³÷åíèé àöèêë³÷íèé îð³ºíòîâàíèé ãðàô ç îäí³ºþ êîðåíåâîþ âåðøèíîþ. Âèçíà÷åíî ïîíÿòòÿ äîïóñòèìîãî ãðàôà — òàêîãî íåðîçì³÷åíîãî àöèêë³÷íîãî îðãðàôà ç îäí³ºþ êîðåíå- âîþ âåðøèíîþ, ÿêèé â³äïîâ³äàº êëàñó ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð. Òàêîæ âèçíà÷åíî ïîíÿòòÿ ðîçì³ðíîñò³ äîïóñòèìîãî ãðàôà òà â³äïîâ³äíèõ éîìó ³çîìîðôíèõ ôðàãìåíòàðíèõ ñòðóêòóð. Âñòàíîâëåíî âëàñòèâîñò³ òàêèõ ãðàô³â, ùî äîçâîëÿº ðîç- â’ÿçàòè çàäà÷ó ïåðåë³êó [12] öèõ ãðàô³â. Ïðîâåäåíî ðîçðàõóíêè ³ îòðèìàíî ðåçóëüòà- òè äëÿ ìàëèõ ðîçì³ðíîñòåé ôðàãìåíòàðíèõ ñòðóêòóð. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 169 {x1, x2} {x2} {x1, x2} {x1} �� Ðèñ. 8. Äîïóñòèì³ ðîçì³òêè ãðàôà ç ðèñ. 7, ã áà {x2, x3} {x1, x2, x3} {x1, x2} {x1}� {x3} {x2} {x1, x3} Ðèñ. 9. Ï³äãðàô ã³ïåðêóáà ðîçì³ðíîñò³ 3, ÿêèé íå º äîïóñòèìèì ãðàôîì ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ 1. Whitney H. On the abstract properties of linear dependence. American Journal of Mathematics. 1935. Vol. 57, N 3. P. 509–533. 2. Bjorner A., Ziegler G. M. Introduction to greedoids. Cambridge: Cambridge University Press: Matroid Applications, 1992. 180 ð. 3. Èëüåâ Â.Ï. Çàäà÷è íà ñèñòåìàõ íåçàâèñèìîñòè, ðàçðåøèìûå æàäíûì àëãîðèòìîì. Äèñêðåòíàÿ ìàòåìàòèêà. 2009. Ò. 21, âûï. 4. Ñ. 85–94. 4. Êîçèí È.Â., Êðèâöóí Å.Â., Ïèí÷óê Â.Ï. Ýâîëþöèîííî-ôðàãìåíòàðíàÿ ìîäåëü çàäà÷è òðàññè- ðîâêè. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2015. Ò. 51, ¹ 3. Ñ. 125–131. 5. Êîçèí È.Â., Êðèâöóí Å.Â., Ïîëþãà Ñ.È. Ôðàãìåíòàðíàÿ ñòðóêòóðà è ýâîëþöèîííûé àëãîðèòì äëÿ çàäà÷ ïðÿìîóãîëüíîãî ðàñêðîÿ. Â³ñíèê Çàïîð³çüêîãî íàö³îíàëüíîãî óí³âåðñèòåòó. Ñåð. Ô³çèêî-ìàòåìàòè÷í³ íàóêè. 2014. ¹ 2. Ñ. 65–72. 6. Êîçèí È.Â., Êðèâöóí Å.Â. Ìîäåëèðîâàíèå îäíîñëîéíûõ è äâóõñëîéíûõ òðàññèðîâîê. Óïðàâ- ëÿþùèå ñèñòåìû è ìàøèíû. 2016. ¹ 2. Ñ. 58–64. 7. Êîç³í ².Â., Áîðþ Ñ.Þ., Êðèâöóí Î.Â. Ìàòåìàòè÷íà ìîäåëü ïàêóâàííÿ â êîíòåéíåðè ð³çíèõ òèï³â. Â³ñíèê Çàïîð³çüêîãî íàö³îíàëüíîãî óí³âåðñèòåòó. Ñåð. Åêîíîì³÷í³ íàóêè. 2016. ¹ 2. Ñ. 85–92. 8. Êðèâöóí Å.Â. Ýâîëþöèîííî-ôðàãìåíòàðíûé àëãîðèòì ïîèñêà ìèíèìàëüíîãî ìíîæåñòâà àêñè- îì. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2016. ¹ 5. Ñ. 25–31. 9. Êîçèí È.Â., Ïîëþãà Ñ.È. Î ñâîéñòâàõ ôðàãìåíòàðíûõ ñòðóêòóð. Â³ñíèê Çàïîð³çüêîãî íàö³î- íàëüíîãî óí³âåðñèòåòó. Ñåð. Ô³çèêî-ìàòåìàòè÷í³ íàóêè. 2012. ¹ 1. Ñ. 99–106. 10. Ïîëþãà Ñ.². Ôðàãìåíòàðí³ îïòèì³çàö³éí³ ìîäåë³ â çàäà÷àõ ïîêðèòòÿ ãðàô³â òèïîâèìè ï³äãðà- ôàìè: äèñ. … êàíä. ô³ç.-ìàò. íàóê. Çàïîð³ææÿ, 2015. 140 ñ. URL: http://phd.znu.edu.ua/page/dis/ 06_2016/Polyuga_dis.pdf. 11. Áåðæ Ê. Òåîðèÿ ãðàôîâ è åå ïðèìåíåíèÿ. Ìîñêâà: Èçä-âî èíîñòðàííîé ëèò., 1962. 320 ñ. 12. Õàðàðè Ô., Ïàëìåð Ý. Ïåðå÷èñëåíèå ãðàôîâ. Ìîñêâà: Ìèð, 1977. 324 ñ. Íàä³éøëà äî ðåäàêö³¿ 20.03.2018 Å.Â. Êðèâöóí ÏÐÅÄÑÒÀÂËÅÍÈÅ ÔÐÀÃÌÅÍÒÀÐÍÛÕ ÑÒÐÓÊÒÓÐ ÎÐÈÅÍÒÈÐÎÂÀÍÍÛÌÈ ÃÐÀÔÀÌÈ Àííîòàöèÿ. Èññëåäîâàíû ñâîéñòâà ôðàãìåíòàðíûõ ñòðóêòóð è óñòàíîâëåíà ñâÿçü ìåæäó ôðàãìåíòàðíûìè ñòðóêòóðàìè è ðàçìå÷åííûìè àöèêëè÷åñêèìè îðèåíòèðîâàííûìè ãðàôàìè ñ îäíèì èñòî÷íèêîì, òàêæå óñòàíîâëåíî ñîîòâå- òñòâèå êëàññîâ èçîìîðôíûõ ôðàãìåíòàðíûõ ñòðóêòóð íåðàçìå÷åííûì àöèêëè- ÷åñêèì îðèåíòèðîâàííûì ãðàôàì îïðåäåëåííîãî âèäà, êîòîðûå íàçûâàþòñÿ äîïóñòèìûìè ãðàôàìè. Îïðåäåëåíî ïîíÿòèå ðàçìåðíîñòè äîïóñòèìîãî ãðàôà è ñîîòâåòñòâóþùèõ åìó èçîìîðôíûõ ôðàãìåíòàðíûõ ñòðóêòóð. Ïîëó÷åíî âû- ðàæåíèå äëÿ íèæíåé îöåíêè ðàçìåðíîñòè. Äîêàçàíà òåîðåìà î ñâîéñòâàõ äî- ïóñòèìûõ ãðàôîâ. Ïîäñ÷èòàíî êîëè÷åñòâî ôðàãìåíòàðíûõ ñòðóêòóð è êëàññîâ èçîìîðôíûõ ôðàãìåíòàðíûõ ñòðóêòóð ìàëûõ ðàçìåðíîñòåé. Êëþ÷åâûå ñëîâà: ôðàãìåíòàðíàÿ ñòðóêòóðà, ÷àñòè÷íî óïîðÿäî÷åííîå ìíî- æåñòâî, àöèêëè÷åñêèé îðãðàô, ãèïåðêóá. O.V. Kryvtsun REPRESENTATION OF FRAGMENTARY STRUCTURES BY ORIENTED GRAPHS Abstract. In the paper, the properties of fragmentary structures are investigated and relation between fragmentary structures and marked acyclic oriented graphs with one source is established, also the correspondence of isomorphic fragmentary structure classes with unmarked acyclic oriented graphs of certain type, which are called feasible graphs, is established. The notion of the dimension of a feasible graph and its corresponding isomorphic fragmentary structures is defined. An expression for the lower-bound estimate of the dimension is obtained. A theorem on the properties of feasible graphs is proved. The number of fragmentary structures and classes of isomorphic fragmentary structures of small dimensions is calculated. Keywords: fragmentary structure, partially ordered set, DAG, hypercube. Êðèâöóí Îëåíà Âîëîäèìèð³âíà, êàíäèäàò ô³ç.-ìàò. íàóê, äîöåíò êàôåäðè Çàïîð³çüêîãî íàö³îíàëüíîãî òåõí³÷íîãî óí³âåðñèòåòó, e-mail: kryvtsun@ukr.net. 170 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2

Представлення фрагментарних структур орієнтованими графами

Institution

Ähnliche Einträge