Метод перечисления максимальных независимых множеств в произвольных неориентированных графах
Предложена процедура перечисления только максимальных независимых множеств в неориентированных произвольных графах, позволяющая уменьшить временную сложность реализации алгоритма....
Saved in:
| Date: | 2014 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Series: | Электронное моделирование |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/100981 |
| 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: | Метод перечисления максимальных независимых множеств в произвольных неориентированных графах / С.В. Листровой // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 3-16. — Бібліогр.: 4назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-100981 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1009812016-05-29T03:03:40Z Метод перечисления максимальных независимых множеств в произвольных неориентированных графах Листровой, С.В. Математические методы и модели Предложена процедура перечисления только максимальных независимых множеств в неориентированных произвольных графах, позволяющая уменьшить временную сложность реализации алгоритма. Запропоновано процедуру перелічування тільки максимальних незалежних множин у неорієнтованих довільних графах, яка дозволяє зменшити часову складність реалізації алгоритму. A procedure of enumeration of only maximum independent sets in unoriented arbitrary graphs has been proposed; it allows reducing a temporary difficulty of the algorithm realization. 2014 Article Метод перечисления максимальных независимых множеств в произвольных неориентированных графах / С.В. Листровой // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 3-16. — Бібліогр.: 4назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/100981 519.682.1 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| 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 |
2014 |
| topic_facet |
Математические методы и модели |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/100981 |
| citation_txt |
Метод перечисления максимальных независимых множеств в произвольных неориентированных графах / С.В. Листровой // Электронное моделирование. — 2014 — Т. 36, № 1. — С. 3-16. — Бібліогр.: 4назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT listrovojsv metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvproizvolʹnyhneorientirovannyhgrafah |
| first_indexed |
2025-07-07T10:16:01Z |
| last_indexed |
2025-07-07T10:16:01Z |
| _version_ |
1836982898780012544 |
| fulltext |
ÓÄÊ 519.682.1
Ñ.Â. Ëèñòðîâîé, ä-ð òåõí. íàóê
Óêðàèíñêàÿ ãîñóäàðñòâåííàÿ àêàäåìèÿ
æåëåçíîäîðîæíîãî òðàíñïîðòà
(Óêðàèíà,61050, Õàðüêîâ, ïë. Ôåéðáàõà, 7,
òåë. 0509355042, e-mail: om1@yandex.ru)
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ
íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
íåîðèåíòèðîâàííûõ ãðàôàõ
Ïðåäëîæåíà ïðîöåäóðà ïåðå÷èñëåíèÿ òîëüêî ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â
íåîðèåíòèðîâàííûõ ïðîèçâîëüíûõ ãðàôàõ, ïîçâîëÿþùàÿ óìåíüøèòü âðåìåííóþ ñëîæ-
íîñòü ðåàëèçàöèè àëãîðèòìà.
Çàïðîïîíîâàíî ïðîöåäóðó ïåðåë³÷óâàííÿ ò³ëüêè ìàêñèìàëüíèõ íåçàëåæíèõ ìíîæèí ó
íåîð³ºíòîâàíèõ äîâ³ëüíèõ ãðàôàõ, ÿêà äîçâîëÿº çìåíøèòè ÷àñîâó ñêëàäí³ñòü ðåàë³çàö³¿
àëãîðèòìó.
Ê ë þ ÷ å â û å ñ ë î â à: ìàêñèìàëüíûå íåçàâèñèìûå ìíîæåñòâà, êëèêè.
Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ ñèíòåçà è àíàëèçà âû÷èñëèòåëüíûõ ñèñòåì
è ñåòåé, à òàêæå ïðè ðàçðàáîòêå ñïåöèàëüíîãî ìàòåìàòè÷åñêîãî îáåñïå÷å-
íèÿ äëÿ èõ ôóíêöèîíèðîâàíèÿ òðåáóåòñÿ íàéòè â êîíå÷íîì ìíîæåñòâå
îáúåêòîâ ìàêñèìàëüíóþ ñèñòåìó îáúåêòîâ, ïîïàðíî íå ñâÿçàííûõ äðóã ñ
äðóãîì, èëè âûáðàòü ìèíèìàëüíóþ ñèñòåìó îáúåêòîâ, ñâÿçàííûõ ñî âñåìè
äðóãèìè. Ôîðìóëèðîâêè ïîäîáíûõ çàäà÷ íà ÿçûêå òåîðèè ãðàôîâ ïðèâî-
äÿò ê ïîíÿòèÿì íåçàâèñèìîñòè è ïîêðûòèÿ.
Ìíîæåñòâî âåðøèí U ãðàôà G (V, Å) íàçûâàåòñÿ íåçàâèñèìûì (âíóò-
ðåííå óñòîé÷èâûì), åñëè íèêàêèå äâå âåðøèíû èç ýòîãî ìíîæåñòâà íå
ñìåæíûå, ò.å. åñëè U V� è U íåçàâèñèìî â ãðàôå G, òî ïîðîæäåííûé
ïîäãðàô G (U) ÿâëÿåòñÿ ïóñòûì. Î÷åâèäíî, ÷òî åñëè ïðè ýòîì U U* � , òî
U * — òàêæå íåçàâèñèìîå ìíîæåñòâî.
Âíóòðåííå óñòîé÷èâîå ìíîæåñòâî íàçûâàåòñÿ ìàêñèìàëüíûì, åñëè
îíî íå ÿâëÿåòñÿ ñîáñòâåííûì ïîäìíîæåñòâîì íåêîòîðîãî äðóãîãî íåçà-
âèñèìîãî ìíîæåñòâà.
Íàèáîëüøåå ïî ìîùíîñòè íåçàâèñèìîå ìíîæåñòâî íàçûâàåòñÿ íàè-
áîëüøèì. ×èñëî âåðøèí â íàèáîëüøåì íåçàâèñèìîì ìíîæåñòâå ãðàôà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 3
����������� ��
���
��
�
�
����
� Ñ.Â. Ëèñòðîâîé, 2014
G (V, Å) íàçûâàåòñÿ ÷èñëîì íåçàâèñèìîñòè, èëè ÷èñëîì âíóòðåííåé óñòîé-
÷èâîñòè, è îáîçíà÷àåòñÿ ÷åðåç � 0( )G . ßñíî, ÷òî íàèáîëüøåå íåçàâèñèìîå
ìíîæåñòâî ÿâëÿåòñÿ ìàêñèìàëüíûì.
Íåòðóäíî âèäåòü, ÷òî çàäà÷à î êëèêå è çàäà÷à î íåçàâèñèìîì ìíî-
æåñòâå, ïî ñóòè, ýêâèâàëåíòíû: êàæäàÿ èç íèõ âûòåêàåò èç äðóãîé ïðè
ïîñòðîåíèè äîïîëíåíèÿ ãðàôà G V E( , ), ò.å. òàêîãî ãðàôà G V E( , )1 , â
êîòîðîì åñòü âñå âåðøèíû èñõîäíîãî. Ïðè ýòîì â äîïîëíåíèè ãðàôà
âåðøèíû ñîåäèíåíû ðåáðîì òîëüêî â òîì ñëó÷àå, åñëè îíè íå áûëè
ñîåäèíåíû â èñõîäíîì ãðàôå. ×èñëî âåðøèí â íàèáîëüøåé êëèêå íàçû-
âàþò òàêæå ïëîòíîñòüþ � ( )G ãðàôà G V E( , ). Î÷åâèäíî, ÷òî� �( ) ( )G G�
è � �( ) ( )G G� .
Îáå çàäà÷è òåñíî ñâÿçàíû ñ çàäà÷åé î ìèíèìàëüíîì âåðøèííîì ïî-
êðûòèè. ×èñëî âåðøèí â íàèìåíüøåì ïîêðûòèè ãðàôà G V E( , )íàçûâàåòñÿ
÷èñëîì âåðøèííîãî ïîêðûòèÿ �0( )G è ñâÿçàíî ñ � 0( )G ñëåäóþùèì ðà-
âåíñòâîì: � �0 0( ) ( )G G n � , ãäå n — ÷èñëî âåðøèí â ãðàôå G V E( , ). Îäèí
èç ñïîñîáîâ íàõîæäåíèÿ íåçàâèñèìîãî ìíîæåñòâà âåðøèí ãðàôà G V E( , )
ñîñòîèò â ïîñòðîåíèè âñåõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ (ÌÍÌ)
è â âûáîðå èç íèõ ìíîæåñòâà ñ íàèáîëüøåé ìîùíîñòüþ.
Îäíèì èç øèðîêî èñïîëüçóåìûõ àëãîðèòìîâ äëÿ îïðåäåëåíèÿ ÌÍÌ
ÿâëÿåòñÿ àëãîðèòì Áðîíà—Êåðáîøà, èñïîëüçóåìûé äëÿ íàõîæäåíèÿ
ÌÍÌ âåðøèí, åñëè ïîñòðîåíî äîïîëíåíèå ê èñõîäíîìó ãðàôó [1, 2]. Ýòîò
àëãîðèòì îñíîâàí íà òîì, ÷òî âñÿêàÿ êëèêà â ãðàôå ÿâëÿåòñÿ åãî ìàê-
ñèìàëüíûì ïî âêëþ÷åíèþ ïîëíûì ïîäãðàôîì. Íà÷èíàÿ ñ îäèíî÷íîé âåð-
øèíû (îáðàçóþùåé ïîëíûé ïîäãðàô) íà êàæäîì øàãå àëãîðèòìà ïðîèñ-
õîäèò óâåëè÷åíèå óæå ïîñòðîåííîãî ïîëíîãî ïîäãðàôà äîáàâëåíèåì âåð-
øèíû èç ìíîæåñòâà êàíäèäàòîâ. Îòñå÷åíèå íåïåðñïåêòèâíûõ âàðèàíòîâ,
çàâåäîìî íå ïðèâîäÿùèõ ê ïîñòðîåíèþ êëèêè, îáåñïå÷èâàåòñÿ èñïîëü-
çîâàíèåì äîïîëíèòåëüíîãî ìíîæåñòâà, â êîòîðîå ïîìåùàþòñÿ âåðøèíû,
óæå èñïîëüçîâàííûå äëÿ óâåëè÷åíèÿ ïîëíîãî ïîäãðàôà.
Àëãîðèòì îïåðèðóåò òðåìÿ ìíîæåñòâàìè âåðøèí ãðàôà: Q-ìíîæåñò-
âîì, ñîäåðæàùèì íà êàæäîì øàãå ðåêóðñèè ïîëíûé ïîäãðàô äëÿ äàííîãî
øàãà (ñòðîèòñÿ ðåêóðñèâíî); ìíîæåñòâîì âåðøèí Í, êîòîðûå ìîãóò óâå-
ëè÷èòü ìíîæåñòâî Q, ìíîæåñòâîì âåðøèí N, êîòîðûå óæå áûëè èñïîëü-
çîâàíû äëÿ ðàñøèðåíèÿ Q íà ïðåäûäóùèõ øàãàõ. Àëãîðèòì ÿâëÿåòñÿ
ðåêóðñèâíîé ïðîöåäóðîé, ïðèìåíÿåìîé ê ýòèì òðåì ìíîæåñòâàì, è åãî
ñëîæíîñòü ëèíåéíà îòíîñèòåëüíî ÷èñëà êëèê â ãðàôå, ãäå n — ÷èñëî âåðøèí,
m — ÷èñëî ðåáåð,
— ÷èñëî êëèê.  ðàáîòå [1] ïîêàçàíî, ÷òî â õóäøåì
ñëó÷àå âðåìåííàÿ ñëîæíîñòü àëãîðèòìà íå ïðåâûøàåò O (3n/3). Âñå èçâåñòíûå
àëãîðèòìû îïðåäåëåíèÿ ÌÍÌ èìåþò ýêñïîíåíöèàëüíóþ ñëîæíîñòü. Ðàçðà-
áîòàííàÿ ïðîöåäóðà ïîçâîëÿåò óìåíüøèòü âðåìåííóþ ñëîæíîñòü àëãîðèòìà
ïåðå÷èñëåíèÿ ÌÍÌ â ïðîèçâîëüíûõ íåîðèåíòèðîâàííûõ ãðàôàõ.
Ñ.Â. Ëèñòðîâîé
4 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Ôîðìàëèçàöèÿ è ðåøåíèå çàäà-
÷è. Ïóñòü çàäàí èñõîäíûé ãðàô G V E( , )
ñ n âåðøèíàìè è òðåáóåòñÿ ïåðå÷èñ-
ëèòü â íåì âñå ÌÍÌ. Âàæíîå ñâîéñòâî
ãðàôîâ, êîòîðîå ïîíàäîáèòñÿ äëÿ ðåøå-
íèÿ ïîñòàâëåííîé çàäà÷è, ñîñòîèò â
òîì, ÷òî ïîäìíîæåñòâî X V� ÿâëÿåòñÿ
ÌÍÌ ãðàôà G V E( , ) òîãäà è òîëüêî
òîãäà, êîãäà åãî äîïîëíåíèå Y ÿâëÿåòñÿ âåðøèííûì ïîêðûòèåì (ò.å.
X V Y� � ). ßñíî, ÷òî åñëè â ãðàôå G V E( , ) åñòü âåðøèíà i ñî ñòåïåíüþ,
ðàâíîé n �1, òî âåðøèíà i ÿâëÿåòñÿ ÌÍÌ.
 ðàáîòå [3] ïîêàçàíî, ÷òî åñëè f-áóëåâà ôóíêöèÿ, ïîñòðîåíà ïî ãðàôó
