Построение гамильтонова пути в графах перестановочных многогранников
Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, як...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45121 |
| 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: | Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859618022289833984 |
|---|---|
| author | Донец, Г.А. Колечкина, Л.Н. |
| author_facet | Донец, Г.А. Колечкина, Л.Н. |
| citation_txt | Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, який використовує цю властивість побудови гамільтонового шляху в графі, що відповідає множині переставлень для n = 4.
The problem of finding an extremum of a linear function on a set of permutations is considered. The polyhedron of admissible values on the permutation set is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path on the graph corresponding to the set of permutations for n = 4.
|
| first_indexed | 2025-11-28T23:05:45Z |
| format | Article |
| fulltext |
ÓÄÊ 519.1
Ã.À. ÄÎÍÅÖ, Ë.Í. ÊÎËÅ×ÊÈÍÀ
ÏÎÑÒÐÎÅÍÈÅ ÃÀÌÈËÜÒÎÍÎÂÀ ÏÓÒÈ
 ÃÐÀÔÀÕ ÏÅÐÅÑÒÀÍÎÂÎ×ÍÛÕ ÌÍÎÃÎÃÐÀÍÍÈÊÎÂ
Êëþ÷åâûå ñëîâà: ïîëèýäðàëüíàÿ êîìáèíàòîðèêà, êîìáèíàòîðíûå ìíîæåñòâà,
êîìáèíàòîðíîå ìíîæåñòâî ïåðåñòàíîâîê, ïåðåñòàíîâî÷íûé ìíîãîãðàííèê, ãðà-
ôû, ãèïåðãðàíè, ãàìèëüòîíîâ ïóòü.
ÂÂÅÄÅÍÈÅ
Ãðàôû ìíîãîãðàííèêîâ îáëàäàþò ìíîãèìè ñïåöèôè÷åñêèìè ñâîéñòâàìè: ïðè èõ
èçó÷åíèè âîçíèêàåò ìíîæåñòâî çàäà÷, ïðåäñòàâëÿþùèõ èíòåðåñ íå òîëüêî äëÿ òå-
îðèè ãðàôîâ, êîìáèíàòîðèêè, òîïîëîãèè, íî è äëÿ òåîðèè ëèíåéíîãî ïðîãðàììè-
ðîâàíèÿ. Ó. Ãàìèëüòîí ïîñòðîèë ïðîñòûå öèêëû, ñîäåðæàùèå êàæäóþ âåðøèíó
äîäåêàýäðà. Ïîçæå áûëî âûñêàçàíî ïðåäïîëîæåíèå, ÷òî êàæäûé ïîëèýäðàëüíûé
ãðàô ÿâëÿåòñÿ ãàìèëüòîíîâûì. Ýòî îáóñëîâèëî ïîÿâëåíèå ìíîæåñòâà ðàáîò, ïîñâÿ-
ùåííûõ óñòàíîâëåíèþ ãàìèëüòîíîâîñòè ïîëèýäðàëüíûõ ãðàôîâ. Ñëåäóåò îòìåòèòü,
÷òî ñâîéñòâà ãðàôîâ è ìíîãîãðàííèêîâ øèðîêî èñïîëüçóþòñÿ ïðè èññëåäîâàíèè
ìíîãèõ êëàññîâ êîìáèíàòîðíûõ ìîäåëåé, äëÿ ðàçðàáîòêè íîâûõ ìåòîäîâ èõ ðå-
øåíèÿ [1–10]. Íàèáîëåå èíòåðåñíûå ðåçóëüòàòû ïîëó÷åíû äëÿ ìíîãîãðàííèêîâ
çàäà÷è îá óïàêîâêå, çàäà÷è î ìàêñèìàëüíîì ïàðîñî÷åòàíèè ãðàôà, çàäà÷è êîììè-
âîÿæåðà, çàäà÷è î ðþêçàêå è ò.ï. Âàæíóþ ðîëü â äèñêðåòíîé îïòèìèçàöèè èãðà-
åò çàäà÷à î êîììèâîÿæåðå. Äîïóñòèìàÿ îáëàñòü îïðåäåëåíèÿ äàííîé çàäà÷è
îïèñûâàåòñÿ ìíîãîãðàííèêîì ãàìèëüòîíîâûõ öèêëîâ è êîíòóðîâ. Âî ìíîãèõ èñ-
òî÷íèêàõ èññëåäóåòñÿ âîçìîæíîñòü ëèíåàðèçàöèè ýòîé çàäà÷è, ò.å. ïîñòðîåíèå
âûïóêëîé îáîëî÷êè åå äîïóñòèìûõ ðåøåíèé. Èñïîëüçîâàíèå èíôîðìàöèè î ñòðóê-
òóðå âûïóêëîé îáîëî÷êè äîïóñòèìûõ ðåøåíèé, ÿâëÿþùåéñÿ îñíîâàíèåì äëÿ
ìíîãèõ ìåòîäîâ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷, — îäèí èç ñàìûõ óñïåøíûõ íà
ñåãîäíÿøíèé äåíü ïîäõîäîâ ê ðåøåíèþ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
Êîìáèíàòîðíàÿ òåîðèÿ ìíîãîãðàííèêîâ èçó÷àåò ýêñòðåìàëüíûå ñâîéñòâà ìíîãî-
ãðàííèêîâ, ðàññìàòðèâàÿ ìíîæåñòâî åãî ãðàíåé âñåõ ðàçìåðíîñòåé êàê íåêîòî-
ðûé êîìïëåêñ. Íî ïðè ðåøåíèè òàêèõ çàäà÷ âîçíèêàþò ïðîáëåìû, ñâÿçàííûå ñî
ñëîæíîñòüþ ìàòåìàòè÷åñêèõ ìîäåëåé, áîëüøèì îáúåìîì èíôîðìàöèè è äðóãèå,
òàê êàê áîëüøèíñòâî çàäà÷ íà êîìáèíàòîðíûõ ìíîæåñòâàõ NP-ïîëíûå. Ñëåäóåò
îòìåòèòü òåñíóþ ñâÿçü ñâîéñòâ ìíîãîãðàííèêîâ è èõ ãðàôîâ ñ ïðîáëåìàìè îöåí-
êè ÷èñëà èòåðàöèé è ýôôåêòèâíîñòè àëãîðèòìîâ òàêîãî òèïà â çàäà÷àõ ëèíåéíî-
ãî ïðîãðàììèðîâàíèÿ.
Áîëüøèíñòâî çàäà÷ íà ãðàôàõ êàñàåòñÿ îïðåäåëåíèÿ êîìïîíåíò ñâÿçíîñòè, ïî-
èñêà ìàðøðóòîâ, ðàññòîÿíèé è ò.ï. Îäíàêî ïðè ðåøåíèè ðåàëüíûõ çàäà÷ ñîîòâå-
òñòâóþùèå èì ãðàôû âåñüìà âåëèêè, à àíàëèç âîçìîæåí ëèøü ñ ïðèâëå÷åíèåì ñî-
âðåìåííîé âû÷èñëèòåëüíîé òåõíèêè. Ïîýòîìó êîíå÷íàÿ öåëü ðàññìîòðåíèÿ êàæäîé
èç çàäà÷ — îïèñàíèå è ðåàëèçàöèÿ ïðàêòè÷åñêîãî àëãîðèòìà ðåøåíèÿ äàííîé çàäà-
÷è íà ÏÝÎÌ. Íà ñåãîäíÿøíèé äåíü â îáëàñòè èññëåäîâàíèÿ ðàçëè÷íûõ êëàññîâ
êîìáèíàòîðíûõ ìîäåëåé è ðàçðàáîòêè íîâûõ ìåòîäîâ èõ ðåøåíèÿ ïîëó÷åíû
ñóùåñòâåííûå ðåçóëüòàòû.
Íàñòîÿùàÿ ðàáîòà ïðîäîëæàåò èññëåäîâàíèÿ êîìáèíàòîðíûõ çàäà÷ íà ðàç-
ëè÷íûõ ìíîæåñòâàõ ïåðåñòàíîâîê, ñî÷åòàíèé, ïîëèïåðåñòàíîâîê, ïðåäñòàâëåííûõ
â [4, 5, 10–13]. Íà îñíîâàíèè óñòàíîâëåííîé âçàèìîñâÿçè ìåæäó çàäà÷àìè êîìáè-
íàòîðíûõ ìíîæåñòâ è ãðàôàìè ìíîãîãðàííèêîâ ñîîòâåòñòâóþùèõ ìíîæåñòâ
â ñòàòüå èçó÷åíû íåêîòîðûå ñòðóêòóðíûå ñâîéñòâà äîïóñòèìîé îáëàñòè, à òàêæå
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
© Ã.À. Äîíåö, Ë.Í. Êîëå÷êèíà, 2010
ñôîðìóëèðîâàí ìåòîä ðåøåíèÿ êîìáèíàòîðíîé çàäà÷è, îñíîâàííûé íà ïðèìåíåíèè
ãðàôîâ.  ÷àñòíîñòè, â ðàáîòå [4] îïèñàí ñïîñîá ïîñòðîåíèÿ ãàìèëüòîíîâà ïóòè
âíóòðè ãèïåðãðàíåé.  íàñòîÿùåé ðàáîòå ñòàâèòñÿ çàäà÷à ïîñòðîåíèÿ ãàìèëüòîíîâà
ïóòè ìåæäó ãèïåðãðàíÿìè, ò.å. ðàññìàòðèâàåòñÿ, êàê ïîñòðîèòü ãàìèëüòîíîâ ïóòü,
«âêëåèâ» ê äâóì ñëîÿì òðåòèé, åñëè èçâåñòåí ãàìèëüòîíîâ ïóòü âíóòðè äâóõ ñëîåâ.
1. ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Îáùàÿ çàäà÷à êîìáèíàòîðíîé îïòèìèçàöèè ñîñòîèò â îòûñêàíèè ýêñòðåìóìà
ëèíåéíîé öåëåâîé ôóíêöèè íà ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå ïðè íàëè÷èè
äîïîëíèòåëüíûõ ëèíåéíûõ îãðàíè÷åíèé. Êàê ïðàâèëî, ïðè ðåøåíèè êëàññà òà-
êèõ çàäà÷ èññëåäóåòñÿ âîçìîæíîñòü èõ ëèíåàðèçàöèè, ò.å. ïîñòðîåíèÿ âûïóê-
ëîé îáîëî÷êè äîïóñòèìûõ ðåøåíèé çàäà÷è. Ïåðåõîä îò ïàðàìåòðè÷åñêîé ôîð-
ìû çàäàíèÿ âûïóêëîãî ìíîãîãðàííèêà ê àíàëèòè÷åñêîé èìååò áîëüøîå çíà÷å-
íèå äëÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè, òàê êàê ïîçâîëÿåò ñôîðìóëèðîâàòü èõ
â òåðìèíàõ ëèíåéíîãî ïðîãðàììèðîâàíèÿ, íî, êàê ïîêàçûâàåò ïðàêòèêà, ýòî
íå âñåãäà îïðàâäàíî. Ïîäçàäà÷åé ñôîðìóëèðîâàííîé âûøå çàäà÷è ìîæåò áûòü
îïðåäåëåíèå ãàìèëüòîíîâà ïóòè, êîòîðûé îòðàæàåò èçìåíåíèå çíà÷åíèÿ öåëå-
âîé ôóíêöèè íà ìíîæåñòâå ïåðåñòàíîâîê. Ìíîãîãðàííèê ãàìèëüòîíîâûõ öèê-
ëîâ ãðàôà ÿâëÿåòñÿ ãðàíüþ ìíîãîãðàííèêà ãàìèëüòîíîâûõ öèêëîâ ïîëíîãî
ãðàôà. Ðàññìîòðèì èç [4] èçâåñòíûé ãðàô ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà.
Óêàæåì íà îñíîâíîå ñâîéñòâî ýòîãî ãðàôà. Îí îòîáðàæàåò ÷àñòè÷íóþ óïîðÿäî-
÷åííîñòü ìíîæåñòâà ïåðåñòàíîâîê äëÿ n � 4 îòíîñèòåëüíî çíà÷åíèé ïðîèçâîëü-
íîé ëèíåéíîé ôóíêöèè f x c x c x c x c x( ) � � � �1 1 2 2 3 3 4 4 , ãäå c c c c1 2 3 4� � � ,
à íàáîð x x x x x� ( , , , )1 2 3 4 ïðîáåãàåò ìíîæåñòâî âñåõ ïåðåñòàíîâîê Pn . Â ãðàôå
äâå âåðøèíû, ñîîòâåòñòâóþùèå äâóì ïåðåñòàíîâêàì, ñìåæíûå, åñëè îòëè÷àþò-
ñÿ îäíà îò äðóãîé ïîçèöèÿìè òîëüêî äâóõ ýëåìåíòîâ. Äðóãèìè ñëîâàìè, äâå
ïåðåñòàíîâêè ñìåæíûå, åñëè îíè ïîëó÷àþòñÿ îäíà èç äðóãîé ñ ïîìîùüþ òðàíñ-
ïîçèöèè äâóõ ýëåìåíòîâ.
Ëåììà 1. Èç äâóõ ñìåæíûõ ïåðåñòàíîâîê ôóíêöèÿ f x( ) ïðèíèìàåò íå ìåíüøåå
(áîëüøåå) çíà÷åíèå äëÿ òîé, â êîòîðîé ìàêñèìàëüíûé èç äâóõ ðàçëè÷àþùèõñÿ ýëå-
ìåíòîâ íàõîäèòñÿ ñïðàâà.
Ýòà ëåììà ñïðàâåäëèâà äëÿ ïðîèçâîëüíîãî n. Äåéñòâèòåëüíî, ïóñòü
p x x x x xk l n1 1 2� ( , ,... , ,... , ,... , ) è p x x x x xl k n2 1 2� ( , ,... , ,... , ,... , ) — äâå ïåðåñòà-
íîâêè, êîòîðûå îòëè÷àþòñÿ ïîëîæåíèåì äâóõ ýëåìåíòîâ: xk è xl , ïðè ýòîì ïóñòü
x xl k� . Ðàññìîòðèì ðàçíîñòü çíà÷åíèé f p f p( ) ( )1 2� . Ïîñëå óïðîùåíèé ïîëó÷èì,
÷òî îíà ðàâíà c x x c x x c c x xk k l l l k l k l k( ) ( ) ( )( )� � � � � � . Òàê êàê äëÿ l k� âñåãäà
c cl k� , òî ýòî âûðàæåíèå íå ìåíüøå íóëÿ, ÷òî è ïîäòâåðæäàåò ñïðàâåäëèâîñòü
ëåììû.
 ãðàôå íà ðèñ. 1 âñå ñìåæíûå ïåðåñòàíîâêè ñîåäèíÿþòñÿ äóãàìè â ñîîòâåò-
