Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа
Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное вр...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2017 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/127559 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-127559 |
|---|---|
| record_format |
dspace |
| spelling |
Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. 2017-12-24T09:41:46Z 2017-12-24T09:41:46Z 2017 Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/127559 519.682.1 Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n — число вершин графа. Запропоновано метод пошуку найбільших максимальних незалежних множин неорієнтованого зв’язкового графа, який дозволяє при числі вершин в графі, що не перевищує 120, і щільності ребер у діапазоні від 0,067 до 0,9, вирішувати задачу визначення найбільших максимальних незалежних множин за поліноміальний час. При подальшому збільшенні числа вершин і зменшенні щільності ребер в графі алгоритм має експоненціальну складність, яка має тенденцію до зменшення при збільшенні щільності ребер в графі, де n — число вершин графа. A method of search for the largest maximal independent sets of an undirected connected graph is proposed that allows one to solve the problem of determining the largest maximal independent sets in polynomial time with the number of vertices in the graph not exceeding 120 and the density of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a decrease in the density of edges in the graph, the algorithm has an exponential complexity, which tends to the decrease with increasing the edge density in the graph, where n is the number of vertices in the graph. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа The method of determining the largest maximal independent sets of vertices of undirected graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| spellingShingle |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы |
| title_short |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_full |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_fullStr |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_full_unstemmed |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_sort |
метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| author |
Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_facet |
Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| topic |
Математическое моделирование и вычислительные методы |
| topic_facet |
Математическое моделирование и вычислительные методы |
| publishDate |
2017 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
The method of determining the largest maximal independent sets of vertices of undirected graph |
| description |
Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n — число вершин графа.
Запропоновано метод пошуку найбільших максимальних незалежних множин неорієнтованого зв’язкового графа, який дозволяє при числі вершин в графі, що не перевищує 120, і щільності ребер у діапазоні від 0,067 до 0,9, вирішувати задачу визначення найбільших максимальних незалежних множин за поліноміальний час. При подальшому збільшенні числа вершин і зменшенні щільності ребер в графі алгоритм має експоненціальну складність, яка має тенденцію до зменшення при збільшенні щільності ребер в графі, де n — число вершин графа.
A method of search for the largest maximal independent sets of an undirected connected graph is proposed that allows one to solve the problem of determining the largest maximal independent sets in polynomial time with the number of vertices in the graph not exceeding 120 and the density of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a decrease in the density of edges in the graph, the algorithm has an exponential complexity, which tends to the decrease with increasing the edge density in the graph, where n is the number of vertices in the graph.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/127559 |
| citation_txt |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
| work_keys_str_mv |
AT listrovoisv metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT sidorenkoav metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT listrovaâes metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT listrovoisv themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph AT sidorenkoav themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph AT listrovaâes themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph |
| first_indexed |
2025-11-24T20:24:03Z |
| last_indexed |
2025-11-24T20:24:03Z |
| _version_ |
1850495252160315392 |
| 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)
Ìåòîä ïîèñêà íàèáîëüøèõ
ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ
âåðøèí íåîðèåíòèðîâàííîãî ãðàôà
Ïðåäëîæåí ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ íåîðèåí-
òèðîâàííîãî ñâÿçíîãî ãðàôà, ïîçâîëÿþùèé ïðè ÷èñëå âåðøèí â ãðàôå, íå ïðåâûøàþùåì
120, è ïëîòíîñòÿõ ðåáåð â äèàïàçîíå îò 0,067 äî 0,9, ðåøàòü çàäà÷ó îïðåäåëåíèÿ íàèáîëü-
øèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ çà ïîëèíîìèàëüíîå âðåìÿ. Ïðè äàëüíåéøåì
óâåëè÷åíèè ÷èñëà âåðøèí è óìåíüøåíèè ïëîòíîñòè ðåáåð â ãðàôå àëãîðèòì èìååò ýêñïî-
íåíöèàëüíóþ ñëîæíîñòü, â ñðåäíåì íå ïðåâûøàþùóþO n( ),20 4 , êîòîðàÿ èìååò òåíäåíöèþ
ê óìåíüøåíèþ ïðè óâåëè÷åíèè ïëîòíîñòè ðåáåð â ãðàôå, ãäå n — ÷èñëî âåðøèí ãðàôà.
Ê ë þ ÷ å â û å ñ ë î â à: ìàêñèìàëüíîå íåçàâèñèìîå ìíîæåñòâî, êëèêà, âåðøèííîå ïîêðûòèå.
Çàïðîïîíîâàíî ìåòîä ïîøóêó íàéá³ëüøèõ ìàêñèìàëüíèõ íåçàëåæíèõ ìíîæèí íåîð³ºí-
òîâàíîãî çâ’ÿçêîâîãî ãðàôà, ÿêèé äîçâîëÿº ïðè ÷èñë³ âåðøèí â ãðàô³, ùî íå ïåðåâèùóº
120, ³ ù³ëüíîñò³ ðåáåð ó ä³àïàçîí³ â³ä 0,067 äî 0,9, âèð³øóâàòè çàäà÷ó âèçíà÷åííÿ íàéá³ëü-
øèõ ìàêñèìàëüíèõ íåçàëåæíèõ ìíîæèí çà ïîë³íîì³àëüíèé ÷àñ. Ïðè ïîäàëüøîìó çá³ëü-
øåíí³ ÷èñëà âåðøèí ³ çìåíøåíí³ ù³ëüíîñò³ ðåáåð â ãðàô³ àëãîðèòì ìຠåêñïîíåíö³àëüíó
ñêëàäí³ñòü, ùî â ñåðåäíüîìó íå ïåðåâèùóº O n( ),20 4 , ÿêà ìຠòåíäåíö³þ äî çìåíøåííÿ ïðè
çá³ëüøåíí³ ù³ëüíîñò³ ðåáåð â ãðàô³, äå n — ÷èñëî âåðøèí ãðàôà.
Ê ë þ ÷ î â ³ ñ ë î â à: ìàêñèìàëüíà íåçàëåæíà áåçë³÷, êë³êà, âåðøèííå ïîêðèòòÿ.
Ïîèñê íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ (ÍÌÍÌ) âåð-
øèí íåîðèåíòèðîâàííîãî ãðàôà — îäíà èç âàæíåéøèõ çàäà÷ äèñêðåòíîé
ìàòåìàòèêè. Àëãîðèòìû ðåøåíèÿ ýòîé çàäà÷è èñïîëüçóþòñÿ â øèðîêèõ
ñïåêòðàõ ïðèêëàäíûõ ïðîáëåì, â òîì ÷èñëå â ñîöèîìåòðèè [1], õèìèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 17
� Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ, 2017
[2—4], êîìïüþòåðíûõ òåõíîëîãèÿõ [5—8] è áèîèíôîðìàòèêå [9—15]. Ýòî
îáúÿñíÿåòñÿ òåì, ÷òî, ïðåäñòàâèâ îáúåêò èññëåäîâàíèÿ â âèäå ìîäåëè íà
ãðàôå, ìíîæåñòâî çàäà÷ èç óêàçàííûõ îáëàñòåé íàóêè ìîæíî ñâåñòè ê çàäà-
÷å ïîèñêà êëèêè â íåîðèåíòèðîâàííîì ãðàôå èëè ê çàäà÷å î ìèíèìàëüíîì
âåðøèííîì ïîêðûòèè â ãðàôå, ÷òî, â ñâîþ î÷åðåäü, ëåãêî òðàíñôîðìèðóåòñÿ â
çàäà÷ó íàõîæäåíèÿ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ ãðàôà.
Ïðîáëåìà ïîèñêà íàèìåíüøåãî ïîêðûòèÿ è ñîîòâåòñòâåííî ÍÌÍÌ â
ïðîèçâîëüíîì ãðàôå — îäíà èç ïåðâûõ çàäà÷, âûäåëåííûõ â êàòåãîðèþ NP-
ïîëíûõ [1]. Ñäåëàíî ìíîæåñòâî ïîïûòîê ðàçðàáîòêè ìåòîäîâ, ïîçâîëÿþùèõ
íàéòè òî÷íîå ðåøåíèå çà ïîëèíîìèàëüíîå âðåìÿ. Îäíàêî äî íàñòîÿùåãî
âðåìåíè êàê â òåîðèè, òàê è íà ïðàêòèêå ñóùåñòâóþò ëèøü àëãîðèòìû [2],
äàþùèå ïðèáëèæåííûé ðåçóëüòàò ïðè ïîñòðîåíèíèè òàêîãî âåðøèííîãî ïî-
êðûòèÿ, â êîòîðîì ÷èñëî âåðøèí íå áîëåå ÷åì â k ðàç ïðåâîñõîäèò ìèíè-
ìàëüíî âîçìîæíîå (k — òî÷íîñòü ïðèáëèæåííîãî àëãîðèòìà).
 ïîñëåäíèå ãîäû ïðîáëåìà íàõîæäåíèÿ îïòèìàëüíîãî àëãîðèòìà
