Метод перечисления максимальных независимых множеств в неориентированных графах
На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125....
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2017 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/127632 |
| 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: | Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859647057853153280 |
|---|---|
| author | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_facet | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| citation_txt | Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125.
На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125.
Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125.
|
| first_indexed | 2025-12-07T13:29:37Z |
| format | Article |
| fulltext |
ÓÄÊ 519.682.1
Ñ.Â. Ëèñòðîâîé, ä-ð òåõí. íàóê
Óêðàèíñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò æåëåçíîäîðîæíîãî òðàíñïîðòà
(Óêðàèíà, 61050, Õàðüêîâ, ïë. Ôåéðáàõà, 7,
òåë. (050)9355042, å-mail: om1sergeyvladimirovih@gmail.com),
À.Â. Ñèäîðåíêî
(Samsung Electronics Ukraine Company, LLC Samsung R&D Institute Ukraine
(Óêðàèíà, 01302, Êèåâ, óë. Ëüâà Òîëñòîãî, 57,
òåë. +380509800852, å-mail cdandrey@gmail.com),
Å.Ñ. Ëèñòðîâàÿ, êàíä. òåõí. íàóê
Íàöèîíàëüíûé àýðîêîñìè÷åñêèé óíèâåðñèòåò èì. Í.Å. Æóêîâñêîãî
(Óêðàèíà, 61070, Õàðüêîâ, óë. ×êàëîâà, 17,
å-mail: listravkina@gmail.com)
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ
ìíîæåñòâ â íåîðèåíòèðîâàííûõ ãðàôàõ
Íà îñíîâå ðàíãîâîãî ïîäõîäà ïðåäëîæåí ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñè-
ìûõ ìíîæåñòâ íåîðèåíòèðîâàííîãî ñâÿçíîãî ãðàôà ñ âðåìåííîé ñëîæíîñòüþ, â ñðåäíåì
íå ïðåâûøàþùåé O (n6), ãäå n — ÷èñëî âåðøèí â ãðàôå, äëÿ ãðàôîâ, íå ñîäåðæàùèõ
ðàçäåëÿþùèõ âåðøèí, ðàçìåðíîñòü êîòîðûõ íå ïðåâûøàåò n = 125.
Ê ë þ ÷ å â û å ñ ë î â à: ìàêñèìàëüíîå íåçàâèñèìîå ìíîæåñòâî, êëèêà, âåðøèííîå
ïîêðûòèå.
Íà îñíîâ³ ðàíãîâîãî ï³äõîäó çàïðîïîíîâàíî ìåòîä ïåðåðàõóâàííÿ ìàêñèìàëüíèõ íåçà-
ëåæíèõ ìíîæèí íåîð³ºíòîâàíîãî çâ’ÿçíîãî ãðàôà ç ÷àñîâîþ ñêëàäí³ñòþ, ùî â ñåðåäíüîìó
íå ïåðåâèùóº O (n6), äå n — ÷èñëî âåðøèí ó ãðàô³, äëÿ ãðàô³â, ùî íå ìàþòü ðîçä³ëÿþ÷èõ
âåðøèí, ðîçì³ð ÿêèõ íå ïåðåâèùóº n = 125.
Ê ë þ ÷ î â ³ ñ ë î â à: ìàêñèìàëüíà íåçàëåæíà ìíîæèíà, êë³êà, âåðøèííå ïîêðèòòÿ.
Çàäà÷à ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ — îäíà èç
èçâåñòíûõ NP-òðóäíûõ çàäà÷ òåîðèè ãðàôîâ, äëÿ êîòîðîé ïîêà íå íàéäåíî
àëãîðèòìîâ ðåøåíèÿ çà ïîëèíîìèàëüíîå âðåìÿ. Ìåæäó òåì, äàííàÿ çàäà÷à
èìååò ìíîãî÷èñëåííûå ïðèëîæåíèÿ.  áèîèíôîðìàòèêå ïðè êîìïüþòåð-
íîì àíàëèçå ãåíîìíûõ áàç äàííûõ îíà èñïîëüçóåòñÿ, íàïðèìåð, ïðè ïîèñ-
êå ïîòåíöèàëüíûõ ðåãóëÿòîðíûõ ñòðóêòóð ðèáîíóêëåèíîâûõ êèñëîò.
Èññëåäîâàíèÿ â îáëàñòè ïåðå÷èñëåíèÿ íåçàâèñèìûõ ìíîæåñòâ â ãðà-
ôàõ âåäóòñÿ ñ ñåðåäèíû ïðîøëîãî âåêà. Èõ ðåçóëüòàòû íàõîäÿò ïðèëîæå-
íèÿ íå òîëüêî íåïîñðåäñòâåííî â ìàòåìàòèêå (êîìáèíàòîðíàÿ òåîðèÿ ÷è-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 3
�����������
���
��
��
�����
�������
���
��������
��
� Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ, 2017
ñåë, òåîðèÿ êîäèðîâàíèÿ, òåîðåòè÷åñêàÿ èíôîðìàòèêà), íî è â äðóãèõ îá-
ëàñòÿõ. Òàê, íàïðèìåð, â òåîðåòè÷åñêîé õèìèè âàæíûìè õàðàêòåðèñòè-
êàìè ñîåäèíåíèé ÿâëÿþòñÿ èíäåêñû Ìýððèôèëäà—Ñèììîíñà [1] è Õî-
ñîéè [2], êîòîðûå åñòü íå ÷òî èíîå, êàê ÷èñëî íåçàâèñèìûõ ìíîæåñòâ â
ñîîòâåòñòâóþùèõ ãðàôàõ.
Ìíîæåñòâî X i
r , ñîñòîÿùåå èç r ïîïàðíî íåñìåæíûõ âåðøèí ãðàôà
G V E( , ), íàçûâàåòñÿ íåçàâèñèìûì ìíîæåñòâîì (ÍÌ). Îáîçíà÷èì ÷åðåçYi
k
ìíîæåñòâî âåðøèí, ñ êîòîðûìè ñâÿçàíû âåðøèíû i-ãî ìíîæåñòâà X i
r â
ãðàôåG V E( , ). Ïîä ìàêñèìàëüíûìè íåçàâèñèìûìè ìíîæåñòâàìè (ÌÍÌ)
ïîíèìàþò ìàêñèìàëüíûå ïî âêëþ÷åíèþ ÍÌ, ò.å. ìíîæåñòâà, óäîâëåòâî-
ðÿþùèå óñëîâèþ 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( , ) íå ñóùåñòâóåò.
Ìàêñèìàëüíûé ðàçìåð � 0 íåçàâèñèìîãî ìíîæåñòâà â ãðàôå G V E( , )
íàçûâàåòñÿ ÷èñëîì íåçàâèñèìîñòè ãðàôà G V E( , ). Ñåìåéñòâî âñåõ íåçà-
âèñèìûõ ìíîæåñòâ îáîçíà÷èì I (G). Åãî ìîæíî ðàññìàòðèâàòü êàê îáúåäè-
íåíèå äâóõ ñåìåéñòâ, I G I G| ||( ) ( )� , ãäå I G| ( ) — ñåìåéñòâî âñåõ ÌÍÌ,
÷èñëî êîòîðûõ îáîçíà÷èì � ( )G , è I G|| ( ) — ñåìåéñòâî âñåõ íåçàâèñèìûõ
ìíîæåñòâ, íå ÿâëÿþùèõñÿ ìàêñèìàëüíûìè, ò.å. äëÿ êîòîðûõ âûïîë-
íÿåòñÿ óñëîâèå X Y Vi
r
i
k� � . Â ñåìåéñòâå I G| ( ) áóäåì âûäåëÿòü ïîäñå-
ìåéñòâî I G I GM ( ) ( )|� íàèáîëüøèõ ÌÍÌ (ÍÌÍÌ), ÷èñëî êîòîðûõ îáîç-
íà÷èì ( )G .
Âàæíîé õàðàêòåðèñòèêîé àíàëèçèðóåìûõ ãðàôîâ ÿâëÿåòñÿ ïëîòíîñòü
ðåáåð m â ãðàôå G V E( , ). Ïîä ïëîòíîñòüþ ðåáåð ãðàôà áóäåì ïîíèìàòü
îòíîøåíèå
� m E/ max , ãäå m — ÷èñëî ðåáåð â ãðàôå G V E( , ), E max �
�
�n n( )1
2
— ìàêñèìàëüíî âîçìîæíîå ÷èñëî ðåáåð â ãðàôå G V E( , ), ñîäåð-
æàùåì n-âåðøèí. Íà ïåðâûé âçãëÿä, êàæåòñÿ, ÷òî íàõîæäåíèå âñåõ ÌÍÌ —
ïðîñòàÿ çàäà÷à, ðåøàåìàÿ ïðîñòûì ïåðåáîðîì ÍÌ ñ îäíîâðåìåííîé ïðî-
âåðêîé èõ íà ìàêñèìàëüíîñòü. Ïðåäñòàâëåíèå î ïðîñòîòå çàäà÷è ñïðàâåä-
ëèâî òîëüêî äëÿ íåáîëüøèõ ãðàôîâ (â ïðîñòûõ ïðåäìåòíûõ îáëàñòÿõ) ñ
÷èñëîì âåðøèí íå áîëåå 20. Îäíàêî ïðè óâåëè÷åíèè ÷èñëà âåðøèí ýòîò
ìåòîä ïîèñêà ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ ñòàíîâèòñÿ ãðîìîçäêèì.
Òàêîé âûâîä ïîëó÷àåì, èññëåäóÿ çàâèñèìîñòü ÷èñëà êëèê îò ÷èñëà
âåðøèí â ãðàôàõ Ìóíà—Ìîçåðà [3]. Ïîíÿòèå, ïðîòèâîïîëîæíîå ÍÌ, åñòü
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
4 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
ïîëíûé ïîäãðàô [4].  îòëè÷èå îò ÍÌ, â êîòîðîì íå ìîãóò âñòðåòèòüñÿ äâå
ñìåæíûå âåðøèíû, â ïîëíîì ïîäãðàôå âñå âåðøèíû ïîïàðíî ñìåæíûå.
Î÷åâèäíî, ÷òî ÍÌ ãðàôà G ñîîòâåòñòâóåò ïîëíîìó ïîäãðàôó ãðàôà G , è
íàîáîðîò. Çäåñü G — äîïîëíåíèå ãðàôà G. Ñëåäîâàòåëüíî, çàäà÷à ïîèñêà
ÍÌ ãðàôà G ëèíåéíî ïðåîáðàçóåòñÿ â çàäà÷ó ïîèñêà ïîëíûõ ïîäãðàôîâ
ãðàôà G .
 ðàáîòå [4] óêàçàíî, ÷òî ëó÷øèì èç èçâåñòíûõ àëãîðèòìîâ ïîèñêà
ñåìåéñòâà ÌÍÌ ÿâëÿåòñÿ ìåòîä ïåðåáîðà Áðîíà—Êýðáîøà ñ âðåìåííîé
ñëîæíîñòüþ O n( )3 .  ïðîöåññå âûïîëíåíèÿ ýòîãî àëãîðèòìà ÷èñëî ôîðìè-
ðóåìûõ ÌÍÌ óâåëè÷èâàåòñÿ, íî çàòåì îòáðàñûâàåòñÿ, òàê êàê îáíàðó-
æèâàåòñÿ, ÷òî îíè ñîäåðæàòñÿ â äðóãèõ, ðàíåå ïîëó÷åííûõ ìíîæåñòâàõ, è
ïîýòîìó íå ÿâëÿþòñÿ ìàêñèìàëüíûìè. Îñíîâíûì íåäîñòàòêîì ìåòîäà
Áðîíà—Êýðáîøà ÿâëÿåòñÿ íåîáõîäèìîñòü âî âðåìÿ ðàáîòû àëãîðèòìà
ñîõðàíÿòü áîëüøîå êîëè÷åñòâî âñïîìîãàòåëüíîé èíôîðìàöèè, ïîëó÷åí-
íîé íà âñåõ øàãàõ.
 ðàáîòå [5] ïðèâåäåíû ðåçóëüòàòû ñðàâíåíèÿ àëãîðèòìîâ Ëóêàêèñà
(Loukakis), Öóêèÿìà (Tsukiyama) è ×èáà (Chiba) ñ àëãîðèòìîì Áðîíà—
Êåðáîøà è åãî ðàçëè÷íûìè âàðèàöèÿìè. Ñîãëàñíî ýòèì ðåçóëüòàòàì àëãî-
ðèòì Áðîíà—Êåðáîøà äî ñèõ ïîð ÿâëÿåòñÿ îäíèì èç ñàìûõ ýôôåêòèâíûõ
äëÿ ðåøåíèÿ çàäà÷è î ïîèñêå âñåõ ÌÍÌ íåîðèåíòèðîâàííîãî ãðàôà. Â
ðàáîòå [6] ïðåäñòàâëåíà î÷åðåäíàÿ ìîäèôèêàöèÿ àëãîðèòìà Áðîíà—Êåð-
áîøà.  ðàáîòå [7] òàêæå áûëà ïîëó÷åíà îöåíêà âðåìåííîé ñëîæíîñòè
àëãîðèòìà Áðîíà—Êåðáîøà: O n( )/3 3 .
Ñðåäè ïåðâûõ ðàáîò â îáëàñòè ïåðå÷èñëåíèÿ ÍÌ — ðàáîòû, ïîñâÿ-
ùåííûå ïîèñêó ãðàôîâ ñ íàèáîëüøèì ÷èñëîì ÍÌ [3, 4].  ðàáîòå [8]
ïîëó÷åíû âåðõíèå è íèæíèå îöåíêè ÷èñëà ÍÌ â äåðåâüÿõ ñ çàäàííûì
÷èñëîì âåðøèí. Ïóñòü T — äåðåâî ñ n âåðøèíàìè. Òîãäà I T n( ) �
2 1. Ïðè
ýòîì ðàâåíñòâî I T n( ) �� ñïðàâåäëèâî, åñëè Ò ÿâëÿåòñÿ ïðîñòîé öåïüþ, ãäå
� n — (n + 2)-å ÷èñëî Ôèáîíà÷÷è (� 0 1� ,�1 2� , � � �n n n�
� �1 2 ïðè n � 2).
 îáùåì ñëó÷àå äëÿ ïðîèçâîëüíûõ ãðàôîâ ñïðàâåäëèâî íåðàâåíñòâî
( ) ( )n I G n
� �1 2 , ãäå íèæíÿÿ ãðàíèöà äîñòèãàåòñÿ íà ïîëíîì ãðàôå, à
âåðõíÿÿ — íà ïóñòîì ãðàôå. Ê ñîæàëåíèþ, âñå èçâåñòíûå îöåíêè ñâåðõó
ÿâëÿþòñÿ ãðóáûìè è èõ òðóäíî èñïîëüçîâàòü íà ïðàêòèêå.
Áóäåì ðàññìàòðèâàòü êëàññ ãðàôîâ, â êîòîðûõ ïðè ïåðåõîäå îò ãðàôà
G ê åãî äîïîëíåíèþ G , è íàîáîðîò, ãðàô îñòàåòñÿ ñâÿçíûì è íå ñîäåðæèò
ðàçäåëÿþùèõ âåðøèí. Íàïðèìåð, ïðè ïåðåõîäå îò ãðàôîâ Ìóíà—Ìîçåðà
ê èõ äîïîëíåíèþ ïîëó÷àåì íàáîð íåñâÿçàííûõ êîìïîíåíò. Åñòåñòâåííî, â
òàêîì íåñâÿçíîì ãðàôå ÷èñëî ÍÌ ïðè áîëüøèõ çíà÷åíèÿõ n è áîëüøîì
÷èñëå íåñâÿçàííûõ êîìïîíåíò áóäåò ïðèáëèæàòüñÿ ê âåðõíåé ãðàíèöå 2n .
Ïðåäñòàâëÿåò èíòåðåñ ðàçðàáîòêà ïðîöåäóðû íåÿâíîãî ïîëíîãî ïåðåáîðà,
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 5
ïîçâîëÿþùåé ñíèçèòü âðåìåííóþ ñëîæíîñòü ïðîöåññà ïåðå÷èñëåíèÿ
ÌÍÌ äëÿ ðàññìàòðèâàåìîãî êëàññà ãðàôîâ.
Ôîðìàëèçàöèÿ çàäà÷è è åå ðåøåíèå. Äëÿ ðåàëèçàöèè ïðîöåäóðû
ïåðå÷èñëåíèÿ ÌÍÌ ïðåäëàãàåòñÿ èñïîëüçîâàòü èäåè ðàíãîâîãî ïîäõîäà ê
ðåøåíèþ çàäà÷ äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ [9—12]. Ïî-
ñêîëüêó áóäóò ðàññìàòðèâàòüñÿ òîëüêî ñî÷åòàíèÿ íåñâÿçàííûõ ìåæäó ñî-
áîé âåðøèí ãðàôà, ìíîæåñòâî âñåõ ñî÷åòàíèé âåðøèí ïðîèçâîëüíîãî íå-
îðèåíòèðîâàííîãî ãðàôà G V E( , ) ìîæíî ïðåäñòàâèòü â âèäå òðåóãîëüíîãî
ãðàôà G� (ðèñ. 1). Äëÿ ïðîèçâîëüíîé âåðøèíû i ìíîæåñòâî ïóòåé, âåäó-
ùèõ â ýòó âåðøèíó èç íåêîòîðîé âåðøèíû s, ìîæíî ïðåäñòàâèòü â âèäå
M i m m ms si
r
si
r
si
r n( ) ...� � � �� � � �1 2 1, i n� �1 1, ,
ãäå msi
r
si
r�{ }� , msj
r
sj
r�{ }� — ïîäìíîæåñòâà ïóòåé èç ïðîèçâîëüíîé
âåðøèíû s â íåêîòîðóþ âåðøèíó i ãðàôàG V E( , )ðàíãà r. Ñóììàðíîå ÷èñëî
ïóòåé, çàêàí÷èâàþùèõñÿ íà r-ì ÿðóñå ãðàôà G� , ðàâíî C n
r . Åñëè ïðîñóì-
ìèðîâàòü ìíîæåñòâà ïóòåé, çàêàí÷èâàþùèõñÿ íà âñåõ ÿðóñàõ, ïîëó÷èì
C C C Cn n n n
n n1 2 3 2 1
� �... . Ôàêòè÷åñêè ÷èñëà ïóòåé â ãðàôåG� , âåäóùèõ
ê âåðøèíàì i, îáðàçóþò òðåóãîëüíèê Ïàñêàëÿ (ðèñ. 2).
Ðàññìîòðèì âîçìîæíîñòü ïåðå÷èñëåíèÿ ÌÍÌ íà îñíîâå ôîðìèðî-
âàíèÿ ïóòåé â ãðàôå G� è ââåäåíèÿ ïðàâèë îòñå÷åíèÿ íåïåðñïåêòèâíûõ
ïóòåé, íà îñíîâå êîòîðûõ íåâîçìîæíî ïîñòðîèòü ÌÍÌ. Èñõîäíûìè äàí-
íûìè äëÿ ïðîöåäóðû ïåðå÷èñëåíèÿ áóäóò âåðøèíû i, ðàñïîëàãàåìûå íà
íóëåâîì ÿðóñå r �0. Èõ ìîæíî ðàññìàòðèâàòü êàê ïóòü �si , ñîäåðæàùèé
îäíó âåðøèíó i â ãðàôå G� . Êàæäûé ïóòü �si áóäåì çàäàâàòü òðåìÿ ìíî-
æåñòâàìè: �si = Xi | Yi | Zi, ãäå Xi — ìíîæåñòâî íåçàâèñèìûõ âåðøèí; Yi —
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
6 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
s
1
2 2
3 3 3
4 4 4 4
r =1 r = 2 r =3r =0
Ðèñ. 1. Òðåóãîëüíûé ãðàô G�
s
1
1
1
2
1
3
1
4
1
2
2
3
3
4
1
3
3
4
1
4
r=0 r=1 r=2 r=3
Ðèñ. 2. Òðåóãîëüíèê Ïàñêàëÿ â òðåóãîëüíîì ãðàôå G�
ìíîæåñòâî âåðøèí, ñ êîòîðûìè ñâÿçàíû âåðøèíû èç ìíîæåñòâà Õi; Zi —
ìíîæåñòâî âåðøèí, äîïîëíÿþùåå îáúåäèíåíèå ìíîæåñòâ X Yi i� äî V.
Íàïðèìåð, åñëè ãðàô ïðåäñòàâëÿåò ñîáîé öåïü
1-----2-----3-----4-----5-----6-----7-----8-----9-----10, (1)
èñõîäíûìè äàííûìè äëÿ ðåøåíèÿ çàäà÷è ïåðå÷èñëåíèÿ ÌÍÌ â òàêîì
ãðàôå áóäóò ñëåäóþùèå:
�s
r
1
0� = 1|2|345678910, �s
r
2
0� = 2|13|45678910, �s
r
3
0� = 3|24|15678910,
�s
r
4
0� = 4|35|12678910, �s
r
5
0� = 5|46|12378910, �s
r
6
0� = 6|57|12348910,
�s
r
7
0� = 7|68|12345910, �s
r
8
0� = 8|79|12345610, �s
r
9
0� = 9|810|1234567,
�s
r
10
0� = 10|9|12345678 . (2)
 òðåóãîëüíîì ãðàôå îíè ðàñïîëîæåíû íà íóëåâîì ÿðóñå, êàê ïîêàçàíî íà
ðèñ. 3, ãäå òðåóãîëüíûé ãðàô G� ïðåäñòàâëåí â âèäå òàáëèöû, â êîòîðîé
âåðøèíàì ãðàôà ñîîòâåòñòâóþò êëåòêè ñ íîìåðàìè âåðøèí òðåóãîëüíîãî
ãðàôà. Åñëè âçÿòü ïóòü �s
r
1
0� = 1|2|345678910, òî íà îñíîâå ýòîãî ïóòè
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 7
1|2|345678910
1
2|13|45678910
2 2
3|24|15678910
3
13|24|5678910
3 3
4|35|12678910
4 4 4 4
5|46|12378910
5 5 5 5 5
6|57|12348910
6 6 6 6 6
7|68|12345910
7 7 7 7 7
8|79|12345610
8 8 8 8 8
9|810|1234567
9 9 9 9 9
10|9|123345678
10 10 10 10 10
r � 0 r � 1 r � 2 r � 3 r � 4
Ðèñ. 3. Ïðåäñòàâëåíèå òðåóãîëüíîãî ãðàôà G� â âèäå òàáëèöû
ìîæíî ôîðìèðîâàòü ïóòè â âåðøèíû (3,4,5,6,7,8,9,10). Íàïðèìåð, åñëè
ñôîðìèðîâàòü ïóòü �s
r
13
1� â âåðøèíó 3 íà ïåðâîì ÿðóñå, òî åãî èäåíòè-
ôèêàöèÿ áóäåò èìåòü ñëåäóþùèé âèä:
�s
r
13
1� = X3 = {13} | Y3 = {24} | Z3 = {5,6,7,8,9,10},
ãäå X 3 1 3 13� � �{ }; Y3 2 2 4 2 4� � �{ } { , } { , } èëè â óïðîùåííîì âèäå �s
r
13
1� =
= 13|24|5678910.
Ïðåäïîëîæèì, ÷òî íà íåêîòîðîì ÿðóñå r ïîñòðîåí ïóòü � i
r = abc|gde|qtls.
 ìíîæåñòâå Zi ýòîãî ïóòè ñîäåðæàòñÿ âåðøèíû, â êîòîðûå äàííûé ïóòü
ìîæåò áûòü ïðîäëåí. ßñíî, ÷òî â ãðàôå G� â âåðøèíû ñ íîìåðàìè, áîëü-
øèìè, ÷åì íîìåð âåðøèíû ñ, äàííûé ïóòü íå ìîæåò áûòü ïðîäëåí. Ïîýòîìó
âåðøèíû ñ íîìåðàìè, ìåíüøèìè, ÷åì íîìåð âåðøèíû ñ, ìîãóò áûòü èñêëþ-
÷åíû èç ìíîæåñòâà Zi. Åñëè íîìåðà âñåõ âåðøèí â ìíîæåñòâå Zi ìåíüøå
íîìåðà âåðøèíû ñ, òî èç àíàëèçà ìîæåò áûòü èñêëþ÷åí âåñü ïóòü � i .
Òàêèå îòñå÷åíèÿ íàçîâåì ïðàâèëîì I îòñå÷åíèÿ íåïåðñïåêòèâíûõ
ïóòåé â ãðàôå G� . Ïîñëå ïðèìåíåíèÿ ïðàâèëà I â ìíîæåñòâå Z îáðàçî-
âàëîñü äâà ïîäìíîæåñòâà, Z| è Z|| , óäîâëåòâîðÿþùèå óñëîâèþ Z Z Zi i i� �| || ,
ãäå Zi
| — ìíîæåñòâî âåðøèí, êîòîðîå ìîæíî óäàëèòü èç Zi; Zi
|| — ìíî-
æåñòâî âåðøèí, êîòîðîå îñòàåòñÿ â Zi ïîñëå óäàëåíèÿ âåðøèí j Zi� | . ßñíî,
÷òî åñëè âåðøèíû, óäàëåííûå èç ìíîæåñòâà Zi, íå ñâÿçàíû ñ ìíîæåñòâîì
âåðøèí Zi
|| , òî íà îñíîâå ýòèõ âåðøèí íå óäàñòñÿ ïîñòðîèòü ÌÍÌ, òàê êàê
îíî ìîãëî áûòü ïîïîëíåíî âåðøèíàìè èç ìíîæåñòâà Zi
| , íî îíè óæå
óäàëåíû èç àíàëèçà.
Òàêèì îáðàçîì, ìîæíî ñôîðìóëèðîâàòü ïðàâèëî II îòñå÷åíèÿ íåïåðñ-
ïåêòèâíûõ ïóòåé â ãðàôåG� , à èìåííî: ïðîâåðÿåì, ñâÿçàíû ëè âåðøèíû èç
ìíîæåñòâà Zi
| ñ âåðøèíàìè èç ìíîæåñòâà Zi
|| è, åñëè òàêèõ ñâÿçåé íåò, òî
ïóòü � i èñêëþ÷àåì èç àíàëèçà. Åñëè îðãàíèçîâàòü ïîñëåäîâàòåëüíîå ôîð-
ìèðîâàíèå ïóòåé â ãðàôå G� ñíà÷àëà îò âåðøèíû 1 êî âñåì îñòàëüíûì
âåðøèíàì ãðàôà G� , çàòåì îò âåðøèíû 2 êî âñåì îñòàëüíûì âåðøèíàì
ãðàôà G� è òàê äàëåå, è åñëè â ïðîöåññå ôîðìèðîâàíèÿ ïóòè ê âåðøèíå ñ
íîìåðîì k ïðè ïðèìåíåíèè ïðàâèë I è II îêàçûâàåòñÿ, ÷òî ïóòü �k ìîæíî
èñêëþ÷èòü èç àíàëèçà, òî ÿñíî, ÷òî ïóòè ê âåðøèíàì ñ íîìåðàìè k + 1 è
áîëüøå ïðîöåäóðà íå ñòðîèò. Òàêîå îòñå÷åíèå íàçîâåì ïðàâèëîì III. Èñ-
ïîëüçóÿ ââåäåííûå ïðàâèëà îòñå÷åíèÿ, ðàññìîòðèì ïðîöåäóðó À ïåðå÷èñ-
ëåíèÿ ÌÍÌ.
Ïðîöåäóðà À.
Ø à ã 1. Íà íóëåâîì ÿðóñå â ìíîæåñòâà Õ âíîñèì âñå âåðøèíû è
ôîðìèðóåì äëÿ êàæäîé âåðøèíû ìíîæåñòâà Y è Z. Íà îñíîâå ââåäåííûõ
ïðàâèë I—III èñêëþ÷àåì èç äàëüíåéøåãî àíàëèçà òå âåðøèíû, íà îñíîâå
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
8 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
êîòîðûõ â ïåðñïåêòèâå íåâîçìîæíî ïîñòðîèòü ÌÍÌ, è ïåðåõîäèì ê âû-
ïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 2. Âûáèðàåì ïåðâóþ âåðøèíó (s := 1), ôîðìèðóåì ïóòè �si
r�1 ðàí-
ãà r = 1 è äëÿ êàæäîãî ïóòè îïðåäåëÿåì ìíîæåñòâà Y è Z. Ïóòè, óäîâëåò-
âîðÿþùèå óñëîâèþ X Y Vi
r
i
k� � , çàíîñèì â ìíîæåñòâî U. Â êàæäîì ïóòè
íà îñíîâå ïðàâèë I—III èñêëþ÷àåì èç äàëüíåéøåãî àíàëèçà òå âåðøèíû,
íà îñíîâå êîòîðûõ â ïåðñïåêòèâå íåâîçìîæíî ïîñòðîèòü ÌÍÌ, è, åñëè
ïðàâèëà I—III ïîçâîëÿþò, òî èñêëþ÷àåì èç àíàëèçà è ïîñòðîåííûå ïóòè è
ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 3. Ïðîâåðÿåì ìíîæåñòâà ïóòåé msi
r ��. Åñëè îíè íå ïóñòû, òî
ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà, èíà÷å — ïåðåõîäèì ê øàãó 5.
Ø à ã 4. Íà îñíîâå ïóòåé òåêóùåãî ðàíãà �si
r ôîðìèðóåì ïóòè �si
r r:�
1
ñëåäóþùåãî ðàíãà r + 1 â âåðøèíû, óêàçàííûå â ìíîæåñòâå Z, è äëÿ êàæ-
äîãî ñôîðìèðîâàííîãî ïóòè îïðåäåëÿåì ìíîæåñòâà Y è Z. Ïóòè, óäîâëåò-
âîðÿþùèå óñëîâèþ X Y Vi
r
i
k� � , çàíîñèì â ìíîæåñòâî U. Â êàæäîì ïóòè
ñîãëàñíî ïðàâèëàì I—III èñêëþ÷àåì èç äàëüíåéøåãî àíàëèçà òå âåðøèíû,
íà îñíîâå êîòîðûõ â ïåðñïåêòèâå íåâîçìîæíî ïîñòðîèòü ÌÍÌ, è, åñëè
ïðàâèëà I—III ïîçâîëÿþò, òî è ïîñòðîåííûå ïóòè èñêëþ÷àåì èç àíàëèçà è
ïåðåõîäèì ê âûïîëíåíèþ øàãà 3.
Ø à ã 5. Ïðîâåðÿåì, ïîñòðîåíû ïóòè èëè íåò îò âñåõ âåðøèí, íå èñê-
ëþ÷åííûõ èç àíàëèçà è ðàñïîëîæåííûõ íà íóëåâîì ÿðóñå. Åñëè äà, òî
ïðîöåäóðà çàêàí÷èâàåò ðàáîòó è ìíîæåñòâî U ñîäåðæèò âñå ÌÍÌ, èíà÷å —
s := s + 1; r := 0 è ïåðåõîäèì ê âûïîëíåíèþ øàãà 4.
Ðàññìîòðèì ïðèìåð ðàáîòû ïðîöåäóðû À äëÿ ãðàôà (1). Èñõîäíûìè
äàííûìè äëÿ ãðàôà (1) ÿâëÿþòñÿ ìíîæåñòâà ïóòåé (2). Â ðåçóëüòàòå ïðè-
ìåíåíèÿ ïðàâèë îòñå÷åíèÿ I, II â ìíîæåñòâå îñòàþòñÿ òîëüêî äâà ïóòè:
�s
r
1
0� = 1|2|345678910 è �s
r
2
0� = 2|13|45678910. Ïóòè �s
r
3
0� = 3|24|15678910,
�s
r
4
0� = 4|35|12678910, �s
r
5
0� = 5|46|12378910, �s
r
6
0� = 6|57|12348910, �s
r
7
0� =
= 7|68|12345910, �s
r
8
0� = 8|79|12345610 îòñåêàþòñÿ íà îñíîâå ïðàâèëà II, à
ïóòè �s
r
9
0� = 9|810|1234567 è �s
r
10
0� = 10|9|12345678 — íà îñíîâå ïðàâèëà I.
Ïîñêîëüêó ñðåäè èñõîäíûõ ïóòåé îñòàëîñü òîëüêî äâà, ïðîöåäóðà ôîðìè-
ðîâàíèÿ áóäåò ñîñòîÿòü èç äâóõ ýòàïîâ: ôîðìèðîâàíèÿ âñåõ âîçìîæíûõ
ïóòåé ïðîöåäóðîé À íà îñíîâå ïóòè �s
r
1
0� = 1|2|345678910 è ôîðìèðîâàíèÿ
ïóòåé ïðîöåäóðîé À íà îñíîâå ïóòè �s
r
2
0� = 2|13|45678910.
Ðåçóëüòàòû ðàáîòû ïðîöåäóðû ïðåäñòàâëåíû íà ðèñ. 4, ãäå öâåòîì
âûäåëåíû ïóòè è âåðøèíû, îòñåêàåìûå ïî ïðàâèëó I, çâåçäî÷êîé ïîìå÷å-
íû ñôîðìèðîâàííûå ÌÍÌ, à çíàêîì # — ïóòè, îòñåêàåìûå ïî ïðàâèëó II,
íà ïåðâîì è âòîðîì ÿðóñàõ ïóòè 110|29|345678 è 1310|249|5678 ê âåðøèíå
10 íå ïîñòðîåíû íà îñíîâå ïðàâèëà III.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 9
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
10 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
1|2|345678910
1
2 2
3
13|24|5678910
3 3
4
14|235|678910
4
4 4
5
15|246|378910 #
5
135|246|78910
5 5
5
6
16|257|348910 #
6
136|2457|8910
146|2357|8910
6 6 6
7
17|268|345910 #
7
137|2468|5910 #
147|23568|910
7
1357|2468|910
7 7
8
18|279|345610 #
8
138|2479|5610 #
8
1358|24679|10
1468|23579|10
1469|2357810*
8 8
9
19|2810|3456
9
139|24810|567
9
1359|246810|7
1369|2457810*
1469|2357810*
1479|2356810*
9
13579|246810*
9
10 10 10
14710|23456789*
10
135710|24689*
135810|24679*
136810|24579*
146810|23579*
10
r � 0 r � 1 r � 2 r � 3 r � 4
1 4|2
2|13|45678910
2
2 5|4
3 3 3 7|1
4
24|135|678910
4
4 4 1|0
5
25|1346|78910
5 5 5
5
6
26|1357|48910 #
6
246|1357|8910
6 6 6
7
27|1368|45910 #
7
247|13568|910
257|13468|910
7 7 7
8 8
248|13579|610#
258|134679|610
8
2468|13579|10
8 8
9 9 9
2479|1356810*
2469|1357810*
2579|1346810*
9 9
10 10 10
25810|134679*
25710|134689*
24610|13579|8
10
246810|13579*
10
r � 0 r � 1 r � 2 r � 3 r � 4
Ðèñ. 4. Ôîðìèðîâàíèå ïóòåé ïðîöåäóðîé À íà îñíîâå ïóòè � s
r
1
0� = 1|2|345678910 (à) è íà
îñíîâå ïóòè � s
r
2
0� = 2|13|45678910 (á)
à
á
 àíàëèçèðóåìîì ãðàôå (1) èìååòñÿ âñåãî 16 ÌÍÌ:
{2 4 6 8 10}; {1 4 6 8 10}; {1 3 6 8 10}; {1 3 5 8 10 };
{1 3 5 7 10}; {1 3 5 7 9}; {2 5 8 10}; { 2 5 7 10}; {2 5 7 9};
{2 4 7 10};{2 4 7 9}; {2 4 6 9}; {1 4 7 10}; {1 4 7 9}; {1 4 6 9}; {1 3 6 9}.
Êàê âèäèì, ïðîöåäóðà À âñå èõ ïåðå÷èñëèëà. Çà äâà ïðîõîäà ïðîöåäóðà À
ïîñòðîèëà 49 ïóòåé. Åñëè ïåðå÷èñëÿòü âñå ïóòè äî ÷åòâåðòîãî ÿðóñà,
îïðåäåëÿåìûå òðåóãîëüíèêîì Ïàñêàëÿ (ðèñ. 5), òî ïðèøëîñü áû ïîñòðîèòü
627 ïóòåé. Òàêèì îáðàçîì, ïðîèçîøëî ñîêðàùåíèå ïåðåáèðàåìûõ ïóòåé â
12,79 ðàç.
 ïðåäñòàâëåííîì àëãîðèòìå îòñå÷åíèå íåïåðñïåêòèâíûõ âàðèàíòîâ,
êîòîðûå çàâåäîìî íå ïðèâåäóò ê ïîñòðîåíèþ êëèêè, îáåñïå÷èâàåòñÿ ïî-
ñðåäñòâîì èñïîëüçîâàíèÿ äîïîëíèòåëüíîãî ìíîæåñòâà, â êîòîðîå ïîìå-
ùàþòñÿ âåðøèíû, óæå èñïîëüçîâàííûå äëÿ óâåëè÷åíèÿ ïîëíîãî ïîäãðàôà.
Àëãîðèòì îïåðèðóåò òðåìÿ ìíîæåñòâàìè âåðøèí ãðàôà: ìíîæåñòâîì Q,
ñîäåðæàùåì íà êàæäîì øàãå ðåêóðñèè ïîëíûé ïîäãðàô äëÿ äàííîãî øàãà
(ñòðîèòñÿ ðåêóðñèâíî); ìíîæåñòâîì âåðøèí Ñ, ñ ïîìîùüþ êîòîðîãî ìîæ-
íî óâåëè÷èòü çíà÷åíèå Q, è ìíîæåñòâîì âåðøèí N, óæå èñïîëüçîâàííûõ
äëÿ ðàñøèðåíèÿ Q íà ïðåäûäóùèõ øàãàõ. Àëãîðèòì ÿâëÿåòñÿ ðåêóðñèâíîé
ïðîöåäóðîé, ïðèìåíÿåìîé ê ýòèì òðåì ìíîæåñòâàì, è åãî ñëîæíîñòü
ëèíåéíà îòíîñèòåëüíî ÷èñëà êëèê â ãðàôå.
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 11
1
1
1
2
1
2
1
3
2
3
1
3
1
4
3
4
3
4
1
4
1
5
4
5
6
5
4
5
1
5
1
6
5
6
10
6
10
6
5
6
1
7
6
7
15
7
20
7
15
7
1
8
7
8
21
8
35
8
35
8
1
9
8
9
28
9
56
9
70
9
1
10
9
10
36
10
84
10
126
10
r � 0 r � 1 r � 2 r � 3 r � 4
�� 627 45 120 210 252
Ðèñ. 5. ×èñëî ïóòåé, îïðåäåëÿåìûõ òðåóãîëüíèêîì Ïàñêàëÿ
Ðåçóëüòàòû ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ ðàáîòû ïðîöåäóðû è
îöåíêà åå âðåìåííîé ñëîæíîñòè. Ïðè ýêñïåðèìåíòàëüíîì èññëåäîâàíèè
÷èñëà ýëåìåíòàðíûõ îïåðàöèé, âûïîëíÿåìûõ ïðåäëîæåííîé ïðîöåäóðîé
ôîðìèðîâàíèÿ ÌÍÌ, ÷èñëî âåðøèí n ãðàôîâ èçìåíÿëîñü â äèàïàçîíå îò 10
äî 100, à ïëîòíîñòü
ðåáåð â ãðàôå ãåíåðèðîâàëàñü ïî ðàâíîìåðíîìó çàêîíó
ðàñïðåäåëåíèÿ. Íà êàæäóþ òî÷êó îöåíêè ïðè ôèêñèðîâàííûõ çíà÷åíèÿõ n è
ãåíåðèðîâàëîñü íå ìåíåe 50 ãðàôîâ è îïðåäåëÿëîñü ñðåäíåå çíà÷åíèå ÷èñëà
ýëåìåíòàðíûõ îïåðàöèé ñðàâíåíèÿ �. Ôîðìèðóåìûå â ïðîöåññå ýêñïåðè-
ìåíòà ãðàôû íå ñîäåðæàëè ðàçäåëÿþùèõ âåðøèí, ïîñêîëüêó ïðè èõ íàëè÷èè
÷èñëî ÌÍÌ ìîæåò áûòü ýêñïîíåíöèàëüíî áîëüøèì. Âåðøèíà v ãðàôà G
íàçûâàåòñÿ ðàçäåëÿþùåé, åñëè ãðàô G v� èìååò áîëüøå êîìïîíåíò, ÷åì G.
Âñå ðåçóëüòàòû ïîëó÷åíû ñ äîâåðèòåëüíîé âåðîÿòíîñòüþ 0,95. Ïðè ïðî-
âåäåíèè ýêñïåðèìåíòà îöåíèâàëîñü âðåìÿ ðåøåíèÿ çàäà÷è, âåðîÿòíîñòü
ðåøåíèÿ çàäà÷è çà âðåìÿ, íå ïðåâûøàþùåå íåêîòîðîãî äîïóñòèìîãî, ðàâíîãî
30 ñ, à òàêæå ÷èñëî � ÌÍÌ, ÷èñëî ÍÌÍÌ è ÷èñëî �0 âåðøèí â ÍÌÍÌ. Ðå-
çóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé ïðèâåäåíû â òàáë. 1—6.
Êàê âèäíî èç òàáë. 1, 2, äëÿ ñåìåéñòâà S A S Gi
| ( ) ( )� ñïðàâåäëèâî íå-
ðàâåíñòâî I S| || |� � �, ò.å. åñëè ãðàô â âèäå öåïè — ñâÿçíûé, òî îáùåå
÷èñëî íåçàâèñèìûõ ìíîæåñòâ ñåìåéñòâà S (G) ýêñïîíåíöèàëüíî çàâèñèò îò
n, à ÷èñëî I S| || |� ÌÍÌ ñåìåéñòâà S A S Gi
| ( ) ( )� , ïî âñåé âèäèìîñòè,
âîçðàñòàåò ýêñïîíåíöèàëüíî, íî ñêîðîñòü âîçðàñòàíèÿ äàííîé ýêñïîíåíòû
ñóùåñòâåííî íèæå, ÷òî ïîçâîëÿåò äëÿ ãðàôîâ ñ ÷èñëîì âåðøèí, íå ïðåâû-
øàþùèì 125 çà ïîëèíîìèàëüíîå âðåìÿ, ïåðå÷èñëÿòü ÌÍÌ.
Èç òàáë. 1—4 âèäíî, ÷òî âðåìåííàÿ ñëîæíîñòü ðàáîòû ïðîöåäóðû À â
çàäàííîì äèàïàçîíå èçìåíåíèÿ âåðøèí ãðàôà íå ïðåâûøàåò O n( )6 . Òåñ-
òîâûå èñïûòàíèÿ ïîêàçàëè, ÷òî äàííàÿ òåíäåíöèÿ ñîõðàíÿåòñÿ äî çíà÷å-
íèé, íå ïðåâûøàþùèõ n �125.
Ýêñïåðèìåíòàëüíîå èññëåäîâàíèå ðàáîòû ïðîöåäóðû À ïîêàçàëî, ÷òî
äëÿ ãðàôîâ äàííîãî òèïà âûïîëíÿåòñÿ íåðàâåíñòâî | ( )| ( ) | ( )|| ||I G G I G� ��� è
� �( )G n� � 4, ò.å. äëÿ ðàññìàòðèâàåìîãî êëàññà ãðàôîâ ÷èñëî ÌÍÌ � ( )G
íå ïðåâûøàåò âåëè÷èíó n4. Ïîñëåäíåå ìîæåò áûòü îáóñëîâëåíî òåì, ÷òî
÷èñëî � íåñâÿçàííûõ ïàð X i
r�2 âåðøèí â ãðàôå ðàâíî ÷èñëó ðåáåð â ãðàôå,
ÿâëÿþùåìñÿ äîïîëíåíèåì G ãðàôà G V E( , ), â êîòîðîì âåðøèíû ãðàôà G
ñîåäèíåíû ðåáðàìè, åñëè îíè íå ñîåäèíåíû â ãðàôå G V E( , ). Åñëè â ãðàôå
G V E( , ) ñîäåðæèòñÿ m ðåáåð, òî ñïðàâåäëèâî ðàâåíñòâî
�
� � � �
�
�
�
�
�
� � �E m E
m
E
Emax max
max
max ( )1 1 .
Ïðè ýòîì ñïðàâåäëèâî òàêæå íåðàâåíñòâî � � n2, è ïîñêîëüêó ìàêñèìàëü-
íûé ðàíã ïóòè â òðåóãîëüíîì ãðàôå íå ìîæåò ïðåâûñèòü n �1, à ïðîöåäóðà
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
12 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 13
n
n
30 50 70 90 30 50 70 90
10 1 1 1 1
15 1 1 1 1 60 0,9904 1 1 1
20 1 1 1 1 65 0,9112 1 1 1
25 1 1 1 1 70 0,7413 1 1 1
30 1 1 1 1 75 0,5285 1 1 1
35 1 1 1 1 80 0,3584 1 1 1
40 1 1 1 1 85 0,2257 1 1 1
45 1 1 1 1 90 0,1478 1 1 1
50 1 1 1 1 95 0,0942 1 1 1
55 0,9999 1 1 1 100 0,0614 0,9999 1 1
Òàáëèöà 3. Âåðîÿòíîñòü ïåðå÷èñëåíèÿ ÌÍÌ çà âðåìÿ, íå ïðåâûøàþùåå 30 ñ
n
n
30 50 70 90 30 50 70 90
10 1412,4 762,95 427,125 243,5
15 10080,15 3698,275 1548,375 681,975 60 83253940 2348837 247262,5 33019,1
20 45701,7 12022,68 4080,6 1430,375 65 1,56E+08 3714664 341551,2 42300,55
25 178994,9 31065,93 8925 2632,85 70 2,88E+08 5472673 463163,7 53212,33
30 574507,9 71078,23 17133,35 4368,775 75 5,07E+08 8192267 622493,6 65958,73
35 1630869 154019,6 30304,35 6798,2 80 8,84E+08 11491946 805424,6 80744,53
40 4140749 295232,4 51080,35 9851,625 85 1,43E+09 16430697 1043164 97872,98
45 9376882 524696,7 78721,2 14041,75 90 2,40E+09 23090156 1329069 118094,6
50 20969116 904203,9 119682,7 19218,8 95 3,95E+09 31106591 1693379 139579,8
55 42391736 1494709 177555,5 25593,28 100 6,07E+09 42559745 2086415 164390,6
Òàáëèöà 1. ×èñëî ýëåìåíòàðíûõ îïåðàöèé �
n
n
30 50 70 90 30 50 70 90
10 0,0001 0,0001 0 0
15 0,0009 0,0003 0,0001 0,0001 60 6,3743 0,1672 0,018 0,0025
20 0,0037 0,001 0,0003 0,0001 65 12,1251 0,2654 0,0242 0,0031
25 0,0143 0,0024 0,0007 0,0002 70 22,4983 0,3925 0,0335 0,0039
30 0,0446 0,0054 0,0013 0,0004 75 39,7976 0,5887 0,0447 0,005
35 0,1223 0,0115 0,0022 0,0005 80 69,9057 0,8336 0,0576 0,0061
40 0,3086 0,0218 0,0037 0,0008 85 114,1993 1,207 0,0747 0,0072
45 0,698 0,0385 0,0056 0,0011 90 193,376 1,693 0,0942 0,0087
50 1,5917 0,0655 0,0087 0,0014 95 318,4027 2,2879 0,1191 0,0102
55 3,2247 0,1068 0,0128 0,0019 100 488,7817 3,1361 0,1474 0,0122
Òàáëèöà 2. Âðåìÿ ïåðå÷èñëåíèÿ ÌÍÌ (ñ)
äåëàåò n �1 ïðîõîä, òî îáùåå ÷èñëî ïóòåé, ïîñòðîåííîå ïðîöåäóðîé, íå
ïðåâûñèò âåëè÷èíû � � n4.
 ñëó÷àå ïðîèçâîëüíîãî ãðàôà, íå ñîäåðæàùåãî ðàçäåëÿþùèõ âåðøèí,
ýêñïîíåíöèàëüíî óñòàíîâëåíî, ÷òî åñëè ãðàô—ñâÿçíûé, òî ïðè
= 0,5 è
n �125 ïðîöåäóðà ñòðîèò ÌÍÌ çà ïîëèíîìèàëüíîå âðåìÿ. Îäíàêî ïðè
ìàëûõ çíà÷åíèÿõ ïëîòíîñòåé äëÿ ýòîãî òðåáóåòñÿ ïàìÿòü, ïðîïîðöèîíàëü-
íàÿ n6. Ýòî îáóñëîâëåíî òåì, ÷òî íå âñå ïóòè, ïîñòðîåííûå ïðîöåäóðîé, â
êîíå÷íîì ñ÷åòå ïðèâîäÿò ê ïîñòðîåíèþ ÌÍÌ, ò.å. áóäåò ïîñòðîåíî äîñòà-
òî÷íî áîëüøîå ÷èñëî ëèøíèõ ïóòåé. Ïðè ýòîì ÷èñëî ÌÍÌ íå ïðåâûøàåò
çíà÷åíèÿ � (ñì. òàáë. 4). Ïî âñåé âèäèìîñòè, ïðè
< 0,01 è äîñòàòî÷íî
áîëüøèõ çíà÷åíèÿõ n îáëàñòü íåîáõîäèìîé ïàìÿòè ìîæåò ýêñïîíåí-
öèàëüíî âîçðàñòàòü.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
14 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
n 4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 30 35 40 45 50
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
11
1
12 16 1 21 1 26
� 0
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11 15 18 20 23 25
� 3
4
5
7
9
12
16
21
28
37
49
65
86
114
151
200
265
351
465 4410 17991 73396 299426 1221537
� 256
625
1296
2401
4096
6561
10000
14641
20736
28561
38416
50625
65536
83521
104976
130321
160000
194481
234256 810000 1500625 2560000 4100625 6256000
Ïðèìå÷àíèå: íàä ÷åðòîé óêàçàíû õàðàêòåðèñòèêè äëÿ ÷åòíûõ çíà÷åíèé n, ïîä ÷åðòîé — äëÿ
íå÷åòíûõ çíà÷åíèé n.
Òàáëèöà 5. Õàðàêòåðèñòèêè ãðàôà öåïè íà n âåðøèíàõ
n
n
30 50 70 90 30 50 70 90
10 13,075 11,45 9,075 4,75
15 37,475 27,075 18,95 10,225 60 14723,95 1921,175 452,4 133,225
20 94,3 53,55 33,6 16,975 65 23712,18 2614,375 560,8 153,225
25 214,025 100,125 52,125 26,4 70 37289,55 3520,8 692,25 174,8
30 451,625 167,775 79,475 37,2 75 58063,05 4650,65 838,775 198,4
35 896,95 278,425 113,475 48,75 80 86997 6101,85 1016,375 220,8
40 1667,925 433,675 158,375 63,1 85 128568,5 7886,65 1213,825 247
45 3066,55 651,8 209,725 78,05 90 187178,1 10193,03 1431,7 276,875
50 5327,325 960,625 276,4 95,375 95 273065,9 12855,2 1693,275 304,25
55 9131,375 1358,725 357,075 114,075 100 385555,9 16020,8 1980,95 336,075
Òàáëèöà 4. ×èñëî ÌÍÌ � ( )G
Õàðàêòåðèñòèêè ãðàôà (1) íà ÷åòíûõ è íå÷åòíûõ âåðøèíàõ n ïðåäñòàâ-
ëåíû â òàáë. 5, èç êîòîðîé âèäíî, ÷òî äëÿ ÷åòíûõ çíà÷åíèé n ñïðàâåäëèâû
ñîîòíîøåíèÿ � 0 2� n / è �
n /2 1, à äëÿ íå÷åòíûõ — ýòè ñîîòíîøåíèÿ
èìåþò âèä � 0 1 2�
( ) /n , �1 è ñïðàâåäëèâû ïðè n � 4.
Âûâîäû
Ïðåäëîæåííàÿ ïðîöåäóðà ïðè ÷èñëå âåðøèí â ãðàôå, íå ïðåâûøàþùåì
125, ïîçâîëÿåò ïåðå÷èñëÿòü ÌÍÌ çà ïîëèíîìèàëüíîå âðåìÿ, à ïðè äîñ-
òàòî÷íî áîëüøèõ çíà÷åíèÿõ n è ìàëûõ ïëîòíîñòÿõ ãðàôîâ èìååò ýêñïîíåí-
öèàëüíóþ ñëîæíîñòü. Äàííàÿ ïðîöåäóðà ðàáîòàåò áîëåå ýôôåêòèâíî, ÷åì
ïðîöåäóðû, îñíîâàííûå íà àëãîðèòìå Áðîíà—Êåðáîøà, òàê êàê ïðîäó-
öèðóåò ñóùåñòâåííî ìåíüøå âñïîìîãàòåëüíûõ ìíîæåñòâ äëÿ ïîñòðîåíèÿ
ÌÍÌ.  àëãîðèòìå Áðîíà—Êåðáîøà ôàêòè÷åñêè ïåðå÷èñëÿþòñÿ ïî÷òè
âñå íåçàâèñèìûå ìíîæåñòâà âåðøèí, ÷èñëî êîòîðûõ, åñòåñòâåííî, ýêñïî-
íåíöèàëüíî áîëüøîå.
Îïèñàííûé àëãîðèòì îñíîâàí íà òîì, ÷òî âñÿêàÿ êëèêà â ãðàôå ÿâ-
ëÿåòñÿ åãî ìàêñèìàëüíûì ïî âêëþ÷åíèþ ïîëíûì ïîäãðàôîì. Íà÷èíàÿ ñ
îäèíî÷íîé âåðøèíû (îáðàçóþùåé ïîëíûé ïîäãðàô), íà êàæäîì øàãå àë-
ãîðèòìà ïðîèñõîäèò óâåëè÷åíèå óæå ïîñòðîåííîãî ïîëíîãî ïîäãðàôà â
ðåçóëüòàòå äîáàâëåíèÿ â íåãî âåðøèíû èç ìíîæåñòâà êàíäèäàòîâ. Êàê
ñëåäóåò èç òàáë. 2 è 3, çàäà÷à ïåðå÷èñëåíèÿ ÌÍÌ ïðè ÷èñëå âåðøèí â
ãðàôå, íå ïðåâûøàþùåì 100, ìîæåò áûòü ðåøåíà â ìàñøòàáå ðåàëüíîãî
âðåìåíè, ÷òî âàæíî äëÿ ñîâðåìåííûõ ñèñòåì óïðàâëåíèÿ, èñïîëüçóåìûõ â
ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Merrifield R.E., Simmons H.E. Topological methods in chemistry. N.Y.: John Wiley & Sons,
1989.
2. Hosoya H. Topological index. A newly proposed quantity characterizing the topological na-
ture of structural isomers of saturated hydrocarbons // Bull. Chem. Soc. Jpn. 1971, 44 (9),
ð. 2332—2339.
3. Miller R.E., Muller D.E. The problem of maximum consistent subsets — IBM Research Re-
port RC-240. 1960. J.T.Watson Research Center, Yorktown Heights, N.Y. Moon J.W.,
Moser L. On cliques in graphs // Israel J. Math. 1965, vol. 3, p. 23—28.
4. Watson T. Research Center, Yorktown Heights, N.Y. Moon J.W., Moser L. On cliques in
graphs // Israel J. Math. 1965, vol. 3, p. 23—28.
5. Harley E., Bonner A., Goodman N. Uniform integration of genome mapping data using in-
tersection graphs // Bioinformatics, 2001, vol. 17, p. 487—494.
6. Moon J. W., Moser L. On cliques in graphs // Israel J. Math, 1965, vol. 3, p. 23—28.
7. Tomita E., Tanaka A., Takahashi H. The worst-case time complexity for generating all maxi-
mal cliques and computational experiments // Theoretical Computer Science, 2006, vol. 363,
p. 28—42.
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 15
8. Prodinger H., Tichy R.F. Fibonacci numbers of graphs // Fibonacci Quart, 1982, 20 (1),
p. 16—21.
9. Listrovoy S.V., Minukhin S.V. General Approach to Solving Optimization Problems in Dis-
tributed Cjmputing Sysntems and Theory of Intelligence Systems Construction // Journal of
automation and information sciences, 2010, vol. 42, N 3, p. 30—46
10. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Îáùèé ïîäõîä ê ðåøåíèþ çàäà÷ îïòèìèçàöèè â ðàñïðå-
äåëåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è òåîðèè ïîñòðîåíèÿ èíòåëëåêòóàëüíûõ ñèñòåì //
Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêà, 2010, ¹2, c. 65—82.
11. Ëèñòðîâîé Ñ.Â. Ìåòîä ïåðå÷èñëåííÿ ìàêñèìàëüíèõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèç-
âîëüíûõ íåîðèåíòèðîâàííûõ ãðàôàõ // Ýëåêòðîí. ìîäåëèðîâàíèå, 2014, 36, ¹ 1, c. 3—17.
12. Listrovoy S.V., Listrovaya E.S., Panchenko S.V., Moiseenko V.I., Kamenev A.U. Mathemati-
cal models in computer control systems RAILWAYS and parallel computing. Kharkiv: FOP
Brovin O., 2017, 300 p.
Ïîñòóïèëà 09.03.17;
ïîñëå äîðàáîòêè 15.06.17
REFERENCES
1. Merrifield, R.E. and Simmons, H.E. (1989), Topological methods in chemistry, New York,
John Wiley & Sons, USA.
2. Hosoya, H. (1971),Topological index. A newly proposed quantity characterizing the topolo-
gical nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., Vol. 44,
no. 9, pp. 2332-2339.
3. Miller, R.E. and Muller, D.E. (1960), The problem of the maximum consistent subsets, IBM
Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, New York,
USA. Moon J.W., Moser L. On cliques in graphs, Israel J. Math.,Vol. 3, p. 23-28.
4. Watson J.T. Research Center, Yorktown Heights, N.Y. Moon J.W., Moser L. On cliques in
graphs, Israel J. Math. Vol. 3, p. 23-28.
5. Harley, E., Bonner, A. and Goodman, N. (2001), Uniform integration of genome mapping
data using intersection graphs, Bioinformatics, Vol. 17, pp. 487-494.
6. Moon, J.W. and Moser, L. (1965), On cliques in graphs, Israel J. Math., Vol. 3, pp. 23-28.
7. Tomita, E., Tanaka, A. and Takahashi, H. (2006), The worst-case time complexity for gene-
rating all maximal cliques and computational experiments, Theoretical Computer Science,
Vol. 363, pp. 28-42.
8. Prodinger, H. and Tichy, R.F. (1982), Fibonacci numbers of graphs, Fibonacci Quart, Vol. 20,
no. 1, pp.16-21.
9. Listrovoy, S.V. and Minukhin, S.V. (2010), General approach to solving optimization prob-
lems in distributed computing systems and theory of intelligence systems construction, Jour-
nal of automation and information sciences, Vol. 42, no. 3, pp. 30-46.
10. Listrovoy, S.V. and Minukhin, S.V. (2010), “A general approach to the solution of optimi-
zation problems in distributed computing systems and the theory of constructing intellectual
systems”, Problemy upravleniya i informatika, no. 2, pp.65-82.
11. Listrovoy, S.V. (2014), “The method of enumeration of maximal independent sets in arbi-
trary non-oriented graphs”, Elektronnoe modelirovanie, Vol. 36, no. 1, pp. 3-17.
12. Listrovoy, S.V., Listrovaya, E.S., Panchenko, S.V., Moiseenko, V.I. and Kamenev, A.U.
(2017), Mathematical models in computer control systems RAILWAYS and parallel com-
puting: Monograph, FOP Brovin O., Kharkiv, Ukraine.
Received 09.03.17;
after revision 15.06.17
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
16 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 4
S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya
METHOD OF ENUMERATION OF MAXIMUM
INDEPENDENT SETS IN NONORIENTED GRAPHS
Based on the rank approach the authors propose a method of enumeration of maximum indepen-
dent sets of nonoriented connected graph with time complexity that does not exceed, at an average,
O (n6), where n is the number of vertices in the graph, for the graphs which do not contain separa-
ting vertices, which dimension does not exceed n=125.
K e y w o r d s: maximal independent set, click, vertex cover.
ËÈÑÒÐÎÂÎÉ Ñåðãåé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð Óêðàèíñêîãî ãîñóäàðñòâåííîãî
óíèâåðñèòåòà æåëåçíîäîðîæíîãî òðàíñïîðòà (ã. Õàðüêîâ).  1972 ã. îêîí÷èë Õàðüêîâñêîå
âûñøåå âîåííîå êîìàíäíî-èíæåíåðíîå ó÷èëèùå. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è
äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì
è ñåòåé.
ÑÈÄÎÐÅÍÊÎ Àíäðåé Âëàäèìèðîâè÷, âåä. èíæåíåð-ïðîãðàììèñò ôèðìû Samsung Electronics
Ukraine Company, LLC Samsung R&D Institute Ukraine (ã. Êèåâ).  2001 ã. îêîí÷èë Õàðüêîâñêèé
âîåííûé óíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è äèñêðåòíîé îïòèìèçàöèè è
òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé.
ËÈÑÒÐÎÂÀß Åëåíà Ñåðãååâíà, êàíä. òåõí. íàóê, äîöåíò êàôåäðû ýêîíîìèêè è ìàðêåòèíãà
Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà èì. Í.Å. Æóêîâñêîãî (ã. Õàðüêîâ), êîòîðûé
îêîí÷èëà â 1998 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ïðèìåíåíèå èíôîðìàöèîííûõ ñèñòåì â
ýêîíîìè÷åñêîé ñôåðå äåÿòåëüíîñòè.
Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ â íåîðèåíòèðîâàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 4 17
|
| id | nasplib_isofts_kiev_ua-123456789-127632 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T13:29:37Z |
| publishDate | 2017 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. 2017-12-24T11:14:28Z 2017-12-24T11:14:28Z 2017 Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/127632 519.682.1 На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125. На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125. Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Метод перечисления максимальных независимых множеств в неориентированных графах Method of enumeration of maximum independent sets in nonoriented graphs Article published earlier |
| spellingShingle | Метод перечисления максимальных независимых множеств в неориентированных графах Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы |
| title | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_alt | Method of enumeration of maximum independent sets in nonoriented graphs |
| title_full | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_fullStr | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_full_unstemmed | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_short | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_sort | метод перечисления максимальных независимых множеств в неориентированных графах |
| topic | Математическое моделирование и вычислительные методы |
| topic_facet | Математическое моделирование и вычислительные методы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/127632 |
| work_keys_str_mv | AT listrovoisv metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT sidorenkoav metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovaâes metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovoisv methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT sidorenkoav methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT listrovaâes methodofenumerationofmaximumindependentsetsinnonorientedgraphs |