G V E( , ) â âèäå ïðîèçâåäåíèÿ äèçúþíêòîâ ( )V Vi j� , ãäå{ }Vi
{0, 1}, i n�1, ,
j n�1, , i j� , è ïðè ýòîì êàæäûé äèçúþíêò ( )V Vi j� ñîîòâåòñòâóåò ðåáðó
( , )V Vi j , òî âñå íàáîðû ïåðåìåííûõ {V Vi j, }, íà êîòîðûõ îíà ïðèíèìàåò
çíà÷åíèå èñòèííî, ñîîòâåòñòâóþò âåðøèííûì ïîêðûòèÿì â ãðàôå G V E( , ).
Ñëåäîâàòåëüíî, äëÿ ïåðå÷èñëåíèÿ âñåõ âåðøèííûõ ïîêðûòèé ãðàôà
G V E( , )íåîáõîäèìî îïðåäåëèòü òå ñèñòåìû çíà÷åíèé ïåðåìåííûõ{V Vi j, },
ïðè êîòîðûõ âûñêàçûâàíèå
f V V Vn( , ,..., )1 2 1� (1)
åñòü èñòèííî. Äëÿ òîãî ÷òîáû íàéòè ýòè ñèñòåìû çíà÷åíèé ïåðåìåííûõ
{ , }v vi j , íåîáõîäèìî ïðèâåñòè ëåâóþ ÷àñòü (1) ê ìèíèìàëüíîé äèçúþíê-
òèâíîé íîðìàëüíîé ôîðìå, ðàñêðûâàÿ ñêîáêè è ïîëüçóÿñü çàêîíîì ïîãëî-
ùåíèÿ. Òàêàÿ ôîðìà åäèíñòâåííà ââèäó îòñóòñòâèÿ â (1) ëîãè÷åñêèõ îòðè-
öàíèé. Ïîêàæåì ýòî íà ïðèìåðå ãðàôà G ( ðèñ. 1), áóëåâà ôóíêöèÿ êîòîðîãî
èìååò âèä
f V V V V V V V V V V� � � � � � �( ) ( ) ( ) ( ) ( )1 2 2 3 3 4 2 4 1 4
� � � � � �( ) ( )V V V V V V V V V V V V V V V2 1 3 4 1 2 3 2 4 1 2 3 1 3 4 . (2)
Êàê âèäíî èç (2), â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïî-
äîáíûõ ïîëó÷åí ïîëíûé ïåðå÷åíü âåðøèííûõ ïîêðûòèé ãðàôà G. Èìè
ÿâëÿþòñÿ ïîäìíîæåñòâà âåðøèí {2, 4}, {1, 2, 3}, {1, 3, 4}. Ñîîòâåòñòâåííî
èõ äîïîëíåíèÿ îáðàçóþò ÌÍÌ ãðàôà.  äàííîì ñëó÷àå òàêèìè ÿâëÿþòñÿ
ïîäìíîæåñòâà {1, 3}, {4}, {2}. Ìíîæåñòâî ïîêðûòèé, ïîëó÷åííûõ ïîñëå
ïðèâåäåíèÿ ïîäîáíûõ íà îñíîâå îïåðàöèè ïîãëîùåíèÿ, áóäåì íàçûâàòü
ìíîæåñòâîì íåïîãëîùàåìûõ âåðøèííûõ ïîêðûòèé, ò.å. ïîêðûòèé, íå ñî-
äåðæàùèõñÿ íè â êàêèõ äðóãèõ ïîêðûòèÿõ. Îáîçíà÷èâ ÷èñëî íåïîãëîùàåìûõ
âåðøèííûõ ïîêðûòèé â ãðàôå ÷åðåç �, à ÷èñëî ÌÍÌ ÷åðåç �, óáåäèìñÿ, ÷òî
ñïðàâåäëèâî ðàâåíñòâî � �� .
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 5
4
31
2
Ðèñ. 1. Ãðàô G
Äëÿ ãðàôà G V E( , ) è åãî äîïîëíåíèÿ G V E1 1( , ) ñïðàâåäëèâî ðàâåíñòâî
2 2 11E E n n � �( ), èç êîòîðîãî âèäíî, ÷òî ÷èñëî ïàð íåçàâèñèìûõ âåðøèí
â ãðàôå G V E( , ) íå ìîæåò ïðåâûñèòü ÷èñëà ðåáåð â ãðàôå G1. Åñëè íåçà-
âèñèìûå ïàðû âåðøèí îáúåäèíÿòü â íåçàâèñèìûå ìíîæåñòâà è äàëåå
ïûòàòüñÿ íàðàùèâàòü ìîùíîñòü íåçàâèñèìûõ ìíîæåñòâ, òî ÷èñëî òàêèõ
îáúåäèíåíèé áóäåò îãðàíè÷åíî íàëè÷èåì ñâÿçåé ìåæäó âåðøèíàìè â
ãðàôå G V E( , ), ò.å. ìíîæåñòâîì ðåáåð E â ãðàôå G V E( , ), êîòîðîå â ïðîèç-
âîëüíîì ãðàôå íå ìîæåò ïðåâûñèòü E
n n
max
( )
�
�1
2
. Ïðè ýòîì ñëåäóåò
ó÷åñòü, ÷òî ÷èñëî ÌÍÌ � îïðåäåëÿåòñÿ ÷èñëîì � íåïîãëîùàåìûõ âåðøèí-
íûõ ïîêðûòèé â ãðàôå. ßñíî, ÷òî ÷èñëî � â ãðàôå ïðîïîðöèîíàëüíî
óäâîåííîìó ÷èñëó ðåáåð 2E â ãðàôå G V E( , ), ïîñêîëüêó êàæäîå ðåáðî ìîæåò
áûòü ïîêðûòî äâóìÿ âåðøèíàìè. Ñëåäîâàòåëüíî, ÷èñëî �* ( )� �Cn n 1 ÿâ-
ëÿåòñÿ îöåíêîé ñâåðõó ÷èñëà ÌÍÌ â ãðàôå G V E( , ), ãäå Ñ — íåêîòîðàÿ
êîíñòàíòà, âîçìîæíî, äîñòàòî÷íî áîëüøàÿ.
 ïîëíîì ãðàôå � � n, à åñëè ãðàô ïðåäñòàâëÿåò äåðåâî, òî ÷èñëî �
ìîæåò ïðèáëèæàòüñÿ ê Cn n( )�1 . Äàííàÿ îöåíêà ÿâëÿåòñÿ âåñüìà ãðóáîé. Â
òàáë. 1 ïðåäñòàâëåíû ãðàôû, ïîëó÷åííûå èç ïåðâîãî ãðàôà ïîñðåäñòâîì
óäàëåíèÿ ðåáåð. Ïðè ýòîì ÷èñëî íåïîãëîùàåìûõ âåðøèííûõ ïîêðûòèé �
è ÷èñëî ÌÍÌ îïðåäåëåíû ñîãëàñíî ñîîòíîøåíèþ (1).
Ñ.Â. Ëèñòðîâîé
6 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
Ãðàô Âåðøèííîå ïîêðûòèå ÌÍÌ � � m
2345 v 1345 v 1245 v 1235 v 1234 1 v 2 v 3 v 4 v 5 –5 5 10
235 v 124 v 1345 14 v 35 v 2 3 3 8
124 v 134 v 135 v 235 v 245 35 v 25 v 24 v 14 v 13 –5 5 5
24 v 235 v 134 v 135 135 v 14 v 25 v 24 –4 4 4
Òàáëèöà 1
1
2
3
45
1
2
3
45
1
2
3
45
1
2
3
45
Êàê âèäíî èç òàáë. 1, óäàëåíèå ðåáåð ìîæåò ïðèâîäèòü ê óìåíüøåíèþ
÷èñëà � è, ñëåäîâàòåëüíî, ÷èñëà �, íî îíî ìîæåò è âîçðàñòàòü ñ óâåëè÷å-
íèåì ÷èñëà âåðøèí â ãðàôå.
Ñëåäóåò çàìåòèòü, ÷òî ÷èñëî ðàçëè÷íûõ íåçàâèñèìûõ ìíîæåñòâ è êëèê
â ïðîèçâîëüíîì ãðàôå ìîæåò áûòü ýêñïîíåíöèàëüíî áîëüøèì. Òàê, â
ðàáîòàõ [1, 2] ïîêàçàíî, ÷òî íàèáîëüøåå ÷èñëî âîçìîæíûõ êëèê â ãðàôå ñ n
âåðøèíàìè ìîæåò äîñòèãàòü çíà÷åíèÿ 3n/3, ò.å ñëåäóåò ðàçëè÷àòü ÌÍÌ,
÷èñëî êîòîðûõ íå ïðåâûøàåò �* , è ïðîèçâîëüíûå íåçàâèñèìûå ìíîæåñòâà,
÷èñëî êîòîðûõ ñóùåñòâåííî áîëüøå.
Îáùèì íåäîñòàòêîì âñåõ èçâåñòíûõ ïðîöåäóð ïîèñêà ÌÍÌ è ìàê-
ñèìàëüíûõ êëèê, àíàëîãè÷íûõ ïðîöåäóðå, èñïîëüçóåìîé â àëãîðèòìå
Áðîíà—Êåðáîøà, ÿâëÿåòñÿ ïîïûòêà ïîñòðîèòü íàèáîëüøåå ÌÍÌ ïîñðåäñò-
âîì ïåðå÷èñëåíèÿ âñåõ íåçàâèñèìûõ ìíîæåñòâ è çàòåì âûäåëèòü â íèõ
ìàêñèìàëüíîå. Ïðè ýòîì îðãàíèçàöèÿ ïîèñêà ïðîèñõîäèò â øèðèíó èëè â
ãëóáèíó â äåðåâå âàðèàíòîâ ñ ïåðåáèðàíèåì âñåõ íåçàâèñèìûõ ìíîæåñòâ.
Ïðè òàêîì ïîèñêå ÷èñëî øàãîâ, âûïîëíÿåìûõ ïðîöåäóðîé, ÿâëÿåòñÿ ýêñïî-
íåíöèàëüíî áîëüøèì, è òîëüêî ïîñëå îêîí÷àíèÿ íåÿâíîãî ïîëíîãî ïå-
ðåáîðà âàðèàíòîâ ïîèñêà ìîæåò áûòü âûäåëåíî íàèáîëüøåå ÌÍÌ.
Ðàññìîòðèì ïîäõîä, ïîçâîëÿþùèé ïðåîäîëåòü äàííûé íåäîñòàòîê.
Òàêîé ïîäõîä îñíîâàí íà ïîñòðîåíèè ïðîöåäóðû, ïåðå÷èñëÿþùåé òîëüêî
âñå ÌÍÌ, ÷èñëî êîòîðûõ íå ïðåâûøàåò �* . Ïîñòðîåíèå òàêîé ïðîöåäóðû
âîçìîæíî íà îñíîâå ñîñòàâëåíèÿ ïîñëåäîâàòåëüíîñòè ãðàôîâ G1, G2, …, Gp,
ãäå ãðàô G1 ïîñòðîåí èç èñõîäíîãî ãðàôà G V E( , ) ïîñðåäñòâîì ñîåäèíåíèÿ
ðåáðàìè âåðøèí, êîòîðûå â ãðàôå G V E( , ) íå ñâÿçàíû ìåæäó ñîáîé. Çàòåì
îáúåäèíÿåì âåðøèíû â ïîäìíîæåñòâà, êîòîðûå â ãðàôå G1 ñîåäèíåíû ðåáðà-
ìè. Âåðøèíû i â ãðàôàõ G2, ..., Gp áóäåì õàðàêòåðèçîâàòü äâóìÿ ïîäìíîæåñò-
âàìè: ïîäìíîæåñòâîì X i
r èç r íåçàâèñèìûõ âåðøèí è ïîäìíîæåñòâîì Yi
k ,
ñîñòîÿùèì èç k âåðøèí, ñ êîòîðûìè ñâÿçàíû âåðøèíû èç X i
r .
Ôîðìèðîâàíèå ãðàôîâ G i îñóùåñòâëÿåòñÿ äî òåõ ïîð, ïîêà äëÿ âñåõ
ñôîðìèðîâàííûõ ìíîæåñòâ, ñîîòâåòñòâóþùèõ âåðøèíàì ãðàôà G i, íå áó-
äåò âûïîëíåíî óñëîâèå X Y Vi
r
i
k� � , êîòîðîå îçíà÷àåò, ÷òî ñôîðìèðîâàí-
íîå ìíîæåñòâî ÿâëÿåòñÿ ìàêñèìàëüíî íåçàâèñèìûì, ïîñêîëüêó â ýòîì
ñëó÷àå ïîäìíîæåñòâî Yi
k áóäåò ïðåäñòàâëÿòü âåðøèííîå ïîêðûòèå â ãðàôå
G V E( , ), à ïîäìíîæåñòâî X i
r — ÌÍÌ âåðøèí ãðàôàG V E( , ), äîïîëíÿþùåå
ýòî ïîäìíîæåñòâî äî n.
Åñëè X Y Vi
r
i
k� � , òî, î÷åâèäíî, ñóùåñòâóþò âåðøèíû, êîòîðûå ìîæ-
íî äîáàâèòü â ïîäìíîæåñòâî X i
r , è îíî îñòàíåòñÿ ïðè ýòîì íåçàâèñèìûì.
×èñëî òàêèõ âåðøèí íå ïðåâîñõîäèò n – r. Åñëè X Y Vi
r
i
k� � , òî òàêèõ âåð-
øèí â ãðàôå G V E( , ) íå ñóùåñòâóåò.
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 7
 òåêóùåì ãðàôå G i, åñëè âåðøèíû (i, j … ð) îïèñûâàþòñÿ ïîäìíî-