ðåøåíèÿ çàäà÷è î íàèìåíüøåì ïîêðûòèè ðàññìàòðèâàëàñü ñ ó÷åòîì ôèê-
ñèðîâàííîé ïàðàìåòðè÷åñêîé ñëîæíîñòè [16].  îñíîâå ïàðàìåòðè÷åñêîãî
ìîäåëèðîâàíèÿ ëåæèò èäåÿ ðàçäåëåíèÿ ïðîáëåìû íà äâå ñîñòàâëÿþùèå. Ñ
îäíîé ñòîðîíû, èìååòñÿ ñîâîêóïíîñòü ìíîæåñòâà âõîäíûõ äàííûõ, à ñ
äðóãîé, — ìíîæåñòâî ðàçëè÷íûõ ïàðàìåòðîâ, òàê èëè èíà÷å âëèÿþùèõ íà
îáùóþ âû÷èñëèòåëüíóþ ñëîæíîñòü èññëåäóåìîãî àëãîðèòìà. Ýòî ïîçâî-
ëÿåò ñôîðìèðîâàòü áîëåå ãèáêóþ êëàññèôèêàöèþ NP-ñëîæíûõ ïðîáëåì
ïî ñðàâíåíèþ ñ êëàññè÷åñêèì ïîäõîäîì, êîãäà ñëîæíîñòü àëãîðèòìà çàâè-
ñèò òîëüêî îò âõîäíîãî ïîòîêà.
Ñ íà÷àëà 50-õ ãîäîâ ïðîøëîãî âåêà áûëî ïðåäëîæåíî ìíîãî òî÷íûõ
àëãîðèòìîâ äëÿ ðåøåíèÿ çàäà÷, ñâÿçàííûõ ñ ïîèñêîì ìàêñèìàëüíûõ íåçà-
âèñèìûõ ìíîæåñòâ [1—20], íî ïîñòðîèòü ýôôåêòèâíûé àëãîðèòì, èìåþ-
ùèé ïîëèíîìèàëüíóþ îöåíêó ñëîæíîñòè, äî ñèõ ïîð íå óäàëîñü. Åñëè äëÿ
ðåøåíèÿ çàäà÷è î ïåðå÷èñëåíèè âñåõ êëèê ãðàôà ðàçðàáîòêà òàêîãî àëãî-
ðèòìà ïðåäñòàâëÿåòñÿ ìàëî âåðîÿòíîé (â ñèëó ýêñïîíåíöèàëüíîé çàâèñè-
ìîñòè ÷èñëà êëèê îò ðàçìåðíîñòè ãðàôà [21]), òî äëÿ ïîèñêà îäíîãî ÍÌÍÌ
íåâîçìîæíîñòü ïîñòðîåíèÿ ïîäîáíîãî àëãîðèòìà îñòàåòñÿ íåäîêàçàííîé â
ñèëó íåðåøåííîé ïðîáëåìû âçàèìîñâÿçè êëàññîâ P è NP. Ýòî ïîçâîëÿåò
íàäåÿòüñÿ íà âîçìîæíîñòü ñîçäàíèÿ ïîëèíîìèàëüíîãî àëãîðèòìà äëÿ ðå-
øåíèÿ äàííîé çàäà÷è.
Èñõîäÿ èç òîãî, ÷òî âñå ýòè àëãîðèòìû èìåþò ýêñïîíåíöèàëüíóþ îöåíêó
ñëîæíîñòè O n( )2� , ðàçðàáîò÷èêè ñòàðàþòñÿ ìîäèôèöèðîâàòü ñâîè àëãîðèò-
ìû ñ öåëüþ ñîêðàùåíèÿ äåðåâà ïîèñêà, ÷òî, â ñâîþ î÷åðåäü, ïðèâîäèò ê óìåíü-
øåíèþ ïîêàçàòåëÿ �. Íàèáîëåå ïîëíûé îáçîð àëãîðèòìîâ ðåøåíèÿ äàííîé
çàäà÷è ñäåëàí â ðàáîòå [22], â êîòîðîé ïîäðîáíî îïèñàíà èñòîðèÿ ðàçâèòèÿ
àëãîðèòìîâ ïîèñêà ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
18 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
 îáùåì ñëó÷àå âñå àëãîðèòìû ðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì íåçà-
âèñèìîì ìíîæåñòâå ìîæíî ðàçäåëèòü íà äâå ãðóïïû: àëãîðèòìû ïåðå÷èñ-
ëåíèÿ âñåõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ è àëãîðèòìû îïðåäå-
ëåíèÿ ÍÌÍÌ. Ñðåäè àëãîðèòìîâ íàõîæäåíèÿ ÍÌÍÌ ìîæíî âûäåëèòü
àëãîðèòìû Ðîáñîíà [19] ñ âðåìåííîé ñëîæíîñòüþ O (2 0,276n ) è àëãîðèòì
MaxIS [23] è Ïëîòíèêîâà [24], ïîçâîëèâøèå óëó÷øèòü âðåìåííûå õàðàê-
òåðèñòèêè àëãîðèòìà Ðîáñîíà.
Ðàññìîòðèì ýôôåêòèâíûé àëãîðèòì ïîèñêà ÍÌÍÌ è ïåðå÷èñëåíèÿ
ÍÌÍÌ íåîðèåíòèðîâàííîãî ãðàôà.
Îñíîâíûå ïîíÿòèÿ è îïðåäåëåíèÿ. Âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ
ñèíòåçà è àíàëèçà âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé, à òàêæå ïðè ðàçðàáîòêå
ñïåöèàëüíîãî ìàòåìàòè÷åñêîãî îáåñïå÷åíèÿ äëÿ èõ ôóíêöèîíèðîâàíèÿ
òðåáóåòñÿ íàéòè â êîíå÷íîì ìíîæåñòâå îáúåêòîâ ìàêñèìàëüíóþ ñèñòåìó
îáúåêòîâ, ïîïàðíî íå ñâÿçàííûõ äðóã ñ äðóãîì, èëè âûáðàòü ìèíèìàëüíóþ
ñèñòåìó îáúåêòîâ, ñâÿçàííûõ ñî âñåìè äðóãèìè. Ôîðìóëèðîâêè ïîäîáíûõ
çàäà÷ íà ÿçûêå òåîðèè ãðàôîâ ïðèâîäÿò ê ïîíÿòèÿì íåçàâèñèìîñòè è
ïîêðûòèÿ.
Ìíîæåñòâî âåðøèí U ãðàôà G V E( , ) íàçûâàåòñÿ íåçàâèñèìûì (âíóò-
ðåííå óñòîé÷èâûì), åñëè íèêàêèå äâå âåðøèíû èç ýòîãî ìíîæåñòâà íå
ñìåæíûå, ò.å. åñëèU V� è U íåçàâèñèìî â ãðàôå G, òî ïîðîæäåííûé ïîä-
ãðàô G (U) ÿâëÿåòñÿ ïóñòûì. Î÷åâèäíî, ÷òî åñëè ïðè ýòîìU U* � , òî U* —
òàêæå íåçàâèñèìîå ìíîæåñòâî. Âíóòðåííå óñòîé÷èâîå ìíîæåñòâî íàçû-
âàåòñÿ ìàêñèìàëüíûì, åñëè îíî íå ÿâëÿåòñÿ ñîáñòâåííûì ïîäìíîæåñòâîì
íåêîòîðîãî äðóãîãî íåçàâèñèìîãî ìíîæåñòâà.
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: X i
r — ìíîæåñòâî íåçàâèñèìûõ âåð-
øèí ãðàôà G V E( , ), ìîùíîñòü êîòîðîãî ðàâíà r; Yi
k — ìíîæåñòâî âåðøèí,
ñ êîòîðûìè ñâÿçàíû âåðøèíû, ïðèíàäëåæàùèå i-ìó íåçàâèñèìîìó ìíî-
æåñòâó X i
r .
Ðàññìîòðèì ìíîæåñòâî � âñåõ ïàð íåçàâèñèìûõ X i
r�2 âåðøèí â ãðàôå
G V E( , ) è ìíîæåñòâî âåðøèí Yi
k , ñîñòîÿùåå èç k âåðøèí, ñ êîòîðûìè
ñâÿçàíû âåðøèíû èç X i
r�2 â ãðàôå G V E( , ). Ìîùíîñòü ìíîæåñòâà � îáîç-
íà÷èì �� | |� . Ìíîæåñòâà X i
r ìàêñèìàëüíîé ìîùíîñòè ìîãóò áûòü ïîñò-
ðîåíû èç èñõîäíîãî ãðàôà G V E( , ) ïîñðåäñòâîì îáúåäèíåíèÿ âñåõ ïàð
âåðøèí, êîòîðûå â ãðàôå 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� , òî
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 19
î÷åâèäíî, ñóùåñòâóþò âåðøèíû, êîòîðûå ìîæíî äîáàâèòü â ïîäìíîæåñòâî
X i
r è îíî îñòàíåòñÿ íåçàâèñèìûì, è ÷èñëî òàêèõ âåðøèí íå ïðåâîñõîäèò n –
r. Åñëè X Y Vi
r
i
k� � , òî òàêèõ âåðøèí â ãðàôå G V E( , ) íå ñóùåñòâóåò.
Âàæíîé õàðàêòåðèñòèêîé àíàëèçèðóåìûõ ãðàôîâ ÿâëÿåòñÿ ïëîòíîñòü
ðåáåð m â ãðàôå G V E( , ). Ïîä ïëîòíîñòüþ ðåáåð ãðàôà áóäåì ïîíèìàòü
îòíîøåíèå
� m E/ max , ãäå m — ÷èñëî ðåáåð â ãðàôå G V E( , ), E max �
�
�n n( )1
2
— ìàêñèìàëüíî âîçìîæíîå ÷èñëî ðåáåð â ãðàôå G V E( , ), ñî-
äåðæàùåì n âåðøèí.
Ôîðìàëèçàöèÿ è ïîñòàíîâêà çàäà÷è.  êà÷åñòâå èñõîäíûõ äàííûõ
äëÿ ðàáîòû àëãîðèòìà áóäåì èñïîëüçîâàòü âñå ïàðû íåçàâèñèìûõ X i
r�2
âåðøèí â ãðàôå G V E( , ). Ïðè ýòîì, åñëè åñòü ïîäìíîæåñòâà( | ),X Yi
r
i
k
( | ) ...( | )X Y X Yj
r
j
k
p
r
p
k , ÿâëÿþùèåñÿ ìàêñèìàëüíûìè, òî â ìíîæåñòâî U çàíî-
ñèì íàèáîëüøèå ïî ìîùíîñòè ìàêñèìàëüíûå íåçàâèñèìûå ìíîæåñòâà.
Ñëåäóåò çàìåòèòü, ÷òî ïðè âíåñåíèè íîâûõ ìíîæåñòâ â U äóáëèðóþùèå
ìíîæåñòâà óäàëÿþòñÿ è â ìíîæåñòâå U îñòàþòñÿ òîëüêî ìíîæåñòâà ìàê-
ñèìàëüíîé ìîùíîñòè. Åñëè ìíîæåñòâî ( | )X Yi
r
i
k ÿâëÿåòñÿ ìàêñèìàëüíûì,
òî áóäåì ïîìå÷àòü åãî îäíîé çâåçäî÷êîé. Ðàññìîòðèì ñëåäóþùóþ ïðîöå-
äóðó À0 äëÿ ïåðå÷èñëåíèÿ ÍÌÍÌ íà îñíîâå ââåäåííûõ ïðàâèë ïðåîáðà-
çîâàíèÿ ìíîæåñòâ.
Ïðîöåäóðà À0.
Ø à ã 1. Ôîðìèðóåì ìíîæåñòâî � âñåõ ïàð íåçàâèñèìûõ ìíîæåñòâ
( | )X Yi
r
i
k�2 âåðøèí â ãðàôå G V E( , ) è ïðîâåðÿåì, åñòü ëè ñðåäè íèõ ìíî-
æåñòâà, ÿâëÿþùèåñÿ ìàêñèìàëüíûìè íåçàâèñèìûìè, è åñëè åñòü, òî çàíî-
ñèì èõ â ìíîæåñòâî U, èñêëþ÷àÿ èõ èç ìíîæåñòâà �.
Ø à ã 2. Âûáèðàåì èç � ìíîæåñòâî Q X Yi t
r
i t
k� � �( | ) è íà åãî îñíîâå
íà÷èíàåì ôîðìèðîâàòü ÍÌÍÌ. Äëÿ ýòîãî â îñòàâøèõñÿ ìíîæåñòâàõ â �
óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå âûáðàííûì ìíîæåñòâàì X t
r è Yt
k , è
ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 3. Ïðîâåðÿåì âñå ëè ìíîæåñòâà â � ñòàëè ïóñòûìè. Åñëè äà, òî
äîñòðîèòü ìíîæåñòâî ( | )X Yt
r
t
k äî ìàêñèìàëüíîãî íåëüçÿ, ïîýòîìó äàííîå
ìíîæåñòâî èñêëþ÷àåì èç äàëüíåéøåãî àíàëèçà è ïåðåõîäèì ê âûïîë-
íåíèþ øàãà 2, èíà÷å ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 4. Â � ïîñëå óäàëåíèÿ âåðøèí, ïðèíàäëåæàùèõ ìíîæåñòâàì X t
r
è Yt
k âûáðàííîãî ìíîæåñòâà, âûáèðàåì ìíîæåñòâî ( | )X Yi q
r
i q
k
� � ñ ìàêñè-
ìàëüíûì çíà÷åíèåì | |X i q
r
� . Åñëè òàêèõ ìíîæåñòâ íåñêîëüêî, òî ôîðìèðóåì
îáúåäèíåíèåQ X Xi
r
i q
r� � � è ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 5. Ïðîâåðÿåì, ÿâëÿåòñÿ ëè Q ìàêñèìàëüíûì íåçàâèñèìûì ìíî-
æåñòâîì. Åñëè íåò, òî ïåðåõîäèì ê âûïîëíåíèþ øàãà 2, èíà÷å — çàíîñèì
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
20 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
åãî â ìíîæåñòâî U . Ïðè ýòîì â ìíîæåñòâå U îñòàâëÿåì òîëüêî ìíîæåñòâà ñ
ìàêñèìàëüíîé ìîùíîñòüþ è ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 6. Ïðîâåðÿåì íà îñíîâå âñåõ ìíîæåñòâ èç �, ñôîðìèðîâàíû ëè
ìàêñèìàëüíûå íåçàâèñèìûå ìíîæåñòâà. Åñëè íåò, òî ïåðåõîäèì ê âûïîë-
íåíèþ øàãà 2, èíà÷å — ïðîöåäóðà çàêàí÷èâàåò ðàáîòó, òàê êàê ìíîæåñòâà,
ñîäåðæàùèåñÿ â U, îáðàçóþò ÍÌÍÌ èññëåäóåìîãî ãðàôà.
Äëÿ óäîáñòâà ïðîãðàììíîé ðåàëèçàöèè ïðîöåäóðû À0 åå óäîáíî ïðåä-
ñòàâèòü â âèäå äâóõ âçàèìîñâÿçàííûõ ïðîöåäóð: À è F (Q) (ðèñ. 1).
 ïðîöåäóðå À áëîêè 1, 2 ôîðìèðóþò ìíîæåñòâî �, ñîñòîÿùåå èç ïàð
