О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| 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: | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859738170081411072 |
|---|---|
| author | Стецюк, П.И. Лиховид, А.П. |
| author_facet | Стецюк, П.И. Лиховид, А.П. |
| citation_txt | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі скінченним числом нерівностей, які отримані на основі алгоритму найкоротших шляхів в спеціальному графі. Наведено результати тестових експериментів, коли граф містить від декількох сотень до тисячі вершин.
Upper bounds are considered for the weighted stability number of a graph that are based on the approximation of the polytope of stable sets by linear inequalities for odd cycles and p-wheels in the graph. Algorithms are developed for finding upper bounds on the basis of solution of an LP-problem with a finite number of inequalities produced by the shortest path algorithm for a special graph. The results of test experiments are given for graphs with several hundred or thousand nodes.
|
| first_indexed | 2025-12-01T15:40:39Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Ï.È. ÑÒÅÖÞÊ, À.Ï. ËÈÕÎÂÈÄ
Î ËÏ-ÎÐÈÅÍÒÈÐÎÂÀÍÍÛÕ ÂÅÐÕÍÈÕ ÎÖÅÍÊÀÕ
ÄËß ÂÇÂÅØÅÍÍÎÃÎ ×ÈÑËÀ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÃÐÀÔÀ
Êëþ÷åâûå ñëîâà: âçâåøåííîå ÷èñëî óñòîé÷èâîñòè ãðàôà, ìíîãîãðàííèê óñòîé-
÷èâûõ ìíîæåñòâ, ËÏ-îðèåíòèðîâàííàÿ âåðõíÿÿ îöåíêà, t-ñîâåðøåííûå ãðàôû,
p-êîëåñî, W
p
-ñîâåðøåííûå ãðàôû.
ÂÂÅÄÅÍÈÅ
Çàäà÷à î ìàêñèìàëüíîì íåçàâèñèìîì (óñòîé÷èâîì) ìíîæåñòâå âåðøèí ãðàôà ÿâ-
ëÿåòñÿ îäíîé èç öåíòðàëüíûõ â òåîðèè ãðàôîâ. Îíà èìååò ìíîãî âàæíûõ ïðèëî-
æåíèé, ñâÿçàííûõ ñ âûáîðîì â ãðàôå ýêñòðåìàëüíûõ ìíîæåñòâ âåðøèí ñ çàäàí-
íûìè ñâîéñòâàìè. Òàê, íàïðèìåð, íåïîñðåäñòâåííîå ïðèëîæåíèå ýòîé çàäà÷è
ñâÿçàíî ñ íàõîæäåíèåì ìàêñèìàëüíîãî îáúåìà ïîìåõîóñòîé÷èâûõ êîäîâ (êîäîâ,
êîððåêòèðóþùèõ îøèáêè ïðè ïåðåäà÷å èíôîðìàöèè). Ê çàäà÷å î ìàêñèìàëüíîì íå-
çàâèñèìîì ìíîæåñòâå âåðøèí ãðàôà ñâîäÿòñÿ çàäà÷à î ìàêñèìàëüíîé êëèêå ãðàôà è
çàäà÷à î ìàêñèìàëüíîé k-êëèêå ãðàôà. Ïîñëåäíèå ìîãóò áûòü èñïîëüçîâàíû ïðè íà-
õîæäåíèè âçàèìîñâÿçàííûõ ïîäìíîæåñòâ ïðè èíôîðìàöèîííîì àíàëèçå ñîöèîëîãè-
÷åñêèõ, áèîëîãè÷åñêèõ, òåëåêîììóíèêàöèîííûõ è äðóãèõ ìàññèâîâ äàííûõ. Òàêèå
ïîäìíîæåñòâà â ñîöèîëîãè÷åñêèõ äàííûõ ìîãóò õàðàêòåðèçîâàòü ðîäñòâåííûå, êðè-
ìèíàëüíûå èëè ïðîôåññèîíàëüíûå ñâÿçè; â òåëåêîììóíèêàöèÿõ — ãðóïïû àáîíåí-
òîâ, êîòîðûå ÷àñòî îáùàþòñÿ; â áèîëîãè÷åñêèõ äàííûõ íàõîæäåíèå òàêèõ ïîäìíî-
æåñòâ ìîæåò îçíà÷àòü íàëè÷èå ïðè÷èííî-ñëåäñòâåííûõ ñâÿçåé ïðè ôóíêöèîíèðîâà-
íèè îòäåëüíûõ ÷àñòåé æèâîãî îðãàíèçìà. Ñ ïîìîùüþ çàäà÷è î ìàêñèìàëüíîì
íåçàâèñèìîì ìíîæåñòâå âåðøèí ãðàôà ìîæíî ïðåäñòàâèòü è êëàññè÷åñêóþ çàäà÷ó
î ðàñêðàñêå âåðøèí íåîðèåíòèðîâàííîãî ãðàôà k-êðàñêàìè.
Çàäà÷à î ìàêñèìàëüíîì íåçàâèñèìîì ìíîæåñòâå âåðøèí ãðàôà äëÿ ïðîèçâîëü-
íîãî ãðàôà ÿâëÿåòñÿ NP-òðóäíîé. Áîëåå òîãî, â îáùåì ñëó÷àå íå íàéäåíî ïîëèíîìè-
àëüíîãî àëãîðèòìà, êîòîðûé áû ãàðàíòèðîâàë äëÿ íåå ñêîëü óãîäíî áîëüøóþ ôèêñèðî-
âàííóþ îòíîñèòåëüíóþ ïîãðåøíîñòü ïî îïòèìàëüíîìó çíà÷åíèþ öåëåâîé ôóíêöèè
(åãî íàçûâàþò ÷èñëîì óñòîé÷èâîñòè ãðàôà). Ïîýòîìó àêòóàëåí ïîèñê âåðõíèõ îöåíîê,
äîñòàòî÷íî õîðîøî àïïðîêñèìèðóþùèõ ñâåðõó ÷èñëî óñòîé÷èâîñòè ãðàôà.
 ðàáîòå îáñóæäàþòñÿ âåðõíèå îöåíêè äëÿ âçâåøåííîãî ÷èñëà óñòîé÷èâîñòè
ãðàôà, ÷àñòíûì ñëó÷àåì êîòîðîãî ÿâëÿåòñÿ îáû÷íîå ÷èñëî óñòîé÷èâîñòè ãðàôà.
Îíè áàçèðóþòñÿ íà àïïðîêñèìàöèè ìíîãîãðàííèêà óñòîé÷èâûõ ìíîæåñòâ ñ ïî-
ìîùüþ ëèíåéíûõ íåðàâåíñòâ äëÿ íå÷åòíûõ öèêëîâ è p-êîëåñ â ãðàôå. Àëãîðèòìû
íàõîæäåíèÿ îáñóæäàåìûõ âåðõíèõ îöåíîê èñïîëüçóþò ðåøåíèå çàäà÷è ëèíåéíîãî
ïðîãðàììèðîâàíèÿ ñ êîíå÷íûì ÷èñëîì íåðàâåíñòâ, ïðè ïîñòðîåíèè êîòîðûõ èñ-
ïîëüçóåòñÿ àëãîðèòì Äåéêñòðû äëÿ íàõîæäåíèÿ êðàò÷àéøèõ ïóòåé. Ïðàêòè÷åñêàÿ
ýôôåêòèâíîñòü âåðõíèõ îöåíîê äëÿ ÷èñëà óñòîé÷èâîñòè ãðàôà ïîäòâåðæäàåòñÿ
ðåçóëüòàòàìè òåñòîâûõ ýêñïåðèìåíòîâ äëÿ ãðàôîâ ñ íåñêîëüêèìè ñîòíÿìè è
òûñÿ÷àìè âåðøèí.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÅÅ ÑËÎÆÍÎÑÒÜ
Ïóñòü G V E� ( , ) — íåîðèåíòèðîâàííûé ãðàô (íå ñîäåðæàùèé ïåòåëü) ñ ìíîæåñ-
òâîì âåðøèí V G( ) è ìíîæåñòâîì ðåáåð E G( ) . Äëÿ êàæäîé âåðøèíû i V G� ( ) çà-
äàí ïîëîæèòåëüíûé âåñ w
i
. Ïîäìíîæåñòâî âåðøèí S V G� ( ) íàçûâàåòñÿ óñòîé-
÷èâûì (èëè íåçàâèñèìûì) ìíîæåñòâîì ãðàôà G, åñëè äëÿ ëþáûõ i j S, � ðåáðî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 157
1
Ðàáîòà âûïîëíåíà ïðè ÷àñòè÷íîé ôèíàíñîâîé ïîääåðæêå ãðàíòà UKM2-2812-KV-06 (CRDF Cooperative
Grants Programm).
© Ï.È. Ñòåöþê, À.Ï. Ëèõîâèä, 2009
( , )i j íå ïðèíàäëåæèò E G( ) . Âçâåøåííîå ÷èñëî óñòîé÷èâîñòè ãðàôà G îïðåäåëÿ-
åòñÿ êàê �( , ) maxG w w
i
i S
�
�
�
, ãäå S V G� ( ) — óñòîé÷èâîå ìíîæåñòâî. Ïîäìíî-
æåñòâî S
* , íà êîòîðîì äîñòèãàåòñÿ �( , )G w , íàçûâàåòñÿ ìàêñèìàëüíûì âçâåøåí-
íûì óñòîé÷èâûì (èëè íåçàâèñèìûì) ìíîæåñòâîì ãðàôà G.  ÷àñòíîì ñëó÷àå,
êîãäà âñå âåñà âåðøèí â ãðàôå ðàâíû åäèíèöå, èìååì îáû÷íîå ÷èñëî óñòîé÷è-
âîñòè ãðàôà G, êîòîðîå ïðèíÿòî îáîçíà÷àòü �( )G . ×èñëî óñòîé÷èâîñòè �( )G õà-
ðàêòåðèçóåò ìîùíîñòü ìàêñèìàëüíîãî ïî ÷èñëó âõîäÿùèõ â íåãî âåðøèí óñòîé-
÷èâîãî ìíîæåñòâà â ãðàôå G.
 îáùåì ñëó÷àå çàäà÷è íàõîæäåíèÿ �( , )G w è �( )G ïðèíàäëåæàò ê NP-òðóäíûì
çàäà÷àì [1]. Ïóñòü STAB G( ) — ìíîãîãðàííèê óñòîé÷èâûõ ìíîæåñòâ (stable set
polytope). Îí ÿâëÿåòñÿ âûïóêëîé îáîëî÷êîé èíöèäåíòíûõ âåêòîðîâ óñòîé÷èâûõ
ìíîæåñòâ S â G è ìîæåò áûòü ïðåäñòàâëåí â ñëåäóþùåì âèäå:
STAB G x x x i j E G
V
i j
( ) , : ( , ) ( ) .
| |
� � � � � �conv{ { } }0 1 1 (1)
Íàõîæäåíèå �( , )G w ñâÿçàíî ñ çàäà÷åé ìàêñèìèçàöèè ëèíåéíîé ôóíêöèè íà
âûïóêëîì ìíîãîãðàííèêå STAB G( ), êîòîðàÿ èìååò âèä
�( , ) max , ( ).
( )
G w w x x STAB G
i
i V G
i
� �
�
�
(2)
Ìàêñèìóì â çàäà÷å (2) äîñòèãàåòñÿ â îäíîé èëè íåñêîëüêèõ âåðøèíàõ ìíîãî-
ãðàííèêà STAB G( ) .  îáùåì ñëó÷àå ìíîãîãðàííèê STAB G( ) ìîæåò èìåòü ñëîæ-
íóþ ñòðóêòóðó, èç-çà ÷åãî çàäà÷à (2) ïðèíàäëåæèò ê NP-òðóäíûì. Ïîýòîìó òåî-
ðåòè÷åñêèé è ïðàêòè÷åñêèé èíòåðåñ ïðåäñòàâëÿåò íàõîæäåíèå âåðõíèõ îöåíîê,
äîñòàòî÷íî õîðîøî àïïðîêñèìèðóþùèõ ñâåðõó �( , )G w .
Ïðåäìåòîì îáñóæäåíèÿ â ñòàòüå ÿâëÿþòñÿ âåðõíèå îöåíêè, ñâÿçàííûå ñ ðåøå-
íèåì çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ËÏ-çàäà÷). Òàêèå îöåíêè íàçîâåì
ËÏ-îðèåíòèðîâàííûìè âåðõíèìè îöåíêàìè. Â ñàìîì îáùåì âèäå èõ ìîæíî îïè-
ñàòü ñëåäóþùèì îáðàçîì. Ïóñòü �STAB G( ) — íåêîòîðûé ìíîãîãðàííèê, çàäàííûé
ñ ïîìîùüþ ñèñòåìû ëèíåéíûõ îãðàíè÷åíèé-íåðàâåíñòâ, è ïóñòü îí àïïðîêñèìèðó-
åò (ñâåðõó) ìíîãîãðàííèê STAB G( ) . Òîãäà ËÏ-îðèåíòèðîâàííàÿ âåðõíÿÿ îöåíêà
��
*
( , )G w ñâÿçàíà ñ ðåøåíèåì ËÏ-çàäà÷è
�� �
*
( )
( , ) max , ( ).G w w x x STAB G
i
i V G
i
� �
�
�
 ñèëó òîãî ÷òî ìíîãîãðàííèê �STAB G( ) àïïðîêñèìèðóåò (ñâåðõó) ìíîãîãðàí-