æåñòâàìè ( , ),( , ) ...( , )X Y X Y X Yi
r
i
k
j
r
j
k
p
r
p
k , ó êîòîðûõ Y Y Y Yi
k
j
k
p
k� � � �...
ìîãóò áûòü îáúåäèíåíû â îäíó âåðøèíó, îïèñûâàåìóþ ïîäìíîæåñòâàìè
( , )X Yi
r
, ãäå X X X Xi
r
i
r
j
r
p
r
� � � �... , è ïðè ýòîì åñëè X Y Vi
r
� � ,òî X i
r
—
ÌÍÌ. Âåðøèíû â ãðàôå G i ñîåäèíÿþòñÿ ðåáðîì (i, j), åñëè îáúåäèíåíèÿ
( )X Xi
r
j
r� ÿâëÿþòñÿ íåçàâèñèìûìè ìíîæåñòâàìè. Ïðîöåññ ôîðìèðîâàíèÿ
ãðàôà G i ïðåêðàùàåòñÿ, êîãäà âñå åãî âåðøèíû óäîâëåòâîðÿþò óñëîâèþ
X Y Vi
r
i
k� � èëè äàëüíåéøåå îáúåäèíåíèå íåâîçìîæíî.
Ïðè çàâåðøåíèè ðàáîòû ïðîöåäóðû ìîæåò âîçíèêàòü çàöèêëèâàíèå,
çàêëþ÷àþùååñÿ â òîì, ÷òî âñå ÌÍÌ óæå ïîñòðîåíû è ïðîöåäóðà äîáàâ-
ëÿåò äóáëèðóþùåå ÌÍÌ. Ïîýòîìó íåîáõîäèìî ïðîâåðÿòü, èçìåíèëñÿ ëè
ñïèñîê ñôîðìèðîâàííûõ ÌÍÌ ïî ñðàâíåíèþ ñ ïðåäûäóùèì øàãîì. Åñëè
ñïèñîê íå èçìåíèëñÿ, òî ïðîöåäóðà çàêàí÷èâàåò ðàáîòó. Ñëåäóåò çàìåòèòü,
÷òî â ïðîöåññå ôîðìèðîâàíèÿ ãðàôîâ Gi, ìîãóò âîçíèêàòü îäèíàêîâûå
âåðøèíû. Ïðè ýòîì äóáëèðóþùèå âåðøèíû íåîáõîäèìî óäàëÿòü.
Ââåäåì ïðîöåäóðó À ôîðìèðîâàíèÿ ïîäìíîæåñòâ íåçàâèñèìûõ âåð-
øèí, ïîçâîëÿþùóþ èõ ïåðå÷èñëèòü.
Ïðîöåäóðà À.
Ø à ã 1. Còðîèì ãðàôG i�1 , ÿâëÿþùèéñÿ äîïîëíåíèåì èñõîäíîãî ãðàôà
äî ïîëíîãî. Ôîðìèðóåì âåðøèíû ãðàôà G i�2 (îáúåäèíÿÿ âåðøèíû, ñîåäè-
íåííûå ðåáðàìè â ãðàôå G i�1 â ïîäìíîæåñòâà ( )X i
r ìîùíîñòè 2, ÷èñëî
êîòîðûõ ðàâíî ÷èñëó ðåáåð â ãðàôå G i�1) è äëÿ êàæäîé ñôîðìèðîâàííîé
âåðøèíû îïðåäåëÿåì ïîäìíîæåñòâà âåðøèí ( )Yi
k , ñ êîòîðûìè ñâÿçàíû
âåðøèíû èç ïîäìíîæåñòâ ( )X i
r , â ãðàôå G V E( , ).
Ø à ã 2. Ïðîâåðÿåì, åñòü ëè âåðøèíû ñ îäèíàêîâûìè ïîäìíîæåñòâàìè
Yi
k . Åñëè åñòü, òî îáúåäèíÿåì ñîîòâåòñòâóþùèå X i
r â îäíó âåðøèíó è ïðîâå-
ðÿåì, åñòü ëè âåðøèíû, äëÿ êîòîðûõ âûïîëíÿåòñÿ óñëîâèå X Y Vi
r
i
k� � . Åñëè
òàêèå âåðøèíû åñòü, òî ïîäìíîæåñòâà X i
r , ñîîòâåòñòâóþùèå äàííûì âåðøè-
íàì, ÿâëÿþòñÿ ÌÍÌ. Çàïîìèíàåì èõ è èñêëþ÷àåì ýòè âåðøèíû èç äàëüíåé-
øåãî àíàëèçà, èíà÷å — ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 3. Îáúåäèíÿåì ñôîðìèðîâàííûå âåðøèíû ðåáðàìè (i, j), åñëè
îáúåäèíåíèÿ ( )X Xi
r
j
r� ÿâëÿþòñÿ íåçàâèñèìûìè ìíîæåñòâàìè, è ïðîâå-
ðÿåì, åñòü ëè âåðøèíû, â êîòîðûõ ïîäìíîæåñòâà X i
r íå ÿâëÿþòñÿ ìàêñè-
ìàëüíûìè ìíîæåñòâàìè. Åñëè íåò, òî ñðåäè ñôîðìèðîâàííûõ ìíîæåñòâ
óäàëÿåì äóáëèðóþùèå è ïðîöåäóðà çàêàí÷èâàåò ðàáîòó, ïîñêîëüêó âñå ÌÍÌ
ïîñòðîåíû. Èíà÷å — ïðîâåðÿåì, ïðîèçîøëî äîáàâëåíèå íîâûõ ìíîæåñòâ â
ñôîðìèðîâàííûé ñïèñîê ÌÍÌ èëè íåò. Åñëè íåò, òî ïðîöåäóðà çàêàí÷èâàåò
ðàáîòó, åñëè äîáàâëåíèå ïðîèçîøëî, òî âûïîëíÿåì ñëåäóþùèé øàã.
Ø à ã 4. Ôîðìèðóåì âåðøèíû ãðàôà G i i:� 1, îáúåäèíÿÿ âåðøèíû,
ñîåäèíåííûå ðåáðàìè íà ïðåäûäóùåì øàãå, è äëÿ êàæäîé ñôîðìèðîâàí-
Ñ.Â. Ëèñòðîâîé
8 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
íîé âåðøèíû îïðåäåëÿåì ïîäìíîæåñòâà âåðøèí (Yi
k ), ñ êîòîðûìè ñâÿçàíû
âåðøèíû èç ïîäìíîæåñòâ (X i
r ), â ãðàôå G V E( , ). Ïîñëå ýòîãî ïåðåõîäèì ê
âûïîëíåíèþ øàãà 2.
Ðàññìîòðèì ïðèìåð ðàáîòû ïðîöåäóðû À äëÿ ãðàôà G V E( , ) ïðèâåäåí-
íîãî íà ðèñ. 2, à. Â ãðàôå G V E1( , )� âåðøèíû u è v ñîåäèíåíû ðåáðàìè, åñëè
â ãðàôå G V E( , ) ýòè âåðøèíû íå ñâÿçàíû. Âåðøèíû â ãðàôå G V E2 2 2( , )
îáîçíà÷åíû êâàäðàòàìè (ðèñ. 3).  âåðõíåé ÷àñòè êâàäðàòà çàïèñàíû îáúå-
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 9
1
2
3
4
5
6
7
a á
1
2 3
4
5
67
Ðèñ. 2. Èñõîäíûé ãðàô G V E( , ) (à) è ãðàô G V E1 1( , ) — äîïîëíåíèå ãðàôà G V E( , ) äî
ïîëíîãî ãðàôà (á)
2,6*
2,4
1,3,5,6
1,3
2,4,6
1,4
2,3,5,6
3,7
2,4,6
5,6
3,6
1,2,4,7
2,7
1,3,5,6
1,3,4,5,71,2,4,7
1,5
2,4,6
1,7
2,6
4,7
3,5,6
3,5
2,4
5,7
2,4,6
1 2
3
4
5
6
7
8
9
10
11
12
13
Ðèñ. 3. Ïðîöåññ ôîðìèðîâàíèÿ ãðàôà G V E2 2 2( , )
äèíåíèÿ âåðøèí, ñîåäèíåííûå ðåáðàìè â ãðàôå G i�1 â ïîäìíîæåñòâà (X i
r )
ìîùíîñòè 2, à â íèæíåé ÷àñòè — ïîäìíîæåñòâà âåðøèí (Yi
k ), ñ êîòîðûìè
ñâÿçàíû âåðøèíû èç ïîäìíîæåñòâ (X i
r ) â ãðàôå G V E( , ).
Íàïðèìåð, âåðøèíà 1 â ãðàôå G V E( , ) ñîîòâåòñòâóåò îáúåäèíåíèþ
âåðøèí 1 è 4 â ãðàôåG i�1, êîòîðûå ñîåäèíåíû ðåáðîì. Â ãðàôåG V E( , )âåð-
øèíà 1 ñâÿçàíà ñ âåðøèíàìè 2 è 6, à âåðøèíà 4 ñ âåðøèíàìè {3, 5, 6}, ò.å. ìíî-
æåñòâî âåðøèí 1, 4 ñâÿçàíî ñ ìíîæåñòâîì âåðøèí {2, 3, 5, 6}. Çâåçäî÷êàìè íà
ðèñ. 4 ïîìå÷åíû òå âåðøèíû, â êîòîðûõ ñôîðìèðîâàííûå ïîäìíîæåñòâà âåð-
øèí ÿâëÿþòñÿ ÌÍÌ. Òàê, âåðøèíà 5 ñîîòâåòñòâóåò ÌÍÌ, ïîñêîëüêó îáúå-
äèíåíèå ïîäìíîæåñòâ èìååò âèä ( )X Y5
2
2
5� = {2, 6} � {1, 3, 4, 5, 7} = {1, 2, 3,
4, 5, 6, 7} = V, ò.å. îáðàçóåò ìíîæå`ñòâî âåðøèí V ãðàôà G V E( , ).
Âåðøèíû {2, 9, 12, 13} ãðàôà G V E2 2 2( , ) ñâÿçàíû ñ îäíèì è òåì æå
ìíîæåñòâîì âåðøèí â ãðàôå G V E( , ), ò.å. Y Y Y Y2
2
9
2
12
2
13
2� � � = {2, 4, 6}. Ýòè
âåðøèíû ñîåäèíåíû ìåæäó ñîáîé ðåáðàìè, àíàëîãè÷íî ñîåäèíåíû ðåáðîì
âåðøèíû 4 è 6, òàê êàê Y Y4
2
6
2� = {1, 3, 5, 6} è âåðøèíû 8 è 11 ó íèõ
ñëåäóþùèå: Y Y8
2
11
2� = {1, 2, 4, 7}.
Ïîñëå îáúåäèíåíèÿ âåðøèí ñ îäèíàêîâûìè ïîäìíîæåñòâàìè Yi
2 ïî-
ëó÷èì âåðøèíû, ñîîòâåòñòâóþùèå ÌÍÌ, òàê êàê îáúåäèíåíèÿ ñîîòâåòñò-
âóþùèõ ïîäìíîæåñòâ X Yi
r
i
r� â ýòèõ âåðøèíàõ îáðàçóþò ìíîæåñòâî âåð-
øèí V â ãðàôå G V E( , ) . Çàïîìèíàåì ýòè ìíîæåñòâà, à ñîîòâåòñòâóþùèå
èì âåðøèíû èñêëþ÷àåì èç äàëüíåéøåãî àíàëèçà. Îñòàâøèåñÿ âåðøèíû
ãðàôà ñîåäèíÿåì, åñëè îáúåäèíåíèÿ ( )X Xi
r
j
r� ÿâëÿþòñÿ íåçàâèñèìûìè
ìíîæåñòâàìè, è ïîëó÷àåì ãðàô G V E2 2 2( , ) (ðèñ. 5).
Îáúåäèíåíèÿ ïîäìíîæåñòâà â ñîîòâåòñòâèè ñ ãðàôîì G V E2 2 2( , ) íà÷è-
íàåì ôîðìèðîâàòü ñ âåðøèíû ãðàôà G V E3 3 3( , ) (ðèñ. 6). Ïîñêîëüêó âñå
ñôîðìèðîâàííûå âåðøèíû ñîîòâåòñòâóþò ÌÍÌ, ïðîöåäóðà çàêàí÷èâàåò
ðàáîòó è óäàëÿþòñÿ äóáëèðóþùèå âåðøèíû. Òàê, èç îáúåäèíåíèé âåðøèí (1,
3), (1, 10), (3, 10) îñòàâëÿåì òîëüêî îäíî.
Òàêèì îáðàçîì, ñ ïîìîùüþ ïðîöåäóðû À ïîñòðîåíî ïÿòü ÌÍÌ: {1, 3,
5, 7}; {1, 4, 7}; {3, 5, 6}; {2, 4, 7}; {2, 6}. Ïðè ýòîì ñóììàðíîå ÷èñëî âåðøèí,
êîòîðîå ïðèøëîñü ïîñòðîèòü ïðè ôîðìèðîâàíèè ãðàôîâ G V E2 2 2( , ),
Ñ.Â. Ëèñòðîâîé
10 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
1, 3, 5, 7*
2, 4, 6
2, 4, 7*
1, 3, 5, 6
2, 6*
1, 3, 4, 5, 7
3, 5, 6*
1, 2, 4, 7
Îáúåäèíåíèÿ âåðøèí
(2, 9, 12, 13) (5) (4, 6) (8, 11)
Ðèñ. 4. Ðåçóëüòàò îáúåäèíåíèÿ âåðøèí ñ îäèíàêîâûìè çíà÷åíèÿìè Yi
2
G V E3 3 3( , ), íå ïðåâûñèëî ÷èñëà ðåáåð â ãðàôå G V E1 1( , ). Ãðàôû G1 è
G V E( , ) ÿâëÿþòñÿ èñõîäíûìè äàííûìè äëÿ ðàáîòû ïðîöåäóðû À.
Äëÿ òîãî ÷òîáû ïðîâåðèòü ïðàâèëüíîñòü ðåçóëüòàòà, ïðåäñòàâèì èñ-
õîäíûé ãðàô G V E( , ) â âèäå áóëåâîé ôóíêöèè:
f � � � � � � � � �( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )1 2 1 6 2 3 2 5 3 4 4 5 4 6 6 7 .
Ïðîâåäÿ îáúåäèíåíèå ïî 2, 4 è 6, ïîëó÷èì f � � � �( ) ( ) ( )2 135 4 356 6 17 .
Äàëåå, ðàñêðûâàÿ ñêîáêè, ïðèâîäÿ ïîäîáíûå è èñïîëüçóÿ ôîðìó ïîãëî-
ùåíèÿ, ïîëó÷àåì ïåðå÷åíü íåïîãëîùàåìûõ âåðøèííûõ ïîêðûòèé ãðàôà
G V E( , ), ïðèâåäåííîãî íà ðèñ. 2:
f � � � � �1247 246 2356 1356 13457. (3)
Ïîñêîëüêó ÌÍÌ ÿâëÿþòñÿ äîïîëíåíèÿìè âåðøèííûõ ïîêðûòèé, íà îñíî-
âàíèè (3) ïîëó÷àåì ïåðå÷åíü ÌÍÌ f 1 356 1357 147 247 26� � � � � , ò.å. ðå-
çóëüòàò èäåíòè÷åí ðåçóëüòàòó ïðîöåäóðû À.  ïðîöåññå ðàáîòû ïðîöå-
äóðû À èñêëþ÷àþòñÿ èç àíàëèçà òîëüêî íåçàâèñèìûå ïîäìíîæåñòâà âåð-
øèí, äóáëèðóþùèå óæå ñôîðìèðîâàííûå ÌÍÌ âåðøèí, ò.å. ïåðå÷èñ-
ëÿþòñÿ âñå ÌÍÌ â èññëåäóåìîì ãðàôå.
Îöåíèì âðåìåííóþ ñëîæíîñòü ðàáîòû ïðîöåäóðû À. Â ãðàôå G i�1
÷èñëî âåðøèí ðàâíî n , à ÷èñëî ðåáåð íå ìîæåò ïðåâûøàòü E
n n
E1 1
2
�
�
�
( )
.
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 11
1 3
10 7
1,4
2,3,5,6
4,7
2,4,6
1,7
2,6
3,5
2,4
Ðèñ. 5. Ãðàô G V E2 2 2( , )
1,4,7*
2,3,5,6
1,4,7*
2,3,5,6
1, 3, 5,7*
2,4,6
1,4,7*
2,3,5,6
Îáúåäèíåíèÿ âåðøèí
(1,3) (1,10) (3,10) (3,7)
Ðèñ. 6. Ïðîöåññ ôîðìèðîâàíèÿ ãðàôà G V E3 3 3( , )
 ãðàôå G i�2 ÷èñëî âåðøèí íå ìîæåò ïðåâûñèòü E
n n
E
n n1 1
2
1
2
�
�
� �
�( ) ( )
.
Ïîñêîëüêó ÷èñëî ÌÍÌ ïðîïîðöèîíàëüíî n n( )�1 , îáùåå ÷èñëî âåðøèí,
ñôîðìèðîâàííûõ â ïðîöåññå ôîðìèðîâàíèÿ îäíîãî èç ãðàôîâ G i, íå ìîæåò
ïðåâûñèòü
n n2 21
2
( )�
ïðè ïëîòíîñòÿõ ðåáåð, ïðåâûøàþùèõ 0,5. Ïðè ôîð-
ìèðîâàíèè ãðàôîâ G i ïðîèñõîäèò ïðîöåññ óäâîåíèÿ ÷èñëà âåðøèí â ïîä-
ìíîæåñòâàõ, ñîîòâåòñòâóþùèõ âåðøèíàì ãðàôà, êîòîðûé ìîæíî îïèñàòü
ïîñëåäîâàòåëüíîñòüþ
2 2 2 2 21 2 4 8 ... p . (4)
Ïîñêîëüêó ÷èñëî âåðøèí â èñõîäíîì ãðàôå ðàâíî n, ïðîöåññ (4) ìîæåò
áûòü çàâåðøåí, êîãäà 2p n� , îòêóäà p n� log2 . ßñíî, ÷òî ñïðàâåäëèâî
íåðàâåíñòâî
2 2 2 2 2 21 2 4 8
2 2
2 � �... log log
logp nn n n .
Ñëåäîâàòåëüíî, ÷èñëî ãðàôîâ G i, êîòîðîå ïðèäåòñÿ ïîñòðîèòü ïðè ðåà-
ëèçàöèè ïðîöåäóðû À, íå ìîæåò ïðåâûñèòü n nlog2 . Ïðè ýòîì îáùåå ÷èñëî
âåðøèí, êîòîðîå ïðèäåòñÿ ïîñòðîèòü, íå ïðåâûñèò
n n
n n
2 2
2
1
2
( )
log
�
. Ïî-
ñêîëüêó íà ôîðìèðîâàíèå îäíîé âåðøèíû ãðàôà òðåáóåòñÿ íå áîëåå 2 2n
îïåðàöèé ñðàâíåíèÿ, îáùåå ÷èñëî îïåðàöèé, çàòðà÷èâàåìîå ïðîöåäóðîé À
íà ôîðìèðîâàíèå âñåõ ÌÍÌ, íå ìîæåò ïðåâûñèòü n n n n n5 2
2
7
21( ) log log� � .
Òàêèì îáðàçîì, âðåìåííàÿ ñëîæíîñòü ðàáîòû ïðîöåäóðû â õóäøåì ñëó÷àå
ïðè ïëîòíîñòÿõ ðåáåð â ãðàôå � > 0,5 íå ïðåâûñèò O ( log )n n7
2 .
Äàííàÿ îöåíêà ÿâëÿåòñÿ îöåíêîé ñâåðõó, ïîýòîìó ïðåäñòàâëÿåò èíòå-
ðåñ ïîëó÷èòü îöåíêó âðåìåííîé ñëîæíîñòè äàííîé ïðîöåäóðû â ñðåäíåì
ïðè ðàçëè÷íûõ ïëîòíîñòÿõ ðåáåð â ãðàôå. Äëÿ ýòîãî áûëî ïðîâåäåíî ýêñïå-
ðèìåíòàëüíîå èññëåäîâàíèå:
à) âðåìåííîé ñëîæíîñòè ðàáîòû ïðîöåäóðû À ïðè ðàçëè÷íûõ ïëîò-
íîñòÿõ ðåáåð â ãðàôàõ G V E( , );
á) çàâèñèìîñòè ÷èñëà ÌÍÌ îò ïëîòíîñòè ðåáåð â ãðàôå ïðè ôèêñè-
ðîâàííîì çíà÷åíèè ÷èñëà âåðøèí;
â) çàâèñèìîñòè ÷èñëà � 0( )G îò ïëîòíîñòè ðåáåð â ãðàôå G V E( , ) ïðè
ôèêñèðîâàííîì ÷èñëå âåðøèí.
Ïðè îöåíêå âðåìåííîé ñëîæíîñòè ïîäñ÷èòàíî ÷èñëî îïåðàöèé ñðàâ-
íåíèÿ è îáúåäèíåíèÿ, âûïîëíÿåìûõ ïðîöåäóðîé À ïðè ôîðìèðîâàíèè
âåðøèí ãðàôîâ G i. Äëÿ ïîëó÷åíèÿ êàæäîãî çíà÷åíèÿ, ïðèâåäåííîãî â òàáë. 2
Ñ.Â. Ëèñòðîâîé
12 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
è íà ðèñ.7, 8, ãåíåðèðîâàëîñü íå ìåíåå 40 ãðàôîâ ðàçìåðíîñòè n è 40 ðàç
ðåøàëàñü çàäà÷à ïåðå÷èñëåíèÿ âñåõ ÌÍÌ, îïðåäåëÿëîñü ñðåäíåå ÷èñëî
ýëåìåíòàðíûõ îïåðàöèé (ÝÎ), âûïîëíÿåìûõ ïðîöåäóðîé À äëÿ âñåõ çíà-
÷åíèé n. Ïðè ýòîì ðåáðà â ãðàôàõ ãåíåðèðîâàëèñü ïî ðàâíîìåðíîìó çàêîíó
ðàñïðåäåëåíèÿ.
Êàê âèäíî èç òàáë. 2 è ðèñ. 8, à, ÷èñëî ÌÍÌ ñóùåñòâåííî ìåíüøå
âåëè÷èíû òåîðåòè÷åñêîé îöåíêè �* ( )� �Cn n 1 , à çíà÷åíèå � 0( )G ñ óâåëè-
÷åíèåì ïëîòíîñòè ãðàôà óìåíüøàåòñÿ è â ñðåäíåì ïðè ìàëûõ ïëîòíîñòÿõ
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 13
n Îöåíêà ñâåðõó
÷èñëà ÝÎ
×èñëî
âûïîëíåííûõ
ÝÎ
t, c
Îöåíêà
ñâåðõó
�*
� �0( )G
×èñëî
îäèíàêî-
âûõ ÌÍÌ
� = 0,02 � 0,2; Ñ = 1
10 1300000 16598 0,03 90 16 5 6
11 67620483 50195 0,06 110 21 6 1
12 128636191 215043 0,15 132 28 6 7
13 232796998 472669 0,32 156 37 7 1
14 402679585 1688780 0,89 182 49 7 8
15 669768750 4030206 2,1 210 65 7 8
16 1076426179 12280294 5,7 240 86 8 8
17 410338673 32790573 14,7 272 114 9 1
18 2559079734 88805250 38,1 306 151 9 9
19 3807893608 238947325 98,44 342 200 10 1
20 554240000 593443818 239 380 265 10 2
� = 0,5; Ñ = 1
20 5504000000 239244 0,1 380 32 5 —
30 107163000000 6967613 1,7 870 149 6 —
40 874905600000 100974931 18,2 1560 466 7 —
50 4375000000000 693336285 102,9 2450 1012 8 —
60 16572211200000 1005307365 724,4 3540 1950 8 —
� = 0,9; Ñ = 1
50 4375000000000 35955 0,04 2450 81 3 —
100 660000000000000 3541338 0,51 9900 226 4 —
150 12387304687500000 55974348 4,6 22350 340 4 —
200 98176000000000000 381577400 26,1 39800 389 5 —
250 487670898437500000 11500160701 99,3 62250 436 4 —
Òàáëèöà 2
ðåáåð â ãðàôå íå ïðåâûøàåò çíà÷åíèÿ n /2 (ñì. ðèñ. 8, á). Ñðåäíåå ÷èñëî
îïåðàöèé, âûïîëíÿåìûõ ïðîöåäóðîé À, òàêæå íå ïðåâûøàåò ïîëó÷åííîé
îöåíêè ñâåðõó (ñì. òàáë. 2 è ðèñ. 7).
Ðåçóëüòàòû ýêñïåðèìåíòà ïîêàçàëè, ÷òî âðåìåííàÿ ñëîæíîñòü ïðî-
öåäóðû À íà÷èíàåò ïðèáëèæàòüñÿ ê ïîëó÷åííîé âåðõíåé îöåíêå ïðè áîëü-
øèõ çíà÷åíèÿõ n è ìàëûõ �. Ïîñêîëüêó ñòåïåíü ïîëèíîìà, îöåíèâàþùåãî
âðåìåííóþ ñëîæíîñòü åå ðàáîòû, î÷åíü áîëüøàÿ, âðåìÿ ðåøåíèÿ çàäà÷è
ìîæåò âîçðàñòàòü äî äåñÿòêîâ ñîòåí ìèíóò è ÷àñîâ. Ïîýòîìó äëÿ ýô-
ôåêòèâíîé ðàáîòû ïðåäëîæåííîãî àëãîðèòìà ïðè ìàëûõ ïëîòíîñòÿõ ðåáåð
è áîëüøîì ÷èñëå âåðøèí íåîáõîäèì ïðîöåññ ðàñïàðàëëåëèâàíèÿ äàííîé
ïðîöåäóðû, ÷òî âîçìîæíî îñóùåñòâèòü, ïðèìåíèâ äëÿ åå ðåàëèçàöèè
CUDA òåõíîëîãèè.
Äëÿ ïðîâåðêè ïðàâèëüíîñòè ðàáîòû ïðîöåäóðû À èñïîëüçîâàí òî÷íûé
ðàíãîâûé àëãîðèòì RM [4], èìåþùèé ýêñïîíåíöèàëüíóþ ñëîæíîñòü, è
àëãîðèòì IND, ðåàëèçóþùèé ïðîöåäóðó À. Èç ðèñ. 7 âèäíî, ÷òî ÷èñëî ÝÎ,
âûïîëíÿåìûõ ïðîöåäóðîé À, ïðè � = 50 % â ãðàôàõ íå ïðåâûøàåò çíà-
Ñ.Â. Ëèñòðîâîé
14 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
0
10000000
20000000
30000000
ÝÎ
n
y = n
5
t, c
à
á
0
1
2
10 15 20 25 30
Ðèñ. 7. Çàâèñèìîñòü ñðåäíåãî ÷èñëà ÝÎ (à) è ñðåäíåãî âðåìåíè t (á) ðàáîòû ïðîöåäóðû À
îò ÷èñëà âåðøèí â ãðàôå ïðè � = 50 % : � — àëãîðèòì RM; � — àëãîðèòì IND
÷åíèé äàííîãî ïîëèíîìà.  ïðîöåññå ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé
íåñîâïàäåíèé ïðè îïðåäåëåíèè ÌÍÌ ðàíãîâûì àëãîðèòìîì è èññëåäóå-
ìîé ïðîöåäóðîé À íå íàáëþäàëîñü.
Âûâîäû
Ïðåäëîæåííàÿ ïðîöåäóðà À ïðè � > 0,5 â ñðåäíåì çà ïîëèíîìèàëüíîå âðå-
ìÿ ïîçâîëÿåò ðåøàòü òàêèå çàäà÷è êàê îïðåäåëåíèå ÌÍÌ, âåðøèííûõ
ïîêðûòèé è êëèê â ïðîèçâîëüíûõ íåîðèåíòèðîâàííûõ ãðàôàõ, ñòåïåíü
âåðøèí êîòîðûõ áîëüøå èëè ðàâíà åäèíèöå. Îäíàêî ïðè ìàëûõ ïëîò-
íîñòÿõ ðåáåð â ãðàôå ïðîöåäóðà âûïîëíÿåò ýêñïîíåíöèàëüíîå ÷èñëî ÝÎ,
ïîñêîëüêó ÷èñëî ÌÍÌ âîçðàñòàåò ýêñïîíåíöèàëüíî.  õóäøåì ñëó÷àå ïðè
� < 0,5 ïðîöåäóðà À âûïîëíÿåò íå áîëåå, ÷åì Î (2n) ÝÎ, à ïðè � � 0,5 —
O ( log )n n7
2 ÝÎ, ÷òî âûãîäíî îòëè÷àåò åå îò àëãîðèòìà Áðîíà — Êåðáîøà,
èìåþùåãî âðåìåííóþ ñëîæíîñòü O (3n/3). Êðîìå òîãî, â àëãîðèòìå Áðîíà —
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèçâîëüíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 1 15
0
20
40
60
ÌÍÌ
�� �
20 30 40 50 60 70 80
0
10
30
200
400
600
800
20
20
, %�
n = 30
n = 10
à
á
Ðèñ. 8. Çàâèñèìîñòü ñðåäíåãî ÷èñëà ÌÍÌ (à) è ñðåäíåé ìîùíîñòè íàèáîëüøåãî ÌÍÌ (á)
îò ïëîòíîñòè ðåáåð ïðè ðàçëè÷íîì ÷èñëå âåðøèí â ãðàôå
Êåðáîøà ïåðå÷èñëÿþòñÿ âñå íåçàâèñèìûå ìíîæåñòâà è ñðåäè íèõ âû-
áèðàþòñÿ ìàêñèìàëüíî íåçàâèñèìûå, à â ïðåäëîæåííîé ïðîöåäóðå À
ïåðå÷èñëÿþòñÿ òîëüêî ÌÍÌ, ÷òî ïîçâîëÿåò ñóùåñòâåííî ñîêðàòèòü âðåìÿ
íà èõ ïåðå÷èñëåíèå.
A procedure of enumeration of only maximum independent sets in unoriented arbitrary graphs
has been proposed; it allows reducing a temporary difficulty of the algorithm realization.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Êðèñòîôèäåñ Í. Òåîðèÿ ãðàôîâ. Àëãîðèòìè÷åñêèé ïîäõîä. — Ì. : Ìèð, 1978. — 309 ñ.
2. Åìåëè÷åâ Â.À., Ìåëüíèêîâ Î.È., Ñàðâàíîâ Â.È., Òûøêåâè÷ Ð.È. Ëåêöèè ïî òåîðèè
ãðàôîâ. — Ì. : Íàóêà, 1990. — 383 c.
3. Ëèñòðîâîé Ñ.Â., ßáëî÷êîâ Ñ.Â. Ìåòîä ðåøåíèÿ çàäà÷è îïðåäåëåíèÿ ìèíèìàëüíûõ
âåðøèííûõ ïîêðûòèé è íåçàâèñèìûõ ìàêñèìàëüíûõ ìíîæåñòâ // Ýëåêòðîí. ìîäåëè-
ðîâàíèå. — 2003. — 25, ¹ 2. — Ñ. 31—40.
4. Ëèñòðîâîé Ñ.Â., Ãóëü À.Þ. Ìåòîä ðåøåíèÿ çàäà÷è î ìèíèìàëüíîì ïîêðûòèè íà îñíîâå
ðàíãîâîãî ïîäõîäà // Òàì æå. — 1999. — 21, ¹ 1 — Ñ. 58—70.
Ïîñòóïèëà 06.08.13
ËÈÑÒÐÎÂÎÉ Ñåðãåé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû ñïåöèàëè-
çèðîâàííûõ êîìïüþòåðíûõ ñèñòåì Óêðàèíñêîé ãîñóäàðñòâåííîé àêàäåìèè æåëåçíîäîðîæ-
íîãî òðàíñïîðòà.  1972 ã. îêîí÷èë Õàðüêîâñêîå âûñøåå âîåííîå êîìàíäíî-èíæåíåðíîå
ó÷èëèùå. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ
è èõ ïðèëîæåíèå ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé.
Ñ.Â. Ëèñòðîâîé
16 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 1
|