X |Y; áëîê 3 ñîîòâåòñòâóåò îðãàíèçàöèè öèêëà ïåðåáîðà âñåõ ïàð X | Y èç �,
íà îñíîâå êîòîðûõ ñòðîÿòñÿ ÍÌÍÌ ñ çàïóñêîì ðàáîòû ïðîöåäóðû F (Q);
áëîêè 5—8 ðåàëèçóþò ïðîöåññ ôîðìèðîâàíèÿ ìíîæåñòâà U.
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 21
Ðèñ. 1. Áëîê-ñõåìû ïðîöåäóð À è F (Q)
 ïðîöåäóðå F (Q) áëîêè 1, 2 ðåàëèçóþò âûáîð ïàðûQ X Y� ( | )èç âñåõ
ïàð ìíîæåñòâà � è óäàëåíèå âåðøèí {vi}, ïðèíàäëåæàùèõ ìíîæåñòâàì X
è Y èç âñåõ ïàð X Y| �� ; áëîêè 3—6 ðåàëèçóþò öèêë äî òåõ ïîð, ïîêà íå
áóäóò ïðîàíàëèçèðîâàíû âñå ïàðû X | Y è âûïîëíåíî ðàâåíñòâî � =
, ò.å.
äî òîãî ìîìåíòà, êîãäà ìíîæåñòâî ñòàíåò ïóñòûì, � =
, à ìíîæåñòâà Q
íå ìîãóò ñòàòü ìàêñèìàëüíûìè, ò.å. X Y V� ; áëîê 7 âîçâðàùàåò ìíî-
æåñòâî Q â ðàáîòó ïðîöåäóðû À.
Ïðèìåð ðàáîòû ïðîöåäóðû À0. Ïóñòü çàäàí ãðàô G V E( , ) ñ íàáîðîì
âåðøèí i è èõ ñâÿçåé ñ îñòàëüíûìè âåðøèíàìè {j} (òàáë. 1). Ôîðìèðóåì
ìíîæåñòâî � (òàáë. 2). Ìàêñèìàëüíûå ìíîæåñòâà âíîñèì â ìíîæåñòâî
U �{ ; ; }67 38 18 è óäàëÿåì èõ èç òàáë. 2. Çàòåì ôîðìèðóåì ìíîæåñòâà, íà÷è-
íàÿ ñ Q = 23 | 1568, êîòîðîå â òàáë. 3 ïîìå÷åíî äâóìÿ çâåçäî÷êàìè. Äëÿ
ýòîãî óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 23 | 1568, è ïîëó-
÷àåì òàáë. 4.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
22 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
Ãðàô G (V, E)
i 1 2 3 4 5 6 7 8
{j} 3 6 7 5 6 8 1 5 6 6 8 2 3 6 7 8 1 2 3 4 5 8 1 5 8 2 4 5 6 7
Òàáëèöà 1
Ìíîæåñòâî ïàð X Yi
r
i
k�2 | ìíîæåñòâà P
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
67 | 123 458* 38 | 124 567* 18 | 234 567*
Òàáëèöà 2
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568** 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 3
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 2, 3, 5, 6, 8 èç ìíîæåñòâ â òàáë. 3
7 |
4 |
7 |
47 |
4 |
4 |
4 |
Òàáëèöà 4
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè, 47 |
, è ôîðìèðóåì ìíî-
æåñòâà Q = 23 | 1568 � 47 |
= 2347 | 1568* è U = {2347}. Çàòåì ôîðìèðóåì
ìíîæåñòâà, íà÷èíàÿ ñ Q = 27 | 1568, êîòîðîå â òàáë. 5 ïîìå÷åíî äâóìÿ
çâåçäî÷êàìè. Óäàëÿÿ âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 27 | 1568,
ïîëó÷àåì òàáë. 6.
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè, 34 |
, è ôîðìèðóåì ìíî-
æåñòâà Q = 27 | 1568 � 34 |
= 2347 | 1568* èU �{ }2347 . Äàëåå ôîðìèðóåì
ìíîæåñòâà, íà÷èíàÿ ñ Q = 34 | 1568, êîòîðîå â òàáë. 7 ïîìå÷åíî äâóìÿ çâåçäî÷-
êàìè. Äëÿ ýòîãî óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 34 | 1568,
è ïîëó÷àåì òàáë. 8.
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 23
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568** 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 7
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 3, 4, 5, 6, 8 èç ìíîæåñòâ â òàáë. 7
2 |
27 |
7 |
7 |
4 |
2 |
4 |
2 |
Òàáëèöà 8
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 2, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 5
3 |
34 |
3 |
4 |
4 |
4 |
4 |
Òàáëèöà 6
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568** 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 5
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà P
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568** 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 9
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè, 27 |
, è ôîðìèðóåì ìíî-
æåñòâà Q = 34|1568 � 27 |
= 2347 | 1568* èU �{ }2347 . Äàëåå ôîðìèðóåì
ìíîæåñòâà, íà÷èíàÿ ñ Q = 37 | 1568, êîòîðîå â òàáë. 9 ïîìå÷åíî äâóìÿ
çâåçäî÷êàìè. Äëÿ ýòîãî óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q =
= 37 | 1568, è ïîëó÷àåì òàáë. 10.
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè, 24 |
, è ôîðìèðóåì ìíî-
æåñòâà Q = 37 | 1568 � 24 |
= 2347 | 1568* èU �{ }2347 . Çàòåì ôîðìèðóåì
ìíîæåñòâà, íà÷èíàÿ ñ Q = 47 | 1568, êîòîðîå â òàáë. 11 ïîìå÷åíî äâóìÿ
çâåçäî÷êàìè. Óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 47 | 1 568,
è ïîëó÷àåì òàáë. 12.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
24 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568**
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 11
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 4, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 11
23 |
2 |
3 |
3 |
2 |
2 |
Òàáëèöà 12
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 3, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 9
2 |
2 |
4 |
4 |
4 |
2 |
4 |
24 |
Òàáëèöà 10
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678** 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 13
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 2, 3, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 13
4 |
4 |
4 |
4 |
4 |
Òàáëèöà 14
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè, 23 |
, è ôîðìèðóåì ìíî-
æåñòâà Q = 47 | 1568 � 23 |
= 2347 | 1568* èU �{ }2347 . Çàòåì ôîðìèðóåì
ìíîæåñòâà, íà÷èíàÿ ñ Q = 15 | 23678, êîòîðîå â òàáë. 13 ïîìå÷åíî äâóìÿ
çâåçäî÷êàìè. Óäàëÿåì âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 15 | 23678, è
ïîëó÷àåì òàáë. 14.
Âûáèðàåì ìíîæåñòâî 4 |
è ôîðìèðóåì ìíîæåñòâà Q = 115 | 23678 �
� 4 |
= 145 | 23678* è U �{ }2347 . Äàëåå ôîðìèðóåì ìíîæåñòâà, íà÷èíàÿ
ñ Q = 45 | 23678, êîòîðîå â òàáë. 15 ïîìå÷åíî äâóìÿ çâåçäî÷êàìè. Óäàëÿåì
âåðøèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 45 | 23678, è ïîëó÷àåì òàáë. 16.
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 25
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678** 12 | 35 678 14 | 3 678 24 | 568
Òàáëèöà 15
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 2, 3, 4, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 15
1 |
1 |
1 |
Òàáëèöà 16
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 2, 3, 5, 6, 7, 8 èç ìíîæåñòâ â òàáë. 17
4 |
4 |
4 |
4 |
Òàáëèöà 18
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678** 14 | 3 678 24 | 568
Òàáëèöà 17
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678** 24 | 568
Òàáëèöà 19
Âûáèðàåì ìíîæåñòâî 1 |
è ôîðìèðóåì ìíîæåñòâà Q = 45 | 23678 � ��
�
= 145 | 23678* èU �{ }2347 . Ôîðìèðóåì ìíîæåñòâà, íà÷èíàÿ ñ Q = 12 | 35678,
êîòîðîå â òàáë. 17 ïîìå÷åíî äâóìÿ çâåçäî÷êàìè. Óäàëÿåì âåðøèíû, ïðè-
íàäëåæàùèå ìíîæåñòâó Q = 12 | 35678, è ïîëó÷àåì òàáë. 18.
Èç îñòàâøåãîñÿ ìíîæåñòâà 4 |
ôîðìèðóåì ìíîæåñòâà Q = 12 | 35678 �
� 4 |
= 124 | 23678* èU �{ }2347 . Äàëåå ôîðìèðóåì ìíîæåñòâà, íà÷èíàÿ ñ
Q = 14 | 3678, êîòîðîå â òàáë. 19 ïîìå÷åíî äâóìÿ çâåçäî÷êàìè. Óäàëÿåì âåð-
øèíû, ïðèíàäëåæàùèå ìíîæåñòâó Q = 14 | 3678, è ïîëó÷àåì òàáë. 20.
Âûáèðàåì ìíîæåñòâî 2 | 5 è ôîðìèðóåì ìíîæåñòâà Q = 14 |3678 � 2 | 5 =
= 124 | 235678* è U �{ }2347 . Äàëåå ôîðìèðóåì ìíîæåñòâà, íà÷èíàÿ ñ Q =
= 24 | 568, êîòîðîå â òàáë. 21 ïîìå÷åíî äâóìÿ çâåçäî÷êàìè. Óäàëÿåì âåðøèíû,
ïðèíàäëåæàùèå ìíîæåñòâó Q = 24 | 568, è ïîëó÷àåì òàáë. 22.
Âûáèðàåì ìíîæåñòâî áîëüøåé ìîùíîñòè 37 | 15 è ôîðìèðóåì ìíî-
æåñòâà Q = 24 | 568 � 37 | 15 = 2347 | 1568* èU �{ }2347 .
Ìàêñèìàëüíûå ìíîæåñòâà ïîñòðîåíû íà îñíîâå âñåõ ìíîæåñòâ �,
ïðèâåäåííûõ â òàáë. 2, è ïðè ýòîì îñòàëîñü îäíî ìíîæåñòâî { }2347 .
Ñëåäîâàòåëüíî, ÷èñëî ìàêñèìàëüíûõ ìíîæåñòâ â àíàëèçèðóåìîì ãðàôå —
îäíî. Ðåøåíèå çàäà÷è äëÿ ãðàôà, çàäàííîãî òàáë. 1, ìåòîäîì, ïåðå÷èñëÿþùèì
âñå ìàêñèìàëüíûå íåçàâèñèìûå ìíîæåñòâà [25], äàëî ñëåäóþùèé ðåçóëü-
òàò:{2347;145; 67; 38; 18}, ÷òî ïîäòâåðæäàåò âåðíîñòü ïðîöåäóðû À0.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
26 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 1, 3, 4, 6, 7, 8 èç ìíîæåñòâ â òàáë. 19
2 | 5 2 | 5
5 | 2 5 | 2 2 | 5
2 | 5
Òàáëèöà 20
Ìíîæåñòâî ïàð X Yi
r
i
k| ìíîæåñòâà �
23 | 1 568 27 | 1 568 34 | 1 568 37 | 1 568 47 | 1 568
15 | 23 678 45 | 23 678 12 | 35 678 14 | 3 678 24 | 568**
Òàáëèöà 21
Ìíîæåñòâî ïàð X Yi
r
i
k| ïîñëå óäàëåíèÿ âåðøèí 2, 4, 5, 6, 8 èç ìíîæåñòâ â òàáë. 21
3 | 15 7 | 1 3 | 15 37 | 15 7 | 15
1 | 37
1 | 37 1 | 37
Òàáëèöà 22
Îöåíêà ñëîæíîñòè ðàáîòû ïðîöåäóðû À0 è åå ýêñïåðèìåíòàëüíîå
èññëåäîâàíèå. Ïîñêîëüêó èñõîäíûìè äàííûìè äëÿ ðàáîòû ïðîöåäóðû
ÿâëÿþòñÿ âñå ïàðû íåçàâèñèìûõ âåðøèí â àíàëèçèðóåìîì ãðàôå, ïðåä-
ñòàâëÿåò èíòåðåñ îöåíèòü èõ ÷èñëî äëÿ âñåõ ïðîèçâîëüíûõ íåîðèåíòèðî-
âàííûõ ãðàôîâ, ìîùíîñòü �� | |� , ãäå � — ìíîæåñòâà âñåõ ïàð X i
r�2
íåçàâèñèìûõ âåðøèí â ãðàôå G V E( , ). Ïîêàæåì, ÷òî ñïðàâåäëèâî ñëåäóþ-
ùåå ñîîòíîøåíèå:
� �
� E max ( ), (1)
ãäå �
( ) � �1 . ßñíî, ÷òî ÷èñëî � íåñâÿçàííûõ ïàð X i
r�2 âåðøèí â ãðàôå
ðàâíî ÷èñëó ðåáåð â ãðàôå, ÿâëÿþùåìñÿ äîïîëíåíèåì G ãðàôà G V E( , ), â
êîòîðîì âåðøèíû ñîåäèíåíû ðåáðàìè, åñëè îíè íå ñîåäèíåíû â ãðàôå
G V E( , ). Åñëè â ãðàôå G V E( , ) ñîäåðæèòñÿ m ðåáåð, òî ñïðàâåäëèâî ðà-
âåíñòâî
� � � �
� � �
� � �
�
�
�
�
� �E m E
m
E
E Emax max
max
max max( ( )1 1 ,
÷òî è òðåáîâàëîñü ïîêàçàòü.  îáùåì ñëó÷àå ñëîæíîñòü ðàáîòû ïðîöåäóðû
À0 îïðåäåëÿåòñÿ ýòàïîì âûïîëíåíèÿ ïîî÷åðåäíîãî ïîñòðîåíèÿ ìàêñèìàëü-
íûõ íåçàâèñèìûõ ìíîæåñòâ íà îñíîâå êàæäîãî èç îñòàâøèõñÿ ìíîæåñòâ
{ | }X Yi
r
i
k , ÷èñëî êîòîðûõ íå ìîæåò ïðåâûøàòü � �
� E max ( ). Ïðè ýòîì ôîð-
ìèðîâàíèå ìíîæåñòâ îñóùåñòâëÿåòñÿ ðåêóðñèâíî ñ âûáîðîì êàæäûé ðàç
íàèáîëüøåãî ïî ìîùíîñòè ìíîæåñòâà.
Äëÿ èíòåðïðåòàöèè ðàáîòû ïðîöåäóðû À0 âîñïîëüçóåìñÿ ïðåäñòàâ-
ëåíèåì èñõîäíîãî ãðàôà G â âèäå ñèììåòðè÷íîãî äåðåâà ïóòåé, ïðåäëî-
æåííîãî â ðàáîòàõ [26, 27], â êîòîðûõ ïîäðîáíî ðàññìîòðåíû èäåè ðàíãî-
âîãî ïîäõîäà ê ðåøåíèþ çàäà÷ òåîðèè ãðàôîâ è äèñêðåòíîé îïòèìèçàöèè.
Ñìûñë òàêîãî ïðåäñòàâëåíèÿ çàêëþ÷àåòñÿ â ñëåäóþùåì. Âìåñòî ãðàôà
G V E( , ) ñ n âåðøèíàìè áóäåì ðàññìàòðèâàòü ãðàô D (ðèñ. 2). Ýòîò ãðàô ñ
(n – 1)2 âåðøèíàìè ïîçâîëÿåò ðàññìîòðåòü âîçìîæíîñòü äîñòèæåíèÿ âåð-
øèíû i â ãðàôå G V E( , ) ïóòÿìè ðàíãà r = 1, ò.å. èñïîëüçóÿ îäíî ðåáðî,
ïóòÿìè ðàíãà r = 2, èñïîëüçóÿ äâà ðåáðà, ïóòÿìè ðàíãà r = n – 1, èñïîëüçóÿ
n – 1 ðåáðî.
 ðàáîòàõ [26, 27] ãðàô D íàçâàí ñòÿíóòûì äåðåâîì âñåõ ïóòåé ãðàôà
G V E( , ). Äåðåâî âñåõ ïóòåé D ñîäåðæèò (n – 1) ãîðèçîíòàëüíóþ ëèíåéêó è
(n – 1) ÿðóñ. Äëÿ ïðî÷òåíèÿ ïóòåé íà êàæäîé ãîðèçîíòàëüíîé ëèíåéêå ìîæ-
íî áûòü òîëüêî îäèí ðàç. Èñõîäÿ èç ñòÿíóòîãî äåðåâà ïóòåé, äëÿ ïðîèç-
âîëüíîé âåðøèíû j ìíîæåñòâî ïóòåé, âåäóùèõ â ýòó âåðøèíó èç íåêîòî-
ðîé âåðøèíû s, ìîæíî ïðåäñòàâèòü â ñëåäóþùåì âèäå:
m j m m ms sj
r
sj
r
sj
r n( ) ...� � � �� � � �1 2 1; j n� �( , )1 1 , (2)
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 27
ãäå msj
r
sj
r�{ }� — ïîäìíîæåñòâà ïóòåé èç ïðîèçâîëüíîé âåðøèíû s â íåêî-
òîðóþ âåðøèíó j ãðàôà G V E( , ) ðàíãà r.
Ñëåäóåò çàìåòèòü, ÷òî äåðåâî âñåõ ïóòåé D ìîæåò áûòü ïîñòðîåíî è îò
êîíêðåòíîé âåðøèíû i ãðàôà.  ýòîì ñëó÷àå âåðøèíà s = i è i-ÿ ãîðè-
çîíòàëüíàÿ ëèíåéêà èñêëþ÷àþòñÿ â D. Íàïðèìåð, ïðè i = 2 äåðåâî D áóäåò
èìåòü âèä, ïðåäñòàâëåííûé íà ðèñ. 3. Êàæäîé âåðøèíå â ãðàôå D ïîñòàâèì
â ñîîòâåòñòâèå ïàðó ( | )X Yi
r
i
k . Ïîñêîëüêó ìîùíîñòü ìíîæåñòâà Ð âñåõ ïàð
ðàâíà �, îáùåå ÷èñëî âåðøèí n â òàêîì ãðàôå D áóäåò ðàâíî �.
Åñëè ðàññìàòðèâàòü äâå ïàðû âåðøèí, ( | )X Yi
r
i
k è ( | )X Yj
r
j
k�1 , ðàñïî-
ëîæåííûõ ñîîòâåòñòâåííî íà ÿðóñàõ r è r + 1 ãðàôà D, òî ðåáðî, ñîåäèíÿþ-
ùåå ýòó ïàðó âåðøèí â ãðàôå D, áóäåò ñóùåñòâîâàòü òîãäà è òîëüêî òîãäà,
åñëè îáúåäèíåíèå X Xi
r
j
r� �1 îáðàçóåò íåçàâèñèìîå ìíîæåñòâî âåðøèí. Ïðè
ýòîì áóäåì ïîëàãàòü, ÷òî âåðøèíû i è j óäîâëåòâîðÿþò ñâîéñòâó �.
Åñëè â ãðàôå D âûäåëèòü ïóòü � ip
r q
i
r
i
k
j
r
j
k
p
r q
p
kX Y X Y X Y� �� ( | ) ( | )...( | ) ðàí-
ãà r = h èç âåðøèíû i â âåðøèíó p, òî äëèíó ýòîãî ïóòè d ip
r q( )� � áóäåì õàðàê-
òåðèçîâàòü ìîùíîñòüþ ìíîæåñòâà íåçàâèñèìûõ âåðøèí X X Xi
r
j
r
p
r� � �... ,
õàðàêòåðèçóþùèõ äàííûé ïóòü â ãðàôå D.
Òàêèì îáðàçîì, çàäà÷ó íàõîæäåíèÿ ÍÌÍÌ ìîæíî ðàññìàòðèâàòü êàê
çàäà÷ó îïðåäåëåíèÿ ñàìîãî äëèííîãî ïóòè d max â ãðàôå D, à çàäà÷ó ïåðå-
÷èñëåíèÿ âñåõ ÍÌÍÌ — êàê çàäà÷ó ïåðå÷èñëåíèÿ âñåõ ïóòåé äëèíû d max â
ãðàôå D. Ðåøåíèå äàííîé çàäà÷è ìîæåò áûòü ðåàëèçîâàíî ïîñðåäñòâîì
ôîðìèðîâàíèÿ ïóòåé â ãðàôå D íà îñíîâå ñëåäóþùåãî ðåêóððåíòíîãî
ñîîòíîøåíèÿ:
� �sp
r
sj
r j p� � �1 { } ( , )}max , j � ( , )1 � , p � ( , )1 � , j p , (3)
ãäå { }max�sj
r — ïóòü ìàêñèìàëüíîé äëèíû, âûäåëåííûé íà r-ì ÿðóñå, ò.å.
ñôîðìèðîâàííîå íà òåêóùèé ìîìåíò íåçàâèñèìîå ìíîæåñòâî âåðøèí ìàê-
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
28 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
s
n n n n
1 1 1 1
2 2 2 2
r = r = r = n r = n1 2 2 . . . . . . 1� �
Ðèñ. 2. Ñòÿíóòîå äåðåâî âñåõ ïóòåé D ãðà-
ôà G (V, E)
s = 2
n n n n
1 1 1 1
3 3 3 3
r = r = r = n r = n1 2 2 . . . . . 1� �
Ðèñ. 3. Ñòÿíóòîå äåðåâî âñåõ ïóòåé D ãðà-
ôà G (V, E) îò âåðøèíû s = 2
ñèìàëüíîé ìîùíîñòè; (j, p) — ðåáðî ãðàôà D, åñëè âåðøèíû j, p óäîâëåò-
âîðÿþò ñâîéñòâó �; � — ÷èñëî ðàçëè÷íûõ âåðøèí â ãðàôå D.
Ôàêòè÷åñêè ðàáîòà ïðîöåäóðû À0 çàêëþ÷àåòñÿ â ïîî÷åðåäíîì íà-
õîæäåíèè ïóòåé ìàêñèìàëüíîé äëèíû â ãðàôå D îò âåðøèí s = (1, 2, ..., �)
êî âñåì îñòàëüíûì âåðøèíàì ãðàôà íà îñíîâå ðåêóððåíòíîãî ñîîòíî-
øåíèÿ (3). Ïðè ôîðìèðîâàíèè ïóòåé �sp
r�1 ñëåäóþùåãî ðàíãà r + 1 íà îñíîâå
ïóòåé �sj
r â ãðàôå D íà êàæäîì øàãå èõ ôîðìèðîâàíèÿ óäàëÿþòñÿ âñå âåð-
øèíû, óæå âîøåäøèå â ïóòü �sj
r , ÷òî ñîîòâåòñòâóåò øàãó 2 ïðîöåäóðû À0 .
Òàêàÿ èíòåðïðåòàöèÿ ðàáîòû ïðîöåäóðû À0 ïîçâîëÿåò ïîëó÷èòü
îöåíêó ñâåðõó åå âðåìåííîé ñëîæíîñòè, òàê êàê íà êàæäîì ÿðóñå â ëþáîì
ïîäìíîæåñòâå msj
r ïðîöåäóðà À0, â ñëó÷àå âûäåëåíèÿ òîëüêî îäíîãî ýêñòðå-
ìàëüíîãî ïóòè íà ÿðóñå, ñòðîèò íå áîëåå îäíîãî ïóòè, à íà ñëåäóþùåì
ÿðóñå — ñîîòâåòñòâåííî íå áîëåå � ïóòåé. Ïîñêîëüêó ÷èñëî ÿðóñîâ â
ãðàôå D íå ìîæåò ïðåâîñõîäèòü (� – 1), îáùåå ÷èñëî ïóòåé, ïîñòðîåííîå
ïðîöåäóðîé À0 äî ïîñëåäíåãî ÿðóñà, íå ïðåâûñèò âåëè÷èíû (� � 1) � � �2.
Ñëåäîâàòåëüíî, ÷èñëî ýëåìåíòàðíûõ îïåðàöèé ñðàâíåíèÿ ðàáîòû ïðîöå-
äóðû çà îäèí ïðîõîä íå ïðåâûñèò ��. Ñëåäóåò òàêæå ó÷åñòü ÷èñëî îïåðà-
öèé, ñâÿçàííûõ ñ âûäåëåíèåì ìàêñèìàëüíîãî ýëåìåíòà â ìàññèâå èç �
÷èñåë, êîòîðîå íå ïðåâûñèò � �log2 . Ïîñêîëüêó ÷èñëî òàêèõ ïðîõîäîâ
ðàâíî �, îáùàÿ ñëîæíîñòü ðàáîòû ïðîöåäóðû íå ïðåâûñèò O ( (� �2 �
� �� �� �log ( )2
3
O . Ó÷èòûâàÿ, ÷òî
� �
�
� �
�
E
n n
max ( )
( )
( )
1
2
è ïîëàãàÿ � max ,� 0 9, ïîëó÷àåì âðåìåííóþ ñëîæíîñòü ïðîöåäóðû À0, â
õóäøåì ñëó÷àå ðàâíóþ O (0,09n6).
Äàííàÿ îöåíêà ïîëó÷åíà â ïðåäïîëîæåíèè, ÷òî ÷èñëî ïóòåé íà êàæäîì
ñëåäóþùåì ÿðóñå óìåíüøàåòñÿ è íå ïðåâûøàåò �2. Îäíàêî ïðè
� 0
ìîæåò íàáëþäàòüñÿ ýêñïîíåíöèàëüíîå âîçðàñòàíèå ôîðìèðóåìûõ ïóòåé è
ñëåäîâàòåëüíî, äàííàÿ îöåíêà ÿâëÿåòñÿ îöåíêîé ñíèçó. Ïîýòîìó ïðåäñòàâ-
ëÿåò èíòåðåñ ñäåëàòü îöåíêó ðàáîòû ïðîöåäóðû À0 â ñðåäíåì.
Äëÿ îöåíêè âðåìåííîé ñëîæíîñòè ðàáîòû ïðîöåäóðû À0 â ñðåäíåì è
òî÷íîñòè åå ðàáîòû áûëî ïðîâåäåíî ýêñïåðèìåíòàëüíîå èññëåäîâàíèå.
Ïðè ýòîì â ïðîöåññå òåñòèðîâàíèÿ íà êàæäóþ òî÷êó ïîñòðîåííûõ çàâè-
ñèìîñòåé ãåíåðèðîâàëîñü îò 50 äî 70 çàäà÷ çàäàííîé ðàçìåðíîñòè è îöåíè-
âàëîñü ñðåäíåå ÷èñëî ýëåìåíòàðíûõ îïåðàöèé, âûïîëíÿåìûõ ïðîöåäóðîé
À0, ñðåäíåå âðåìÿ ðåøåíèÿ çàäà÷è â ìèëëèñåêóíäàõ, âåðîÿòíîñòü ðåøåíèÿ
çàäà÷è çà âðåìÿ, íå ïðåâûøàþùåå çàäàííîå äîïóñòèìîå âðåìÿ Òä, è ïðîâî-
äèëîñü ñðàâíåíèå òî÷íîñòè ðåøåíèÿ ñ ïîìîùüþ àëãîðèòìà ïåðå÷èñëåíèÿ
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 29
âñåõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ [25]. Ïðè ýòîì ÷èñëî âåðøèí â
ãðàôå ìåíÿëîñü â äèàïàçîíå îò 10 äî 70, à ïëîòíîñòü ãðàôà — îò 10 äî 70 %.
Âñå ðåçóëüòàòû ïîëó÷åíû ñ äîâåðèòåëüíîé âåðîÿòíîñòüþ 0,95 è ïðèâå-
äåíû â òàáë. 23.
Ýêñïåðèìåíòàëüíîå èññëåäîâàíèå ðàáîòû ïðîöåäóðû À0 ïîêàçàëî, ÷òî
ïðè ìàëûõ ðàçìåðíîñòÿõ èññëåäóåìîãî ãðàôà âðåìåííàÿ ñëîæíîñòü ïðî-
öåäóðû ìîæåò áûòü óìåíüøåíà ïîñðåäñòâîì îáúåäèíåíèé ìíîæåñòâ â �.
Åñëè â � åñòü ïîäìíîæåñòâà ( | ); ( | ) ...( | )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
� — ìàêñèìàëüíîå íåçàâèñèìîå ìíîæåñòâî. Â
ñëó÷àå, êîãäà ìíîæåñòâ ( | )X Yi
r
i
k ñ îäèíàêîâûìè ìíîæåñòâàìè Yi
k íåò, òî
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
30 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
�, %
Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé ïðè n
10 20 30 40 50 60 70
×èñëî ýëåìåíòàðíûõ îïåðàöèé
10 1327 48073 331916 1275734 3729554 9011714 20042018
30 861 19323 106211 361107 965756 2190503 4366822
50 342 5942 30698 92633 222313 474830 853169
70 179 1989 8441 23368 50164 90655 151995
Âðåìÿ ðåøåíèÿ çàäàíèé (ìñ)
10 0,0201 0,4936 4,2625 24,9259 77,6657 184,1488 469,4326
30 0,0072 0,2807 2,3260 14,3485 33,3954 94,4739 195,3890
50 0,0021 0,1199 0,9901 6,0142 13,3891 53,3381 75,8878
70 0,0002 0,0136 0,2585 1,9057 4,4737 13,4991 25,2988
Âåðîÿòíîñòü âûïîëíåíèÿ çàäàíèé çà âðåìÿ Tä � 30 c
10 1 1 0,9991 0,6999 0,3204 0,1503 0,0619
30 1 1 1 0,8764 0,5928 0,2721 0,1423
50 1 1 1 0,9932 0,8936 0,4302 0,3265
70 1 1 1 1 0,9988 0,8916 0,6945
Îöåíêà ñëîæíîñòè âûïîëíåíèÿ çàäàíèé
10 n3 5, n3 7, n3 8, n3 85, n3 9, n3 9, n4
30 n3 3, n3 4, n3 5, n3 55, n3 6, n3 6, n3 6,
50 n3 1, n3 3, n3 4, n3 45, n3 5, n3 5, n3 25,
70 n2 3, n2 6, n2 7, n2 75, n2 8, n2 8, n2 9,
Òàáëèöà 23
äâà ìíîæåñòâà, ( | )X Yi
r
i
k è ( | )X Yj
r
j
k , ìîæíî îáúåäèíèòü ïðè Y Yi
k
j
k� ëèáî
Y Yj
k
i
k� . Îïåðàöèè îáúåäèíåíèÿ ïîçâîëÿþò ïîìåñòèòü çíà÷èòåëüíîå ÷èñ-
ëî ïîäìíîæåñòâ ( | )X Yi
r
i
k â �, íî ïðè ýòîì âîçðàñòàåò ÷èñëî îïåðàöèé
ñðàâíåíèÿ, íåîáõîäèìûõ äëÿ ïðîâåðêè íàëè÷èÿ îäèíàêîâûõ ìíîæåñòâ Yi
k
è ïðîâåðêè óñëîâèé Y Yi
k
j
k� è Y Yj
k
i
k� .
Ñ óâåëè÷åíèåì ðàçìåðíîñòè ÷èñëî îïåðàöèé ñðàâíåíèÿ íà÷èíàåò âîç-
ðàñòàòü ïðîïîðöèîíàëüíî n2. Ïîýòîìó ñ óâåëè÷åíèåì ðàçìåðíîñòè çàäà÷è
íà÷èíàåò âîçðàñòàòü ñëîæíîñòü ïðîöåäóðû À0. Íà ðèñ. 4 ïðèâåäåíû çàâè-
ñèìîñòè ÷èñëà ýëåìåíòàðíûõ îïåðàöèé, âûïîëíÿåìûõ ïðîöåäóðîé À0, îò
ðàçìåðíîñòè ðåøàåìîé çàäà÷è ñ èñïîëüçîâàíèåì ïîãëîùåíèÿ ïîäìíî-
æåñòâ â � è áåç ïîãëîùåíèÿ. Êàê âèäíî èç ðèñ. 4, âûèãðûø â 1,1—1,4 ðàçà â
áûñòðîäåéñòâèè ðàáîòû ïðîöåäóðû À0 íàáëþäàåòñÿ ïðè ðàçìåðíîñòÿõ n � 40.
Äàëüíåéøåå óâåëè÷åíèå ðàçìåðíîñòè ïðèâîäèò ê óõóäøåíèþ âðåìåííîé
ñëîæíîñòè ïðîöåäóðû À0 ïðè èñïîëüçîâàíèè îïåðàöèè îáúåäèíåíèÿ â
ïðîöåññå åå ðàáîòû. Ïðè òåñòîâûõ ïðîâåðêàõ ãðàôîâ ñ ÷èñëîì âåðøèí 100,
200 è 300 ïðè
� 05, óñòàíîâëåíî, ÷òî âðåìåííàÿ ñëîæíîñòü ðàáîòû ïðîöå-
äóðû íå ïðåâûøàåò Î (n5,5).
Âûâîäû
Ïðåäëîæåííàÿ ïðîöåäóðà À0 ïîçâîëÿåò ïåðå÷èñëÿòü ÍÌÍÌ, îäíàêî ïðè
ýòîì ÷àñòü èõ ìîæåò áûòü óòåðÿíà. Ýòî îáóñëîâëåíî òåì, ÷òî â ïðîöåññå
ðàáîòû ïðîöåäóðû ïðè âûáîðå ìíîæåñòâ ìàêñèìàëüíîé ìîùíîñòè ìîæåò
îêàçàòüñÿ íåñêîëüêî îäèíàêîâûõ ìàêñèìàëüíûõ ìíîæåñòâ, èç êîòîðûõ
áóäåò âûáðàíî îäíî. Ýêñïåðèìåíòàëüíî óñòàíîâëåíî, ÷òî òåðÿåòñÿ â ñðåä-
íåì íå áîëåå òðåõ-÷åòûðåõ ÍÌÍÌ. Îäíàêî â ñëó÷àå, êîãäà åñòü îäíî
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 31
×
è
ñë
î
ýë
åì
åí
òà
ð
í
û
õ
î
ï
åð
àö
è
é
0
4 10� 7
8 10� 7
1 2, 10� 8
1 6, 10� 8
2 0, 10� 8
50 60 70 80 90 100
×èñëî âåðøèí
Ðèñ. 4. Çàâèñèìîñòü ÷èñëà ýëåìåíòàðíûõ îïåðàöèé, âûïîëíÿåìûõ ïðîöåäóðîé À0, îò ÷èñ-
ëà âåðøèí â ãðàôå ïðè
� 0 3, :�— ïëîòíîñòü 30;�— ïëîòíîñòü 30 ñ ïîãëîùåíèåì; � — n4
ìàêñèìàëüíîå ìíîæåñòâî, òî îíî âñåãäà áóäåò ïîñòðîåíî, ïîñêîëüêó íà
âñåõ øàãàõ ðàáîòû ïðîöåäóðû ìíîæåñòâî Q, ïîñòðîåííîå íà îñíîâå ïàð
âåðøèí, åìó ïðèíàäëåæàùèõ, áóäåò äîìèíèðîâàòü. Ïîñêîëüêó ïðîöåäóðà
ïðîâåðÿåò âîçìîæíîñòü ïîñòðîåíèÿ ÍÌÍÌ íà îñíîâå âñåõ ïàð íåçàâè-
ñèìûõ ìíîæåñòâ âåðøèí, ïðèíàäëåæàùèõ åìó, îíî ãàðàíòèðîâàíî áóäåò
ïîñòðîåíî.
Òàêèì îáðàçîì, ïðåäëîæåííàÿ ïðîöåäóðà ðåøåíèÿ çàäà÷è ïðè ÷èñëå
âåðøèí, íå ïðåâûøàþùåì 120, è ïëîòíîñòÿõ ðåáåð â äèàïàçîíå îò 0,067 äî
0,9 ïîçâîëÿåò ðåøàòü çàäà÷ó îïðåäåëåíèÿ ÍÌÍÌ çà ïîëèíîìèàëüíîå âðå-
ìÿ, è çàäà÷à ìîæåò áûòü ðåøåíà â ìàñøòàáå ðåàëüíîãî âðåìåíè, ÷òî âàæíî
äëÿ ñîâðåìåííûõ ñèñòåì óïðàâëåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Harary F., Ross I.C. A Procedure for Clique Detection Using the Group Matrix // Socio-
metry. — 1957. — Vol. 20. — P. 205—215.
2. Butenko S., Wilhelm W.E. Clique-detection models in computational biochemistry and geno-
mics // European Journal of Operational Research. — 2006. — Vol. 173. — P. 1—17.
3. Raymond J.W., Willett P. Maximum common subgraph isomorphism algorithms matching
chemical structures // Journal of Computer-Aided Molecular Design. — 2002. — Vol. 16. —
P. 521—533.
4. Varmuza K., Penchev P.N., Scsibrany H. Maximum common substructures of organic com-
pounds exhibiting similar infrared spectra // J. Chem. Inf. Comput. Sci. — 1998. —Vol. 38. —
P. 420—427.
5. Horaud R., Skordas T. Stereo correspondence through feature grouping and maximal cliques //
IEEE Trans. Pattern Anal. Mach. Intell. — 1989. — Vol. 11, ¹ 11.
6. Pelillo M., Siddiqi K., Zucker S.W. Matching hierarchical structures using association graphs
// IEEE Trans. Pattern Anal. Mach. Intell. — 1999. — Vol. 21, ¹ 11.
7. Shearer K., Bunke H., Venkatesh S. Video indexing and similarity retrieval by largest com-
mon subgraph detection using decision trees. IDIAP-RR 00-15, Dalle Molle Institute for
Perceptual Artificial Intelligence, Martigny, Valais, Switzerland, 2000.
8. Shirinivas S.G., Vetrivel S., Elango N.M. Application of graph theory in computer science an
overview // International Journal of Engineering Science and Technology. — 2010. — Vol. 2,
¹ 9. — P. 4610—4621.
9. Ñåëèâåðñòîâ A.Â., Ëþáåöêèé Â.À. Àëãîðèòì ïîèñêà êîíñåðâàòèâíûõ ó÷àñòêîâ íóêëåî-
òèäíûõ ïîñëåäîâàòåëüíîñòåé // Èíôîðìàöèîííûå ïðîöåññû. — 2006. — 6, ¹ 1. —
C. 33—36.
10. Bahadur D.K.C., Akutsu T., Tomita E. et al. Point matching under non-uniform distortions
and protein side chain packing based on efficient maximum clique algorithms // Genome In-
form. — 2002. — Vol. 13. — P. 143—152.
11. Carr R.D., Lancia G., Istrail S. Branch-and-cut algorithms for independent set problems:
integrality gap and application to protein structure alignment. Technical report, Sandia Na-
tional Laboratories, Albuquerque, NM (US); Sandia National Laboratories, Livermore, CA
(US), September 2000.
12. Harley E., Bonner A., Goodman N. Uniform integration of genome mapping data using in-
tersection graphs // Bioinformatics. — 2001. — Vol. 17. — P. 487—494.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
32 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
13. Samudrala R., Moult J. A graph-theoretic algorithm for comparative modeling of protein
structure // J. Mol. Biol. — 1998. — Vol. 279. — P. 287—302.
14. Tomita E., Akutsu T., Hayashida M. et al. Algorithms for computing an optimal protein
threading with profiles and distance restraints // Genome Informatics. — 2003. — Vol. 14. —
P. 480—481.
15. Bahadur D.K.C., Tomita E., Suzuki J. et al. Protein sidechain packing problem: a maximum
edge-weight clique algorithmic approach // J. Bioinform Comput. Biol. — 2005. — Vol. 3. —
P. 103—126.
16. Jianer C., Iyad K.A., Ge X. Improved Parameterized Upper Bounds for Vertex Cover. —
Elsevier: Theoretical Computer Science. — 2010. —Vol. 411. — P. 3736—3756.
17. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph // Comm.
of ACM. — 1973. — Vol. 16. — P. 575—577.
18. Fomin F.V., Grandoni F., Kratsch D. Measure and conquer: a simple O(20.288n ) indepen-
dent set algorithm//Proc. of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms,
SODA 2006, Miami, Florida, USA, January 22- 26, 2006, P. 18—25. ACM Press, 2006.
19. Robson J.M. Algorithms for maximum independent set // Journal of Algorithms. — 1986. —
Vol. 7, No. 3. — P. 425—440.
20. Tarjan R.E., Trojanowski A.E. Finding a Maximum Independent Set // SIAM Journal on
Computing. — 1977. — Vol. 6. —P. 537—546.
21. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. — 1965. — Vol. 3. — P. 23—28.
22. Pardalos P.M., Xue J. The maximum clique problem // Journal of Global Optimization. —
1994. — Vol. 4. — P. 301—328.
23. Îëåìñêîé È.Â., Ôèðþëèíà Î.Ñ. Àëãîðèòì ïîèñêà íàèáîëüøåãî íåçàâèñèìîãî ìíî-
æåñòâà // Âåñòí. Ñ.-Ïá. óí-òà. Ñåð. 10: Ïðèêëàäíàÿ ìàòåìàòèêà, èíôîðìàòèêà, ïðîöåñ-
ñû óïðàâëåíèÿ. — 2014. — Âûï. 1. — Ñ. 81—91.
24. Ïëîòíèêîâ À.Ä. Ýâðèñòè÷åñêèé àëãîðèòì äëÿ ïîèñêà íàèáîëüøåãî íåçàâèñèìîãî
ìíîæåñòâà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 5. — Ñ. 41—48.
25. Ëèñòðîâîé Ñ.Â. Ìåòîä ïåðå÷èñëåíèÿ ìàêñèìàëüíèõ íåçàâèñèìûõ ìíîæåñòâ â ïðîèç-
âîëüíûõ íåîðèåíòèðîâàííûõ ãðàôàõ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 2014. — 36, ¹ 1. —
Ñ. 3—17.
26. Listrovoy S.V., Minukhin S.V. General Approach to Solving Optimization Problems in Dis-
tributed Computing Systems and Theory of Intelligence Systems Construction // Journal of
automation and information sciences. — 2010. — Vol. 42, No. 3. — P. 30—46.
27. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Îáùèé ïîäõîä ê ðåøåíèþ çàäà÷ îïòèìèçàöèè â ðàñ-
ïðåäåëåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è òåîðèè ïîñòðîåíèÿ èíòåëëåêòóàëüíûõ
ñèñòåì // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêà. — 2010. — ¹ 2. — Ñ. 65—82.
Ïîñòóïèëà 10.01.17
ïîñëå äîðàáîòêè 22.03.17
REFERENCES
1. Harary, F. and Ross, I.C. (1957), “A procedure for clique detection using the group matrix”,
Sociometry, Vol. 20, pp. 205-215.
2. Butenko, S. and Wilhelm, W.E. (2006), “Clique-detection models in computational bio-
chemistry and genomics”, European Journal of Operational Research, Vol. 173, pp. 1-17.
3. Raymond, J.W. and Willett, P. (2002), “Maximum common subgraph isomorphism algo-
rithms matching chemical structures”, Journal of Computer-Aided Molecular Design, Vol. 16,
pp. 521-533.
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 33
4. Varmuza, K., Penchev, P.N. and Scsibrany, H. (1998), “Maximum common substructures of
organic compounds exhibiting similar infrared spectra”, J. Chem. Inf. Comput. Sci., Vol. 38,
pp. 420-427.
5. Horaud, R. and Skordas, T. (1989), “Stereo correspondence through feature grouping and
maximal cliques”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 11, no. 11.
6. Pelillo, M., Siddiqi, K. and Zucker, S.W. (1999), “Matching hierarchical structures using as-
sociation graphs”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 21, no. 11.
7. Shearer, K., Bunke, H. and Venkatesh, S. (2000), Video indexing and similarity retrieval by
largest common subgraph detection using decision trees, IDIAP-RR 00-15, Dalle Molle In-
stitute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland.
8. Shirinivas, S.G., Vetrivel, S. and Elango, N.M. (2010), “Application of graph theory in com-
puter science an overview”, International Journal of Engineering Science and Technology,
Vol. 2, no. 9, pp. 4610-4621.
9. Seliverstov, A.V. and Lyubetskiy, V.A. (2006), “Algorithm for the search for conservative
segments of nucleotide sequences”, Informatsionnyie protsessy, Vol. 6, no. 1, pp. 33-36.
10. Bahadur, D.K.C., Akutsu, T., Tomita, E. and et al. (2002), “Point matching under non-uni-
form distortions and protein side chain packing based on efficient maximum clique algo-
rithms”, Genome Inform., Vol. 13, pp. 143-152.
11. Carr, R.D., Lancia, G. and Istrail, S. (2000), Branch-and-cut algorithms for independent set
problems: integrality gap and application to protein structure alignment. Technical report,
Sandia National Laboratories, Albuquerque, NM (US); Sandia National Laboratories,
Livermore, CA (US).
12. Harley, E., Bonner, A. and Goodman, N. (2001), “Uniform integration of genome mapping
data using intersection graphs”, Bioinformatics, Vol. 17, pp. 487-494.
13. Samudrala, R. and Moult, J. (1998), “A graph-theoretic algorithm for comparative modeling
of protein structure”, J. Mol. Biol., Vol. 279, pp. 287-302.
14. Tomita, E., Akutsu, T., Hayashida, M. and et al. (2003), “Algorithms for computing an opti-
mal protein threading with profiles and distance restraints”, Genome Informatics, Vol. 14,
pp. 480-481.
15. Bahadur, D.K.C., Tomita, E., Suzuki, J. and et al. (2005), “Protein sidechain packing prob-
lem: a maximum edge-weight clique algorithmic approach”, J. Bioinform Comput. Biol.,
Vol. 3, pp. 103-126.
16. Jianer, C., Iyad, K.A. and Ge, X. (2010), “Improved parameterized upper bounds for vertex
cover”, Elsevier: Theoretical Computer Science, Vol. 411, pp. 3736-3756.
17. Bron, C. and Kerbosch, J. (1973), “Algorithm 457: Finding all cliques of an undirected
graph”, Comm. of ACM, Vol. 16, pp. 575-577.
18. Fomin, F.V., Grandoni, F. and Kratsch, D. (2006), “Measure and conquer: a simple
O(20.288n ) independent set algorithm”, Proceedings of the 17th Annual ACM-SIAM Symp.
on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006.
19. Robson, J.M. (1986), “Algorithms for maximum independent set”, Journal of Algorithms,
Vol. 7, no. 3, pp. 425-440.
20. Tarjan, R.E. and Trojanowski, A.E. (1977), “Finding a maximum independent set”, SIAM
Journal on Computing, Vol. 6, pp. 537-546.
21. Moon, J.W. and Moser, L. (1965), “On cliques in graphs”, Israel J. Math., Vol. 3, pp. 23-28.
22. Pardalos, P.M. and Xue, J. (1994), “The maximum clique problem”, Journal of Global Opti-
mization, Vol. 4, pp. 301-328.
23. Olemskoy, I.V. and Firyulina, O.S. (2014), “The algorithm for finding the largest indepen-
dent set”, Vestnik, S.Pb. Universiteta, Ser. 10: Prikladnaya matematika, informatika, pro-
tsessy upravleniya, Iss. 1, pp. 81-91.
Ñ.Â. Ëèñòðîâîé, À.Â. Ñèäîðåíêî, Å.Ñ. Ëèñòðîâàÿ
34 ISSN 0204–3572. Electronic Modeling. 2017. V. 39. ¹ 3
24. Plotnikov, A.D. (2012), “Heuristic algorithm for searching for the largest independent set”,
Kibernetika i sistemnyi analiz, no. 5, pp. 41-48.
25. 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.
26. Listrovoy, S.V. and Minukhin, S.V. (2010), “General approach to solving optimization
problems in distributed computing systems and theory of intelligence systems construction”,
Journal of Automation and Information Sciences, Vol. 42, no. 3, pp. 30-46.
27. Listrovoy, S.V. and Minukhin, S.V. (2010), “A general approach to solving optimization
problems in distributed computing systems and the theory of constructing intelligent sys-
tems”, Problemy upravleniya i informatiki, no. 2, pp.65-82.
Received 10.01.17;
after revision 22.03.17
S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya
THE METHOD OF DETERMINING THE LARGEST MAXIMAL
INDEPENDENT SETS OF VERTICES OF UNDIRECTED GRAPH
A method of search for the largest maximal independent sets of an undirected connected graph is
proposed that allows one to solve the problem of determining the largest maximal independent
sets in polynomial time with the number of vertices in the graph not exceeding 120 and the den-
sity of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a
decrease in the density of edges in the graph, the algorithm has an exponential complexity that
does not exceed at an averageO n( ),20 4 , which tends to the decrease with increasing the edge den-
sity in the graph, where n is the number of vertices in the graph.
K e y w o r d s: maximal independent set, click, the top cover.
ËÈÑÒÐÎÂÎÉ Ñåðãåé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð Óêðàèíñêîãî ãîñóäàðñòâåííîãî
óíèâåðñèòåòà æåëåçíîäîðîæíîãî òðàíñïîðòà (ã. Õàðüêîâ).  1972 ã. îêîí÷èë Õàðüêîâñêîå
âûñøåå âîåííîå êîìàíäíî-èíæåíåðíîå ó÷èëèùå. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è
äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì
è ñåòåé.
ÑÈÄÎÐÅÍÊÎ Àíäðåé Âëàäèìèðîâè÷, âåä. èíæåíåð-ïðîãðàììèñò ôèðìû Samsung Electronics
Ukraine Company, LLC Samsung R&D Institute Ukraine (ã. Êèåâ).  2001 ã. îêîí÷èë Õàðüêîâñêèé
âîåííûé óíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è äèñêðåòíîé îïòèìèçàöèè è
òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé.
ËÈÑÒÐÎÂÀß Åëåíà Ñåðãååâíà, êàíä. òåõí. íàóê, äîöåíò êàôåäðû ýêîíîìèêè è ìàðêåòèíãà
Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà èì. Í.Å. Æóêîâñêîãî (ã. Õàðüêîâ), êîòîðûé
îêîí÷èëà â 1998 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ïðèìåíåíèå èíôîðìàöèîííûõ ñèñòåì â
ýêîíîìè÷åñêîé ñôåðå äåÿòåëüíîñòè.
Ìåòîä ïîèñêà íàèáîëüøèõ ìàêñèìàëüíûõ íåçàâèñèìûõ ìíîæåñòâ âåðøèí
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2017. Ò. 39. ¹ 3 35
|