íèê STAB G( ) , èìååì � ��
*
( , ) ( , )G w G w� , è, ñëåäîâàòåëüíî, îöåíêà ��
*
( , )G w
âñåãäà ÿâëÿåòñÿ îöåíêîé ñâåðõó äëÿ �( , )G w . Ñâîéñòâà êîíêðåòíîé îöåíêè
��
*
( , )G w çàâèñÿò îò òîãî, ñ ïîìîùüþ êàêèõ ïîäìíîæåñòâ ëèíåéíûõ íåðàâåíñòâ
îïèñûâàåòñÿ ìíîãîãðàííèê �STAB G( ).
ÎÖÅÍÊÀ �C G w
*
( , ) È ÀËÃÎÐÈÒÌÛ LPCSTAB
Ïóñòü C
k2 1�
, k � 1 2, , ,� — íå÷åòíûé öèêë â ãðàôå G (ñîäåðæèò íå÷åòíîå êîëè-
÷åñòâî âåðøèí). Äëÿ ìíîãîãðàííèêà STAB G( ) ñïðàâåäëèâû ñëåäóþùèå êëàññû
ëèíåéíûõ íåðàâåíñòâ:
0 1� � � �x i V G
i
( ), (3)
x x i j E G
i j
� � � �1 ( , ) ( ), (4)
x k C G
i
i V C
k
k
�
�
�
�
� � �
( )
.
2 1
2 1 (5)
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Ñåìåéñòâî íåðàâåíñòâ (3) ïðèíÿòî íàçûâàòü âåðøèííûìè îãðàíè÷åíèÿìè
(vertix constraints), ñåìåéñòâî íåðàâåíñòâ (4) — ðåáåðíûìè îãðàíè÷åíèÿìè (edge
constraints), à ñåìåéñòâî íåðàâåíñòâ (5) — íåðàâåíñòâàìè íå÷åòíûõ öèêëîâ
(odd-cycle constraints). Âñå âìåñòå îíè îïðåäåëÿþò ìíîãîãðàííèê íå÷åòíûõ öèêëîâ
(odd-cycle polytope)
CSTAB G x R x
V
( ) :
| |
� �{ óäîâëåòâîðÿåò (3)–(5)},
êîòîðûé àïïðîêñèìèðóåò (ñâåðõó) ìíîãîãðàííèê STAB G( ) .
Îöåíêà �
C
G w
*
( , ) ñâÿçàíà ñ ðåøåíèåì ñëåäóþùåé ËÏ-çàäà÷è:
�
C i
i V G
i
G w w x x CSTAB G
*
( )
( , ) max , ( ).� �
�
�
(6)
Äëÿ ïðîèçâîëüíîãî ãðàôà G âñåãäà èìååò ìåñòî íåðàâåíñòâî � �
C
G w G w
*
( , ) ( , )� .
Åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó t-ñîâåðøåííûõ ãðàôîâ, äëÿ êîòîðûõ
STAB G CSTAB G( ) ( )� , òî îöåíêà �
C
G w
*
( , ) ÿâëÿåòñÿ òî÷íîé äëÿ �( , )G w , ò.å.
� �
C
G w G w
*
( , ) ( , )� .
Çàäà÷à (6) â îáùåì ñëó÷àå ìîæåò ñîäåðæàòü íåïîëèíîìèàëüíîå êîëè÷åñòâî
îãðàíè÷åíèé, ÷òî îáóñëîâëåíî íàëè÷èåì îãðàíè÷åíèé âèäà (5) äëÿ âñåõ âîçìîæíûõ
íå÷åòíûõ öèêëîâ. Íåñìîòðÿ íà ýòî, çàäà÷à (6) ðàçðåøèìà çà ïîëèíîìèàëüíîå âðåìÿ.
 [2] îïèñàí ïîëèíîìèàëüíûé àëãîðèòì åå ðåøåíèÿ, áàçèðóþùèéñÿ íà èñïîëüçîâà-
íèè ìåòîäà ýëëèïñîèäîâ è òîì ôàêòå, ÷òî äëÿ òî÷êè x, óäîâëåòâîðÿþùåé îãðàíè÷å-
íèÿì (3), (4), çà ïîëèíîìèàëüíîå âðåìÿ ìîæíî ëèáî óáåäèòüñÿ, ÷òî îíà óäîâëåòâî-
ðÿåò îãðàíè÷åíèÿì (5) äëÿ êàæäîãî íå÷åòíîãî öèêëà, ëèáî íàéòè òàêîé íå÷åòíûé
öèêë, äëÿ êîòîðîãî îãðàíè÷åíèå âèäà (5) ÿâëÿåòñÿ ìàêñèìàëüíî íàðóøåííûì. Ìå-
òîä èç ðàáîòû [2] èìååò òåîðåòè÷åñêóþ öåííîñòü, îäíàêî îí ìàëîïðèãîäåí äëÿ
ïðàêòè÷åñêîãî íàõîæäåíèÿ îöåíîê �
C
G w
*
( , ) .
Åñëè ãðàô ñîäåðæèò íåñêîëüêî ñîòåí âåðøèí, äëÿ âû÷èñëåíèÿ îöåíêè
�
C
G w
*
( , ) ýôôåêòèâíûå àëãîðèòìû ìîæíî ðåàëèçîâàòü íà îñíîâå ñîâðåìåííûõ
ËÏ-ïðîãðàìì, äëÿ êîòîðûõ ðåøåíèå ËÏ-çàäà÷ ñ ñîòíÿìè ïåðåìåííûõ è äåñÿòêàìè
èëè ñîòíÿìè òûñÿ÷ îãðàíè÷åíèé íå ïðåäñòàâëÿåò îñîáûõ ïðîáëåì. Ýòè àëãîðèòìû
íàçîâåì ËÏ-îðèåíòèðîâàííûìè àëãîðèòìàìè íàõîæäåíèÿ �
C
G w
*
( , ) è áóäåì èõ
îðèåíòèðîâàòü íà ðåøåíèå ËÏ-çàäà÷ ñ êîíå÷íûì ÷èñëîì ëèíåéíûõ îãðàíè÷åíèé.
 îñíîâó ËÏ-îðèåíòèðîâàííîãî àëãîðèòìà äëÿ íàõîæäåíèÿ �
C
G w
*
( , ) ïîëîæèì ïî-
ëèíîìèàëüíûé àëãîðèòì èç [2] äëÿ íàõîæäåíèÿ ìàêñèìàëüíîãî íàðóøåííîãî îãðà-
íè÷åíèÿ, ñâÿçàííîãî ñ íå÷åòíûì öèêëîì, è ËÏ-çàäà÷ó
f w x
C i
i V
i
*
max�
�
�
(7)
ïðè îãðàíè÷åíèÿõ:
0 1� � � �x i V G
i
( ), (8)
x x i j E G
i j
� � � �1 ( , ) ( ), (9)
x k C C G
i
i V C
k
k
�
�
�
�
� � � �
( )
.
2 1
2 1 odd (10)
Çäåñü Codd — êîíå÷íîå ìíîæåñòâî íå÷åòíûõ öèêëîâ (âîçìîæíî, ïóñòîå).
Òîãäà ËÏ-îðèåíòèðîâàííûé àëãîðèòì äëÿ íàõîæäåíèÿ �
C
G w
*
( , ) (íàçîâåì åãî
LPCSTABa) ñîñòîèò â ñëåäóþùåì.
Íà÷àëüíàÿ óñòàíîâêà. Ïîëîæèì itn = 0 è C0 � (ìíîæåñòâî íå÷åòíûõ öèê-
ëîâ ïóñòî). Ïåðåéäåì ê øàãó 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 159
Øàã 1. Èìååì ìíîæåñòâî íå÷åòíûõ öèêëîâ C itn . Ïîëîæèì C Codd itn� è, ðå-
øèâ ËÏ-çàäà÷ó (7)–(10), íàéäåì f
C
*
è x x x
V
* *
| |
*( , , )� 1 � .
Øàã 2. Ïîñòðîèì âçâåøåííûé íåîðèåíòèðîâàííûé ãðàô
�
G V E( , ) , ãäå ìíîæåñ-
òâî âåðøèí
V G( ) âêëþ÷àåò 2| |V âåðøèí (âåðøèíà i è åå êîïèÿ
i äëÿ âñåõ i V G� ( )) .
Ìíîæåñòâî ðåáåð
E G( ) ñîñòîèò èç ðåáåð, ñîåäèíÿþùèõ âñå òå ïàðû âåðøèí ( , )i j
è
( , )
i j , äëÿ êîòîðûõ ïàðà âåðøèí i è j ñîåäèíåíà ðåáðîì ( , )i j â ãðàôå G. Ïðèñâîèì ðåá-
ðàì ( , )i j
è ( , )
i j îäèí è òîò æå ïîëîæèòåëüíûé âåñ (äëèíà ðåáðà), ðàâíûé 1� �x x
i j
* *
.
Øàã 3. Ðàññìîòðèì ãðàô
G êàê îðèåíòèðîâàííûé (ðåáðó ( , )i j
ñîîòâåòñòâóþò
äóãè ( , )i j
è ( , )
j i ñ äëèíàìè, ðàâíûìè äëèíå ðåáðà ( , )i j
, ò.å. l i j( , )
) è íàéäåì äëÿ
êàæäîé âåðøèíû i V� êðàò÷àéøèé ïóòü, êîòîðûé íà÷èíàåòñÿ â âåðøèíå i è çàêàí-
÷èâàåòñÿ â âåðøèíå
i (êîïèè âåðøèíû i). ×èñëî òàêèõ êðàò÷àéøèõ ïóòåé ðàâíî | |V .
Ïóñòü äëèíû íàéäåííûõ êðàò÷àéøèõ ïóòåé ðàâíû l
i
, i V� 1, , | |� .
Øàã 4. Ñðåäè íàéäåííûõ | |V êðàò÷àéøèõ ïóòåé âûáåðåì êðàò÷àéøèé ïóòü
ñ ìèíèìàëüíîé (íàèìåíüøåé) äëèíîé l l
i V
i
*
, , , | |
min ( )�
�1 2 �
(íå îáÿçàòåëüíî åäèí-
ñòâåííûé). Åñëè äëèíà l
*
áîëüøå ëèáî ðàâíà åäèíèöå, òî �
C C
G w f
* *
( , ) � è îñòàíîâ
(äîñòàòî÷íîå óñëîâèå òîãî, ÷òî òî÷êà x
*
óäîâëåòâîðÿåò îãðàíè÷åíèÿì â ôîðìå (5)
äëÿ âñåõ íå÷åòíûõ öèêëîâ). Èíà÷å ïåðåõîäèì ê øàãó 5.
Øàã 5. Ïîëàãàåì
�
�
C C
k2 1, ãäå C
k2 1�
— íå÷åòíûé öèêë, ñîîòâåòñòâóþùèé
âåðøèíàì, ÷åðåç êîòîðûå ïðîõîäèò êðàò÷àéøèé ïóòü ìèíèìàëüíîé äëèíû, ñ ó÷å-
òîì çàìåíû âåðøèí «
i » âåðøèíàìè «i». Íå÷åòíûé öèêë
C îïðåäåëÿåò îãðàíè÷åíèå
â ôîðìå (5), êîòîðîå â òî÷êå x
*
ÿâëÿåòñÿ ìàêñèìàëüíî íàðóøåííûì (îíî íå îáÿçà-
òåëüíî åäèíñòâåííîå). Ïåðåéäåì ê øàãó 6.
Øàã 6. Ïîëîæèì C C Citn +1 itn� �
è itn = itn+1. Ïåðåéäåì ê øàãó 1.
Îäíà èòåðàöèÿ àëãîðèòìà LPCSTABa òðåáóåò ðåøåíèÿ ËÏ-çàäà÷è (øàã 1) è
íàõîæäåíèÿ | |V ðàç êðàò÷àéøåãî ïóòè (øàã 3). Åñëè ãðàô G ñîäåðæèò ïîðÿäêà íå-
ñêîëüêèõ ñîòåí âåðøèí, òî äîáàâëåíèå ê ËÏ-çàäà÷å ñòà íå÷åòíûõ öèêëîâ ðàâíî-
ñèëüíî ñòà èòåðàöèÿì àëãîðèòìà è ìîæåò ïîòðåáîâàòü çíà÷èòåëüíûõ çàòðàò ïî âðå-
ìåíè. Ïîýòîìó àëãîðèòì LPCSTABa ëåãêî óñîâåðøåíñòâîâàòü, åñëè èñïîëüçîâàòü
èíôîðìàöèþ òðóäîåìêîãî ïî âû÷èñëåíèÿì øàãà 3 è äîáàâèòü íà êàæäîé èòåðàöèè
âñå òå íå÷åòíûå öèêëû, äëÿ êîòîðûõ îãðàíè÷åíèå â ôîðìå (5) íàðóøåío. Äëÿ ìîäè-
ôèöèðîâàííîãî ËÏ-îðèåíòèðîâàííîãî àëãîðèòìà íàõîæäåíèÿ �
C
G w
*
( , ) (íàçîâåì
åãî LPCSTABb) øàãè 4 è 5 çàìåíÿþòñÿ ñëåäóþùèìè.
Øàã 4a. Ñðåäè íàéäåííûõ V êðàò÷àéøèõ ïóòåé îñòàâëÿåì òîëüêî òå, êîòîðûå
îïðåäåëÿþò íå÷åòíûé öèêë (òàêàÿ ïðîâåðêà òðåáóåòñÿ, ïîñêîëüêó íå êàæäûé êðàò-
÷àéøèé ïóòü îïðåäåëÿåò íå÷åòíûé öèêë â ãðàôå G). Ïóñòü ÷èñëî êðàò÷àéøèõ ïóòåé,
îïðåäåëÿþùèõ íå÷åòíûå öèêëû, ðàâíî n (n V� | |), è äëèíû ýòèõ êðàò÷àéøèõ ïóòåé
ðàâíû l
i
, i n� 1, ,� . Åñëè âñå l
i
, i n� 1, , ,� íå ìåíüøå åäèíèöû, òî �
C
G w f
* *
( , ) � è
îñòàíîâ. Èíà÷å ïåðåõîäèì ê øàãó 5a.
Øàã 5a. Ñôîðìèðóåì ñïèñîê íå÷åòíûõ öèêëîâ
C , âêëþ÷àþùèé âñå íå÷åòíûå
öèêëû, ñîîòâåòñòâóþùèå êðàò÷àéøèì ïóòÿì èç 1, ,� n, äëÿ êîòîðûõ l
i
1. Êàæäûé
èç íå÷åòíûõ öèêëîâ èç ñïèñêà
C îïðåäåëÿåò îãðàíè÷åíèå â ôîðìå (5), êîòîðîå
â òî÷êå x
*
ÿâëÿåòñÿ íàðóøåííûì (íå îáÿçàòåëüíî ìàêñèìàëüíî íàðóøåííûì, õîòÿ
ïî êðàéíåé ìåðå îäèí èç òàêèõ íå÷åòíûõ öèêëîâ äàåò ìàêñèìàëüíî íàðóøåííîå
îãðàíè÷åíèå). Ïåðåéäåì ê øàãó 6.
Îáà àëãîðèòìà, LPCSTABa è LPCSTABb, ïîçâîëÿþò íàéòè îöåíêó �
C
G w
*
( , ) ,
è åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó t-ñîâåðøåííûõ ãðàôîâ, òî îöåíêà �
C
G w
*
( , )
áóäåò òî÷íîé äëÿ �( , )G w , ò.å. � �
C
G w G w
*
( , ) ( , )� . Îäíàêî âðåìÿ ðàáîòû êàæäîãî
àëãîðèòìà ðàçíîå. Äëÿ îöåíêè âðåìåíè íàõîæäåíèÿ �
C
G w
*
( , ) , êîãäà ãðàô ñîäåðæèò
ïîðÿäêà íåñêîëüêèõ ñîòåí âåðøèí, îáà àëãîðèòìà ïðîãðàììíî ðåàëèçîâàíû (ïðî-
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
ãðàììû LPCSTABa è LPCSTABb). Äëÿ ðåøåíèÿ ËÏ-çàäà÷è èñïîëüçîâàëàñü ïðî-
ãðàììà SOPLEX [3], à äëÿ íàõîæäåíèÿ êðàò÷àéøåãî ïóòè â îðèåíòèðîâàííîì ãðà-
ôå — ïðîãðàììà DIKH (èç áèáëèîòåêè SPLIB) [4].
Ðåçóëüòàòû òåñòîâûõ ýêñïåðèìåíòîâ äëÿ ñðàâíåíèÿ âðåìåíè ðàáîòû îáîèõ àëãî-
ðèòìîâ ïðèâåäåíû â òàáë. 1. Âû÷èñëåíèÿ ïðîâîäèëèñü íà ïðîöåññîðå AMD Athlon
1,81GHz. Âåðõíÿÿ îöåíêà �
C
G
*
( ) äëÿ âçâåøåííîãî ÷èñëà óñòîé÷èâîñòè ãðàôà (w
i
� 1
� �i V G( )) âû÷èñëåíà äëÿ ðÿäà òåñòîâûõ íàáîðîâ èç DIMACS-áèáëèîòåêè [5]. Çäåñü
NCa — ìàêñèìàëüíîå êîëè÷åñòâî âêëþ÷åííûõ â ËÏ-çàäà÷ó íå÷åòíûõ öèêëîâ ïðîãðàì-
ìîé LPCSTABa. Îíî ðàâíî è êîëè÷åñòâó èòåðàöèé, çàòðà÷åííûõ íà íàõîæäåíèå îöåí-
êè �
C
G
*
( ) . Äëÿ ïðîãðàììû LPCSTABb ïðèâåäåíî êîëè÷åñòâî èòåðàöèé (ñòîëáåö itnb).
Èç òàáë. 1 ëåãêî âèäåòü, ÷òî ïî âðåìåíè ïðîãðàììà LPCSTABb âñåãäà âûèãðûâàåò,
èíîãäà ñóùåñòâåííî, ó ïðîãðàììû LPCSTABa (ñòîëáåö t t
a b
/ ), íåçíà÷èòåëüíî ïðîèã-
ðûâàÿ â êîëè÷åñòâå íàêîïëåííûõ íå÷åòíûõ öèêëîâ (ñòîëáåö NCb NCa/ ). Íàïðèìåð,
äëÿ ãðàôà hamming8-4 äîñòèãíóò âûèãðûø ïî âðåìåíè â ïÿòüäåñÿò ðàç, íå÷åòíûõ öèê-
ëîâ íàêàïëèâàåòñÿ íå òàê ìíîãî (â äâà ðàçà áîëüøå). Ïðè ýòîì ïðèøëîñü ðåøàòü
ËÏ-çàäà÷ó ÷åòûðå ðàçà, à íàõîäèòü êðàò÷àéøèå ïóòè â îðèåíòèðîâàííîì ãðàôå
ñ 256 âåðøèíàìè è 47104 äóãàìè 4 256� ðàç.
Îòíîñèòåëüíî òî÷íîñòè îöåíêè �
C
G
*
( ) äëÿ ðàññìîòðåííûõ ïðèìåðîâ îòìåòèì
ñëåäóþùåå.  òðåõ ñëó÷àÿõ, ãðàôû san200.0.9-1, hamming6-2 è hamming8-2, îöåíêà
�
C
G
*
( ) îêàçàëàñü òî÷íîé âåðõíåé îöåíêîé äëÿ �( )G , äëÿ ãðàôîâ hamming6-2
è hamming8-2 îíà áûëà òî÷íîé ïðè íàëè÷èè òîëüêî ðåáåðíûõ îãðàíè÷åíèé â ËÏ-çàäà÷å
è íå áûëî íàéäåíî íè îäíîãî íå÷åòíîãî öèêëà (â ñâÿçè ñ ýòèì t t
a b
/ ðàâíî åäèíèöå).
Îäíàêî äëÿ îñòàëüíûõ ïðèìåðîâ îöåíêà �
C
G
*
( ) íåòî÷íà, è äëÿ ãðàôîâ c-fat200-1 è
hamming8-4 îíà ñèëüíî çàâûøåíà. Â ñëåäóþùèõ ðàçäåëàõ ðàññìàòðèâàåòñÿ óëó÷øåííûé
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 161
Ò à á ë è ö à 1
Òåñòîâûå
íàáîðû èç
DIMACS-ãðàôîâ
Ðåçóëüòàòû òåñòîâûõ ýêñïåðèìåíòîâ äëÿ îöåíêè �C G
*
( )
è çàòðàòû íà åå íàõîæäåíèå
| |V | |E �( )G �
C
G
*
( ) NCa itnb t t
a b
/ NCb NCa/
c-fat200-l 200 18366 12 66,6667 241 4 43,5 2,2
c-fat200-2 200 16665 24 66,6667 232 4 40,1 2,4
c-fat200-5 200 11427 58 66,6667 237 4 36,1 2,2
johnson16-2-4 120 1680 8 40,0000 143 4 29,7 2,1
johnson8-2-4 28 210 4 9,3333 32 4 5,8 2,1
johnson8-4-4 70 560 14 23,3333 81 4 14,5 2,1
keller4 171 5100 11 57,0000 211 4 35,1 2,2
hamming6-2 64 192 32 32,0000 0 1 1,0 —
hamming6-4 64 1312 4 21,3333 73 4 14,7 2,2
hamming8-2 256 1024 128 128,0000 0 1 1,0 —
hamming8-4 256 11776 16 85,3333 322 4 50,6 2,1
san200-0.7-2 200 5970 18 66,6667 232 5 30,7 3,3
san200.0.9-l 200 1990 70 70,0000 175 6 14,8 4,7
san200-0.9-2 200 1990 60 66,6667 274 12 12,9 4,7
san200.0.9-3 200 1990 44 66,6667 247 8 17,4 3,7
brock200-l 200 5066 21 66,6667 237 4 31,4 2,9
mann-a27 378 702 126 135,0000 146 7 15,4 1,6
mann-a9 45 72 16 18,0000 12 2 4,2 1,7
âàðèàíò ËÏ-îðèåíòèðîâàííîãî àëãîðèòìà, êîòîðûé ïîçâîëèò â ðÿäå ñëó÷àåâ íàéòè áîëåå
òî÷íûå âåðõíèå îöåíêè äëÿ ÷èñëà óñòîé÷èâîñòè ýòèõ ãðàôîâ.
ÎÖÅÍÊÀ �Wp
G w
*
( , ) È Wp -ÑÎÂÅÐØÅÍÍÛÅ ÃÐÀÔÛ
Ðàññìîòðèì áîëåå òî÷íóþ âåðõíþþ îöåíêó äëÿ �( , )G w , ÷åì îöåíêà �
C
G w
*
( , ),
è îáñóäèì åå ñâÿçü ñ îäíîé èç âåðõíèõ îöåíîê, ïðåäëîæåííîé Í.Ç. Øîðîì [6].
Ïóñòü èìååòñÿ ãðàô W
k p2 1� �
, âåð-
øèíàìè êîòîðîãî ÿâëÿþòñÿ âåðøèíû íå-
ïåðåñåêàþùèõñÿ íå÷åòíîãî öèêëà C
k2 1�
è êëèêè Q
p
(ïîëíûé ïîäãðàô, ñîäåðæà-
ùèé p âåðøèí). Åñëè p � 1, òî êëèêà ñî-
ñòîèò èç îäíîé âåðøèíû. Ìíîæåñòâî ðå-
áåð â ãðàôå W
k p2 1� �
âêëþ÷àåò âñå ðåáðà
íå÷åòíîãî öèêëà C
k2 1�
, âñå ðåáðà êëèêè
Q
p
, à òàêæå ðåáðà, ñâÿçûâàþùèå êàæ-
äóþ âåðøèíó C
k2 1�
ñî âñåìè âåðøèíàìè êëèêè Q
p
. Ãðàô W
k p2 1� �
ïðèíÿòî íàçû-
âàòü p-êîëåñîì ( p-wheel) [7]. Ïðèìåðû 1-êîëåñà è 2-êîëåñà íà áàçå íå÷åòíîãî öèêëà
C5 ïðèâåäåíû íà ðèñ. 1, à,á ñîîòâåòñòâåííî.
C p-êîëåñîì ñâÿçàíî ñåìåéñòâî ëèíåéíûõ íåðàâåíñòâ
x k x k W G
i
i V C
j
j V Q
k p
k p
� � � �
� �
� �
�
� �
( ) ( )
,
2 1
2 1 (11)
êîòîðûå ñïðàâåäëèâû äëÿ ìíîãîãðàííèêà STAB G( ) . Ñåìåéñòâî íåðàâåíñòâ (11)
ïðèíÿòî íàçûâàòü p-êîëåñíûìè îãðàíè÷åíèÿìè ( p-wheel constraints). Îíè îçíà÷à-
þò, ÷òî äëÿ êàæäîãî p-êîëåñà èç ãðàôà G â óñòîé÷èâîå (íåçàâèñèìîå) ìíîæåñòâî
ìîæåò áûòü âêëþ÷åíà ëèáî îäíà èç âåðøèí êëèêè Q
p
, ëèáî k âåðøèí èç íå÷åò-
íîãî öèêëà C
k2 1�
. Åñëè ñåìåéñòâî íåðàâåíñòâ (11) äîáàâèòü ê ëèíåéíûì íåðàâå-
íñòâàì, êîòîðûå îïðåäåëÿþò ìíîãîãðàííèê CSTAB G( ) , òî ïîëó÷èì ìíîãîãðàííèê
W STAB G x R x
p
V
( ) :
| |
� �{ óäîâëåòâîðÿåò (3)–(5), (11)},
êîòîðûé àïïðîêñèìèðóåò (ñâåðõó) ìíîãîãðàííèê óñòîé÷èâûõ ìíîæåñòâ STAB G( ) .
Ñåìåéñòâî ãðàôîâ, äëÿ êîòîðûõ STAB G W STAB G
p
( ) ( )� , íàçîâåì W
p
-ñîâåðøåí-
íûìè (W
p
-perfect).
Îöåíêà �
W
p
G w
*
( , ) ñâÿçàíà ñ ðåøåíèåì ËÏ-çàäà÷è
�
W i
i V G
i p
p
G w w x x W STAB G
*
( )
( , ) max , ( )� �
�
�
. (12)
Åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó W
p
-ñîâåðøåííûõ ãðàôîâ, òî �
W
p
G w
*
( , ) �
� �( , )G w . Äëÿ ïðîèçâîëüíîãî ãðàôà G âñåãäà èìååò ìåñòî íåðàâåíñòâî
� � �
C W
G w G w G w
p
* *
( , ) ( , ) ( , ),� � (13)
ò.å. îöåíêà �
W
p
G w
*
( , ) ÿâëÿåòñÿ âåðõíåé îöåíêîé (îöåíêîé ñâåðõó) äëÿ �( , )G w è
îíà âñåãäà íå õóæå, ÷åì îöåíêà �
C
G w
*
( , ) .
ËÏ-çàäà÷à (12) â îáùåì ñëó÷àå ìîæåò ñîäåðæàòü íåïîëèíîìèàëüíîå êîëè÷åñ-
òâî îãðàíè÷åíèé.  îòëè÷èå îò ËÏ-çàäà÷è (6) îíà íå ìîæåò áûòü ðàçðåøåíà çà ïî-
ëèíîìèàëüíîå âðåìÿ. Òàê, íàïðèìåð, ïðè k � 1 (ò.å. ðàññìàòðèâàþòñÿ òîëüêî íå÷åò-
íûå öèêëû, ñîâïàäàþùèå ñ 3-êëèêîé) è ïðîèçâîëüíîì p, 1 3� � �p V| | , èç ìíîãî-
ãðàííèêà W STAB G
p
( ) ñëåäóåò èçâåñòíûé êëèêîâûé ìíîãîãðàííèê (clique polytope)
QSTAB G
x Q G
x
i
i V Q
i
( )
,
( )�
� �
� �
�
�
1
0 1
äëÿ êàæäîé êëèêè
äëÿ êàæäîé âåðøèíû i G�
�
�
�
�
� .
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Ðèñ. 1
à á
Çäåñü íåðàâåíñòâà äëÿ 2-êëèê ñëåäóþò èç ðåáåðíûõ íåðàâåíñòâ (4), íåðàâåíñòâà
äëÿ 3-êëèê — èç íåðàâåíñòâ äëÿ íå÷åòíûõ öèêëîâ (5) ïðè k � 1, à íåðàâåíñòâà
äëÿ êëèê ñ áîëüøèì êîëè÷åñòâîì âåðøèí — èç íåðàâåíñòâ äëÿ p-êîëåñ (11) ïðè
k � 1 è ïðîèçâîëüíîì p. Ñ ìíîãîãðàííèêîì QSTAB G( ) ñâÿçàíà ËÏ-îðèåíòèðîâàí-
íàÿ âåðõíÿÿ îöåíêà
�
Q i
i V G
i
G w w x x QSTAB G
*
( )
( , ) max , ( )� �
�
�
,
êîòîðàÿ íàçûâàåòñÿ äðîáíûì âçâåøåííûì ÷èñëîì óñòîé÷èâîñòè ãðàôà G.  îá-
ùåì ñëó÷àå íàõîæäåíèå �
Q
G w
*
( , ) — NP-òðóäíàÿ çàäà÷à, ïîñêîëüêó ýòî ñâÿçàíî
ñ íàõîæäåíèåì ìàêñèìàëüíîé êëèêè â ãðàôå G, à òàêàÿ çàäà÷à äëÿ ïðîèçâîëüíî-
ãî ãðàôà G ÿâëÿåòñÿ NP-òðóäíîé [1]. Îäíàêî êîãäà ãðàô G ïðèíàäëåæèò ñåìåé-
ñòâó ñîâåðøåííûõ ãðàôîâ (äëÿ íèõ STAB G QSTAB G( ) ( )� ), òî çàäà÷à íàõîæäåíèÿ
�
Q
G w
*
( , ) ðàçðåøèìà çà ïîëèíîìèàëüíîå âðåìÿ. Ýòî îáúÿñíÿåòñÿ ñâîéñòâàìè íå
ñàìîé îöåíêè �
Q
G w
*
( , ) , à áîëåå òî÷íîé âåðõíåé îöåíêè äëÿ �( , )G w , à èìåííî
èçâåñòíîãî ÷èñëà Ëîâàñà �( , )G w [2]. ×èñëî Ëîâàñà ìîæíî íàéòè çà ïîëèíîìè-
àëüíîå âðåìÿ, è äëÿ ïðîèçâîëüíîãî ãðàôà G îíî óäîâëåòâîðÿåò íåðàâåíñòâó
� � �
Q
G w G w G w
*
( , ) ( , ) ( , ),� �
êîòîðîå, åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó ñîâåðøåííûõ ãðàôîâ, ïðåâðàùàåò-
ñÿ â òî÷íîå ðàâåíñòâî
� � �
Q
G w G w G w
*
( , ) ( , ) ( , ).� �
Îòìåòèì åùå îäèí èíòåðåñíûé ìíîãîãðàííèê WSTAB G w( , ) , ñ êîòîðûì ñâÿçà-
íî ñåìåéñòâî W-ñîâåðøåííûõ (W-perfect) ãðàôîâ. Îí ïîëó÷àåòñÿ èç W STAB G
p
( )
ïðè p � 1, ò.å. íåðàâåíñòâà äëÿ ïðîèçâîëüíîãî p-êîëåñà â ôîðìå (11) çàìåíÿþòñÿ
ëèíåéíûìè íåðàâåíñòâàìè
x k x k W G
i i
i V C
k
k
k
� � � �
�
�
�
��
2 2
2 1
2 2
( )
äëÿ îáû÷íîãî êîëåñà W
k2 2�
, êîãäà êëèêà ñîñòîèò âñåãî èç îäíîé âåðøèíû. Ñå-
ìåéñòâî ýòèõ íåðàâåíñòâ ïðèíÿòî íàçûâàòü êîëåñíûìè îãðàíè÷åíèÿìè (wheel
constraints). Ñ ìíîãîãðàííèêîì WSTAB G( ) ñâÿçàíà âåðõíÿÿ îöåíêà äëÿ �( , )G w ,
ÿâëÿþùàÿñÿ ðåøåíèåì ñëåäóþùåé ËÏ-çàäà÷è:
�
W i
i V G
i
G w w x x WSTAB G
*
( )
( , ) max , ( ).� �
�
�
Íàõîæäåíèå îöåíêè �
W
G w
*
( , ) ìîæåò áûòü îñóùåñòâëåíî çà ïîëèíîìèàëüíîå âðå-
ìÿ äëÿ ïðîèçâîëüíîãî ãðàôà G [2]. Åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó W-ñî-
âåðøåííûõ (W-perfect) ãðàôîâ (äëÿ íèõ STAB G WSTAB G( ) ( )� ), òî îöåíêà
�
W
G w
*
( , ) ÿâëÿåòñÿ òî÷íîé äëÿ �( , )G w .
Èòàê, äëÿ ñîâåðøåííûõ, t-ñîâåðøåííûõ è W-ñîâåðøåííûõ ãðàôîâ çàäà÷à íà-
õîæäåíèÿ �( , )G w ðàçðåøèìà çà ïîëèíîìèàëüíîå âðåìÿ. Ïîýòîìó èíòåðåñ ïðåäñòàâ-
ëÿåò ñëåäóþùèé âîïðîñ: áóäåò ëè ïîëèíîìèàëüíî ðàçðåøèìîé çàäà÷à íàõîæäåíèÿ
�( , )G w äëÿ ñåìåéñòâà W
p
-ñîâåðøåííûõ ãðàôîâ? Îêàçûâàåòñÿ — áóäåò. Ýòî îáúÿñ-
íÿåòñÿ ñâîéñòâàìè îäíîé èç îöåíîê Øîðà, êîòîðàÿ äëÿ ïðîèçâîëüíîãî ãðàôà G ÿâ-
ëÿåòñÿ áîëåå òî÷íîé âåðõíåé îöåíêîé äëÿ �( , )G w , ÷åì îöåíêà �
W
p
G w
*
( , ) .
Îöåíêà Øîðà (îáîçíà÷èì åå �1
*
( , )G w ) ÿâëÿåòñÿ îïòèìàëüíîé (íàèëó÷øåé) ëàã-
ðàíæåâîé (äâîéñòâåííîé) îöåíêîé äëÿ êâàäðàòè÷íîé áóëåâîé çàäà÷è
�( , ) maxG w w x
i
i V
i
�
�
�
(14)
ïðè îãðàíè÷åíèÿõ:
x x i j E G
i j
� � �0 ( , ) ( ), (15)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 163
x x i V G
i i
2
0� � � � ( ), (16)
x x x x x i j E G k i j
i k j k k
� � � � �( , ) ( ), , , (17)
â âèäå êîòîðîé ôîðìóëèðóåòñÿ çàäà÷à î ìàêñèìàëüíîì âçâåøåííîì óñòîé÷èâîì
ìíîæåñòâå ãðàôà. Îöåíêó �1
*
( , )G w ìîæíî íàéòè ñ ëþáîé çàäàííîé òî÷íîñòüþ
ñ ïîìîùüþ ìåòîäîâ ìèíèìèçàöèè íåãëàäêèõ âûïóêëûõ ôóíêöèé [6]. Çäåñü áóëå-
âà ïåðåìåííàÿ x
i
�{ }0 1, ðàâíà åäèíèöå, åñëè âåðøèíà i V� âêëþ÷àåòñÿ â óñòîé-
÷èâîå ìíîæåñòâî, è ðàâíà íóëþ â ïðîòèâíîì ñëó÷àå. Áóëåâû ïåðåìåííûå äëÿ
âñåõ âåðøèí îïèñàíû êâàäðàòè÷íûìè îãðàíè÷åíèÿìè-ðàâåíñòâàìè (16). Êâàäðà-
òè÷íûå îãðàíè÷åíèÿ (15) îçíà÷àþò, ÷òî åñëè äâå âåðøèíû ñâÿçàíû ðåáðîì â ãðà-
ôå G, òî îíè îáå íå ìîãóò îäíîâðåìåííî ïðèíàäëåæàòü óñòîé÷èâîìó ìíîæåñòâó.
Êâàäðàòè÷íûå îãðàíè÷åíèÿ â ôîðìå íåðàâåíñòâ (17) ôóíêöèîíàëüíî èçáûòî÷íû,
ò.å. íå èçìåíÿþò ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé êâàäðàòè÷íîé çàäà÷è
(14)–(16). Îíè ïîëó÷àþòñÿ êàê ðåçóëüòàò óìíîæåíèÿ ðåáåðíûõ îãðàíè÷åíèé
â âèäå (4) íà ïåðåìåííûå x
k
, k i j� , . Çíàê íåðàâåíñòâ íå èçìåíèòñÿ â ñèëó òîãî,
÷òî x x
k
k
� �
2
0, è â ðåçóëüòàòå ïîëó÷àåì êâàäðàòè÷íûå íåðàâåíñòâà (17).
Èìåííî íàëè÷èå îãðàíè÷åíèé (17) ïðèäàåò îöåíêå �1
*
( , )G w ðÿä çàìå÷àòåëü-
íûõ ñâîéñòâ, êîòîðûå ñâÿçàíû ñî ñïåöèàëüíûìè ñåìåéñòâàìè ãðàôîâ. Òàê, íàïðè-
ìåð, â [6] ïîêàçàíî, ÷òî âåðõíÿÿ îöåíêà �1
*
( , )G w ÿâëÿåòñÿ òî÷íîé äëÿ �( , )G w , êîã-
äà ãðàô G t-ïåðôåêòíûé. Ñõåìà äîêàçàòåëüñòâà îñíîâàíà íà òîì, ÷òî îñëàáëåíèåì
(ðåëàêñàöèåé) êâàäðàòè÷íûõ îãðàíè÷åíèé (15)–(17) ëåãêî ïîëó÷èòü ËÏ-çàäà÷ó äëÿ
îöåíêè �
C
G w
*
( , ) . Îäíàêî èç êâàäðàòè÷íûõ îãðàíè÷åíèé (15)–(17) ñëåäóþò íåðàâå-
íñòâà â ôîðìå (11) [8]. Ýòî îçíà÷àåò, ÷òî äëÿ ïðîèçâîëüíîãî ãðàôà G ñïðàâåäëèâî
íåðàâåíñòâî
� � �
W
p
G w G w G w
* *
( , ) ( , ) ( , )� �1 . (18)
Äëÿ W
p
-ñîâåðøåííûõ ãðàôîâ íåðàâåíñòâî (18) ïðåâðàùàåòñÿ â ñòðîãîå
ðàâåíñòâî
� � �
W
p
G w G w G w
* *
( , ) ( , ) ( , ),� �1 (19)
êîòîðîå îçíà÷àåò, ÷òî îöåíêà �1
*
( , )G w äëÿ íèõ ÿâëÿåòñÿ òî÷íîé âåðõíåé îöåí-
êîé äëÿ �( , )G w . Ó÷èòûâàÿ, ÷òî îöåíêó �1
*
( , )G w ìîæíî íàéòè çà ïîëèíîìèàëü-
íîå âðåìÿ, ïîëó÷àåì, ÷òî åñëè ãðàô G ïðèíàäëåæèò ñåìåéñòâó W
p
-ñîâåðøåííûõ
ãðàôîâ, òî çàäà÷à íàõîæäåíèÿ �( , )G w ïîëèíîìèàëüíî ðàçðåøèìà. Îäíàêî îòâåò,
êîòîðûé äàåò ðàâåíñòâî (19), íîñèò ñêîðåå òåîðåòè÷åñêèé õàðàêòåð, ÷åì ïðàêòè-
÷åñêèé. Âû÷èñëåíèå îöåíêè �1
*
( , )G w ñâÿçàíî ñ ðåøåíèåì çàäà÷è ìèíèìèçàöèè
âûïóêëîé íåãëàäêîé ôóíêöèè, îïðåäåëåííîé íà ïàðàìåòðè÷åñêè çàäàííîì ñåìåé-
ñòâå íåîòðèöàòåëüíî îïðåäåëåííûõ ñèììåòðè÷íûõ ìàòðèö ðàçìåðà | | | |V V� , ëè-
íåéíî çàâèñÿùèõ îò íåèçâåñòíûõ ìíîæèòåëåé Ëàãðàíæà (ñîîòâåòñòâóþò îãðàíè-
÷åíèÿì (15), (16) è (17)). Êîëè÷åñòâî íåèçâåñòíûõ ìíîæèòåëåé Ëàãðàíæà èìååò
ïîðÿäîê O V(| | )
3
, è êîãäà ãðàô ñîäåðæèò íåñêîëüêî ñîòåí âåðøèí, äîñòàòî÷íî
òî÷íîå íàõîæäåíèå îöåíêè �1
*
( , )G w ÿâëÿåòñÿ ïðàêòè÷åñêè íåðàçðåøèìîé
çàäà÷åé äëÿ ñîâðåìåííûõ ìåòîäîâ íåäèôôåðåíöèðóåìîé îïòèìèçàöèè.
ÎÖÅÍÊÀ �W G w( , ) È ÀËÃÎÐÈÒÌ LPWSTAB
Íàõîæäåíèå îöåíêè �
W
p
G w
*
( , ) — NP-òðóäíàÿ çàäà÷à. Áîëåå òîãî, NP-òðóäíîé ÿâ-
ëÿåòñÿ è çàäà÷à íàõîæäåíèÿ íà îñíîâå óæå èìåþùåãîñÿ íå÷åòíîãî öèêëà òàêîãî
p-êîëåñà, äëÿ êîòîðîãî â òî÷êå x x x
V
* *
| |
*
, ,� { }1 � ìàêñèìàëüíî íàðóøàåòñÿ ëèíåé-
íîå íåðàâåíñòâî â âèäå (11). Ïîýòîìó âìåñòî îöåíêè �
W
p
G w
*
( , ) ðàññìîòðèì
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
îñëàáëåííóþ ËÏ-îðèåíòèðîâàííóþ âåðõíþþ îöåíêó äëÿ �( , )G w íà îñíîâå ëè-
íåéíûõ íåðàâåíñòâ äëÿ òàêèõ p-êîëåñ â ãðàôå G, êîòîðûå ëåãêî ïîñòðîèòü. Ýòó
îöåíêó íàçîâåì îöåíêîé �
W
G w( , ) è â îñíîâó àëãîðèòìà äëÿ åå íàõîæäåíèÿ ïî-
ëîæèì ñëåäóþùåå.
Íà êàæäîé èòåðàöèè àëãîðèòìà áóäåì ðåøàòü ËÏ-çàäà÷ó â âèäå
f w x
W i
i V
i
*
max�
�
�
(20)
ïðè îãðàíè÷åíèÿõ:
0 1� � � �x i V G
i
( ), (21)
x x i j E G
i j
� � � �1 ( , ) ( ), (22)
x k C C G
i
i V C
k
k
�
�
�
�
� � � �
( )
,
2 1
2 1 odd (23)
x k x k W W G
i
i V C
j
j V Q
k p
k p
� � � � �
� �
� �
�
� �
( ) ( )
.
2 1
2 1 odd (24)
Çäåñü Codd è Wodd — êîíå÷íûå ìíîæåñòâà íå÷åòíûõ öèêëîâ è p-êîëåñ (âîçìîæíî,
ïóñòûå). Äëÿ ôîðìèðîâàíèÿ ìíîæåñòâà íå÷åòíûõ öèêëîâ ïðèìåíèì àëãîðèòì íà-
õîæäåíèÿ íå÷åòíûõ öèêëîâ èç [2], èñïîëüçóÿ x x x
V
* *
| |
*
, ,� { }1 � — îïòèìàëüíîå ðå-
øåíèå ËÏ-çàäà÷è (20)–(24). Äëÿ ôîðìèðîâàíèÿ ìíîæåñòâà p-êîëåñ èñïîëüçóåì óæå
íàéäåííûå íå÷åòíûå öèêëû è äîïîëíèì èõ äî p-êîëåñ ñ ïîìîùüþ ïðîñòåéøåãî ïî
êîëè÷åñòâó âû÷èñëåíèé àëãîðèòìà (ïî òèïó «æàäíîãî» àëãîðèòìà). Òàêîé àëãîðèòì
íàçîâåì àëãîðèòìîì «ïîñëåäîâàòåëüíîãî âêëþ÷åíèÿ íàèëó÷øèõ âåðøèí».
Ïóñòü i i
k1 2 1, ,�
�
— âåðøèíû, ÷åðåç êîòîðûå ïðîõîäèò íå÷åòíûé öèêë C
k2 1�
,
è âåêòîð x
*
— îïòèìàëüíîå ðåøåíèå ËÏ-çàäà÷è (20)–(24). ×òîáû íà îñíîâå íå÷åò-
íîãî öèêëà C
k2 1�
ïîñòðîèòü p-êîëåñî â àëãîðèòìå «ïîñëåäîâàòåëüíîãî âêëþ÷åíèÿ
íàèëó÷øèõ âåðøèí», òðåáóåòñÿ âûïîëíåíèå ñëåäóþùåé ïîñëåäîâàòåëüíîñòè äåé-
ñòâèé. Íàéäåì ïîäìíîæåñòâî âåðøèí èç V G( ), äëÿ êîòîðîãî êàæäàÿ èç âõîäÿùèõ
â íåãî âåðøèí ñâÿçàíà ñî âñåìè âåðøèíàìè íå÷åòíîãî öèêëà C
k2 1�
. Åñëè òàêîå
ïîäìíîæåñòâî âåðøèí íåïóñòî, òî âûáåðåì èç íåãî òó âåðøèíó, äëÿ êîòîðîé çíà÷å-
íèå êîìïîíåíòû âåêòîðà x
*
ìàêñèìàëüíî, è äîáàâèì åãî ê ìíîæåñòâó âåðøèí ñ íî-
ìåðîì ( )2 2k � .  ðåçóëüòàòå ïîëó÷èì 1-êîëåñî ñ ìíîæåñòâîì âåðøèí
i i i
k k1 2 1 2 2, , ,�
� �
. Äëÿ íåãî òî÷íî òàê æå íàéäåì ïîäìíîæåñòâî âåðøèí èç V G( ) ,
äëÿ êîòîðîãî êàæäàÿ èç âõîäÿùèõ â íåãî âåðøèí ñâÿçàíà ñî âñåìè âåðøèíàìè 1-êî-
ëåñà. Åñëè ïîäìíîæåñòâî âåðøèí íåïóñòî, òî âûáåðåì âåðøèíó ñ ìàêñèìàëüíûì
çíà÷åíèåì êîìïîíåíòû âåêòîðà x
*
è äîáàâèì ê ìíîæåñòâó âåðøèí ñ íîìåðîì
( )2 3k � .  ðåçóëüòàòå ïîëó÷èì 2-êîëåñî ñ ìíîæåñòâîì âåðøèí i i
k1 2 1, , ,�
�
i i
k k2 2 2 3� �
, . Äëÿ íåãî ïðèìåíèì òàêóþ æå ïðîöåäóðó, è ëèáî ïîëó÷èì 3-êîëåñî, ëèáî
ïðåðâåì ïðîöåññ, åñëè 3-êîëåñà íå ñóùåñòâóåò (ïîäìíîæåñòâî âåðøèí èç V G( ) , ñâÿ-
çàííûõ ñ êàæäîé èç âåðøèí 2-êîëåñà, îêàæåòñÿ ïóñòûì). Ïóñòü 3-êîëåñî ïîëó÷åíî. Áó-
äåì ïðîäîëæàòü ïðîöåññ äî òåõ ïîð, ïîêà ïîäìíîæåñòâî âåðøèí èç V G( ) , ñâÿçàííûõ
ñ êàæäîé èç âåðøèí óæå íàéäåííîãî p-êîëåñà, íå îêàæåòñÿ ïóñòûì.
Àëãîðèòì äëÿ íàõîæäåíèÿ îöåíêè �
W
G w( , ) (íàçîâåì åãî LPWSTAB) ñîñòîèò
â ñëåäóþùåì.
Íà÷àëüíàÿ óñòàíîâêà. Ïîëîæèì itn = 0 è C0 � , W0 � (ìíîæåñòâà íå÷åò-
íûõ öèêëîâ è p-êîëåñ ïóñòûå). Ïåðåéäåì ê øàãó 1.
Øàã 1. Èìååì ìíîæåñòâî íå÷åòíûõ öèêëîâ C itn è ìíîæåñòâî p-êîëåñ Witn .
Ïîëîæèì C Codd itn� , W Wodd itn� è, ðåøèâ ËÏ-çàäà÷ó (20)–(24), íàéäåì f
W
*
è
x x x
V
* *
| |
*
( , , )� 1 � .
Øàã 2. Ïîñòðîèì âçâåøåííûé íåîðèåíòèðîâàííûé ãðàô
�
G V E( , ) . Ìíî-
æåñòâî âåðøèí
V G( ) âêëþ÷àåò âåðøèíó i è åå êîïèþ
i äëÿ âñåõ i V G� ( ) . Ìíîæåñ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 165
òâî ðåáåð
E G( ) ñîñòîèò èç ðåáåð, êîòîðûå ñîåäèíÿþò âñå òå ïàðû âåðøèí ( , )i j
è
( , )
i j , äëÿ êîòîðûõ ïàðà âåðøèí i è j ñîåäèíåíà ðåáðîì ( , )i j â ãðàôå G. Ïðèñâîèì
ðåáðàì ( , )i j
è ( , )
i j îäèí è òîò æå ïîëîæèòåëüíûé âåñ (äëèíà ðåáðà)
l i j l i j x x
i j
( , ) ( , ) * *
�
� � �1 .
Øàã 3. Ðàññìîòðèì ãðàô
G êàê îðèåíòèðîâàííûé (ðåáðó ( , )i j
ñîîòâåòñòâóþò
äóãè ( , )i j
è ( , )
j i ñ äëèíàìè, ðàâíûìè äëèíå ðåáðà ( , )i j
, ò.å. l i j( , )
) , è äëÿ êàæäîé
âåðøèíû i V� íàéäåì êðàò÷àéøèé ïóòü, êîòîðûé íà÷èíàåòñÿ â âåðøèíå i è çàêàí÷è-
âàåòñÿ â âåðøèíå i
(êîïèè âåðøèíû i). ×èñëî òàêèõ êðàò÷àéøèõ ïóòåé ðàâíî | |V . Èç
íèõ îñòàâëÿåì òîëüêî òå, êîòîðûå îïðåäåëÿþò íå÷åòíûé öèêë. Ïóñòü ÷èñëî òàêèõ
êðàò÷àéøèõ ïóòåé ðàâíî n (n V� | | ) . Íàéäåì íå÷åòíûå öèêëû C C
k k
n
2 1 2 11� �
, ,�
(îíè ñîîòâåòñòâóþò n íàéäåííûì êðàò÷àéøèì ïóòÿì).
Øàã 4. Óñòàíîâèì ìíîæåñòâà
C è
W ïóñòûìè è çàïîëíèì èõ ñëåäóþùèì îá-
ðàçîì. Êàæäûé èç íå÷åòíûõ öèêëîâ C
k
i
2 1�
äëÿ i n� 1, ,� ñ ïîìîùüþ àëãîðèòìà
«ïîñëåäîâàòåëüíîãî âêëþ÷åíèÿ íàèëó÷øèõ âåðøèí» äîïîëíÿåì äî p-êîëåñà â ãðà-
ôå G. Ïóñòü òàêîå p-êîëåñî ïîëó÷åíî. Åñëè ëèíåéíîå íåðàâåíñòâî â ôîðìå (11) äëÿ
íåãî íàðóøåíî, òî íàéäåííîå p-êîëåñî âêëþ÷àåì â ìíîæåñòâî
W . Åñëè ïîñòðîèòü
p-êîëåñî íà áàçå íå÷åòíîãî öèêëà íå óäàëîñü, íî ëèíåéíîå íåðàâåíñòâî â âèäå (5)
äëÿ ýòîãî íå÷åòíîãî öèêëà ÿâëÿåòñÿ íàðóøåííûì, òî òàêîé íå÷åòíûé öèêë âêëþ÷à-
åì â ìíîæåñòâî
C . Åñëè ïîñëå çàâåðøåíèÿ ýòîé ïðîöåäóðû äëÿ âñåõ i n� 1, ,� îáà
ìíîæåñòâà
C è
W ïóñòûå, òî �
W W
G w f( , )
*
� è îñòàíîâ. Èíà÷å ïåðåéäåì ê øàãó 5.
Øàã 5. Ïîëîæèì C C Citn +1 itn� �
, W W Witn +1 itn� �
, itn = itn + 1. Ïåðåéäåì
ê øàãó 1.
ËÏ-çàäà÷à (20)–(24) ïîñòðîåíà êàê ðàñøèðåíèå ËÏ-çàäà÷è (7)–(10) çà ñ÷åò êîíå÷-
íîãî íàáîðà ñïðàâåäëèâûõ äëÿ p-êîëåñ ëèíåéíûõ íåðàâåíñòâ â âèäå (24). Ïîýòîìó
îöåíêó �
W
G w( , ) ìîæíî ðàññìàòðèâàòü êàê óëó÷øåíèå îöåíêè �
C
G w
*
( , ) ñ ïîìîùüþ
èñïîëüçîâàíèÿ ëèíåéíûõ íåðàâåíñòâ äëÿ p-êîëåñ â ãðàôå G. Â ðåçóëüòàòå îíà áóäåò ñî-
õðàíÿòü ñâîéñòâà îöåíêè �
C
G w
*
( , ) , à â ñëó÷àå îáíàðóæåíèÿ p-êîëåñ, äëÿ êîòîðûõ ëè-
íåéíûå íåðàâåíñòâà â âèäå (11) ÿâëÿþòñÿ íàðóøåííûìè, îöåíêà �
W
G w( , ) ìîæåò îêà-
çàòüñÿ áîëåå òî÷íîé âåðõíåé îöåíêîé äëÿ �( , )G w , ÷åì îöåíêà �
C
G w
*
( , ) .
 öåëÿõ ïðîâåðêè ñâîéñòâ îöåíêè �
W
G w( , ) àëãîðèòì ðåàëèçîâàí ïðîãðàììîé
LPWSTAB íà ÿçûêå C++. Äëÿ ðåøåíèÿ ËÏ-çàäà÷è èñïîëüçîâàíà ïðîãðàììà
SOPLEX [3], à äëÿ íàõîæäåíèÿ êðàò÷àéøåãî ïóòè â îðèåíòèðîâàííîì ãðàôå — ïðî-
ãðàììà DIKH [4]. Â ïðîãðàììå LPWSTAB èñïîëüçóåòñÿ ïàðàìåòð �, êîòîðûé îçíà-
÷àåò, ÷òî ëèíåéíûå íåðàâåíñòâà, ñâÿçàííûå ñ íå÷åòíûì öèêëîì C
k2 1�
è p-êîëåñîì
W
k p2 1� �
, ñ÷èòàþòñÿ íàðóøåííûìè (â òî÷êå x
*
) è âêëþ÷àþòñÿ â ËÏ-çàäà÷ó, åñëè
äëÿ íèõ âûïîëíÿþòñÿ óñëîâèÿ:
x k x k x k
i
i V C
i
i V C
j
j V Q
k k p
*
( )
*
( )
*
( )
,
� � �
� �
� � �
� � � � �
2 1 2 1
� �.
Ïåðâàÿ ñåðèÿ ýêñïåðèìåíòîâ ñ ïðîãðàììîé LPWSTAB çàêëþ÷àëàñü â ïðîâåðêå
òî÷íîñòè îöåíêè �
W
G w( , ) , ãäå w
i
� 1� �i V G( ) , äëÿ òîãî æå íàáîðà DIMACS-ãðàôîâ,
äëÿ êîòîðîãî âû÷èñëÿëàñü îöåíêà �
C
G
*
( ) . Ðàññìàòðèâàëèñü 16 ãðàôîâ. Èñêëþ÷åíû
òîëüêî äâà ãðàôà — hamming6-2 è hamming8-2, äëÿ êîòîðûõ íå òðåáîâàëîñü âêëþ÷åíèÿ
íè îäíîãî íå÷åòíîãî öèêëà. Äëÿ ïðîãðàììû LPWSTAB èñïîëüçîâàëîñü çíà÷åíèå
� � 0 01, . Ðåçóëüòàòû ýêñïåðèìåíòà îòðàæåíû â òàáë. 2. Äëÿ êàæäîãî èç 16 ãðàôîâ ïðèâå-
äåíû çíà÷åíèÿ îöåíêè �
W
G( ) è çàòðàòû íà åå íàõîæäåíèå — êîëè÷åñòâî èòåðàöèé
(ñòîëáåö itn) è âðåìÿ â ñåêóíäàõ íà ïðîöåññîðå AMD Athlon 1,81GHz (ñòîëáåö t
W
).
Îñòàëüíûå ñòîëáöû â òàáëèöå õàðàêòåðèçóþò ñòðóêòóðó íàêîïëåííûõ ïðîãðàììîé
LPWSTAB (âêëþ÷åííûõ â ËÏ-çàäà÷ó íà ïîñëåäíåé èòåðàöèè) ëèíåéíûõ íåðàâåíñòâ, èñ-
êëþ÷àÿ «ðåáåðíûå» íåðàâåíñòâà. Ñòîëáåö N çàäàåò ïîëíîå êîëè÷åñòâî âêëþ÷åííûõ
â ËÏ-çàäà÷ó ëèíåéíûõ íåðàâåíñòâ, à â ñòîëáöàõ NC, NW è NQ óêàçàíî, ñêîëüêî ñðåäè
íèõ áûëî íå÷åòíûõ öèêëîâ (ñþäà æå âêëþ÷åíû 3-êëèêè), p-êîëåñ ñ k � 2 è êëèê, êîòî-
ðûå ïîëó÷åíû êàê p-êîëåñà ïðè k � 1 è ïðîèçâîëüíûõ p.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Èç òàáë. 2 âèäíî, ÷òî îöåíêà �
W
G( ) ÿâëÿåòñÿ òî÷íîé äëÿ �( )G äëÿ äåâÿòè ãðà-
ôîâ èç 16. Ñòðóêòóðà íàêîïëåííûõ íåðàâåíñòâ äëÿ ãðàôà san200.0.9-1 ïîçâîëÿåò
óòâåðæäàòü, ÷òî îí íå ìîæåò áûòü t-ñîâåðøåííûì, õîòÿ äëÿ íåãî îöåíêà �
C
G
*
( ) ÿâ-
ëÿåòñÿ òî÷íîé âåðõíåé îöåíêîé äëÿ �( )G (ñì. òàáë. 1). Òàêîé âûâîä äàþò âîçìîæ-
íîñòü ñäåëàòü 16 íàêîïëåííûõ 4-êëèê (ñì. ñòîëáåö NQ â òàáë. 2), è, ñëåäîâàòåëüíî,
äëÿ ãðàôà san200.0.9-1 ìîæíî ïîäîáðàòü òàêèå âåñà âåðøèí, ïðè êîòîðûõ îöåíêà
�
C
G w
*
( , ) íå áóäåò òî÷íîé äëÿ �( , )G w .
Çàòðàòû ïî âðåìåíè íàõîæäåíèÿ îöåíêè �
W
G( ) ïðåâûøàþò (èíîãäà ñóùåñ-
òâåííî) çàòðàòû ïî âðåìåíè íà íàõîæäåíèå îöåíêè �
C
G
*
( ) ïðîãðàììîé LPCSTABb.
Îäíó èç ïðè÷èí ýòîãî îáúÿñíÿþò íàêîïëåííûå íåðàâåíñòâà äëÿ ãðàôà san200.0.9-1,
÷òî ïîäñêàçûâàåò ïóòü äëÿ óñîâåðøåíñòâîâàíèÿ àëãîðèòìà LPWSTAB. Òàê, äëÿ
îöåíêè �
W
G( ) íàêîïëåíî 663 íåðàâåíñòâà (èç íèõ íå÷åòíûõ öèêëîâ — 646 è
4-êëèê — 16). Èõ ìåíüøå, ÷åì êîëè÷åñòâî íàêîïëåííûõ íå÷åòíûõ öèêëîâ ïðîãðàì-
ìîé LPCSTABb (ðàâíî 828) ïðè òîé æå òî÷íîñòè � � 0 01, , è ñóùåñòâåííî áîëüøå,
÷åì ÷èñëî íå÷åòíûõ öèêëîâ, íàêîïëåííûõ ïðîãðàììîé LPCSTABa (ðàâíî 175,
ñì. òàáë. 1). Ýòî îçíà÷àåò, ÷òî ïðîöåäóðà âêëþ÷åíèÿ íåðàâåíñòâ â ËÏ-çàäà÷ó â ïðî-
ãðàììå LPWSTAB òðåáóåò äîðàáîòêè è äîïîëíèòåëüíîãî èññëåäîâàíèÿ ñ öåëüþ
óìåíüøèòü êîëè÷åñòâî âêëþ÷àåìûõ â ËÏ-çàäà÷ó íàðóøåííûõ íåðàâåíñòâ. Íàïðè-
ìåð, ìîæíî óñòðîèòü èõ ðàíæèðîâàíèå ïî òî÷íîñòè íàðóøåíèÿ íåðàâåíñòâ, îãðàíè-
÷èòü êîëè÷åñòâî âêëþ÷àåìûõ íåðàâåíñòâ íà îäíîé èòåðàöèè. Ñîçäàíèå áîëåå êîí-
ñòðóêòèâíîãî êðèòåðèÿ äëÿ âêëþ÷åíèÿ íàðóøåííûõ íåðàâåíñòâ ìîæåò ñïîñîáñòâî-
âàòü è óìåíüøåíèþ îáùåãî êîëè÷åñòâà èòåðàöèé LPWSTAB-àëãîðèòìà, ÷òî ìîæåò
ñäåëàòü çàòðàòû ïî âðåìåíè íàõîæäåíèÿ îöåíêè �
W
G w( , ) áîëåå áëèçêèìè ê çàòðà-
òàì íà íàõîæäåíèå îöåíêè �
C
G w
*
( , ) ñ ïîìîùüþ àëãîðèòìà LPCSTABb.
Êðîìå òåñòîâûõ ïðèìåðîâ èç DIMACS-áèáëèîòåêè ïðîãðàììà LPWSTAB ïðî-
âåðåíà íà òåñòîâûõ çàäà÷àõ äëÿ ïîìåõîóñòîé÷èâûõ êîäîâ èç ñàéòà
http://www.reseach.att.com/~njas/doc/graphs.html, äëÿ êîòîðûõ ïîëó÷åíû ïîìåõîçà-
ùèùåííûå êîäû ìàêñèìàëüíîãî îáúåìà [9]. Íàïðèìåð, äëÿ âñåõ òåñòîâûõ çàäà÷,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 167
Ò à á ë è ö à 2
Òåñòîâûå
íàáîðû èç
DIMACS-ãðàôîâ
Ðåçóëüòàòû òåñòîâûõ ýêñïåðèìåíòîâ äëÿ îöåíêè �W G( )
è çàòðàòû íà åå íàõîæäåíèå
| |V �( )G �
W
G( ) itn t
W
N NC NW NQ
c-fat200-1 200 12 12,00 31 485,8 5787 0 0 5787
c-fat200-2 200 24 24,00 17 219,5 3342 0 12 3330
c-fat200-5 200 58 66,66 3 29,0 533 533 0 0
johnson16 120 8 8,00 3 2,3 128 36 7 85
johnson8-2 28 4 4,00 3 0,7 41 8 7 26
johnson8-4 70 14 14,00 3 1,0 139 12 4 123
keller4 171 11 14,82 14 32,8 1151 41 36 1074
hamming6-4 64 4 5,33 5 2,1 301 0 16 285
hamming8-4 256 16 16,00 5 54,8 1144 48 48 1048
san200-0.7 200 18 19,35 18 58 1569 134 1 1434
san200.0.9-1 200 70 70,00 4 6,4 663 646 1 16
san200-0.9-2 200 60 60,00 11 16 1369 1299 0 70
san200.0.9-3 200 44 44,00 21 23,4 1526 1378 0 148
brock200-l 200 21 38,58 32 88,5 1543 227 28 1288
mann-a27 378 126 135,00 7 5,1 245 245 0 0
mann-a9 45 16 18,00 1 0,5 21 21 0 0
ñâÿçàííûõ ñ êîððåêòèðîâàíèåì åäèíè÷íîé îøèáêè â Z-êàíàëå, ïðîãðàììà
LPWSTAB íàøëà âåðõíèå îöåíêè äëÿ ìàêñèìàëüíîãî îáúåìà êîäà, êîòîðûå ñîâïà-
ëè ñ ÷èñëîì Ëîâàñà. Äëÿ òåñòîâîé çàäà÷è, ãäå ãðàô âêëþ÷àåò 1024 âåðøèíû è 33280
ðåáåð, ïðîãðàììà çàòðàòèëà âðåìÿ t � 1139 c íà ïðîöåññîðå AMD Athlon. Ïðè ýòîì
ïðèøëîñü ðåøàòü ËÏ-çàäà÷ó 12 ðàç è íàõîäèòü êðàò÷àéøèå ïóòè â îðèåíòèðîâàí-
íîì ãðàôå (ñîäåðæèò 2048 âåðøèí è 133120 äóã) 12�1024 ðàç. Êîëè÷åñòâî íàêîï-
ëåííûõ íåðàâåíñòâ ïðè ýòîì ñîñòàâèëî 2768 — èç íèõ 249 íå÷åòíûõ öèêëîâ, 2468
êëèê è 51 p-êîëåñî.
Âòîðàÿ ñåðèÿ ýêñïåðèìåíòîâ äëÿ ïðîãðàììû LPWSTAB ñâÿçàíà ñ åå âûõîäîì,
à èìåííî ñ ËÏ-çàäà÷åé, êîòîðàÿ ñîîòâåòñòâóåò îöåíêå �
W
G( ). Öåëüþ ýêñïåðèìåí-
òîâ áûëî âûÿñíèòü: íàñêîëüêî áûñòðåå ñ ïîìîùüþ ïðîãðàìì äëÿ ðåøåíèÿ çàäà÷è
öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ ìîæíî ðåøèòü áóëåâó ËÏ-çàäà÷ó,
ïîäãîòîâëåííóþ ïðîãðàììîé LPWSTAB, ÷åì áóëåâó ËÏ-çàäà÷ó ñ ðåáåðíûìè îãðà-
íè÷åíèÿìè (âêëþ÷àåò òîëüêî ëèíåéíûå íåðàâåíñòâà äëÿ âñåõ ðåáåð ãðàôà). Äëÿ
ýòîé öåëè áûëà âûáðàíà ñâîáîäíî ðàñïðîñòðàíÿåìàÿ ïðîãðàììà SCIP (Solving
Constraint Integer Programming) [10]. Äëÿ òåõ æå íàáîðîâ DIMACS-ãðàôîâ ðåçóëüòà-
òû ýêñïåðèìåíòîâ îòðàæåíû â òàáë. 3. Çäåñü N
SCIP
— êîëè÷åñòâî ïåðåìåííûõ
â îáåèõ áóëåâûõ ËÏ-çàäà÷àõ (ðàâíî êîëè÷åñòâó âåðøèí ãðàôà), M
ESCIP
— êîëè-
÷åñòâî îãðàíè÷åíèé â áóëåâîé ËÏ-çàäà÷å ñ ðåáåðíûìè îãðàíè÷åíèÿìè (ðàâíî êîëè-
÷åñòâó âåðøèí è ðåáåð â ãðàôå), M
WSCIP
— êîëè÷åñòâî îãðàíè÷åíèé â áóëåâîé
ËÏ-çàäà÷å äëÿ îöåíêè �
W
G w( , ) (ðàâíî ñóììå êîëè÷åñòâà âåðøèí è ðåáåð â ãðàôå è
íàêîïëåííûõ ïðîãðàììîé LPWSTAB ëèíåéíûõ íåðàâåíñòâ), M
SCIP
— êîëè÷åñòâî
îãðàíè÷åíèé â áóëåâîé ËÏ-çàäà÷å, êîòîðîå îñòàëîñü ïîñëå ïðåïðîöåññèíãà ïðîãðàì-
ìû SCIP (çàäà÷à ñ ýòèì êîëè÷åñòâîì îãðàíè÷åíèé ÿâëÿåòñÿ ñòàðòîâîé äëÿ ìåòîäà
âåòâåé è ãðàíèö, ðåàëèçîâàííîé â ïðîãðàììå SCIP), t
ESCIP
è t
WSCIP
— âðåìÿ ðåøå-
íèÿ ïðîãðàììîé SCIP áóëåâîé ËÏ-çàäà÷è ñ ðåáåðíûìè îãðàíè÷åíèÿìè è áóëåâîé
ËÏ-çàäà÷è äëÿ îöåíêè �
W
G( ) ñîîòâåòñòâåííî. Ïîñëåäíèé ñòîëáåö õàðàêòåðèçóåò îò-
íîøåíèå çàòðàò ïî âðåìåíè ðåøåíèÿ îáåèõ áóëåâûõ ËÏ-çàäà÷: óêàçàíî, âî ñêîëüêî
ðàç áûñòðåå ïðîãðàììà SCIP ðåøèëà áóëåâó ËÏ-çàäà÷ó äëÿ îöåíêè �
W
G( ) , ÷åì áó-
ëåâó ËÏ-çàäà÷ó äëÿ ðåáåðíûõ îãðàíè÷åíèé.
Èç òàáë. 3 âèäíî, ÷òî áóëåâà ËÏ-çàäà÷à äëÿ îöåíêè �
W
G( ) ïðîèãðàëà òîëüêî
â ÷åòûðåõ ñëó÷àÿõ: íåçíà÷èòåëüíî äëÿ ãðàôîâ c-fat200-5, san200-0.9-2 è mann-a9 è
ñóùåñòâåííî (ïî÷òè â òðè ðàçà) äëÿ ãðàôà san200.0.9-3.  îñòàëüíûõ ñëó÷àÿõ áóëåâà
ËÏ-çàäà÷à äëÿ îöåíêè �
W
G( ) âûèãðàëà, è î÷åíü ñóùåñòâåííî (áîëåå ÷åì â 20 ðàç
äëÿ ãðàôà hamming8-4, áîëåå ÷åì â âîñåìü ðàç äëÿ ãðàôà c-fat200-1, áîëåå ÷åì â ÷å-
òûðå ðàçà äëÿ ãðàôà c-fat200-2, ïî÷òè â ÷åòûðå ðàçà äëÿ ãðàôà keller4, áîëåå ÷åì
â äâà ðàçà äëÿ ãðàôà san200-0.7-2, áîëåå ÷åì â øåñòü ðàç äëÿ ãðàôà mann-a27). Íàè-
áîëåå çíà÷èòåëüíûé âûèãðûø ïî ðåàëüíîìó âðåìåíè ïîëó÷èëñÿ äëÿ ãðàôà
brock200-1 — 2 ÷ 13 ìèí ïðîòèâ 6 ÷ 19 ìèí. Äëÿ ãðàôîâ johnson16-2-4, johnson8-2-4
è johnson8-4-4 êàê íåçíà÷èòåëüíûé, òàê è ñóùåñòâåííûé âûèãðûø ïî âðåìåíè íè-
÷åãî íå çíà÷àò. Äëÿ íèõ îáùåå âðåìÿ ðåøåíèÿ îáåèõ áóëåâûõ ËÏ-çàäà÷ î÷åíü ìàëî.
 ýòîì ñëó÷àå ïðåäñòàâëÿåò èíòåðåñ êîëè÷åñòâî ëèíåéíûõ íåðàâåíñòâ, êîòîðûå