ñòâèè ñ ëåììîé 1. Àíàëîãè÷íî ñòðîèòñÿ ãðàô ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà
G Pn( ) äëÿ ïðîèçâîëüíîãî n.
Ñëåäñòâèå. Ìàêñèìàëüíîå çíà÷åíèå ëèíåéíàÿ ôóíêöèÿ f x( ) íà ïåðåñòàíîâî÷-
íîì ìíîãîãðàííèêå G Pn( ) ïðèíèìàåò â ïåðåñòàíîâêå ( , ,... , )1 2 n , à ìèíèìàëüíîå —
â ïåðåñòàíîâêå ( , , ... , , )n n �1 2 1 .
Äåéñòâèòåëüíî, ëþáàÿ ïåðåñòàíîâêà, îòëè÷íàÿ îò ïåðâîé, áóäåò íà êàêîì-òî
j-ì ìåñòå èìåòü ÷èñëî, ìåíüøåå j. Ïî ëåììå 1 ýòî îçíà÷àåò, ÷òî çíà÷åíèå ôóíêöèè
â ýòîé ïåðåñòàíîâêå âñåãäà ìåíüøå èñõîäíîãî, ÷òî è òðåáîâàëîñü äîêàçàòü. Ýòè æå
ðàññóæäåíèÿ ìîæíî ïðèâåñòè è îòíîñèòåëüíî ìèíèìàëüíîãî çíà÷åíèÿ ôóíêöèè.
Äëÿ ïîäîáíûõ ãðàôîâ äîñòàòî÷íî ÷àñòî âîçíèêàåò ñëåäóþùàÿ çàäà÷à: íàéòè
ìíîæåñòâî ïåðåñòàíîâîê, â êîòîðûõ çíà÷åíèå öåëåâîé ôóíêöèè ðàâíî çàäàííîìó
çíà÷åíèþ, ò.å.
x f x
x Pn
* ( )�
arg , (1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 11
ãäå f x y( )* � . Òàêæå èìååò
ñìûñë ðàññìàòðèâàòü àíàëî-
ãè÷íóþ çàäà÷ó, ãäå íå âñåãäà
ñóùåñòâóþò ïåðåñòàíîâêè,
â êîòîðûõ öåëåâàÿ ôóíêöèÿ
ïðèíèìàåò çàäàííîå çíà÷å-
íèå. Òîãäà ñôîðìóëèðîâàí-
íàÿ âûøå ïðîáëåìà ïðåäñòà-
íåò êàê çàäà÷à: îïðåäåëèòü
ìíîæåñòâî ïàð ïåðåñòàíîâîê
( , )x x , äëÿ êîòîðûõ ïðè çà-
äàííîì y
x f x
x f x
f x y
f x y
�
�
�
�
arg min
arg
( )
( )
( ),
max ( ).
(2)
2. ÏÎÄÕÎÄ Ê ÐÅØÅÍÈÞ
Î÷åâèäíî, ÷òî îáå çàäà÷è
ìîæíî ðåøèòü, åñëè íà ãðà-
ôå G Pn( ) äîñòðîèòü ìíîæå-
ñòâî äóã ìåæäó íåñìåæíûìè
ïåðåñòàíîâêàìè, ïîçâîëÿþ-
ùåå ïðîéòè ïî äóãàì ïóòü
îò íà÷àëüíîé âåðøèíû, ãäå
f x( ) ïðèíèìàåò ìàêñèìàëü-
íîå çíà÷åíèå, ê êîíå÷íîé,
ãäå f x( ) ïðèíèìàåò ìèíè-
ìàëüíîå çíà÷åíèå. Ïðè ýòîì
íåîáõîäèìî ïðîéòè âñå
îñòàëüíûå âåðøèíû ãðàôà.
Ýòîò ïóòü è íàçûâàåòñÿ ãà-
ìèëüòîíîâ. Åñëè èçâåñòíà
ïîñëåäîâàòåëüíîñòü ïåðåñòà-
íîâîê, ÷åðåç êîòîðûå îí
ïðîõîäèò, òî ñ ïîìîùüþ äè-
õîòîìèè ãàìèëüòîíîâà ïóòè,
âû÷èñëÿÿ çíà÷åíèÿ ôóíêöèè
â ñîîòâåòñòâóþùåé ïåðåñòà-
íîâêå, âñåãäà ìîæíî ëîêàëè-
çîâàòü ïðîèçâîëüíîå çíà÷åíèå öåëåâîé ôóíêöèè f x( ) .
Ëåììà 2. Ñëîæíîñòü ðåøåíèÿ çàäà÷ (1), (2) îöåíèâàåòñÿ ñâåðõó ïîëèíîìîì íå
âûøå âòîðîé ñòåïåíè.
Ïîñêîëüêó ÷èñëî âåðøèí ãðàôà G Pn( ) (ïåðåñòàíîâîê) ðàâíî n !, òî ñëîæíîñòü
âû÷èñëåíèé ïðè äèõîòîìèè îöåíèâàåòñÿ âåëè÷èíîé R n i
i
n
� �
�
log ! log2 2
2
. Äëÿ åå
îïðåäåëåíèÿ ðàññìîòðèì ãðàôèê ôóíêöèè y x� log 2 íà ðèñ. 2.
Ïëîùàäü âñåõ ïðÿìîóãîëüíèêîâ, âîçâûøàþùèõñÿ íàä êðèâîé y, è ñ îñíîâàíè-
åì íà îñè Ox , ðàâíà S i R
i
n
� �
�
log 2
2
. Àíàëîãè÷íî ïëîùàäü âñåõ ïðÿìîóãîëüíèêîâ,
ïîñòðîåííûõ ïîä êðèâîé y (çàøòðèõîâàííûõ), ðàâíà S i R n
i
n
� � �
�
�
log log2
2
1
2 .
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
8
22
24131423
2143 4123 4213
1234
2134
1324 2314
3124 3214
1243
1 3
2
5
4 6
7 9 11
10 12
34212431
3241 4231 4321
1342
3142
1432 3412
4132 4312
2341
13 15
14
17
16 18
19 21 23
20 24
D
C
B
A
Ðèñ. 1
1 2 3 4 5 6 7 8 n � 1 n x
y = log2x
1
2
3
Ðèñ. 2
Èç ðèñóíêà ìîæíî óâèäåòü, ÷òî ïëîùàäü, îãðàíè÷åííàÿ êðèâîé y x� log 2 è îñüþ
àáñöèññ, óäîâëåòâîðÿåò îãðàíè÷åíèÿì
R n xdx R
n
� � ��log log2 2
1
. (3)
Çíà÷åíèå íåîïðåäåëåííîãî èíòåãðàëà ðàâíî [ ln ] / lnx x x� 2. Òàê êàê n n�� log 2 ,
òî ïîëó÷èì îöåíêó R n� 2 , ÷òî è òðåáîâàëîñü.
Ïåðåéäåì íåïîñðåäñòâåííî ê ïîñòðîåíèþ ãàìèëüòîíîâà ïóòè â ãðàôå G P( )4 .
Äëÿ óäîáñòâà îïåðèðîâàíèÿ ïåðåñòàíîâêàìè ïðîíóìåðóåì èõ îò 1 äî 24, êàê ïîêà-
çàíî íà ðèñ. 1, è íàçîâåì èõ òî÷êàìè (âåðøèíàìè) pi ( , , , )i � 1 2 24� , íàïðèìåð
p16 4 1 3 2� ( , , , ) . Âåêòîð êîýôôèöèåíòîâ ôóíêöèè f x( ) îáîçíà÷èì c c c cn� ( , , , )1 2 � ,
íà ðèñ. 1 ýòî c c c c c� ( , , , )1 2 3 4 . Òîãäà çíà÷åíèå ôóíêöèè f x( ) â ïðîèçâîëüíîé òî÷êå
pi ( )1 24� �i îïðåäåëÿåòñÿ êàê ñêàëÿðíîå ïðîèçâåäåíèå f p p ci i( ) ( , )� . Ïîêàæåì,
÷òî ãðàô G P( )4 ìîæíî ïîñòðîèòü èíäóêòèâíûì ñïîñîáîì, íà÷èíàÿ ñ äâóõ ïåðâûõ
ïåðåñòàíîâîê. Ïðåäñòàâèì, ÷òî âåðøèíû p1 è p2 ñîñòàâëÿþò ïîäãðàô ãðàôà G P( )4 ,
ó êîòîðîãî ôèêñèðîâàíû äâà ïîñëåäíèõ ýëåìåíòà: 3 è 4. Âåðøèíà p
2
îáðàçîâàíà
èç p1 òðàíñïîçèöèåé ýëåìåíòîâ 1 è 2, ïîýòîìó ñîãëàñíî ëåììå 1 f p f p( ) ( )1 2� .
Åñëè òåïåðü â âåðøèíàõ p1 è p2 ïîìåíÿòü ìåñòàìè ýëåìåíòû 2 è 3, òî ïîëó÷èì
âåðøèíû p3 è p4 , ó êîòîðûõ îñòàåòñÿ ñîîòíîøåíèå f p f p( ) ( )3 4� , êðîìå òîãî, ïî
ëåììå 1 èìååì f p f p( ) ( )1 3� è f p f p( ) ( )2 4� . Àíàëîãè÷íî òðàíñïîçèöèåé ýëå-
ìåíòîâ 1 è 2 â âåðøèíàõ p3 è p4 áóäåì èìåòü âåðøèíû p5 è p6 . Â ðåçóëüòàòå
ýòèõ äåéñòâèé ïîëó÷èì ïîäãðàô A , êîòîðûé ñîäåðæèò âñå ïåðåñòàíîâêè P4 ñ ôèê-
ñèðîâàííûì ÷åòâåðòûì ýëåìåíòîì x4 4� . Î÷åâèäíî, ÷òî â ïîäãðàôå A f x( ) ïðèíè-
ìàåò ìàêñèìàëüíîå çíà÷åíèå â âåðøèíå p1 è ìèíèìàëüíîå — â âåðøèíå p6 . Îäíà-
êî äëÿ ïîñòðîåíèÿ ãàìèëüòîíîâà ïóòè â ýòîì ïîäãðàôå äóã íå õâàòàåò. Ìîæíî ïî-
ñòðîèòü åùå îäíó äóãó èç âåðøèíû p2 ê âåðøèíå p5 , òàê êàê ýòè ïåðåñòàíîâêè
îòëè÷àþòñÿ ìåæäó ñîáîé òðàíñïîçèöèåé ÷èñåë 1 è 3, íî ýòîãî òàêæå íåäîñòàòî÷íî
(ýòà äóãà îòìå÷åíà ïóíêòèðîì).
Âîçüìåì âñå ïåðåñòàíîâêè ïîäãðàôà A è îäíîâðåìåííî ñäåëàåì â íèõ òðàíñïî-
çèöèþ ÷èñåë 3 è 4.  ðåçóëüòàòå ïîëó÷èì ïîäãðàô B , êîòîðûé ñîäåðæèò âñå òå æå
ïåðåñòàíîâêè P4 , ó êîòîðûõ ôèêñèðîâàí ÷åòâåðòûé ýëåìåíò x4 3� . Ïî ëåììå 1 ñî-
îòâåòñòâóþùèå âåðøèíû ïîäãðàôîâ A è B ñìåæíûå è ñîåäèíÿþùèå èõ äóãè èäóò
ñâåðõó (îò ïîäãðàôà A) âíèç (ê ïîäãðàôó B). Î÷åâèäíî, ÷òî âíóòðåííÿÿ îðèåíòàöèÿ
ïîäãðàôà B ñîõðàíÿåò âíóòðåííþþ îðèåíòàöèþ ïîäãðàôà A . Åñëè òåïåðü â ïîäãðà-
ôå B âî âñåõ ïåðåñòàíîâêàõ ñäåëàòü òðàíñïîçèöèþ ÷èñåë 2 è 3, òî â ðåçóëüòàòå ïî-
ëó÷èì ïîäãðàô C , ñîäåðæàùèé âñå òå ïåðåñòàíîâêè P4 , ó êîòîðûõ çàôèêñèðîâàí
÷åòâåðòûé ýëåìåíò x4 2� . Î÷åâèäíî, ÷òî ýòîò ïîäãðàô òàêæå ñîõðàíÿåò âíóòðåí-
íþþ îðèåíòàöèþ ïîäãðàôà B (à òàêæå ïîäãðàôà A) è â êàæäóþ åãî âåðøèíó âõîäèò
äóãà îò ñîîòâåòñòâóþùåé âåðøèíû ïîäãðàôà B . È, íàêîíåö, åñëè â ïîäãðàôå C â
êàæäîé ïåðåñòàíîâêå ñäåëàåì òðàíñïîçèöèþ ÷èñåë 1 è 2, òî ïîëó÷èì ïîäãðàô D,
êîòîðûé ñîäåðæèò âñå ïåðåñòàíîâêè P4 ñ ôèêñèðîâàííûì ÷åòâåðòûì ýëåìåíòîì
x4 1� .
Âñå ÷åòûðå ïîäãðàôà A B C D, , , ñîñòàâëÿþò ãðàô G P( )4 . Ìîæíî ãîâîðèòü, ÷òî
îí ïîñòðîåí èíäóêòèâíûì ïóòåì, íà÷èíàÿ ñ äâóõ âåðøèí: p1 è p2 . Ñíà÷àëà ýòè
âåðøèíû êàê áû ïðîåöèðîâàëèñü ïîñëåäîâàòåëüíî äâàæäû, îáðàçóÿ ïîäãðàô A . Çà-
òåì ïîäãðàô A ïðîåöèðîâàëñÿ òðèæäû, îáðàçóÿ âåñü ãðàô G P( )4 .
Âåðíåìñÿ ê âîïðîñó î ïîñòðîåíèè ãàìèëüòîíîâà ïóòè â ïîäãðàôå A . Ïðèíöè-
ïèàëüíî âàæíî óñòàíîâèòü ñîîòíîøåíèå çíà÷åíèé ôóíêöèé â òî÷êàõ p2 è p3 ,
à òàêæå â òî÷êàõ p4 è p5 . Ðàññìîòðèì ñîîòâåòñòâóþùèå ðàçíîñòè, êîòîðûå îáîçíà-
÷èì � f :
�
�
f f p f p p c p c c c c
f
( , ) ( ) ( ) ( , ) ( , ) ;
( ,
2 3 2
4 5
2 3 2 3 1 2 3� � � � � � �
) ( ) ( ) ( , ) ( , ) .� � � � � � �f p f p p c p c c c c4 5 4 5 1 2 32
(4)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 13
Îíè ñîâïàäàþò, ïîýòîìó åñëè çíà÷åíèå � f ( , )2 3 èçâåñòíî, òî ýòîãî äîñòàòî÷íî
äëÿ îïðåäåëåíèÿ ãàìèëüòîíîâà ïóòè â ïîäãðàôå A . Åñëè � f ( , )2 3 0� , òî ïîëó÷àåì
äóãè p p2 3 è p p4 5 , ÷òî îïðåäåëÿåò ãàìèëüòîíîâ ïóòü �1 1 2 3 4 5 6( ) ( , , , , , )A � .
Åñëè � f ( , )2 3 0� , òî ïîëó÷àåì äóãè p p3 2 è p p5 4 , ÷òî äàåò ãàìèëüòîíîâ ïóòü
� 2 1 3 2 5 4 6( ) ( , , , , , )A � .
Ââèäó òîãî, ÷òî ïðè ïðîåöèðîâàíèè ïîäãðàôà A íà ïîäãðàôû B , C è D ïåðâûå
òðè ýëåìåíòà â ïåðåñòàíîâêàõ ìåíÿþòñÿ, òî ñîîòíîøåíèÿ (4), ñïðàâåäëèâûå äëÿ
ïîäãðàôà A , íà ïîñëåäóþùèå ïîäãðàôû íå ïåðåíîñÿòñÿ. Ââåäåì îáîçíà÷åíèÿ:
�i i ic c i n� � � ��1 1 2 1( , , , )� . Ïóñòü � � � ��
�( , )1 2 2� n — âåêòîð, îòðàæàþùèé
îñîáåííîñòè çàäàííîé ëèíåéíîé ôóíêöèè: � �i i i� � �� 1 1 ( , , , )i n� �2 3 1� .  êàæ-
äîì ïîäãðàôå A B C D, , , ÷åòâåðòûé ýëåìåíò âñåõ ïåðåñòàíîâîê ôèêñèðîâàí, ïîýòî-
ìó ñòðóêòóðà ýòèõ ïîäãðàôîâ çàâèñèò òîëüêî îò ïåðâûõ òðåõ ýëåìåíòîâ, êîòîðûå
äëÿ îáùåãî ñëó÷àÿ îáîçíà÷èì ( , , )i i i1 2 3 , ãäå ( )i i i1 2 3� � .  êàæäîì ïîäãðàôå ýòè
ýëåìåíòû îïðåäåëÿþò ïåðâóþ âåðøèíó Pj , ãäå j � 1 6( )mod , ò.å. âåðøèíû p1, p7 ,
p13 , p19 . Åñëè äëÿ ïðîèçâîëüíîãî n èç G Pn( ) âûáðàòü ïîäãðàô, ó êîòîðîãî â ïåðå-
ñòàíîâêàõ çàôèêñèðîâàíî n � 4 ïîñëåäíèõ ýëåìåíòà ( , , , , )i i i i Nn n n5 6 1� � , òî ïî-
ëó÷èì ïîäãðàô òèïà G P( )4 , ó êîòîðîãî âìåñòî ýëåìåíòîâ 1–4 áóäóò ýëåìåíòû
i i i i1 2 3 4� � � .  ãðàôå A áóäåò çàôèêñèðîâàí ÷åòâåðòûé ýëåìåíò i4 , â ãðàôå B —
ýëåìåíò i3 , â ãðàôå C — ýëåìåíò i2 è â ãðàôå D — ýëåìåíò i1.
Îïðåäåëåíèå. Íàçîâåì ñòðóêòóðíûìè êîýôôèöèåíòàìè ãðàôà G P( )4 âåëè÷èíû
� A
i i
i i
�
�
�
2 1
3 2
; � B
i i
i i
�
�
�
2 1
4 2
; �C
i i
i i
�
�
�
3 1
4 3
; � D
i i
i i
�
�
�
3 2
4 3
. (5)
Äëÿ ïîñòðîåíèÿ ãàìèëüòîíîâà ïóòè â êàæäîì ïîäãðàôå íåîáõîäèìî âû÷èñëèòü
ðàçíîñòü çíà÷åíèé ôóíêöèè â âåðøèíàõ p
i
è p j , ãäå i � 2 6( )mod , j � 3 6( )mod ,
à òàêæå â âåðøèíàõ pk è pl , ãäå k � 4 6( )mod , l � 5 6( )mod . Â ïîäãðàôå A
p i i i ii � ( , , , )2 1 3 4 , p i i i ij � ( , , , )1 3 2 4 , ïîýòîìó
� f p c p c c i i c i i c i ii j( , ) ( , ) ( , ) ( )– ( ) (2 3 1 2 1 2 3 1 3 3 2� � � � � � � ) ,
( , ) ( ) ( ) .� f i i i i2 3 2 1 1 3 2 2� � � � �� �
(6)
Äóãà, ñîåäèíÿþùàÿ âåðøèíû p2 è p3 , áóäåò èìåòü íàïðàâëåíèå p p2 3 , åñëè
� f ( , )2 3 0� , à ýòî âîçìîæíî òîëüêî ïðè óñëîâèè
�
�
2
1
2 1
3 2
�
�
�
i i
i i
èëè � �1 1� / A . (7)
Ïðîäîëæàÿ òàêèå æå âû÷èñëåíèÿ îòíîñèòåëüíî âåðøèí p4 è p5 , ïîëó÷èì
� f i i i i( , ) ( ) ( )4 5 3 2 1 2 1 2� � � � �� � . Äóãà áóäåò èìåòü íàïðàâëåíèå p p4 5 , åñëè âû-
ïîëíÿþòñÿ óñëîâèÿ
�
�
2
1
3 2
2 1
�
�
�
i i
i i
èëè � �1 1� / A . (8)
Àíàëîãè÷íûå ðåçóëüòàòû ìîæíî ïîëó÷èòü è äëÿ äðóãèõ ïîäãðàôîâ. Íàïðèìåð,
äëÿ ïîäãðàôà C âû÷èñëèì � f ( , )14 15 . Äóãà áóäåò èìåòü íàïðàâëåíèå p p14 15 , åñëè
�
�
2
1
3 1
4 3
�
�
�
i i
i i
èëè � �1 � C ,
à äóãà p p16 17 áóäåò èìåòü ìåñòî, åñëè � �1 1� / C .
Ðàññìîòðèì íîìåðà âåðøèí ãðàôà G P( )4 â êëàññå âû÷åòîâ ïî mod 6, ãäå â êà-
÷åñòâå ïîëíîé ñèñòåìû âû÷åòîâ ïðèíÿòà ñèñòåìà (1, 2, 3, 4, 5, 6). Ïîñëåäíèå âû÷èñ-
ëåíèÿ äàþò ïðàâî óòâåðæäàòü, ÷òî ñïðàâåäëèâà òåîðåìà.
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Òåîðåìà 1. Â ïðîèçâîëüíîì ïîäãðàôå X ãðàôà G P( )4 , ãäå X A B C D { }, , , , ãà-
ìèëüòîíîâ ïóòü ïðîõîäèò â ïîñëåäîâàòåëüíîñòè:
( , , , , , )( )1 3 2 5 4 6 6mod , åñëè � � �1 1� min( , / )x x ;
( , , , , , )( ), max( , / ) ;
( , , , ,
1 2 3 4 5 6 6 1
1 2 3 4 5
1mod åñëè � � �� x x
, )( ), / ;6 6 1 11mod åñëè è� � � �x x x� � �
(9)
( , , , , , )( )1 2 3 5 4 6 6mod , åñëè � � �x x� �1 1/ è � x � 1.
Âñå ÷åòûðå ãàìèëüòîíîâû ïóòè ìîãóò èìåòü ìåñòî ïðè îäíîì óñëîâèè, åñëè
äëÿ �1 íè â îäíîì èç îãðàíè÷åíèé (9) íå âûïîëíÿåòñÿ ðàâåíñòâî. Åñëè âûïîëíÿåòñÿ
ðàâåíñòâî òèïà (7), òî f p f pi j( ( )) � , ðåáðî p pi j è åãî ìîæíî ïðîõîäèòü â ïðîèç-
âîëüíîì íàïðàâëåíèè, îòêóäà ñëåäóåò, ÷òî ïåðâûé è ÷åòâåðòûé ïóòè (èëè âòîðîé
è òðåòèé) ðàâíîïðàâíû. Åñëè æå âûïîëíÿåòñÿ ðàâåíñòâî òèïà (8), òî ýòî æå ñïðà-
âåäëèâî è îòíîñèòåëüíî ðåáðà p pi j , ãäå i � 4 6( )mod , à j � 5 6( )mod , è òîãäà ïåð-
âûé è òðåòèé ïóòè (èëè âòîðîé è ÷åòâåðòûé) ðàâíîïðàâíû. Îñîáûé ñëó÷àé âîçíèêà-
åò ïðè � x � 1. Åñëè �1 1� , òî âîçìîæíû òîëüêî ïåðâûå äâà ãàìèëüòîíîâû ïóòè.
Åñëè �1 1� , òî òîãäà âñå ÷åòûðå ïóòè ðàâíîïðàâíû, òàê êàê óêàçàííûå äâå ïàðû
âåðøèí ìîæíî îáúåäèíèòü è ïîëó÷èòü äâå âåðøèíû, à ãàìèëüòîíîâû ïóòè çàïè-
øóòñÿ â îáùåì âèäå [ , ( , ), ( , ), ] ( )1 2 3 4 5 6 6mod . Âî èçáåæàíèå ïîäîáíûõ íåîïðåäå-
ëåííîñòåé çíà÷åíèÿ �1, ðàâíûå êàêîìó-ëèáî ïàðàìåòðó � x (èëè 1/ � x), áóäåì ïðè-
ïèñûâàòü ê ëåâîìó èíòåðâàëó. Òåì ñàìûì äîáüåìñÿ, ÷òî â ïðîèçâîëüíîì ñëó÷àå äëÿ
êàæäîãî ïîäãðàôà A B C D, , , áóäåò âûáðàí îäèí (èç ÷åòûðåõ âîçìîæíûõ) ãàìèëüòî-
íîâ ïóòü. Îçíà÷àåò ëè ýòî, ÷òî äëÿ ïîñòðîåíèÿ ãàìèëüòîíîâà ïóòè â ãðàôå G P( )4
ïðèäåòñÿ ðàññìàòðèâàòü 44 âàðèàíòà ðàçëè÷íûõ ñî÷åòàíèé ýòèõ ïóòåé? Ðàññìîòðèì
ýòîò âîïðîñ ñ ó÷åòîì ñëåäóþùåãî óòâåðæäåíèÿ.
Ëåììà 3. Äëÿ ñòðóêòóðíèõ êîýôôèöèåíòîâ ïîäãðàôîâ A B C D, , , ñïðàâåäëèâû
ñîîòíîøåíèÿ:
(à) � � � � � �A B C B C D� � �; ; ;
(á) 1 1 1/ ; / ; /� � � � � � � � � � � �A B C B C D� � � .
Î÷åâèäíî, ÷òî (á) âûòåêàåò èç (à), ïîýòîìó äîñòàòî÷íî äîêàçàòü ñïðàâåäëè-
âîñòü (à). Ïåðâîå íåðàâåíñòâî ñëåäóåò èç òîãî, ÷òî ó äâóõ âåëè÷èí ÷èñëèòåëè îäè-
íàêîâû, à çíàìåíàòåëü áîëüøå ó � B , òàê êàê i i4 3� . Âòîðîå íåðàâåíñòâî ñïðàâåäëè-
âî ïîòîìó, ÷òî ó �C ÷èñëèòåëü áîëüøå, à çíàìåíàòåëü ìåíüøå, ÷åì ó � B . Òðåòüå
íåðàâåíñòâî âûòåêàåò èç òîãî, ÷òî ó äâóõ âåëè÷èí çíàìåíàòåëè îäèíàêîâûå, à ÷èñ-
ëèòåëü ó �C áîëüøå, òàê êàê i i3 1� áîëüøå i i2 1� .
Òåîðåìà 2. Ñóùåñòâóåò íå áîëüøå äåâÿòè ñîâìåñòíûõ âàðèàíòîâ ïîñòðîåíèÿ
ãàìèëüòîíîâûõ ïóòåé â ïîäãðàôàõ A B C D, , , ãðàôà ïåðåñòàíîâîê G P( )4 .
Ëåììà 2 ïîçâîëÿåò óñòàíîâèòü ÷àñòè÷íóþ óïîðÿäî÷åííîñòü äëÿ çíà÷åíèé � x è
1/ � x , ãäå X A B C D { }, , , . Ýòà çàâèñèìîñòü îòðàæåíà íà ðèñ. 3.
Åñëè íèêàêèå äâà èç ýòèõ
âîñüìè ïàðàìåòðîâ íå ðàâíû
ìåæäó ñîáîé, òî ïðè ðàçëè÷íûõ
èõ çíà÷åíèÿõ íà ÷èñëîâîé îñè
îíè îáðàçóþò äåâÿòü èíòåðâàëîâ,
â îäèí èç êîòîðûõ ïîïàäàåò êîí-
êðåòíîå çíà÷åíèå �1. Åñëè íåêî-
òîðûå èç ýòèõ ïàðàìåòðîâ ñîâïà-
äàþò, òî ÷èñëî èíòåðâàëîâ óìåíüøàåòñÿ. Ýòî è äîêàçûâàåò òåîðåìó. Ðàññìîòðèì
ïðèìåð.
Ïðèìåð. Ïóñòü i1 1� , i2 2� , i3 4� , i4 9� . Ïîëó÷àåì çíà÷åíèÿ � A � 1 2/ ,
� B � 1 7/ , �C � 3 5/ , � D � 2 5/ , 1 2/ � A � , � � � B � 7, 1 5 3/ /�C � , 1 5 2/ /� D � .
Ïîñëå óïîðÿäî÷åíèÿ èìååì âîçðàñòàþùóþ ïîñëåäîâàòåëüíîñòü òî÷åê íà ÷èñëîâîé
îñè (1 7/ , 2 5/ , 1 2/ , 3 5/ , 5 3/ , 5 2/ , 2, 7). Ðåçóëüòàòû ðàñ÷åòîâ ïðèâåäåíû â òàáë. 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 15
1�
B
� 1�
A
� 1�
D
� 1�
C
�C�
D� A� B�
Ðèñ. 3
Íåòðóäíî âèäåòü, ÷òî âñå ãàìèëüòîíîâû ïóòè â ïîäãðàôàõ îïðåäåëÿþòñÿ îäíî-
çíà÷íî, åñëè èçâåñòåí òîëüêî îäèí ïàðàìåòð — �1. Äëÿ ïîñòðîåíèÿ ãàìèëüòîíîâà
ïóòè íà âñåì ãðàôå G P( )4 íåîáõîäèìî èñïîëüçîâàòü âòîðîé ïàðàìåòð — �2 . Â çàâè-
ñèìîñòè îò ñî÷åòàíèé ýòîãî ïàðàìåòðà ñî çíà÷åíèÿìè ñòðóêòóðíûõ êîýôôèöèåíòîâ
ïîäãðàôîâ ïîëó÷àòñÿ ðàçëè÷íûå âàðèàíòû ãàìèëüòîíîâà ïóòè â ãðàôå G P( )4 . Åñëè
ýòè âàðèàíòû èçâåñòíû, òî òîãäà çàäà÷è íà ïåðåñòàíîâêàõ äëÿ n � 4 ìîæíî ñâîäèòü ê
ïîäçàäà÷àì íà ïîäãðàôàõ ñ ÷èñëîì âåðøèí n � 4 .
ÇÀÊËÞ×ÅÍÈÅ
Èññëåäóåòñÿ îáëàñòü äîïóñòèìûõ çíà÷åíèé íåêîòîðîé êîìáèíàòîðíîé çàäà÷è
îïòèìèçàöèè ñ èñïîëüçîâàíèåì òåîðèè ãðàôîâ. Ñòðîèòñÿ ãàìèëüòîíîâ ïóòü äëÿ
ïðîèçâîëüíîãî ìíîãîãðàííèêà ïåðåñòàíîâîê, êîòîðûé ÿâëÿåòñÿ ïîäãðàôîì ãðà-
ôà G P( )4 . Îáîñíîâûâàþòñÿ âîçìîæíîñòè èñïîëüçîâàíèÿ äàííûõ ðåçóëüòàòîâ äëÿ
ïîñòðîåíèÿ ýôôåêòèâíîãî ìåòîäà ðåøåíèÿ ñëîæíûõ êîìáèíàòîðíûõ çàäà÷ íà ìíî-
æåñòâå ïåðåñòàíîâîê. Äàëüíåéøåå ðàçâèòèå äàííîé ðàáîòû íàïðàâëåíî íà ðàçðà-
áîòêó íîâûõ ìåòîäîâ ðåøåíèÿ êîìáèíàòîðíûõ îïòèìèçàöèîííûõ çàäà÷ ñ ó÷åòîì
âõîäíûõ äàííûõ è äðóãèõ êîìáèíàòîðíûõ ìíîæåñòâ, à òàêæå èõ ìíîãîãðàííèêîâ
è ãðàôîâ ìíîãîãðàííèêîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ä î í å ö Ã . À . , Ø ó ë è í î ê È . Ý . Î ñëîæíîñòè àëãîðèòìîâ ïîèñêà â ãëóáèíó íà ìîäóëüíûõ ãðà-
ôàõ // Òåîð³ÿ îïòèìàëüíèõ ð³øåíü. — 2002. — ¹ 1. — Ñ. 105–110.
2. Ä î í å ö Ã . À . Àëãîðèòìû ðàñêðàñêè ïëîñêèõ ãðàôîâ // Òàì æå. — 2006. — ¹ 5. — C. 134–143.
3. Ä î í å ö à . À . , Ñ à ì å ð È . Ì . À ë ü ø à ë à ì å Ðåøåíèå çàäà÷è î ïîñòðîåíèè ëèíåéíîé ìîçàèêè //
Òàì æå. — 2005. — ¹ 4. — C. 15–24.
4. Ä î í å ö à . À . , Ê î ë å ÷ ê è í à Ë . Í . Ìåòîä óïîðÿäî÷åíèÿ çíà÷åíèé ëèíåéíîé ôóíêöèè íà ìíî-
æåñòâå ïåðåñòàíîâîê // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009 — ¹ 2. — Ñ. 50–61.
5. Ä î í å ö à . À . , Ê î ë å ÷ ê è í à Ë . Í . Îá îäíîì ïîäõîäå ê ðåøåíèþ êîìáèíàòîðíîé çàäà÷è îïòè-
ìèçàöèè íà ãðàôàõ // Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. — 2009 — ¹ 3. — Ñ. 34–42.
6. Ð û á í è ê î â Ê . À . Ââåäåíèå â êîìáèíàòîðíûé àíàëèç. — Ì:. Èçä-âî Ìîñêîâ. óí-òà, 1985. — 308 ñ.
7. Ð î ì à í î â ñ ê è é È . Â . Äèñêðåòíûé àíàëèç. — Ì:. Ôèçìàòëèò, 2001. — 240 ñ.
8. Ë è ï ñ ê è é Â . Êîìáèíàòîðèêà äëÿ ïðîãðàììèñòîâ. — Ì.: Ìèð, 1988. — 213 ñ.
9. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíàòîðíûõ
çàäà÷ îïòèìèçàöèè. — Êèåâ: Íàóê. äóìêà, 1981. — 287 ñ.
10. Å ì å ë è ÷ å â Â . À . , Ê î â à ë å â Ì . Ì . , Ê ð à â ö î â Ì . Ê . Ìíîãîãðàííèêè, ãðàôû, îïòèìèçà-
öèÿ. — Ì.: Íàóêà, 1981. — 344 ñ.
11. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðåøåíèÿ
è èññëåäîâàíèÿ. — Êèåâ: Íàóê, äóìêà. 2003 — 260 ñ.
12. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåîìåòðè-
÷åñêîãî ïðîåêòèðîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 1986. — 265 ñ.
13. Á à ð à í î â  . È . , Ñ ò å ÷ ê è í Á . Ñ . Ýêñòðåìàëüíûå êîìáèíàòîðíûå çàäà÷è è èõ ïðèëîæåíèÿ. —
Ì.: Ôèçìàòëèò., 2004. — 238 ñ.
Ïîñòóïèëà 15.09.2009
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Òàáëèöà 1
Çíà÷åíèÿ ��
Ðåçóëüòàòû ðàñ÷åòîâ ãàìèëüòîíîâûõ ïóòåé â ïîäãðàôàõ ïî âåðøèíàì
A B C D
�1 1 7� / 1, 3, 2, 5, 4, 6 7, 9, 8, 11, 10, 12 13, 15, 14, 17, 16, 18 19, 21, 20, 23, 22, 24
1 7 2 51/ /� �� 1, 3, 2, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 15, 14, 17, 16, 18 19, 21, 20, 23, 22, 24
2 5 1 21/ /� �� 1, 3, 2, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 15, 14, 17, 16, 18 19, 20, 21, 23, 22, 24
1 2 3 51/ /� �� 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 15, 14, 17, 16, 18 9, 20, 21, 23, 22, 24
3 5 5 31/ /� �� 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 15, 14, 17, 16, 18 9, 20, 21, 23, 22, 24
5 3 5 21/ /� �� 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 14, 15, 17, 16, 18 9, 20, 21, 23, 22, 24
5 2 21/ � �� 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 14, 15, 16, 17, 18 9, 20, 21, 23, 22, 24
2 71� �� 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 14, 15, 16, 17, 18 9, 20, 21, 23, 22, 24
7 1� � 1, 2, 3, 5, 4, 6 7, 8, 9, 11, 10, 12 13, 14, 15, 16, 17, 18 9, 20, 21, 23, 22, 24
|
| id | nasplib_isofts_kiev_ua-123456789-45121 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-28T23:05:45Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Колечкина, Л.Н. 2013-06-07T19:02:00Z 2013-06-07T19:02:00Z 2010 Построение гамильтонова пути в графах перестановочных многогранников / Г.А. Донец, Л.Н. Колечкина // Кибернетика и системный анализ. — 2010. — № 1. — С. 10–16. — Бібліогр.: 13 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45121 519.1 Розглянуто проблему розв’язання екстремальних задач на множині переставлень для лінійної функції. Побудовано граф многогранника допустимих значень цієї функції на переставленнях. Доведено, що цей граф частково-упорядкований відносно транспозиції двох елементів переставлення. Запропоновано спосіб, який використовує цю властивість побудови гамільтонового шляху в графі, що відповідає множині переставлень для n = 4. The problem of finding an extremum of a linear function on a set of permutations is considered. The polyhedron of admissible values on the permutation set is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path on the graph corresponding to the set of permutations for n = 4. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Построение гамильтонова пути в графах перестановочных многогранников Побудова гамільтонового шляху в графах переставного многогранника Construction of Hamiltonian paths in graphs of permutation polyhedrons Article published earlier |
| spellingShingle | Построение гамильтонова пути в графах перестановочных многогранников Донец, Г.А. Колечкина, Л.Н. Кибернетика |
| title | Построение гамильтонова пути в графах перестановочных многогранников |
| title_alt | Побудова гамільтонового шляху в графах переставного многогранника Construction of Hamiltonian paths in graphs of permutation polyhedrons |
| title_full | Построение гамильтонова пути в графах перестановочных многогранников |
| title_fullStr | Построение гамильтонова пути в графах перестановочных многогранников |
| title_full_unstemmed | Построение гамильтонова пути в графах перестановочных многогранников |
| title_short | Построение гамильтонова пути в графах перестановочных многогранников |
| title_sort | построение гамильтонова пути в графах перестановочных многогранников |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45121 |
| work_keys_str_mv | AT donecga postroeniegamilʹtonovaputivgrafahperestanovočnyhmnogogrannikov AT kolečkinaln postroeniegamilʹtonovaputivgrafahperestanovočnyhmnogogrannikov AT donecga pobudovagamílʹtonovogošlâhuvgrafahperestavnogomnogogrannika AT kolečkinaln pobudovagamílʹtonovogošlâhuvgrafahperestavnogomnogogrannika AT donecga constructionofhamiltonianpathsingraphsofpermutationpolyhedrons AT kolečkinaln constructionofhamiltonianpathsingraphsofpermutationpolyhedrons |