Критерий ребра общего многогранника размещений

Критерий ребра общего многогранника размещений

Исследуются свойства общего многогранника размещений для задач оптимизации на размещениях: рассмотрено описание ребра общего многогранника размещений системой уравнений и неравенств, являющихся подсистемой системы, которая описывает этот многогранник. Получен критерий ребра общего многогранника разм...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2018
Автори: Емец, О.А., Емец, А.О., Поляков, И.М.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Назва видання:Кибернетика и системный анализ
Теми:
Системний аналіз
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/161436
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Критерий ребра общего многогранника размещений / О.А. Емец, А.О. Емец, И.М. Поляков // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 128-138. — Бібліогр.: 33 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-161436
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1614362025-02-09T22:44:03Z Критерий ребра общего многогранника размещений Критерій ребра загального многогранника розміщень Criterion of the edge of the general polyhedron of arrangements Емец, О.А. Емец, А.О. Поляков, И.М. Системний аналіз Исследуются свойства общего многогранника размещений для задач оптимизации на размещениях: рассмотрено описание ребра общего многогранника размещений системой уравнений и неравенств, являющихся подсистемой системы, которая описывает этот многогранник. Получен критерий ребра общего многогранника размещений, описаны его вершины. Досліджено властивості загального многогранника розміщень для задач оптимізації на розміщеннях: розглянуто опис ребра загального многогранника розміщень системою рівнянь і нерівностей, що є підсистемою системи, яка описує цей многогранник. Отримано критерій ребра загального многогранника розміщень, описано вершини загального многогранника розміщень. The properties of the general polyhedron of arrangements for optimization problems on arrangements are investigated in the paper. An edge of the general polyhedron of arrangements is described by the system of equations and inequalities that is a subsystem of the system describing this polyhedron. The criterion of the edge of the general polyhedron of arrangements is obtained and its vertices are described. 2018 Article Критерий ребра общего многогранника размещений / О.А. Емец, А.О. Емец, И.М. Поляков // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 128-138. — Бібліогр.: 33 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/161436 519.85 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Системний аналіз
Системний аналіз
spellingShingle Системний аналіз
Системний аналіз
Емец, О.А.
Емец, А.О.
Поляков, И.М.
Критерий ребра общего многогранника размещений
Кибернетика и системный анализ
description Исследуются свойства общего многогранника размещений для задач оптимизации на размещениях: рассмотрено описание ребра общего многогранника размещений системой уравнений и неравенств, являющихся подсистемой системы, которая описывает этот многогранник. Получен критерий ребра общего многогранника размещений, описаны его вершины.
format Article
author Емец, О.А.
Емец, А.О.
Поляков, И.М.
author_facet Емец, О.А.
Емец, А.О.
Поляков, И.М.
author_sort Емец, О.А.
title Критерий ребра общего многогранника размещений
title_short Критерий ребра общего многогранника размещений
title_full Критерий ребра общего многогранника размещений
title_fullStr Критерий ребра общего многогранника размещений
title_full_unstemmed Критерий ребра общего многогранника размещений
title_sort критерий ребра общего многогранника размещений
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2018
topic_facet Системний аналіз
url https://nasplib.isofts.kiev.ua/handle/123456789/161436
citation_txt Критерий ребра общего многогранника размещений / О.А. Емец, А.О. Емец, И.М. Поляков // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 128-138. — Бібліогр.: 33 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT emecoa kriteriirebraobŝegomnogogrannikarazmeŝenii
AT emecao kriteriirebraobŝegomnogogrannikarazmeŝenii
AT polâkovim kriteriirebraobŝegomnogogrannikarazmeŝenii
AT emecoa kriteríirebrazagalʹnogomnogogrannikarozmíŝenʹ
AT emecao kriteríirebrazagalʹnogomnogogrannikarozmíŝenʹ
AT polâkovim kriteríirebrazagalʹnogomnogogrannikarozmíŝenʹ
AT emecoa criterionoftheedgeofthegeneralpolyhedronofarrangements
AT emecao criterionoftheedgeofthegeneralpolyhedronofarrangements
AT polâkovim criterionoftheedgeofthegeneralpolyhedronofarrangements
first_indexed 2025-12-01T12:05:31Z
last_indexed 2025-12-01T12:05:31Z
_version_ 1850307492676894720
fulltext ÓÄÊ 519.85 Î.À. ÅÌÅÖ, À.Î. ÅÌÅÖ, È.Ì. ÏÎËßÊΠÊÐÈÒÅÐÈÉ ÐÅÁÐÀ ÎÁÙÅÃÎ ÌÍÎÃÎÃÐÀÍÍÈÊÀ ÐÀÇÌÅÙÅÍÈÉ Àííîòàöèÿ. Èññëåäóþòñÿ ñâîéñòâà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé äëÿ çàäà÷ îïòèìèçàöèè íà ðàçìåùåíèÿõ: ðàññìîòðåíî îïèñàíèå ðåáðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé ñèñòåìîé óðàâíåíèé è íåðàâåíñòâ, ÿâëÿþùèõñÿ ïîäñèñòåìîé ñèñòåìû, êîòîðàÿ îïèñûâàåò ýòîò ìíîãîãðàííèê. Ïîëó÷åí êðè- òåðèé ðåáðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé, îïèñàíû åãî âåðøèíû. Êëþ÷åâûå ñëîâà: îáùèé ìíîãîãðàííèê ðàçìåùåíèé, êðèòåðèé ðåáðà, çàäà- ÷è îïòèìèçàöèè íà ðàçìåùåíèÿõ. ÂÂÅÄÅÍÈÅ Çàäà÷è îïòèìèçàöèè íà ðàçìåùåíèÿõ ïðåäñòàâëÿþò ñîáîé àêòóàëüíûé êëàññ (ñì., â ÷àñòíîñòè, [1–6]). Èññëåäîâàíèå è ðåøåíèå òàêèõ çàäà÷ ïðåäïîëàãàåò èçó÷åíèå ñâîéñòâ êàê öåëåâûõ ôóíêöèé, òàê è èõ äîïóñòèìûõ ìíîæåñòâ, â òîì ÷èñëå îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé. Ðåçóëüòàòû òàêèõ èññëåäîâàíèé èçëî- æåíû âî ìíîãèõ ïóáëèêàöèÿõ, èç êîòîðûõ ñëåäóåò îòìåòèòü [2–21]. Êîìáèíàòîð- íûå ìíîãîãðàííèêè — âûïóêëûå îáîëî÷êè åâêëèäîâûõ êîìáèíàòîðíûõ ìíî- æåñòâ — èçó÷àëèñü â ðÿäå ðàáîò, íàïðèìåð [2, 3, 6–8, 14, 22–33]. Îñíîâíîå âíè- ìàíèå ïðè ýòîì óäåëÿåòñÿ ïåðåñòàíîâî÷íîìó ìíîãîãðàííèêó [2, 7, 22–24, 26, 29–33]. Îáùèé ìíîãîãðàííèê ðàçìåùåíèé — âûïóêëàÿ îáîëî÷êà ìíîæåñòâà óïîðÿäî÷åííûõ âûáîðîê èç çàäàííîãî ìóëüòèìíîæåñòâà — èññëåäîâàëñÿ, â ÷àñòíîñòè, â ðàáîòàõ [2, 3, 6–8, 14, 25, 27, 28]. Îòìåòèì, ÷òî ýòè èññëåäîâà- íèÿ åùå íå èñ÷åðïàëè ñåáÿ.  íàñòîÿùåé ñòàòüå ðàññìîòðåíà ãðàíåâàÿ ñòðóêòóðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé (ÎÌÐ). Òåðìèíîëîãèÿ, èñïîëüçóåìàÿ äàëåå, ñîîòâåòñòâóåò ïðèíÿòîé â [2]. Î ÐÅÁÐÀÕ ÌÍÎÃÎÃÐÀÍÍÈÊÀ ÐÀÇÌÅÙÅÍÈÉ Ðàññìîòðèì ìíîãîãðàííèê ��n k G( ) k-ðàçìåùåíèé, ãäå G g g� { , ..., }1 � , S G e en( ) { , ..., }� 1 — îñíîâà ìóëüòèìíîæåñòâà, [ ] { , ..., }G n� � �1 — ïåðâè÷íàÿ ñïåöèôèêàöèÿ. Ïóñòü g g1 � �� � , e en1 � �� , à ��n k G( ) çàäàåòñÿ [2] ñèñòåìîé ëèíåéíûõ îãðàíè÷åíèé g x gi i i i i i� � � � � � � �� � 1 1 1 | | | |� � � � �� J kk { , , ..., }1 2 , | |� � k. (1) Âåðøèíà x x xk� ( , ..., )1 ìíîãîãðàííèêà ��n k G( ) ÿâëÿåòñÿ ïåðåñòàíîâêîé ýëå- ìåíòîâ ëþáîãî ìóëüòèìíîæåñòâà âèäà { , ..., , , ..., , }g g g g gs r1 1 1� � �� � � , r s k� � � �s r J k k , { , , , ..., }0 0 1 2 (ýòî ïåðâûé êðèòåðèé âåðøèíû èç [2, òåîðåìà 2.33, ñ. 53]). Âåðøèíà x ÿâëÿåòñÿ ñîñåäíåé ñ âåðøèíîé y äëÿ vert ��n k G( ) , åñëè âûïîëíÿåòñÿ [2] îäíî è òîëüêî îäíî èç óñëîâèé: 1) ïðîâåäåíà ïåðåñòàíîâêà êîîðäèíàò gi , gi�1 (g gi i� �1); 2) ïðîâåäåíà çàìåíà gs íà g r�� , g gs r� �� (èëè g r�� �1 íà gs�1, g gr s�� � ��1 1 ) . 128 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 © Î.À. Åìåö, À.Î. Åìåö, È.Ì. Ïîëÿêîâ, 2018 Èçâåñòåí âòîðîé êðèòåðèé âåðøèíû [6, òåîðåìà 3.1, ñ. 3–6]: âåðøèíà A âèäà x g1 1� , … , x gs s� , x gs r� � ��1 1� , …, x gk� ��1 1� ; x gk � � çàäàåòñÿ ñîâìåñòíî ñ (1) ñèñòåìîé x g x x g g x x g g x g x x s s k k k 1 1 1 2 1 2 1 1� � � � � � � � � � � � ; ; ...; ; ; � � � 1 1 1 1 1� � � � � � � � � � � � � � �g g x x g g gk s r� � � � �; ...; .� � (2) Óðàâíåíèÿ ñ ïåðâîãî ïî s-å íàçîâåì ëåâîïîðîæäåííîé ÷àñòüþ ñèñòåìû (2), à îñòàëüíûå óðàâíåíèÿ — ïðàâîïîðîæäåííîé ÷àñòüþ ýòîé ñèñòåìû, ÷òî îáóñëîâëåíî èõ ñâÿçüþ ñ ëåâîé è ïðàâîé ÷àñòÿìè ñèñòåìû (1). Î÷åâèäíî, íå íàðóøàÿ îáùíîñòè, äîñòàòî÷íî ðàññìàòðèâàòü ñèñòåìó äëÿ âåðøèíû, íîìåðà êîîðäèíàò êîòîðîé çàäàþòñÿ òîæäåñòâåííîé ïîäñòàíîâêîé 12 12 � � k k � � � � � � . Äëÿ ïîäñòàíîâêè 12 1 2 � � k i i ik � � � � � � èìååì x g x x g g x x g g x g i i i i i s i s k 1 1 2 11 1 2 1� � � � � � � � � � ; ; ...; ; ; � � � x x g g x x g g gi i i i rk k k s � � � � � � � � � � �� � � �1 11 1 1� � � � �; ...; � � . � � (3) Êàê è â (2), ïåðâûå s óðàâíåíèé (3) — ëåâîïîðîæäåííàÿ ÷àñòü ñèñòåìû, îñòàëüíûå óðàâíåíèÿ — ïðàâîïîðîæäåííàÿ ÷àñòü ñèñòåìû. Ðåáðî ìíîãîãðàí- íèêà — ýòî îòðåçîê, ñîåäèíÿþùèé äâå ñìåæíûå (ñîñåäíèå) âåðøèíû. Ðàññìîòðèì âåðøèíû, ñîñåäíèå ñ âåðøèíîé À , çàäàâàåìîé âìåñòå ñ (1) ñèñòåìîé (2). Èñïîëüçóåì êðèòåðèé ñìåæíîñòè âåðøèí ÎÌÐ [2], ò.å. èìååì äâà ñëó÷àÿ: 1) ïåðåñòàíîâêà êîîðäèíàò (ñ âîçìîæíûìè ïîäñëó÷àÿìè); 2) çàìåíà êîîðäèíàò. Ñëó÷àé 1. Äëÿ ïîëó÷åíèÿ ñîñåäíåé âåðøèíû ïåðåñòàâëÿåì êîîðäèíàòû gi è gi�1 ( )g gi i� �1 . 1. Ïðè i i J s, � �1 ïîëó÷àåì âåðøèíó Â. Òîãäà èìååì x g x x g g x x g g g x i i i i i1 1 1 1 1 1 1 1 1 1� � � � � � � � � � � �� � � �; ; ;� � � � 1 1 1 1 1 1 1� � � � � � � � � � � � �� � �� � � �x x g g g g x x g gi i i i i s s; ...; ; x g x x g g x x g g gk k k k s r� � � � � � � � � �� � � � �� � � � � �; ; ...;1 1 1 1� � � � � �� 1. (4) ×àñòü ñèñòåìû, ñîäåðæàùàÿ óðàâíåíèÿ ñ xk , äëÿ ýòîé âåðøèíû B (ïðàâîïî- ðîæäåííàÿ ÷àñòü) ïîâòîðÿåò ÷àñòü ñèñòåìû (2) ñ óðàâíåíèÿìè, ñîäåðæàùèìè xk . Áîëåå òîãî, âñå óðàâíåíèÿ (2) è (4), íå ñîäåðæàùèå xk , êðîìå i-ãî, òàêæå ñîâïàäà- þò. Îáùèì óðàâíåíèÿì óäîâëåòâîðÿþò ñîñåäíèå âåðøèíû À è  , ò. å. ðåáðî À çàäàåòñÿ ñîâìåñòíî ñ (1) ñèñòåìîé, â êîòîðîé i J s� �1: x g1 1� ; …; x x g gi i1 1 1 1� � � � �� �� � ; x x x gi i1 1 1� � � � ��� � ...� � �g gi i 1 ; …; x x g gs s1 1� � � � �� � ; x gk � � ; x x g gk k� � �� �1 1� � ; … ; x x g gk s� � � �� �� 1 1� � � � � �� g r� 1. 2. Äëÿ ïîëó÷åíèÿ ñîñåäíåé âåðøèíû ïåðåñòàâëÿåì êîîðäèíàòû g j è g j�1, ãäå j j J r rr, { , , ..., , }� � � � � � � �� �1 1 2 11 � � � � � � ; ïîëó÷àåì âåðøèíó Ñ . Òîã- äà óðàâíåíèÿ, ñîäåðæàùèå x1 â ñèñòåìå (2) (ëåâîïîðîæäåííàÿ ÷àñòü), ïîâòîðÿþò- ñÿ â ñèñòåìå äëÿ âåðøèíû Ñ: x g1 1� ; …; x x g gs s1 1� � � � �� � ; x gk � � ; x x g gk k� � �� �1 1� � ; … ; x x x g gk k k j j� � � � � �� � � � �1 1 1� �� � ; ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 129 x x x x g g gk k k j k j j j� � � � � � � �� � � � � � � �1 1 1 1� �� � � ; x x x x x gk k k j k j k j� � � � � � � �� � � � � �1 1 1� �� g g gj j j� � �� � � � �� �1 1 ; x x x x x x g gk k k j k j k j k j j� � � � � � � � �� � � � � � � � � �1 1 1 2 2� �� � ; … ; x x g g gk s r� � � � � �� � � �� �1 1 1� � � . Âñå óðàâíåíèÿ ïîñëåäíåé ñèñòåìû è ñèñòåìû (2), êðîìå óðàâíåíèÿ, ñîäåðæà- ùåãî îäíîâðåìåííî òîëüêî âñå ïåðåìåííûå xk , xk�1 , …, xk j� �1, ñîâïàäàþò è èì óäîâëåòâîðÿþò òî÷êè À è Ñ . Èíûìè ñëîâàìè, ðåáðî ÀÑ çàäàåòñÿ ñîâìåñòíî ñ (1) ñëåäóþùåé ñèñòåìîé, ãäå j J r r r � � � � �1 0 0 1 2 2 1{ , , , ..., , } (îòìåòèì, ÷òî r s k� � ): x g1 1� ; …; x x g gs s1 1� � � � �� � ; x gk � � ; x x g gk k� � �� �1 1� � ; … ; x x x g gk k k j j� � � � � �� � � � �1 1 1� �� � ; x x x x x g g gk k k j k j k j j� � � � � � � � � �� � � � � � � � �1 1 1 1 1� �� � � g gj j� �� � �� 1 ; …; x x g g gk s r� � � � � �� � � �� �1 1 1� � � , ò.å. èç ñèñòåìû (2) ðåáðà ÀÂ, ÀÑ ïîëó÷àåì èñêëþ÷åíèåì ëþáîãî óðàâíåíèÿ, êðîìå s-ãî èëè ïîñëåäíåãî. Ñëó÷àé 2. Äëÿ ïîëó÷åíèÿ ñîñåäíåé âåðøèíû ìîæåò áûòü âûïîëíåíà çàìåíà êîîðäèíàò. 1. Îáðàçîâàíèå ñîñåäíåé âåðøèíû D èç (2) âûïîëíÿåòñÿ çàìåíîé gs íà g r�� (g gs r� �� ). Äëÿ D ïîëó÷àåì x g x x g g x g x x s s k k s 1 1 1 1 1 1 1 � � � � � � � � � � � � � ; ...; ; ; ...;� � � � g g x x x g g gr k s s r r� � � � �� � � � � � � � � � � � � � � � �� � �1 1 1; . (5) Èç (2) â ñèñòåìó (5) âõîäÿò âñå óðàâíåíèÿ, êðîìå s-ãî. Ñèñòåìà äëÿ ðåáðà ÀD ÿâëÿåòñÿ îáùåé ÷àñòüþ (1), (2) è (5), ò. å. èç (2) áåðåì âñå óðàâíåíèÿ, êðîìå s-ãî. 2. Îáðàçîâàíèå ñîñåäíåé ê À âåðøèíû Å èç (5) ïðîâîäèì çàìåíîé êîîðäèíà- òû g r�� �1 íà gs�1 (g gr s�� � ��1 1). Äëÿ Å ïîëó÷àåì x g x x g g x x g g g x s s s s s1 1 1 1 1 1 1 1� � � � � � � � � � � �� �; ...; ; ;� � � � k k s rg x x g g� � � � � � � � � � �� � �; .� �2 2 (6) Èç (2) â (6) âõîäÿò âñå óðàâíåíèÿ, êðîìå ïîñëåäíåãî. Èíûìè ñëîâàìè, åñëè âçÿòü îáùèå â (2) è (6) óðàâíåíèÿ, ò.å. èç (2) èñêëþ÷èòü ïîñëåäíåå óðàâíåíèå, òî ïîëó÷èì èç (1) ðåáðî ÀÅ. Çíà÷èò, íåêîòîðîå ðåáðî èç âåðøèíû À ïîëó÷èì èç ñèñòåìû (1), ïðèñîåäèíèâ ê íåé ñèñòåìó (2) áåç îäíîãî óðàâíåíèÿ. Òàêèì îáðà- çîì, äîêàçàíî ñëåäóþùåå îïèñàíèå ðåáðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé. Òåîðåìà 1. Åñëè ïîäñèñòåìà îãðàíè÷åíèé ñèñòåìû (1) îïèñûâàåò âíóòðåí- íèå òî÷êè ðåáðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé, òî âìåñòå ñ (1) âûïîëíÿåòñÿ k �1 óðàâíåíèå èç (3). Ïðè ýòîì äëÿ êîíöîâ ðåáåð (âåðøèí) âûïîëíÿþòñÿ âñå óðàâíåíèÿ èç (3) èëè àíàëîãè÷íîé ñèñòåìû, îïèñûâàþùåé äðóãîé êîíåö ðåáðà. Ïðåäñòàâëåíèå (4) äëÿ âåðøèíû ñ ïîâòîðåíèåì êîîðäèíàò íå åäèíñòâåííî. ×èñëî òàêèõ ïðåäñòàâëåíèé ìîæíî ïîäñ÷èòàòü. Åñëè âåðøèíà èìååò êîîðäèíà- òû g g g gs r1 1, ..., , , ...,� �� � , ïîäñ÷èòàåì êîëè÷åñòâî ñèñòåì (4) äëÿ íåå. Îáîçíà- ÷èì G g g g gr s s r , { , ..., , , ..., }� � �1 1� � , îáðàçîâàâ îñíîâó ìóëüòèìíîæåñòâà S G e er s r rnr ( ) ( , ..., ), � 1 è ïåðâè÷íóþ ñïåöèôèêàöèþ [ ] ( , ..., ),G r s r rnr � � �1 . Òîã- äà êîëè÷åñòâî ñèñòåì äëÿ ïðåäñòàâëåíèÿ âåðøèí ñîñòàâëÿåò � � �r r rnr1 2! ! !� � �� , ïîñêîëüêó ëþáîå eri èìååò êðàòíîñòü � ri è ñîîòâåòñòâóþùèå g gj j ri , ..., � �� 1, ðàâ- 130 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 íûå eri , ìîæíî ïåðåñòàâëÿòü � ri ! ðàç (ïðè ýòîì èìååì îäíè è òå æå âåðøèíû), à äëÿ êàæäîé ïîëó÷åííîé âåðøèíû çàïèñûâàòü ñâîþ ñèñòåìó âèäà (4). ÈËËÞÑÒÐÀÒÈÂÍÛÅ ÏÐÈÌÅÐÛ Ïðèìåð 1. Ïóñòü çàäàíî ìóëüòèìíîæåñòâî G � { , , , , }0 1 2 2 4 , k � 3 . Íà ðèñ. 1 èçîáðàæåí ìíîãîãðàííèê ðàçìåùåíèé � 5 4 3 , ( )G . Çäåñü âåðøèíû ïî ñëîÿì x c1 � ( ; ; ; )c � 0 1 2 4 : ( , , )0 1 2 , ( , , )0 2 1 , ( , , )0 1 4 , ( , , )0 4 1 , ( , , )0 2 4 , ( , , )0 4 2 ; ( , , )1 0 2 , ( , , )1 2 0 , ( , , )1 0 4 , ( , , )1 4 0 ; ( , , )2 0 1 , ( , , )2 1 0 , ( , , )2 2 4 , ( , , )2 4 2 , ( , , )2 0 4 , ( , , )2 4 0 ; ( , , )4 2 2 , ( , , )4 2 0 , ( , , )4 0 2 , ( , , )4 0 1 , ( , , )4 1 0 . Ðàññìîòðèì íåêîòîðûå åãî ðåáðà. Âåðøèíà — òî÷êà A � ( , , )4 2 2 . Ñîñåäíèå òî÷êè B � ( , , )2 2 4 , C � ( , , )2 4 2 , D � ( , , )4 0 2 , E � ( , , )4 2 0 . Ñèñòåìà äëÿ À (ÀI) èìååò âèä x1 4� ; x x1 2 4 2� � � ; x x x1 2 3 4 2 2� � � � � . Äðóãàÿ ñèñòåìà äëÿ À (ÀII) èìååò âèä x1 4� ; x x1 3 4 2� � � ; x x1 3� � x2 4 2 2� � � . Çàïèøåì ñèñòåìû äëÿ âåðøèí B, C, D, E. Âåðøèíà  èìååò äâå ñèñòåìû (BI; BII) âèäà x x x x x x x x 3 3 2 3 1 3 2 1 4 6 6 8 � � � � � � � � � � �� , , . èëè Âåðøèíà C òàêæå èìååò äâå ñèñòåìû (CI; CII) âèäà x x x x x x x x 2 2 1 2 3 1 2 3 4 6 6 8 � � � � � � � � � � �� , , . èëè Âåðøèíà D èìååò îäíó ñèñòåìó âèäà x1 4� ; x x1 3 6� � ; x2 0� . Âåðøèíà E òàêæå èìååò îäíó ñèñòåìó âèäà x1 4� ; x x1 2 6� � ; x3 0� . Ïðåäñòàâèì ñèñòåìû äëÿ ðåáåð. Ðåáðî AB îáðàçóåòñÿ âòîðûì è òðåòüèì óðàâíåíèÿìè ñèñòåìû AII (ÂII) (ò.å. èñêëþ÷åíû ïåðâûå óðàâíåíèÿ): x x1 3 6� � ; x x x1 2 3 8� � � . Ðåáðî AC îáðàçóåòñÿ âòîðûì è òðåòüèì óðàâíåíèÿìè ñèñòåìû À² (C²) (ò.å. èñêëþ÷åíû ïåðâûå óðàâíåíèÿ): x x1 3 6� � ; x x x1 2 3 8� � � . Ðåáðî AD îáðàçóåòñÿ ïåðâûì è âòîðûì óðàâíåíèÿìè ñèñòåìû À²² (D) (ò.å. èñêëþ÷åíû òðåòüè óðàâíåíèÿ): x1 4� ; x x1 3 6� � . Ðåáðî AE îáðàçóåòñÿ ïåðâûì è âòîðûì óðàâíåíèÿìè ñèñòåìû À² (E) (ò.å. èñêëþ÷åíû ïåðâûå óðàâíåíèÿ): x1 4� ; x x1 2 6� � . Òàêèì îáðàçîì, ÷òîáû ïîëó÷èòü âñå ðåáðà, ñëåäóåò âñå ñèñòåìû äëÿ âåðøèíû âûïèñàòü. Ðàññìîòðèì ñèñòåìû äëÿ ÀI è ÀII, èñêëþ÷èâ âòîðûå óðàâíåíèÿ: äëÿ À² èìå- åì ñèñòåìó (íàçîâåì åå 1) âèäà x1 4� ; x x x1 2 3 8� � � ; äëÿ ÀII èìååì ñèñòåìó (íàçîâåì åå 2) âèäà x1 4� ; x x x1 2 3 8� � � . Ñèñòåìû 1 è 2 ñîâïàäàþò è îïèñûâà- þò òî÷êó À . Ïðè x1 4� óðàâíåíèå x x2 3 4� � äëÿ òî÷åê ìíîãîãðàííèêà E Gn k � ( ) âûïîëíÿåòñÿ òîëüêî â òî÷êå (x1, 2 2, ); ïðè x1 4� — â òî÷êàõ (x1, 0 4, ), (x1, 4 0, ).  òî÷êå A( , , )4 2 2 x1 4� ; ñëåäîâàòåëüíî, ( , , ) ( , , )4 2 2 2 21� x , ò.å. ýòîé ñèñòåìå èç E Gn k � ( ) óäîâëåòâîðÿåò òîëüêî À . ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 131 Ðèñ. 1. Ìíîãîãðàííèê 3-ðàçìåùåíèé ïðè G � { , , , , }0 1 2 2 4 , k � 3 Çàìå÷àíèå 1.  ñõåìå, îïèñàííîé âûøå äëÿ ïîëó÷åíèÿ ðåáðà ìíîãîãðàííèêà ðàçìåùåíèé, à òàêæå â òåîðåìå 1 íå ïðîèçâîäèòñÿ çàìåíà gi è gi�1 , íå èçìåíÿ- þòñÿ g gs r� �� , g gs r� ��1 � .  ýòèõ ñëó÷àÿõ ñèñòåìà äëÿ âåðøèíû ïðè óäàëåíèè îäíîãî óðàâíåíèÿ ïî-ïðåæíåìó îïèñûâàåò ýòó æå âåðøèíó. Ïðèìåð 2. Ïóñòü, êàê è â ïðèìåðå 1, G � { , , , , }0 1 2 2 4 , S G( ) ( , , , )� 0 1 2 4 , [ ] ( , , , )G � 1 1 2 1 . Êðàòíîñòè � i ýëåìåíòîâ îñíîâû ñîñòàâëÿþò �1 1� ; � 2 1� ; � 3 2� ; � 4 1� . Ââåäåì â ðàññìîòðåíèå ïàðàìåòðû k i , i J n� 0 : k0 0� ; k1 1 1� �� ; k2 1 2 2� � �� � ; k3 1 2 3 4� � � �� � � ; k4 1 2 3 4 5� � � � � �� � � � � . Ïðîâåäåì äîïîëíèòåëüíûé àíàëèç, èñïîëüçóÿ ðåçóëüòàòû ïðèìåðà 1. Ïðîàíàëèçèðóåì âòî- ðûå óðàâíåíèÿ èç ñèñòåì À² è À²². Äëÿ À² èìååì óðàâíåíèå x x1 2 6� � . Îáîçíà÷èì � � { , }1 2 ìíîæåñòâî èíäåêñîâ ýòîãî óðàâíåíèÿ. Äëÿ ñèñòåìû À², êîòîðàÿ îïèñûâà- åò À , ââåäåì â ðàññìîòðåíèå ìíîæåñòâà èíäåêñîâ íåèçâåñòíûõ â ñîîòâåòñòâóþùèõ óðàâíåíèÿõ: �1 1� { }, | |�1 1� ; � 2 1 2� { , } , | |� 2 2� ; � 3 1 2 3� { , , } , | |� 3 3� ; � � �1 2 3 3 � J . Êîëè÷åñòâî âëîæåííûõ îäíî â äðóãîå ïîäìíîæåñòâ èíäåê- ñîâ îáîçíà÷èì � . Äëÿ À²² èìååì x x1 3 6� � : � � { , }1 3 . Äëÿ âñåé ñèñòåìû À²² , êî- òîðàÿ îïèñûâàåò À , èìååì ìíîæåñòâà èíäåêñîâ íåèçâåñòíûõ: �1 1� { }, | |�1 1� ; � 2 1 3� { , } , | |� 2 2� ; � 3 1 3 2� { , , } , | |� 3 3� ; � � �1 2 3 3 � J .  îáîèõ ñëó÷à- ÿõ èìååì � � 3 , k � 3 . Îïðåäåëèì m k� � � � ���{ ( | | | | ) }� � �� � 1 1 . Ñóììèðîâà- íèå ïðîâîäèòñÿ, êîãäà | | | |� �� �� �1 è �j òàêîå, ÷òî k j� ��1 1| |� � , | |� � � k j . Ðàññìîòðèì ââåäåííóþ â ïðèìåðå 1 ñèñòåìó 1 (àíàëîãè÷íî 2). Äëÿ ëåâîïî- ðîæäåííîé ÷àñòè ñèñòåìû ïîëàãàþò k0 0� ; k1 1� � ; k2 1 2� �� � , …; äëÿ ïðàâî- ïîðîæäåííîé ÷àñòè ñèñòåìû ïîëàãàþò k0 0� ; k n1 � � ; k n n2 1� � �� � , … Äëÿ G � { , , , , }0 1 2 2 4 è [ ] ( , , , )G � 1 1 2 1 ïîëó÷àåì k0 0� , k1 1� , k2 2� , k3 4� , k5 5� . Ñèñòåìà 1 ñîäåðæèò ïðàâîïîðîæäåííûå óðàâíåíèÿ è ïðè � 3 2� ; � 4 1� ïîëó÷à- åì k2 3� ; k1 1� ; k0 0� . Ìåæäó k2 è k1 ñòîÿò ÷èñëà | |� 2 3� ; | |�1 1� ; � � 2 , ïî- ñêîëüêó ñèñòåìà 1 (èëè 2) èìååò âèä x x x x 1 1 2 3 4 1 8 3 � � � � � � � � (| | ), (| | ) � � � � è �1 1� { } , | |�1 1� ; � 2 1 2 3� { , , } , | |� 2 3� . Íàéäåì m k� � � � � ���{ ( | | | | ) }� � �� � 1 1 3 2 3 1 1 3 3 0� � � � � � �( ( )) . Èìååì 0-ãðàíü — âåðøèíó, êîòîðàÿ îïèñàíà ñèñòåìîé 1 (èëè 2). Ïðèìåð 3. Ïóñòü, êàê è â ïðèìåðàõ 1 è 2, èìååì ìóëüòèìíîæåñòâî G � { , , , , }0 1 2 2 4 , íî ïðè ýòîì k � 4 . Ðàññìîòðèì âåðøèíó g 0 0 1 2 2� ( , , , ) îáùåãî ìíîãîãðàííèêà ðàçìåùåíèÿ E Gn k � ( ) . Äëÿ ýòîé âåðøèíû èìååì òàêèå ñèñòåìû. Ïåðâàÿ ñèñòåìà (ñèñòåìà I): x x x x x x x x x x 1 1 2 1 2 3 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , . Âòîðàÿ ñèñòåìà (ñèñòåìà ²²): x x x x x x x x x x 1 1 2 1 2 4 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , . 132 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 Ñîñåäíèå ñ g 0 âåðøèíû g1 1 0 2 2� ( , , , ) ; g 2 0 2 1 2� ( , , , ) ; g 3 0 2 2 1� ( , , , ) ïî- ëó÷åíû ïåðåñòàíîâêîé íåðàâíûõ ýëåìåíòîâ gi è gi�1 , à âåðøèíû g 4 0 1 2 4� ( , , , ) ; g 5 0 1 4 2� ( , , , ) ïîëó÷åíû çàìåíîé íåðàâíûõ ýëåìåíòîâ gs íà g r�� . Äëÿ âåðøèíû g1 èìååì äâå ñèñòåìû: x x x x x x x x x x 2 1 2 1 2 3 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , ; x x x x x x x x x x 2 1 2 1 2 4 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , . Ðåáðî g g0 1 èç ïåðâîé ñèñòåìû èìååò âèä x x x x x x x x x 1 2 1 2 3 1 2 3 4 1 3 5 � � � � � � � � � � � �� , , . Ðåáðî g g0 1 èç âòîðîé ñèñòåìû èìååò âèä x x x x x x x x x 1 2 1 2 4 1 2 3 4 1 3 5 � � � � � � � � � � � �� , , . Íà ýòîì ðåáðå èìåþòñÿ äâå âåðøèíû, â êîòîðûõ ïåðåñòàâëåíû êîîðäèíàòû 0 è 1: ( , , , ) ( , , , )0 1 2 2 1 0 2 2� . Äëÿ âåðøèíû g 2 0 2 1 2� ( , , , ) òàêæå èìååì äâå ñèñòåìû: x x x x x x x x x x 1 1 3 1 3 2 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , ; x x x x x x x x x x 1 1 3 1 3 4 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , . Ðåáðî g g0 2 ìîæåò ïðåäñòàâëÿòüñÿ îäíîé èç äâóõ ñèñòåì: x x x x x x x x 1 1 2 3 1 2 3 4 0 3 5 � � � � � � � � � � �� , , èëè x x x x x x x x 1 1 3 4 1 2 3 4 0 3 5 � � � � � � � � � � �� , , . Çäåñü èìååì ( , , , ) ( , , , )0 1 2 2 0 2 1 2� . Äëÿ âåðøèíû g 3 èìååì äâå ñèñòåìû: x x x x x x x x x x 1 1 4 1 4 2 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , ; x x x x x x x x x x 1 1 4 1 4 3 1 2 3 4 0 1 3 5 � � � � � � � � � � � � � � , , , . Ðåáðî g g0 3 èìååò îäíó ñèñòåìó: x x x x x x x x 1 1 4 2 1 2 3 4 0 3 5 � � � � � � � � � � �� , , , ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 133 ò.å. g g0 3 — ðåáðî, â âåðøèíàõ êîòîðîãî ïåðåñòàâëåíû 2 è 1 (x1 è x4): ( , , , ) ( , , , )0 1 2 2 0 2 2 1� . Âåðøèíà g 4 0 1 2 4� ( , , , ) îïðåäåëÿåòñÿ êàê x x x x x x x 1 1 2 1 2 3 4 0 1 3 4 � � � � � � � � � � � , , , . Äëÿ ðåáðà g g0 4 èìååì îäíó ñèñòåìó: x x x x x x 1 1 2 1 2 3 0 1 3 � � � � � � � � �� , , . Ðàññìîòðèì âåðøèíó g 5 0 1 4 2� ( , , , ) , êîòîðàÿ îïðåäåëÿåòñÿ ñèñòåìîé x x x x x x x 1 1 2 1 2 4 3 0 1 3 4 � � � � � � � � � � � , , , . Äëÿ ðåáðà g g0 5 èìååì îäíó ñèñòåìó: x x x x x x 1 1 2 1 2 4 0 1 3 � � � � � � � � �� , , . Ñèñòåìà, ïîëó÷åííàÿ èç ñèñòåìû äëÿ îïèñàíèÿ âåðøèíû g 0 (ñèñòåìà ² èëè ñèñòåìà II) èñêëþ÷åíèåì òðåòüåãî óðàâíåíèÿ, îïðåäåëÿåò îäíó ñèñòåìó: x x x x x x x 1 1 2 1 2 3 4 0 1 5 � � � � � � � � � �� , , ; çàìåòèì, ÷òî | |�1 0� ; | |� 2 2� ; | |� 3 4� ; � � 3 . Äëÿ ýòîãî ìóëüòèìíîæåñòâà G èìååì îñíîâó S G( ) ( , , , )� 0 1 2 4 ; ïåðâè÷íóþ ñïåöèôèêàöèþ [ ] ( , , , )G � 1 1 2 1 , ò.å. k0 0� ; k1 1� ; k2 2� ; | |� 2 2� ; | |� 3 4� ; k3 4� ; k4 5� . Íàéäåì m k� � � � � ���{ ( | | | | ) }� � �� � 1 1 4 3 4 2 1 4 4 0� � � � � � �{ ( )} . Òàêèì îáðàçîì, ýòà ñèñòåìà îïèñûâàåò âåðøèíó g 0 . ÈÄÅÍÒÈÔÈÊÀÖÈß ÐÅÁÐÀ ÓÐÀÂÍÅÍÈßÌÈ ÈÇ ÑÈÑÒÅÌÛ ÄËß ÎÌÐ Ïóñòü âåðøèíà g Gn k��� ( ) îïðåäåëÿåòñÿ ñèñòåìîé (3). Ââåäåì îáîçíà÷åíèÿ äëÿ ëåâîïîðîæäåííîé ÷àñòè ñèñòåìû (3) : � 1 1 L i� { }; � 2 1 2 L i i� { , } ; … ; � s L si i i� { , , ..., }1 2 , à äëÿ ïðàâîïîðîæäåííîé ÷àñòè ñèñòåìû (3) � 1 R ki� { } ; � 2 1 R k ki i� �{ , } ; … ; � r R k k si i i� � �{ , , ..., }1 1 ; îòìåòèì, ÷òî r s k� � , s r J k , � 0 . Î÷åâèäíî, ÷òî � � � 1 2 L L s L � , (7) � � � 1 2 R R r R � , (8) à òàêæå ÷òî � �s L r R kJ k� � � { , , ..., }1 2 . 134 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 Ïóñòü ïîñëå èñêëþ÷åíèÿ óðàâíåíèÿ èç ñèñòåìû, êîòîðàÿ îïèñûâàåò âåðøè- íó, ñ öåëüþ îáðàçîâàíèÿ ðåáðà ñîîòâåòñòâóþùèå ñèñòåìû ïîäìíîæåñòâ èçìåíè- ëèñü (òî÷íåå, êîëè÷åñòâî ýëåìåíòîâ â îäíîì èç ïîäìíîæåñòâ óìåíüøèëîñü íà åäèíèöó), ò.å. åñëè èñêëþ÷èì óðàâíåíèå èç ëåâîïîðîæäåííîé ïîäñèñòåìû, òî èìååì ïîäìíîæåñòâà èíäåêñîâ � � � i L i L i L s1 2 1 � � (9) è ïîäìíîæåñòâà èíäåêñîâ (8). Åñëè èñêëþ÷èì óðàâíåíèå èç ïðàâîïîðîæäåííîé ïîäñèñòåìû, òî èìååì ïîäìíîæåñòâà èíäåêñîâ (7) è ïîäìíîæåñòâà èíäåêñîâ � � � j R j R j R r1 2 1 � � . (10) Êàê óêàçàíî âûøå, ðàññìàòðèâàþòñÿ ìíîæåñòâî k-ðàçìåùåíèé E Gn k � ( ) , îá- ùèé ìíîãîãðàííèê ðàçìåùåíèé ��n k G( ) , ãäå G g g� { , ..., }1 � , g g1 � �� � ; S G e en( ) ( , ..., )� 1 , e en1 � �� ; [ ] ( , ..., )G n� � �1 . Îòìåòèì [2], ÷òî âåðøèíîé x x x Gk n k� �( , ..., ) ( )1 vert �� ÿâëÿåòñÿ òî÷êà, êîîðäèíàòû êîòîðîé — ýòî òàêèå ýëåìåíòû g1, …, gs, g r�� �1, g r�� � 2 , …, g� èç G, ãäå s r k� � ; s r J k k , { , , , ..., }� �0 0 1 2 , è òîëüêî îíè, ñòîÿùèå â ëþáîì ïîðÿäêå â x . Òàêèì îáðà- çîì, îäíîé èç âåðøèí ÿâëÿåòñÿ òî÷êà g g g g g g gs r r 0 1 2 1 2� � � � �( , , ..., , , , ..., )� � � , à äðóãèå âðåøèíû ïîëó÷àþòñÿ ïåðåñòàíîâêîé ýòèõ ýëåìåíòîâ èëè âûáîðîì äðóãî- ãî ýëåìåíòà s J k � 0 , à çíà÷èò, è r k s� � . Ïàðàìåòð � â ñëó÷àå s � 0 îïðåäåëèì òàê: g es � � ; (11) à â ñëó÷àå s � 0 èìååì � � 0 . Ïàðàìåòð � â ñëó÷àå r � 0 îïðåäåëèì òàê: g er� �� � �1 , (12) à â ñëó÷àå r � 0 èìååì � � 0 . Îïðåäåëèì K0 0� ; K1 1� � ; K2 1 2� �� � ; …; K s K� �� � �1 , ãäå � íàõîäèòñÿ èç (11). Îïðåäåëèì 0 0� , �1 � n , � �2 1� � �n n , … , � �� � �r 1 , ãäå � íàõîäèòñÿ èç (12). Òàêèì îáðàçîì, èìååì òåîðåìó. Òåîðåìà 2. (Îá èäåíòèôèêàöèè ðåáðà óðàâíåíèÿìè â ñèñòåìå ÎÌÐ.) 1. Åñëè F — ðåáðî ÎÌÐ, òî ñóùåñòâóåò, âîçìîæíî, íå åäèíñòâåííàÿ (â ñëó- ÷àå, êîãäà G — ìóëüòèìíîæåñòâî, à íå ìíîæåñòâî), ñèñòåìà ðàâåíñòâ ñ ïîäìíî- æåñòâàìè èíäåêñîâ, êîòîðûå îïðåäåëÿþòñÿ ñîîòíîøåíèÿìè (8), (9) èëè (7), (10). 2. Åñëè èìååì ìíîæåñòâî èíäåêñîâ (8), (9) èëè (7), (10), êîòîðûå â ñèñòå- ìå (1) îïðåäåëÿþò ðàâåíñòâà, òî ýòè óñëîâèÿ äàþò ìíîæåñòâî F : ðåáðî ÎÌÐ èëè åãî âåðøèíó. Ðàçìåðíîñòü ýòîãî ìíîæåñòâà F îïðåäåëÿåòñÿ òàê: dim F k� � � � ���{ ( | | | | ) }� � � 1 1 , ãäå � � �k 1 , à ñóììèðîâàíèå ïðîâîäèòñÿ äëÿ (9) èëè (10) ïðè òàêèõ èíäåêñàõ ( � �Js 1 äëÿ (9); � �Jr 1 äëÿ (10)), äëÿ êàæ- äîãî èç êîòîðûõ íàéäåòñÿ j J� � (äëÿ (9)), j J� � (äëÿ (10)), ÷òî äëÿ (9) âûïîëíÿ- åòñÿ K j i L � �� � � 1 1 1 | | | |� � è | | | |� � i L jK� � (ãäå � 0 0� ), à äëÿ (10) èìååò ìåñòî � �� � j j R � �� � � 1 1 1 | | | | è | | | |� � � �j R j� � (ãäå � 0 0� ). Çàìå÷àíèå 2.  òåîðåìå 2 ðàçìåðíîñòü F ðàâíà íóëþ â ñëó÷àå, êîãäà F — âåð- øèíà, èëè åäèíèöå, êîãäà F — ðåáðî. Ïîýòîìó òåîðåìà 2 ÿâëÿåòñÿ êðèòåðèåì ðåáðà. Ïðèìåð 4. Ïóñòü G � { , , , , }1 2 2 2 3 , k � 4. Èìååì �1 1� ; � 2 3� ; � 3 1� , � � 5 . Çàäàäèì K0 0� , K1 1� , K2 4� ; 2 4� , 1 1� , 0 0� . Ðàññìîòðèì âåðøèíó ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 135 g 0 1 2 2 3� ( , , , ) . Åñëè ñ÷èòàòü g1 1� ; g g2 3 2� � ; g g r4 1 2� �� �� , g g� � �5 3 , r s� � 2 (÷åðòà ñíèçó è ñâåðõó â g 0 : ñíèçó ñëåâà ïîä÷åðêèâàåì s ýëåìåíòîâ, ñïðà- âà ñâåðõó ïîä÷åðêèâàåì r ýëåìåíòîâ), òî âåðøèíó îïèñûâàåò ñèñòåìà, ñîñòîÿùàÿ èõ äâóõ (ëåâîïîðîæäåííîé è ïðàâîïîðîæäåííîé) ïîäñèñòåì: x1 1� , x2 1 2� � , | |�1 1� , | |� 2 2� ; x4 3� , x x4 3 5� � , | |�1 1� , | |� 2 2� . Äëÿ ïåðâîãî ðåáðà èìååì ñèñòåìû è ñîîòâåòñòâåííî ïàðàìåòðû: x1 1� , | |� 0 0� , | |� 1 1� ; x4 3� , x x4 3 5� � , | |� 0 0� , | |�1 1� , | |� 2 2� ; m k� � � � � � � � �( ( ) ( ))� 1 0 1 2 1 1 1. Äëÿ âòîðîãî ðåáðà ëåâîïîðîæäåííàÿ ñèñòåìà èìååò âèä x1 1� , x x1 2 3� � , ïðàâîïîðîæäåííàÿ ñèñòåìà èìååò âèä x3 3� . Êàê è äëÿ ïåðâîãî ðåáðà, ðàçìåðíîñòü m �1. Äëÿ òðåòüåãî ðàáðà èìååì x x1 2 3� � , | |�1 2� , | |� 0 0� ; x3 3� ; x x4 3 5� � , | |�1 1� , | |� 2 2� ; m �1. Äëÿ ÷åòâåðòîãî ðåá- ðà èìååì x1 1� ; x x1 2 3� � ; x x4 3 5� � ; m �1. Ïóñòü òåïåðü âåðøèíà g 0 1 2 2 3� ( , , , ) ïðåäñòàâëåíà â âèäå åå ëåâîïîðîæäåííîé ÷àñòè: x1 1� ; x x1 2 3� � ; x x x1 2 3 5� � � (ò.å. s � 3, ïîä÷åðêíóòî ñëåâà â g 0) è ïðàâîïîðîæäåííîé ÷àñòè: x4 3� (ò.å. r �1). Ïåðâîå ðåáðî, ñîñòîÿùåå èç ëåâîïîðîæäåííîé ÷àñòè ñèñòåìû äëÿ g 0 , îïðåäåëÿåò | |�1 1� , | |� 2 2� , | |� 3 3� . Äåéñòâèòåëüíî, ðàçìåðíîñòü m ìíîæåñòâà F ðàâíà åäèíèöå. Äëÿ âòîðîãî ðåáðà ëåâîïîðîæäåííàÿ ÷àñòü ñèñòåìû èìååò âèä x2 1� , x x1 2 3� � , à ïðàâîïîðîæäåííàÿ ÷àñòü èìååò âèä x4 3� . Ëåãêî ïîäñ÷èòàâ m , óáåæäàåìñÿ, ÷òî äåéñòâèòåëüíî ðàçìåðíîñòü m ìíîæåñòâà F ðàâíà åäèíèöå. Ðàññìîòðèì òðåòüå ìíîæåñòâî F , êîòîðîå îïðåäåëÿåòñÿ ñèñòåìîé x1 1� , x x x1 2 3 5� � � , x4 3� , | |�1 1� , | |� 2 3� , | |� 3 1� . Ïîäñ÷èòàåì ðàçìåðíîñòü m ýòîãî ìíîæåñòâà: m k� � � � � � � � �( ( ))� 3 1 1 4 3 1 0 . Ñëåäîâàòåëüíî, F — ýòî âåðøèíà. Ïðåäñòàâèâ ñèñòåìó äëÿ òðåòüåãî ìíîæåñòâà F â âèäå x1 1� , x4 3� , x x2 3 4� � , ëåãêî óâèäåòü, ÷òî ýòà ñèñòåìà ÿâëÿåòñÿ âåðøèíîé g 0 , ïîñêîëüêó ïðè x1 1� , x4 3� èç (1) èìååì 2 22� �x ; 2 23� �x . Âñå âûêëàäêè ïî àíàëîãèè ñ ïðèìåðîì 4 ëåãêî ïðîâåñòè è äëÿ îáùåãî ñëó÷àÿ. ÇÀÊËÞ×ÅÍÈÅ Â ðàáîòå ðàññìîòðåíî îïèñàíèå ðåáðà îáùåãî ìíîãîãðàííèêà ðàçìåùåíèé ñèñ- òåìîé óðàâíåíèé è íåðàâåíñòâ, ÿâëÿþùèõñÿ ïîäñèñòåìîé ñèñòåìû, îïèñûâàþ- ùåé ýòîò ìíîãîãðàííèê. Ïîëó÷åí êðèòåðèé ðåáðà ÎÌÐ è äàíî îïèñàíèå âåð- øèíû ÎÌÐ, ñîäåðæàùåå k �1 óðàâíåíèå èç ñèñòåìû äëÿ ÎÌÐ. Êàê íàïðàâëå- íèå äàëüíåéøèõ èññëåäîâàíèé, öåëåñîîáðàçíî ðàññìàòðèâàòü âñåñòîðîííèå èññëåäîâàíèÿ ñòðóêòóðû ÎÌÐ, âûÿâëåíèå è òèïèçàöèþ êîìáèíàòîðíûõ òèïîâ ÎÌÐ è ýòè ñâîéñòâà èñïîëüçîâàòü äëÿ ðàçðàáîòêè ìåòîäîâ îïòèìèçàöèè â çà- äà÷àõ íà ðàçìåùåíèÿõ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñåðãèåíêî È.Â., Êàñïøèöêàÿ Ì.Ô. Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè. Êèåâ: Íàóê. äóìêà, 1981. 288 ñ. 2. Ñòîÿí Þ.Ã., ªìåöü Î.Î. Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Êè¿â: ²í-ò ñèñ- òåìíèõ äîñë³äæåíü îñâ³òè, 1993. 188 ñ. URL: http://dspace.uccu.org.ua/handle/123456789/487. 3. Ñòîÿí Þ.Ã., ªìåöü Î.Î., ªìåöü ª.Ì. Îïòèì³çàö³ÿ íà ïîë³ðîçì³ùåííÿõ: òåîð³ÿ òà ìåòîäè. Ïîë- òàâà: ÐÂÖ ÏÓÑÊÓ, 2005. 103 ñ. URL: http://dspace.uccu.org.ua/handle/123456789/376. 4. Åìåö Î.À., Áàðáîëèíà Ò.Í. Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ. Êè¿â: Íàóê. äóìêà, 2008. 159 ñ. URL: http://dspace.uccu.org.ua/handle/123456789/473. 5. ªìåöü Î.Î., ×åðíåíêî Î.Î. Ìîäåë³ åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Ïîëòàâà: ÏÓÅÒ, 2011. 204 ñ. URL: http://dspace.uccu.org.ua/handle/123456789/354. 136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 6. Åìåö Î.À., ×åðíåíêî Î.À. Îïòèìèçàöèÿ äðîáíî-ëèíåéíûõ ôóíêöèé íà ðàçìåùåíèÿõ. Êè¿â: Íàóê. äóìêà, 2011. 154 ñ. URL: http://dspace.uccu.org.ua/handle/123456789/467. 7. Åìåëè÷åâ Â.À., Êîâàëåâ Ì.Ì., Êðàâöîâ Ì.Ê. Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ. Ìîñêâà: Íàóêà, 1981. 344 ñ. 8. Ñòîÿí Þ.Ã., ªìåöü Î.Î., ªìåöü ª.Ì. Ìíîæèíè ïîë³ðîçì³ùåíü â êîìá³íàòîðí³é îïòèì³çàö³¿. Äîïîâ³ä³ ÍÀÍÓ. 1999. ¹ 8. Ñ. 37–41. 9. Emets O.A., Barbolina T.N. Solving linear optimization problems on arrangements by the truncation method. Cybernetics and Systems Analysis. 2003. Vol. 39, N 6. P. 889–896. 10. Emets’ O.O., Roskladka O.V., Nedobachii S. I. Irreducible system of constraints for a general polyhedron of arrangements. Ukrainian Mathematical Journal. 2003. Vol. 55, N 1. P. 1–12. 11. Yemets O.A., Barbolina T.N. Solution of Euclidean combinatorial optimization problems by the method of construction of a lexicographic equivalence. Cybernetics and Systems Analysis. 2004. Vol. 40, N 5. P. 726–734. 12. Yemets O., Chernenko O. A nonreducible system of constraints of a combinatorial polyhedron in a linear-fractional optimization problem on arrangements. Cybernetics and Systems Analysis. 2005. Vol. 41, N 2. P. 246–254. 13. Yemets O.A., Barbolina T.N., Chernenko O.A. Solving optimization problems with linear-fractional objective functions and additional constraints on arrangements. Cybernetics and Systems Analysis. 2006. Vol. 42, N 5. P. 680–685. 14. ªìåöü Î.Î., ×åðíåíêî Î.Î. Îïòèì³çàö³ÿ äðîáîâî-ë³í³éíî¿ ôóíêö³¿ íà ðîçì³ùåííÿõ: âëàñòè- âîñò³ äîïóñòèìî¿ îáëàñò³. Íàóêîâ³ â³ñò³ ÍÒÓÓ «Êϲ». 2006. ¹ 5. Ñ. 22–29. 15. Emets O.A., Ustian N.Yu. Studies of problems of combinatorial optimization of game type on arrangements. Journal of Automation and Information Sciences. 2007. Vol. 39, N 1. Ð. 24–35. 16. Åìåö Î.À., ×åðíåíêî Î.À. Àíàëèç àëãîðèòìà ðåøåíèÿ óñëîâíûõ çàäà÷ îïòèìèçàöèè ñ äðîá- íî-ëèíåéíîé öåëåâîé ôóíêöèåé íà ðàçìåùåíèÿõ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2007. ¹ 4. Ñ. 133–146. 17. Iemets O.O., Yemets O.O. Solving a linear problem of Euclidean combinatorial optimization on arrangements with the constant sum of the elements. Cybernetics and Systems Analysis. 2012. Vol. 48, N 4. P. 547–557. 18. Iemets O.A., Olkhovskaja E.V. Proving the convergence of the iterative method for solving a game-type combinatorial optimization problem on arrangements. Cybernetics and Systems Analysis. 2013. Vol. 49, N 1. Ð. 86–97. 19. Iemets O.O., Barbolina T.M. Properties of the linear unconditional problem of combinatorial optimization on arrangements under probabilistic uncertainty. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 285–295. 20. Iemets O.O., Barbolina T.M. Solving linear unconstrained problems of combinatorial optimization on arrangements under stochastic uncertainty. Cybernetics and Systems Analysis. 2016. Vol. 52, N 3. P. 457–466. 21. ªìåöü Î.Î., ׳ë³ê³íà Ò.Â. Ïðî ê³ëüê³ñòü åëåìåíò³â â çàãàëüíèõ ìíîæèíàõ ðîçì³ùåíü òà ïîë³ðîçì³ùåíü. ³ñíèê ×åðêàñüêîãî óí³âåðñèòåòó. Ñåð. Ïðèêëàäíà ìàòåìàòèêà. ²íôîðìàòèêà. 2015. ¹ 18 (351). Ñ. 3–10. 22. Guilband G.Th., Rosenstiehl P. Analyse algebrique d’un scrutin. Mathematiques et Sciences Humaines. 1963. T. 4. P. 9–33. URL: http://www.numdam.org/item?id=MSH_1963_4_9_0.1. 23. Gaiha P., Gupta S.K. Adjacent vertices on permutation. SIAM J. Appl. Math. 1977. T. 32, N 2. P. 323–327. 24. Áîëîòàøâèëè Ã.Ã. Î ãðàíÿõ ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà. Ñîîáùåíèÿ ÀÍ Ãðóçèè. 1986. Ò. 121, ¹ 2. Ñ. 281–284. 25. Rahmania N. Distance vectorielles entremots. Mathematiques et Sciences Humaines. 1987. T. 97. P. 67–78. URL: http://www.numdam.org/item?id=MSH_1987_97_67_0. 26. Vonarnim Annelie, Faigle Ulrich, Schrader Rainer. The permutahedron of series-parallel posets. Discrete Applied Mathematics. 1990. Vol. 28. P. 3–9. 27. Concini C., Procesi C. Wonderful models for subspace arrangements. Selecta Math. (N.S.). 1995. Vol. 1. P. 1–23. 28. Postnikov A., Stanley R.P. Deformations of Coxeter hyperplane arrangements. Journal of Combinatorial Theory. Special issue dedicated to G.-C. Rota. Ser. A 91. 2000. Nos. 1–2. P. 544–597. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5 137 29. Postnikov A. Permutohedra, associahedra, and beyond. URL: http://arXiv:math/0507163v1[math.CO] . 2005. 59 p. 30. Baumeister B., Haase C., Nill B., Pattenholz A. On permutation polytopes. URL: http://arXiv:/0709.1615v1[math.CO], 2007. 22 p. 31. Hwang F.K., Lee J.S., Rothblum U.G. Equivalence of permutation polytopes corresponding to strictly supermodular functions. Discrete Applied Mathematics. 2008. Vol. 156. P. 2336–2343. 32. Èñà÷åíêî À.Í., Èñà÷åíêî ß.À. Íàñëåäîâàíèå ãèïåðãðàíåé â çàäà÷àõ íà ïåðåñòàíîâêàõ. Ìåæäóíàð. êîíãðåññ ïî èíôîðìàòèêå: èíôîðìàöèîííûå ñèñòåìû è òåõíîëîãèè: Ìàòåðèàëû ìåæäóíàð. íàó÷. êîíãðåññà (Ðåñïóáëèêà Áåëàðóñü, Ìèíñê, 31 îêòÿáðÿ – 3 íîÿáðÿ 2011 ãîäà). ×. 2. Ìèíñê: ÁÃÓ, 2011. Ñ. 279–282. 33. Croitoru D. , Oh SuHo, Postnikov A. Poset verctors and generalized permutohedra. URL: http://arXiv:/1309.1994v1[math.CO] , 2013. 13 p. Íàäiéøëà äî ðåäàêö³¿ 14.07.2017 ªìåöü Î.Î., ªìåöü Îë-ðà Î., Ïîëÿêîâ ².Ì. ÊÐÈÒÅÐ²É ÐÅÁÐÀ ÇÀÃÀËÜÍÎÃÎ ÌÍÎÃÎÃÐÀÍÍÈÊÀ ÐÎÇ̲ÙÅÍÜ Àíîòàö³ÿ. Äîñë³äæåíî âëàñòèâîñò³ çàãàëüíîãî ìíîãîãðàííèêà ðîçì³ùåíü äëÿ çàäà÷ îïòèì³çàö³¿ íà ðîçì³ùåííÿõ: ðîçãëÿíóòî îïèñ ðåáðà çàãàëüíîãî ìíîãî- ãðàííèêà ðîçì³ùåíü ñèñòåìîþ ð³âíÿíü ³ íåð³âíîñòåé, ùî º ï³äñèñòåìîþ ñèñòå- ìè, ÿêà îïèñóº öåé ìíîãîãðàííèê. Îòðèìàíî êðèòåð³é ðåáðà çàãàëüíîãî ìíî- ãîãðàííèêà ðîçì³ùåíü, îïèñàíî éîãî âåðøèíè. Êëþ÷îâ³ ñëîâà: çàãàëüíèé ìíîãîãðàííèê ðîçì³ùåíü, êðèòåð³é ðåáðà, çàäà÷³ îïòèì³çàö³¿ íà ðîçì³ùåííÿõ. Iemets O.Ol., Yemets’ O.Ol., Polyakov ².Ì. CRITERION OF THE EDGE OF THE GENERAL POLYHEDRON OF ARRANGEMENTS Abstract. The properties of the general polyhedron of arrangements for optimization problems on arrangements are investigated in the paper. An edge of the general polyhedron of arrangements is described by the system of equations and inequalities that is a subsystem of the system describing this polyhedron. The criterion of the edge of the general polyhedron of arrangements is obtained and its vertices are described. Keywords: general polyhedron of arrangements, edge criterion, optimization on arrangements. Åìåö Îëåã Àëåêñååâè÷, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, çàâåäóþùèé êàôåäðîé Ïîëòàâñêîãî óíèâåðñèòåòà ýêîíîìèêè è òîðãîâëè, e-mail: yemetsli@ukr.net. Åìåö Àëåêñàíäðà Îëåãîâíà, êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò êàôåäðû Ïîëòàâñêîãî óíèâåðñèòåòà ýêîíîìèêè è òîðãîâëè, e-mail: yemets2008@ukr.net. Ïîëÿêîâ Èâàí Ìèõàéëîâè÷, àñïèðàíò Ïîëòàâñêîãî óíèâåðñèòåòà ýêîíîìèêè è òîðãîâëè. 138 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 5

Схожі ресурси