îñòàâëåíû â áóëåâûõ ËÏ-çàäà÷àõ ïîñëå ïðåïðîöåññèíãà. Îíî íåâåëèêî ïî ñðàâíå-
íèþ ñ êîëè÷åñòâîì âåðøèí â ýòèõ ãðàôàõ, è ýòî îáúÿñíÿåòñÿ íàõîæäåíèåì àëãîðèò-
ìîì LPWSTAB äîñòàòî÷íî «õîðîøèõ» êëèêîâûõ îãðàíè÷åíèé, êîòîðûå ñðàâíè-
òåëüíî íåáîëüøèì êîëè÷åñòâîì ïîêðûâàþò âåðøèíû ãðàôà.
Ñ ïîìîùüþ ïðîãðàììû SCIP è ïîäãîòîâëåííîé ïðîãðàììîé LPWSTAB ËÏ-çàäà÷è
äëÿ îöåíêè �
W
G( ) íàéäåíà òî÷íàÿ âåðõíÿÿ îöåíêà äëÿ ìàêñèìàëüíîãî îáúåìà êîäà, êîð-
ðåêòèðóþùåãî îäíî óäàëåíèå áèòà, äëÿ ãðàôà 1dc1024. Çàòðàòû ïî âðåìåíè ñîñòàâèëè
55 ÷ íà ïðîöåññîðå AMD Athlon 1,81GHz. Ýòî çíà÷èòåëüíî ìåíüøå, ÷åì âðåìÿ, óêàçàí-
íîå íà ñàéòå http://www.reseach.att.com/~njas/doc/graphs.html. Îíî ðàâíî 298 ÷ è áûëî
äîñòèãíóòî ñ ïîìîùüþ ìåòîäà âåòâåé è ãðàíèö è îöåíîê Ëîâàñà íà ìîùíîì êîì-
ïüþòåðå IBM P690. Äëÿ ãðàôà 1dc1024 îöåíêà �
W
G( ) ðàâíà 96,412 (òî÷íîå ðåøå-
íèå �( )G � 94). Ïðîãðàììà LPWSTAB íàêîïèëà 3483 íåðàâåíñòâà (èç íèõ 276 —
íå÷åòíûõ öèêëîâ, 3154 — êëèê, 53 — p-êîëåñ) è çàòðàòèëà 1128,7 ñ. Áóëåâà ËÏ-çà-
äà÷à ñîäåðæàëà 28570 ëèíåéíûõ íåðàâåíñòâ äî ïðåïðîöåññèíãà è 2162 ëèíåéíûõ
íåðàâåíñòâà ïîñëå ïðåïðîöåññèíãà ïðîãðàììû SCIP.
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Ïðè ðàáîòå ñ áîëüøèìè ãðàôàìè (ïîðÿäêà òûñÿ÷ âåðøèí) ïðîÿâèëñÿ îñíîâíîé
íåäîñòàòîê àëãîðèòìà LPWSTAB. Îí ñâÿçàí ñ òåì, ÷òî ëåæàùàÿ â åãî îñíîâå
ËÏ-çàäà÷à òîëüêî íàêàïëèâàåò ëèíåéíûå îãðàíè÷åíèÿ, íå îòñåèâàÿ çàâåäîìî ëèø-
íèå. Èç-çà ýòîãî â ïðîãðàììå SCIP çíà÷èòåëüíîå âðåìÿ çàíèìàåò ïðåïðîöåññèíã
ËÏ-çàäà÷è.  ðåçóëüòàòå â áóëåâîé ËÏ-çàäà÷å äëÿ îöåíêè �( , )G w îñòàåòñÿ íàìíîãî
ìåíüøå îãðàíè÷åíèé. Ãëàâíûì îáðàçîì ïî ýòîé ïðè÷èíå ïðèîñòàíîâëåíû ïîïûòêè
ðåøàòü çàäà÷è, ñâÿçàííûå ñ ãðàôàìè áîëüøèõ ðàçìåðîâ. Î÷åâèäíî, ÷òî îòñåâ ëèø-
íèõ ëèíåéíûõ îãðàíè÷åíèé â àëãîðèòìå LPWSTAB òîëüêî óñêîðèò âðåìÿ íàõîæäå-
íèÿ îöåíêè �( , )G w , è ýòî ÿâëÿåòñÿ ðåçåðâîì äëÿ ðàçðàáîòêè áîëåå áûñòðûõ ðåàëè-
çàöèé LPWSTAB-ïðîãðàììû. Òàê, íàïðèìåð, ïðîñòåéøèå óñîâåðøåíñòâîâàíèÿ
çäåñü î÷åâèäíû: òå ðåáåðíûå íåðàâåíñòâà, äëÿ êîòîðûõ ïàðà âåðøèí âõîäèò â êà-
êóþ-ëèáî èç êëèê äëÿ îãðàíè÷åíèé, âõîäÿùèõ â ËÏ-çàäà÷ó, ñëåäóåò îòáðîñèòü. Áî-
ëåå òîíêèå îòñåâû ñâÿçàíû ñ àíàëèçîì äâîéñòâåííûõ ïåðåìåííûõ äëÿ ËÏ-çàäà÷è íà
êàæäîé èç èòåðàöèé LPWSTAB-àëãîðèòìà.
ÇÀÊËÞ×ÅÍÈÅ
Îòìåòèì ðÿä âàæíûõ ìîìåíòîâ äëÿ çàäà÷è íàõîæäåíèÿ âçâåøåííîãî ÷èñëà
óñòîé÷èâîñòè ãðàôà �( , )G w , êîòîðûå ñëåäóþò èç âû÷èñëèòåëüíûõ ýêñïåðèìåí-
òîâ äëÿ îöåíîê �
C
G w
*
( , ) è �
W
G w( , ) .
1. Ñîâðåìåííûå îáùåäîñòóïíûå ËÏ-ïðîãðàììû ïîçâîëÿþò ñîçäàâàòü äëÿ ñî-
âðåìåííûõ ÏÝÂÌ ïðàêòè÷åñêè ïðèãîäíûå (ïî âðåìåíè) àëãîðèòìû äëÿ íàõîæäå-
íèÿ ËÏ-îðèåíòèðîâàííûõ âåðõíèõ îöåíîê äëÿ �( , )G w äëÿ ãðàôîâ, ñîäåðæàùèõ íå-
ñêîëüêî ñîòåí âåðøèí. Ýòî ïîäòâåðæäàþò òåñòîâûå ýêñïåðèìåíòû ñ àëãîðèòìàìè
LPCSTABb è LPWSTAB.
2. Òî÷íîñòü ËÏ-îðèåíòèðîâàííûõ âåðõíèõ îöåíîê ñóùåñòâåííî çàâèñèò îò èñ-
ïîëüçîâàíèÿ òîãî íàáîðà íåðàâåíñòâ, ñ ïîìîùüþ êîòîðûõ àïïðîêñèìèðóåòñÿ ìíî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 169
Ò à á ë è ö à 3
Òåñòîâûå
íàáîðû èç
DIMACS-ãðàôîâ
Ðåçóëüòàòû ñðàâíèòåëüíûõ ýêñïåðèìåíòîâ ñ ïîìîùüþ ïðîãðàììû
SCIP äëÿ áóëåâûõ ËÏ-çàäà÷
N
SCIP
M
ESCIP
t
ESCIP
M
WSCIP
M
SCIP
t
WSCIP
t
t
ESCIP
WSCIP
c-fat200-l 200 18366 1041 24353 5420 125 8,33
c-fat200-2 200 16665 410 20207 5284 91 4,51
c-fat200-5 200 11427 1194 12160 10831 1472 0,81
johnson16-2-4 120 1680 1,41 1928 48 0,14 10,07
johnson8-2-4 28 210 0,04 237 16 0,03 1,33
johnson8-4-4 70 560 1,64 769 135 0,09 18,22
keller4 171 5100 829 6422 1155 259 3,20
hamming6-4 64 1312 10,1 1677 209 2,31 4,39
hamming8-4 256 11776 746 13176 1324 26,64 28,00
san200-0.7-2 200 5970 410 7739 2213 112 3,66
san200.0.9-l 200 1990 5,5 2853 2312 2,39 2,30
san200-0.9-2 200 1990 13,3 3559 2638 4,09 3,25
san200.0.9-3 200 1990 111,9 3716 2562 346 0,32
brock200-l 200 5066 22766 6809 2515 8065 2,82
mann-a27 378 702 359 1325 597 55 6,50
mann-a9 45 72 0,21 138 58 0,26 0,91
ãîãðàííèê STAB G( ). Íàïðèìåð, äàæå ïðîñòåéøèé ó÷åò p-êîëåñ â ãðàôå G ïîçâîëÿåò
î÷åíü ìíîãî ñäåëàòü äëÿ óëó÷øåíèÿ òî÷íîñòè ËÏ-îðèåíòèðîâàííîé îöåíêè ïî
ñðàâíåíèþ ñ èñïîëüçîâàíèåì òîëüêî íå÷åòíûõ öèêëîâ. Óñîâåðøåíñòâîâàííûå ñõå-
ìû ïîñòðîåíèÿ p-êîëåñ ìîãóò óñèëèòü òî÷íîñòü ËÏ-îðèåíòèðîâàííûõ âåðõíèõ
îöåíîê.
3. Íà îñíîâå ñîâðåìåííûõ ÖËÏ-ïðîãðàìì (öåëî÷èñëåííîãî ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ) ìîæíî ïîëó÷èòü è îáîñíîâàòü òî÷íóþ âåðõíþþ ãðàíèöó äëÿ
�( , )G w è, áîëåå òîãî, íàéòè îäíî èç áóëåâûõ ðåøåíèé, íà êîòîðîì äîñòèãàåòñÿ ýòà
ãðàíèöà. Ïðè ýòîì êà÷åñòâî ËÏ-îðèåíòèðîâàííûõ îöåíîê èãðàåò âàæíóþ ðîëü äëÿ
óñêîðåíèÿ ðàáîòû ÖËÏ-ïðîãðàìì. Ýòî äîêàçûâàþò ÷èñëåííûå ýêñïåðèìåíòû
ñ ïðîãðàììîé SCIP.
Ìîæíî ëè ðàñøèðèòü ãðàíèöû ïðèìåíèìîñòè ËÏ-îðèåíòèðîâàííûõ îöåíîê íà
ñëó÷àé ãðàôîâ ñ íåñêîëüêèìè òûñÿ÷àìè âåðøèí, èñïîëüçóÿ êîììåð÷åñêèå ËÏ-ïðî-
ãðàììû è ÖËÏ-ïðîãðàììû? Îòâåò òðåáóåò áîëåå äåòàëüíîãî èññëåäîâàíèÿ. Ïðèìåð
ñ ãðàôîì 1dc1024 óêàçûâàåò íà òî, ÷òî ñ ïîìîùüþ ïðîãðàììû CPLEX äîêàçà-
òåëüñòâî ìàêñèìàëüíîãî îáúåìà ïîìåõîóñòîé÷èâîãî êîäà äëÿ ýòîãî ãðàôà ïîòåíöè-
àëüíî ìîæíî îñóùåñòâèòü çà âðåìÿ t * ,0 08, ãäå t — âðåìÿ äîêàçàòåëüñòâà ñ ïî-
ìîùüþ ïðîãðàììû SCIP. Ýòî ñëåäóåò èç òîãî, ÷òî ðàáîòà ïðîãðàììû SCIP îöåíè-
âàåòñÿ ïî âðåìåíè â ñîîòíîøåíèè 1 ê 0,08 ïî îòíîøåíèþ ê ïðîìûøëåííîìó
âàðèàíòó ïðîãðàììû CPLEX (http://scip.zib.de). Ïðè ýòîì ìîæíî îæèäàòü, ÷òî íà
ïðîöåññîðå AMD Athlon 1,81GHz îáîñíîâàíèå òî÷íîñòè âåðõíåé îöåíêè ìàêñè-
ìàëüíîãî îáúåìà ïîìåõîóñòîé÷èâîãî êîäà äëÿ ãðàôà 1dc1024 ìîæíî îñóùåñòâèòü
ñ ïîìîùüþ CPLEX çà âðåìÿ, ìåíüøåå ïÿòè ÷àñîâ (ñð.: 55 ÷àñîâ ñ ïîìîùüþ ïðî-
ãðàììû SCIP). Ïîäòâåðäèòñÿ ëè ýòî ïðåäïîëîæåíèå? Îòâåò íà ýòîò âîïðîñ ìîæåò
äàòü òîëüêî ÷èñëåííûé ýêñïåðèìåíò.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. à ý ð è Ì . , Ä æ î í ñ î í Ä . Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. — Ì.: Ìèð, 1982.
— 416 ñ.
2. G r ��ît s c h e l M . , L � v a s z L . , S c h r i j v e r A . Geometric algorithms and combinatorial optimiza-
tion. — Berlin: Springer-Verlag, 1988. — 362 p.
3. W u n d e r l i n g R . Paralleler und objektorientierter simplex-algorithmus. — Berlin: Techn. Univ., 1996
(http://www.zib.de/Publications/abstracts/TR-96-09/).
4. C h e r k a s s k y B . V . , G o l d b e r g A . V . , R a d z i k T . Shortest paths algorithms: Theory and ex-
perimental evaluation // Math. Program. — 1996. — 73. — P. 129–174 (http://www.avglab.com/an-
drew/soft.html).
5. D I M A C S ( 1 9 9 5 ) . Cliques, coloring, and satisfiability: second DIMACS implementation challange
(http://dimacs.rutgers.edu/Challenges/).
6. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Boston; Dordrecht; London:
Kluwer Acad. Publ., 1998. — 412 p.
7. C h e n g E . , C u n n i n g h a m W . H . Wheel inequalities for stable set polytopes // Math. Program. —
1997. — 77, N 3. — P. 389–421.
8. Ñ ò å ö þ ê Ï . È . , × ó ì à ê î â Á . Ì . Î ñâîéñòâàõ îäíîé âåðõíåé îöåíêè Í.Ç. Øîðà äëÿ
âçâåøåííîãî ÷èñëà óñòîé÷èâîñòè ãðàôà // Ïðàö³ ì³æíàð. ñèìï. «Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü
(ÏÎÎ-XXXIII)». — Ê.: ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2007. — Ñ. 271–272.
9. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Ïðîáëåìû äèñêðåòíîé îïòèìèçàöèè: ñëîæíûå çàäà÷è,
îñíîâíûå ïîäõîäû ê èõ ðåøåíèþ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 4. — Ñ. 3–25.
10. A c h t e r b e r g T . Constraint integer programming. — Berlin: Techn. Univ., 2007
(http://opus.kobv.de/tuberlin/volltexte/2007/1611/).
Ïîñòóïèëà 30.03.2008
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Gray Gamma 2.2)
/CalRGBProfile (Adobe RGB \0501998\051)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.3
/CompressObjects /Off
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Perceptual
/DetectBlends true
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 524288
/LockDistillerParams true
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveEPSInfo true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts false
/TransferFunctionInfo /Apply
/UCRandBGInfo /Remove
/UsePrologue false
/ColorSettingsFile (Color Management Off)
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 600
/ColorImageDepth 8
/ColorImageDownsampleThreshold 1.01667
/EncodeColorImages true
/ColorImageFilter /FlateEncode
/AutoFilterColorImages false
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 600
/GrayImageDepth 8
/GrayImageDownsampleThreshold 2.03333
/EncodeGrayImages true
/GrayImageFilter /FlateEncode
/AutoFilterGrayImages false
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 2400
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile (None)
/PDFXOutputCondition ()
/PDFXRegistryName (http://www.color.org)
/PDFXTrapped /False
/SyntheticBoldness 1.000000
/Description <<
/DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200036002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300030003400200053007000720069006e006700650072002d005600650072006c0061006700200047006d0062004800200061006e006400200049006d007000720065007300730065006400200047006d00620048000d000d0054006800650020006c00610074006500730074002000760065007200730069006f006e002000630061006e00200062006500200064006f0077006e006c006f006100640065006400200061007400200068007400740070003a002f002f00700072006f00640075006300740069006f006e002e0073007000720069006e006700650072002e00640065002f007000640066002f000d0054006800650072006500200079006f0075002000630061006e00200061006c0073006f002000660069006e0064002000610020007300750069007400610062006c006500200045006e0066006f0063007500730020005000440046002000500072006f00660069006c006500200066006f0072002000500069007400530074006f0070002000500072006f00660065007300730069006f006e0061006c0020003600200061006e0064002000500069007400530074006f007000200053006500720076006500720020003300200066006f007200200070007200650066006c00690067006800740069006e006700200079006f007500720020005000440046002000660069006c006500730020006200650066006f007200650020006a006f00620020007300750062006d0069007300730069006f006e002e>
/ENU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200036002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300030003400200053007000720069006e006700650072002d005600650072006c0061006700200047006d0062004800200061006e006400200049006d007000720065007300730065006400200047006d00620048>
>>
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [2834.646 2834.646]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-44314 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T15:40:39Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Лиховид, А.П. 2013-05-28T19:35:56Z 2013-05-28T19:35:56Z 2009 О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44314 519.8 Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі скінченним числом нерівностей, які отримані на основі алгоритму найкоротших шляхів в спеціальному графі. Наведено результати тестових експериментів, коли граф містить від декількох сотень до тисячі вершин. Upper bounds are considered for the weighted stability number of a graph that are based on the approximation of the polytope of stable sets by linear inequalities for odd cycles and p-wheels in the graph. Algorithms are developed for finding upper bounds on the basis of solution of an LP-problem with a finite number of inequalities produced by the shortest path algorithm for a special graph. The results of test experiments are given for graphs with several hundred or thousand nodes. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Про ЛП-орієнтовані верхні оцінки для зваженого числа стійкості графа LP-oriented upper bounds for the weighted stability number of a graph Article published earlier |
| spellingShingle | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Стецюк, П.И. Лиховид, А.П. Системный анализ |
| title | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_alt | Про ЛП-орієнтовані верхні оцінки для зваженого числа стійкості графа LP-oriented upper bounds for the weighted stability number of a graph |
| title_full | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_fullStr | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full_unstemmed | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_short | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_sort | о лп-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| work_keys_str_mv | AT stecûkpi olporientirovannyhverhnihocenkahdlâvzvešennogočislaustoičivostigrafa AT lihovidap olporientirovannyhverhnihocenkahdlâvzvešennogočislaustoičivostigrafa AT stecûkpi prolporíêntovaníverhníocínkidlâzvaženogočislastíikostígrafa AT lihovidap prolporíêntovaníverhníocínkidlâzvaženogočislastíikostígrafa AT stecûkpi lporientedupperboundsfortheweightedstabilitynumberofagraph AT lihovidap lporientedupperboundsfortheweightedstabilitynumberofagraph |