Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с в...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859665353890594816 |
|---|---|
| author | Листровой, С.В. Минухин, С.В. |
| author_facet | Листровой, С.В. Минухин, С.В. |
| citation_txt | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (mn²), где в случае решения ЗНВП в произвольных графах n — число вершин, а m — число ребер в графе, а в случае решения ЗНП n — число столбцов, а m — число строк в матрице В. Показано, что погрешность решения этих задач предложенными процедурами А₁ и А₂ не превышает 5 % при плотности строк матрицы В, равной 0,5 и более.
Запропоновано наближені алгоритми розв’язування задачі про найменше вершинне покриття (ЗНВП) у довільних графах і задачі про найменше покриття (ЗНП), базовані на зведенні їх відповідно до задач квадратичного та нелінійного булевого програмування, специфіка яких дозволила побудувати алгоритми з часовою складністю, що не перевищує О (mn²), де у випадку розв’язування ЗНВП у довільних графах n — число вершин, а m — число ребер у графі, а при розв’язуванні ЗНП n — число стовпців, а m — число рядків у матриці В. Показано, що похибка розв’язку цих задач запропонованими процедурами А₁ і А₂ не перевищує 5 % при густині рядків матриці В, що дорівнює 0,5 і більше.
The authors propose approximate algorithms for solving the problem of the minimal vertex covering of arbitrary graphs and the problem of minimal coverage on the basis of their reduction, respectively, to the problems of quadratic and nonlinear Boolean programming, their specificity allowing to construct algorithms with time complexity not exceeding O (mn²), where in the case of solving the problem of minimal vertex covering of arbitrary graphs n is the number of vertices in the graph, m is the number of edges in the graph, and in the case of solving the problem of minimal coverage n is the number of columns in the matrix, m is the number of rows in B. It is shown that this error in the solution of these problems by the proposed procedures A₁ and A₂ does not exceed 5 % at the density of rows of B matrix 0.5 or more.
|
| first_indexed | 2025-11-30T10:55:20Z |
| format | Article |
| fulltext |
ÓÄÊ 519.682.1
Ñ. Â. Ëèñòðîâîé, ä-ð òåõí. íàóê
Óêðàèíñêàÿ ãîñóäàðñòâåííàÿ àêàäåìèÿ æåëåçíîäîðîæíîãî òðàíñïîðòà
(Óêðàèíà, 61050, Õàðüêîâ, ïë. Ôåéðáàõà, 7,
òåë. 0509355042, e-mail: om1@ yandex.ru),
Ñ. Â. Ìèíóõèí, êàíä. òåõí. íàóê
Õàðüêîâñêèé íàöèîíàëüíûé ýêîíîìè÷åñêèé óíèâåðñèòåò
(Õàðüêîâ, 61001, ïð. Ëåíèíà, 9-À,
òåë. (057) 702-18-31, e-mail: ms_vl@mail.ru)
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì
âåðøèííîì ïîêðûòèè â ïðîèçâîëüíîì ãðàôå
è çàäà÷è î íàèìåíüøåì ïîêðûòèè
Ïðåäëîæåíû ïðèáëèæåííûå àëãîðèòìû ðåøåíèÿ çàäà÷è î íàèìåíüøåì âåðøèííîì ïî-
êðûòèè (ÇÍÂÏ) â ïðîèçâîëüíûõ ãðàôàõ è çàäà÷è î íàèìåíüøåì ïîêðûòèè (ÇÍÏ) íà îñíîâå
ñâåäåíèÿ èõ ñîîòâåòñòâåííî ê çàäà÷àì êâàäðàòè÷íîãî è íåëèíåéíîãî áóëåâîãî ïðîãðàììè-
ðîâàíèÿ, ñïåöèôèêà êîòîðûõ ïîçâîëèëà ïîñòðîèòü àëãîðèòìû ñ âðåìåííîé ñëîæíîñòüþ,
íå ïðåâûøàþùåé Î (mn2), ãäå â ñëó÷àå ðåøåíèÿ ÇÍÂÏ â ïðîèçâîëüíûõ ãðàôàõ n — ÷èñëî
âåðøèí, à m — ÷èñëî ðåáåð â ãðàôå, à â ñëó÷àå ðåøåíèÿ ÇÍÏ n — ÷èñëî ñòîëáöîâ, à m —
÷èñëî ñòðîê â ìàòðèöå Â. Ïîêàçàíî, ÷òî ïîãðåøíîñòü ðåøåíèÿ ýòèõ çàäà÷ ïðåäëîæåííûìè
ïðîöåäóðàìè À1 è À2 íå ïðåâûøàåò 5 % ïðè ïëîòíîñòè ñòðîê ìàòðèöû Â, ðàâíîé 0,5 è áîëåå.
Ïðåäëîæåííûå àëãîðèòìû ìîãóò áûòü èñïîëüçîâàíû äëÿ ýôôåêòèâíîãî ïëàíèðîâàíèÿ
ðàñïðåäåëåíèÿ ðåñóðñîâ â GRID-ñèñòåìàõ â ìàñøòàáå ðåàëüíîãî âðåìåíè ïðè äîñòàòî÷íî
æåñòêèõ îãðàíè÷åíèÿõ íà âðåìÿ ðåøåíèÿ çàäà÷, åñëè äîïóñòèìîå âðåìÿ ïëàíèðîâàíèÿ
íàõîäèòñÿ â äèàïàçîíå îò 5 äî 100 ìñ.
Çàïðîïîíîâàíî íàáëèæåí³ àëãîðèòìè ðîçâ’ÿçóâàííÿ çàäà÷³ ïðî íàéìåíøå âåðøèííå ïî-
êðèòòÿ (ÇÍÂÏ) ó äîâ³ëüíèõ ãðàôàõ ³ çàäà÷³ ïðî íàéìåíøå ïîêðèòòÿ (ÇÍÏ), áàçîâàí³ íà çâå-
äåíí³ ¿õ â³äïîâ³äíî äî çàäà÷ êâàäðàòè÷íîãî òà íåë³í³éíîãî áóëåâîãî ïðîãðàìóâàííÿ,
ñïåöèô³êà ÿêèõ äîçâîëèëà ïîáóäóâàòè àëãîðèòìè ç ÷àñîâîþ ñêëàäí³ñòþ, ùî íå ïåðåâèùóº
Î (mn2), äå ó âèïàäêó ðîçâ’ÿçóâàííÿ ÇÍÂÏ ó äîâ³ëüíèõ ãðàôàõ n — ÷èñëî âåðøèí, à m —
÷èñëî ðåáåð ó ãðàô³, à ïðè ðîçâ’ÿçóâàíí³ ÇÍÏ n — ÷èñëî ñòîâïö³â, à m — ÷èñëî ðÿäê³â ó
ìàòðèö³ Â. Ïîêàçàíî, ùî ïîõèáêà ðîçâ’ÿçêó öèõ çàäà÷ çàïðîïîíîâàíèìè ïðîöåäóðàìè À1 ³
À2 íå ïåðåâèùóº 5 % ïðè ãóñòèí³ ðÿäê³â ìàòðèö³ Â, ùî äîð³âíþº 0,5 ³ á³ëüøå.
Çàïðîïîíîâàí³ àëãîðèòìè ìîæíà âèêîðèñòîâóâàòè äëÿ åôåêòèâíîãî ïëàíóâàííÿ ðîçïî-
ä³ëó ðåñóðñ³â ó GRID-ñèñòåìàõ â ìàñøòàá³ ðåàëüíîãî ÷àñó ïðè äîñòàòíüî æîðñòêèõ îáìå-
æåííÿõ â ÷àñ³ äëÿ ðîçâ’ÿçóâàííÿ çàäà÷³, êîëè ïðèïóñòèìèé ÷àñ ïëàíóâàííÿ ìຠä³àïàçîí
â³ä 5 äî 100 ìñ.
Ê ë þ ÷ å â û å ñ ë î â à: âåðøèííûå ïîêðûòèÿ â ãðàôàõ, íàèìåíüøåå ïîêðûòèå ñòîëáöàìè
ñòðîê â ìàòðèöå, ñîñòîÿùåé èç åäèíèö è íóëåé, GRID.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 29
Çàäà÷è î íàèìåíüøåì âåðøèííîì ïîêðûòèè (ÇÍÂÏ) è çàäà÷è î íàèìåíü-
øåì ïîêðûòèè (ÇÍÏ) èìåþò øèðîêîå ïðèêëàäíîå çíà÷åíèå â òåîðèè ïîñò-
ðîåíèÿ ñëîæíûõ ñèñòåì, âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé [1], ïðè ðàç-
ðàáîòêå èõ ïðîãðàììíîãî è ìàòåìàòè÷åñêîãî îáåñïå÷åíèÿ, à òàêæå äëÿ
ïëàíèðîâàíèÿ ðàñïðåäåëåíèÿ ðåñóðñîâ â GRID. Êðîìå òîãî, ÇÍÏ øèðîêî
ïðèìåíÿþòñÿ ïðè äèàãíîñòèêå GRID-ñèñòåì è ñåòåé [2], ïðè ðàçìåùåíèè
ïóíêòîâ îáñëóæèâàíèÿ [1, 3], â ñèñòåìàõ èíôîðìàöèîííîãî ïîèñêà, ïðè
íàçíà÷åíèè ýêèïàæåé íà òðàíñïîðòå [1, 3—5], ïðîåêòèðîâàíèè èíòåãðàëü-
íûõ ñõåì [5] è êîíâåéåðíûõ ëèíèé. Îñíîâíûì òðåáîâàíèåì ê àëãîðèòìàì
ðåøåíèÿ äàííûõ çàäà÷ ÿâëÿåòñÿ âûñîêàÿ îïåðàòèâíîñòü è îáåñïå÷åíèå
ìèíèìàëüíî âîçìîæíîé ïîãðåøíîñòè.
Çàäà÷ó íàõîæäåíèÿ íåçàâèñèìûõ ìàêñèìàëüíûõ ìíîæåñòâ èëè âåð-
øèííûõ ïîêðûòèé ìîæíî ðåøèòü, íàïðèìåð, ïîñëåäîâàòåëüíûì ïåðåáî-
ðîì íåçàâèñèìûõ ìíîæåñòâ ñ îäíîâðåìåííîé ïðîâåðêîé êàæäîãî ìíî-
æåñòâà íà ìàêñèìàëüíîñòü (ïîñëåäíåå îñóùåñòâëÿåòñÿ äîáàâëåíèåì ê
èññëåäóåìîìó ìíîæåñòâó äîïîëíèòåëüíîé âåðøèíû, íå ïðèíàäëåæàùåé
åìó, è âûÿñíåíèåì, ñîõðàíÿåòñÿ ëè íåçàâèñèìîñòü) è çàïîìèíàíèåì ìàê-
ñèìàëüíûõ ìíîæåñòâ. Îäíàêî ñ óâåëè÷åíèåì ÷èñëà âåðøèí ýòîò ñïîñîá
ñòàíîâèòñÿ âåñüìà ãðîìîçäêèì. Íà îñíîâå óñîâåðøåíñòâîâàíèÿ ýòîé ïðî-
öåäóðû ïîñòðîåíû àëãîðèòìû Áðîíà è Êýðáîøà [1].
Êàê ïîêàçàíî â ðàáîòå [3], çàäà÷à âåðøèííîãî ïîêðûòèÿ ÿâëÿåòñÿ òðóäíî
ðåøàåìîé è ýôôåêòèâíûå àëãîðèòìû åå ðåøåíèÿ äëÿ ïðîèçâîëüíûõ ãðàôîâ
íåèçâåñòíû. Äëÿ äâóäîëüíûõ ãðàôîâ íà îñíîâå àëãîðèòìîâ Õîïêðîôòà è
Êàðïà (c ïîèñêîì â ãëóáèíó) ðàçðàáîòàíû ìåòîäû [3], ïîçâîëÿþùèå íàõî-
äèòü ìèíèìàëüíîå âåðøèííîå ïîêðûòèå è ìàêñèìàëüíîå íåçàâèñèìîå ìíî-
æåñòâî âåðøèí â ïðîèçâîëüíîì äâóäîëüíîì ãðàôå H X Y E�� �, , çà âðåìÿ
O (( ) )m n n� , ãäå n X Y� �| | è m E� | |.
Ïîëèíîìèàëüíûå àëãîðèòìû îïðåäåëåíèÿ ÷èñëà óñòîé÷èâîñòè áûëè
ïîëó÷åíû äëÿ ñîâåðøåííûõ ãðàôîâ, ò.å. ãðàôîâ, ó êîòîðûõ äëÿ ëþáîãî ïî-
ðîæäåííîãî ïîäãðàôà õðîìàòè÷åñêîå ÷èñëî ðàâíî êëèêîâîìó ÷èñëó. Àëãî-
ðèòì âû÷èñëåíèÿ ÷èñëà óñòîé÷èâîñòè ãðàôà [4] îñíîâàí íà ìåòîäå ýëëèï-
ñîèäîâ ñ èñïîëüçîâàíèåì ïðîöåäóðû îòäåëåíèÿ ìàòðèö ãðàôà. Îäíàêî â
âû÷èñëèòåëüíîì ïëàíå ýòîò àëãîðèòì èìååò ðÿä ñóùåñòâåííûõ íåäîñòàòêîâ,
íå ïîçâîëÿþùèõ èñïîëüçîâàòü åãî íà ïðàêòèêå. Êàê ïîêàçàíî â ðàáîòå [4],
ïîëó÷èòü ïðàâèëüíîå ðåøåíèå ïðè ÷èñëå âåðøèí â ãðàôå áîëåå 10 ïðàêòè-
÷åñêè íåâîçìîæíî. Âñå èçâåñòíûå äåòåðìèíèðîâàííûå òî÷íûå àëãîðèòìû
ðåøåíèÿ ÇÍÏ [1—3, 5—8] èìåþò ýêñïîíåíöèàëüíóþ ñëîæíîñòü.
Ñëåäóåò çàìåòèòü, ÷òî ïðèìåíåíèå èçâåñòíûõ æàäíûõ àëãîðèòìîâ
òèïà Greedy-Set-Cover [9—12] ìîæåò äàâàòü ïîãðåøíîñòü ïîðÿäêàO (log )n . Â
ðàáîòå [13] ïîêàçàíî, ÷òî ïîãðåøíîñòü àïïðîêñèìàöèè æàäíîãî àëãîðèòìà
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
30 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
äëÿ ðåøåíèÿ ÇÍÏ ñîñòàâëÿåò ln lnlnn n O� � ( )1 . Äðóãèå àëãîðèòìû ýòîãî
òèïà [14] ïîñòðîåíû íà àíàëèçå ãàðìîíè÷åñêîãî ðÿäà:
H
i c
k
i
k
�
�
�
�1
1 ,
ãäå k — ìîùíîñòü ìíîæåñòâà, îïðåäåëÿþùåãî ïîêðûòèå; ñ — íåêîòîðàÿ
êîíñòàíòà. Äëÿ ýòîãî ãàðìîíè÷åñêîãî ðÿäà ïîëó÷åíû îöåíêè àïïðîêñè-
ìàöèè [14], óòî÷íÿþùèå âåëè÷èíó êîíñòàíòû ñ.
Òàêèì îáðàçîì, íàèáîëåå ïðèåìëåìîé äëÿ ïðîâåäåíèÿ ñðàâíèòåëüíîãî
àíàëèçà èìåþùèõñÿ òåîðåòè÷åñêèõ ðåçóëüòàòîâ ýôôåêòèâíîñòè àïïðîêñè-
ìàöèè æàäíûõ àëãîðèòìîâ ÿâëÿåòñÿ îöåíêà O n(log ), ïðîïîðöèîíàëüíàÿ
âåëè÷èíå ëîãàðèôìà îò ÷èñëà ñòîëáöîâ (âåðøèí) â ìàòðèöå Â. Ýòè àëãî-
ðèòìû ñ òðóäîì ïîääàþòñÿ ðàñïàðàëëåëèâàíèþ, è ñëåäîâàòåëüíî, èõ ïðè-
ìåíåíèå â êà÷åñòâå ñðåäñòâ ïëàíèðîâàíèÿ â ðàñïðåäåëåííîé ñðåäå, íàïðè-
ìåð â GRID-ñèñòåìàõ, ïðåäñòàâëÿåòñÿ çàòðóäíèòåëüíûì.
Ðàçðàáîòàííûé ìåòîä ïîçâîëÿåò ñîêðàòèòü ñëîæíîñòü è ïîãðåøíîñòü
ðåøåíèÿ ÇÍÂÏ äëÿ ïðîèçâîëüíûõ ãðàôîâ è ÇÍÏ.
Ïîñòàíîâêà è ðåøåíèå çàäà÷è. Ðàññìîòðèì ôîðìàëèçàöèþ ÇÍÂÏ â
ïðîèçâîëüíûõ ãðàôàõ, äëÿ ÷åãî ââåäåì ïîíÿòèå ðàçáîðêè è ñáîðêè ãðàôà
èç áàçîâûõ ýëåìåíòîâ. Ïîä áàçîâûìè ýëåìåíòàìè {li} ãðàôà G (Õ, Å) ñ ìíî-
æåñòâîì âåðøèí Õ è ìíîæåñòâîì ðåáåð Å áóäåì ïîíèìàòü âåðøèíû ãðàôà
{i X } âìåñòå ñ èíöèäåíòíûìè èì ðåáðàìè. Áóäåì ïîëàãàòü, ÷òî áàçîâûå
ýëåìåíòû ãðàôà li è l j ìîãóò áûòü îáúåäèíåíû, åñëè îíè èìåþò îáùèå
âåðøèíû èëè ðåáðà. Òîãäà ïîä îáúåäèíåíèåì äâóõ áàçîâûõ êîìïîíåíòîâ
l li j� áóäåì ïîíèìàòü ïîäãðàô ãðàôà G, ïîëó÷åííûé îáúåäèíåíèåì îäíî-
èìåííûõ ðåáåð è âåðøèí â áàçîâûõ ýëåìåíòàõ li è l j è ñîåäèíåíèåì âñåõ
âåðøèí â îáúåäèíåííîé êîíñòðóêöèè â ñîîòâåòñòâèè ñî ñâÿçÿìè ìåæäó
âåðøèíàìè èñõîäíîãî ãðàôà G. ßñíî, ÷òî ýòà îïåðàöèÿ êîììóòàòèâíà, ò.å.
l l l li j j i� � � .
Îáúåäèíåíèå êîìïîíåíò âîçìîæíî, åñëè åñòü îáùèå ðåáðà èëè âåðøè-
íû â îáúåäèíÿåìûõ êîìïîíåíòàõ. Ïðîöåäóðó óäàëåíèÿ áàçîâûõ êîìïî-
íåíò èç ãðàôà íàçîâåì ðàçáîðêîé ãðàôà G. Åñëè â ïðîöåññå ðàçáîðêè ãðàôà
óäàëÿåòñÿ áàçîâàÿ êîìïîíåíòà li , òî îñòàâøèéñÿ ïîäãðàô îáîçíà÷èì Gi,
åñëè óäàëÿåòñÿ äâå êîìïîíåíòû, li è l j , òî ïîäãðàô îáîçíà÷èì Gij è ò. ä.
Åñëè â ãðàôå n âåðøèí, òî ÷èñëî áàçîâûõ êîìïîíåíò, èç êîòîðûõ ñîñòîèò
ãðàô G, ðàâíî n.
Íàïðèìåð, ãðàô G, ïðåäñòàâëåííûé íà ðèñ. 1, ñîäåðæèò ïÿòü âåðøèí è
èìååò ïÿòü áàçîâûõ êîìïîíåíò. ßñíî, ÷òî ãðàô G ìîæíî ðàññìàòðèâàòü êàê
îáúåäèíåíèå âñåõ êîìïîíåíò li , ò.å. G li
n
�
1
� .
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 31
Ïîñòàâèì â ñîîòâåòñòâèå êàæäîé âåðøèíå ãðàôà ïåðåìåííóþ xi. Òîãäà
êàæäóþ êîìïîíåíòó li ìîæíî îïèñàòü â âèäå ïðîèçâåäåíèÿ
x xi q
q miq
� ,
ãäå miq — ìíîæåñòâî âåðøèí, ñìåæíûõ âåðøèíå i â êîìïîíåíòå li . Åñëè
âåðøèíó i âêëþ÷èòü â âåðøèííîå ïîêðûòèå, òî ìîæíî ñ÷èòàòü, ÷òî xi = 0.
Óìíîæåíèå íà xi = 0 â ïðîèçâåäåíèè
x xi q
q miq
�
îáðàùàåò â íóëü âñå ðåáðà, ïîêðûâàåìûå âåðøèíîé i â êîìïîíåíòå li .
Ðàññìîòðèì ñóììó
x x x x x xq
q m
q
q m
n q
q miq iq iq
1 2
� � �� � �... . (1)
Åñëè ïîäìíîæåñòâî âåðøèí {xi} îáðàçóåò ïîêðûòèå, òî ñóììà (1) áóäåò
ðàâíà íóëþ. Ïîñêîëüêó â êàæäîé ïàðå xi xj îäíà èç ïåðåìåííûõ äëÿ îáðàçî-
âàíèÿ ïîêðûòèÿ äîëæíà áûòü ðàâíà íóëþ, ïîñëå ïåðåìíîæåíèÿ â (1) áóäóò
ñïðàâåäëèâû ðàâåíñòâà xi xj+ xi xj= xi xj, è ñîîòíîøåíèå (1) ìîæíî ïåðåïè-
ñàòü â âèäå
x x x x x x x xq
q m
q
q m
n q
q m
i j
i j Eiq iq iq
1 2
� � � �� � � �...
,
. (2)
Òîãäà çàäà÷ó îïðåäåëåíèÿ ìèíèìàëüíîãî âåðøèííîãî ïîêðûòèÿ ìîæíî
ñôîðìóëèðîâàòü â âèäå
min { }
i
ix (3)
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
32 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
1l 2l 3l
5l
4l
2
2
1
1
1
1
2 44 3
3
3
2
2
5
5
5
13 4 4
4
4
3
Ðèñ. 1. Ãðàô G è åãî áàçîâûå êîìïîíåíòû
ïðè âûïîëíåíèè ñëåäóþùåãî îãðàíè÷åíèÿ:
x xi j
i j E,
� �0. (4)
Ôóíêöèîíàë (3) îçíà÷àåò ïîèñê ìèíèìàëüíîãî ÷èñëà ïåðåìåííûõ
x i �0, êîòîðûå ðàâåíñòâî (4) îáðàòÿò â òîæäåñòâî, ò.å. ïðèõîäèì ê çàäà÷å
êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ. Ñ ó÷åòîì (2) çàäà÷ó (3) ìîæíî ïåðå-
ïèñàòü ïðè âûïîëíåíèè ñëåäóþùèõ îãðàíè÷åíèé:
x x x x x xq
q m
q
q m
n q
q miq iq iq
1 20 0 0
� � �� � �; ... . (5)
Ñèñòåìà óðàâíåíèé (5) ñîñòàâëåíà íà îñíîâå áàçîâûõ êîìïîíåíò ãðàôà.
Ïðè ýòîì ÷èñëî óðàâíåíèé ðàâíî ÷èñëó áàçîâûõ êîìïîíåíò. Íàïðèìåð, äëÿ
ãðàôà, ïðåäñòàâëåííîãî íà ðèñ. 1, äàííàÿ ñèñòåìà óðàâíåíèé èìååò âèä
x x x x x x1 2 1 3 1 4 0� � � ,
x x x x x x2 3 2 4 2 1 0� � � ,
(6)
x x x x x x4 1 4 2 4 3 0� � � ,
x x5 4 0� .
Äëÿ îïðåäåëåíèÿ ìèíèìàëüíîãî âåðøèííîãî ïîêðûòèÿ â ãðàôå G íå-
îáõîäèìî íàéòè íàèìåíüøåå ÷èñëî ïåðåìåííûõ x i �0, îáðàùàþùèõ â
òîæäåñòâî ñèñòåìó óðàâíåíèé (6).
 ðàáîòå [2] ïîêàçàíî, ÷òî ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå. Åñëè â ãðàôå G åñòü âèñÿ÷àÿ âåðøèíà i, îáðàçîâàííàÿ
ðåáðîì (i, j), òî âåðøèíà j ïðèíàäëåæèò îäíîìó èç ìèíèìàëüíûõ âåðøèí-
íûõ ïîêðûòèé â ãðàôå G, åñëè â ãðàôå G èõ íåñêîëüêî, è ìèíèìàëüíîìó
âåðøèííîìó ïîêðûòèþ, åñëè îíî â ãðàôå G îäíî.
Íàëè÷èå âèñÿ÷åé âåðøèíû â ãðàôå îçíà÷àåò, ÷òî åñòü õîòÿ áû îäíà
áàçîâàÿ êîìïîíåíòà ãðàôà, ñîäåðæàùàÿ îäíî ðåáðî (ñì. ðèñ. 1), åé â (6)
ñîîòâåòñòâóåò óðàâíåíèå x x5 4 0� , è ñëåäîâàòåëüíî, íåîáõîäèìî â (6) ïîëî-
æèòü x4 0� , ò.å. âêëþ÷èòü ÷åòâåðòóþ âåðøèíó â ïîêðûòèå. Ïðè ýòîì ñèñòå-
ìà ïðèìåò âèä
x x x x1 2 1 3 0� � ,
x x x x2 3 2 1 0� � .
(7)
Ïåðåìåííûå x1, x2 è x3 îäèíàêîâî ÷àñòî âñòðå÷àþòñÿ â îñòàâøèõñÿ
óðàâíåíèÿõ, ïîýòîìó ëþáóþ èç íèõ âêëþ÷àåì â ïîêðûòèå. Ïîëàãàÿ x2 = 0,
ïîëó÷àåì x1 x3 = 0. Çàòåì â ïîêðûòèå âêëþ÷àåì ëèáî âåðøèíó 1 ëèáî âåð-
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 33
øèíó 3, ò.å. ïîëó÷àåì äâà ìèíèìàëüíûõ ïîêðûòèÿ: âåðøèíû {4, 2, 1} ëèáî
{4, 2, 3}. Ïðàâèëüíîñòü ðåøåíèÿ ëåãêî ïðîâåðèòü, ïåðå÷èñëèâ âñå âåðøèí-
íûå ïîêðûòèÿ ãðàôà G, ïðåäñòàâèâ åãî â âèäå áóëåâîé ôóíêöèè
f x x x x x x x x x x x x x x�
( ) ( ) ( ) ( ) ( ) ( ) (1 2 1 3 1 4 2 3 2 4 3 4 4 5 ). (8)
Ïåðåìíîæèâ âûðàæåíèÿ â ñêîáêàõ è èñïîëüçîâàâ ïðàâèëî ïîãëîùåíèÿ,
ïîëó÷èì ïåðå÷åíü âåðøèííûõ ïîêðûòèé ãðàôà:
f x x x x x x x x x x x x x�
1 2 4 1 3 4 2 3 4 1 2 3 5.
Ñëåäîâàòåëüíî, â ãðàôå G (ñì. ðèñ. 1) èìååòñÿ òðè ìèíèìàëüíûõ ïîêðûòèÿ:
{4,2,1}, {4,2,3}, {1,3,4}, êîòîðûå ïåðåñåêàþòñÿ ïî ìíîæåñòâó âåðøèí {1,2,3},
ñîîòâåòñòâóþùèõ ìíîæåñòâó ïåðåìåííûõ {x x x1 2 3, , }. Ýòè ïåðåìåííûå
îäèíàêîâî ÷àñòî âñòðå÷àëèñü â óðàâíåíèÿõ íà íåêîòîðîì øàãå ïîèñêà
ìàêñèìàëüíîãî ÷èñëà ïåðåìåííûõ, îáíóëÿþùèõ ñîîòâåòñòâóþùèå ïàðû
ñëàãàåìûõ â óðàâíåíèÿõ (7).
Ââåäåì ñëåäóþùóþ ïðîöåäóðó ðåøåíèÿ çàäà÷è (3), (5).
Ïðîöåäóðà À1.
Ø à ã 1. Ïðîâåðÿåì, åñòü ëè â ñèñòåìå óðàâíåíèé ïåðåìåííûå, âñòðå-
÷àþùèåñÿ îäèí ðàç. Åñëè äà, òî ïåðåìåííûå, íàõîäÿùèåñÿ ñ íèìè â ïàðå,
ïðèðàâíèâàåì íóëþ, à ñîîòâåòñòâóþùèå âåðøèíû âíîñèì â ïîêðûòèå è âû-
ïîëíÿåì ñëåäóþùèé øàã, åñëè íåò, òî ïåðåõîäèì ê âûïîëíåíèþ øàãà 3.
Ø à ã 2. Ïðîâåðÿåì, âñå ëè ïàðíûå ñëàãàåìûå â ñèñòåìå óðàâíåíèé
îáíóëåíû. Åñëè íåò, òî ïåðåõîäèì ê âûïîëíåíèþ øàãà 1, åñëè èíà÷å, òî
àëãîðèòì çàêàí÷èâàåò ðàáîòó, è ñôîðìèðîâàííîå ïîêðûòèå ÿâëÿåòñÿ ìè-
íèìàëüíûì.
Ø à ã 3. Íàõîäèì â ñèñòåìå óðàâíåíèé ïåðåìåííóþ, êîòîðàÿ ÷àùå âñå-
ãî âñòðå÷àåòñÿ â ïàðíûõ ïðîèçâåäåíèÿõ ñèñòåìû óðàâíåíèé. Åñëè òàêèõ
ïåðåìåííûõ íåñêîëüêî, òî âûáèðàåì ëþáóþ èç íèõ è ïðèðàâíèâàåì åå
íóëþ, à ñîîòâåòñòâóþùóþ åé âåðøèíó âíîñèì â ïîêðûòèå è ïåðåõîäèì ê
âûïîëíåíèþ øàãà 2.
Èññëåäóåì îïòèìàëüíîñòü ðàáîòû ïðîöåäóðû A1. Äëÿ ýòîãî ðàññìîò-
ðèì òðè ñëåäóþùèõ ñëó÷àÿ.
1. Ïðåäïîëîæèì, ÷òî íà êàæäîì øàãå ðàáîòû ïðîöåäóðû ïîÿâëÿþòñÿ
ïåðåìåííûå, êîòîðûå âñòðå÷àþòñÿ îäèí ðàç. Òîãäà íà êàæäîì øàãå, â
ñîîòâåòñòâèè ñ óòâåðæäåíèåì 1, ïîäñîåäèíÿåì ê ïîêðûòèþ âåðøèíó, ãà-
ðàíòèðîâàíî ïðèíàäëåæàùóþ ìèíèìàëüíîìó âåðøèííîìó ïîêðûòèþ, è,
ñëåäîâàòåëüíî, ïîëó÷åííîå â ðåçóëüòàòå ðàáîòû ïðîöåäóðû A1 ïîêðûòèå
áóäåò ìèíèìàëüíûì.
2. Ïðåäïîëîæèì, ÷òî â èñõîäíîì ãðàôå G ñóùåñòâóåò îäíî ìèíèìàëü-
íîå ïîêðûòèå è íà êàæäîì øàãå 3 ðàáîòû ïðîöåäóðû A1 ñóùåñòâóåò îäíà
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
34 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
ïåðåìåííàÿ, êîòîðàÿ ÷àùå âñåãî âñòðå÷àåòñÿ â ïàðíûõ ïðîèçâåäåíèÿõ ñèñ-
òåìû óðàâíåíèé. Ïîêàæåì, ÷òî â äàííîì ñëó÷àå òàêæå ïîëó÷àåì ìèíè-
ìàëüíîå âåðøèííîå ïîêðûòèå.
Ïóñòü â äàííîì ñëó÷àå ïðîöåäóðà ïîñòðîèëà ïîêðûòèå ìîùíîñòè k.
Ïðåäïîëîæèì, ÷òî â ãðàôå G ñóùåñòâóåò ïîêðûòèå ìîùíîñòè k – 1, íî ýòî
âîçìîæíî òîëüêî â òîì ñëó÷àå, åñëè ñóùåñòâóåò ïåðåìåííàÿ, âñòðå÷àþ-
ùàÿñÿ ÷àùå, ÷åì ïåðåìåííûå, âêëþ÷åííûå â ïîêðûòèå ìîùíîñòè k. Îäíà-
êî ýòî ïðîòèâîðå÷èò òîìó ôàêòó, ÷òî íà êàæäîì øàãå 3 ðàáîòû ïðîöåäóðû
A1 â ïîêðûòèå âêëþ÷àëàñü âåðøèíà ñ ìàêñèìàëüíîé ÷àñòîòîé ïîÿâëåíèÿ â
ïàðíûõ ïðîèçâåäåíèÿõ ñèñòåìû óðàâíåíèé (5), è, ñëåäîâàòåëüíî, ïîêðû-
òèå, ïîëó÷åííîå ïðîöåäóðîé â ýòîì ñëó÷àå, òàêæå áóäåò ìèíèìàëüíûì.
3. Ïðåäïîëîæèì, ÷òî â èñõîäíîì ãðàôå G ñóùåñòâóåò íå îäíî ìèíè-
ìàëüíîå ïîêðûòèå. Ýòî îçíà÷àåò, ÷òî â ïðîöåññå ðàáîòû ïðîöåäóðû A1
âîçíèêàåò ñèòóàöèÿ, êîãäà íà íåêîòîðîì øàãå îêàçûâàåòñÿ, ÷òî ìàêñèìàëü-
íîå ÷èñëî ïåðåìåííûõ, êîòîðîå ìîæåò áûòü îáíóëåíî âñëåäñòâèå âûáîðà
ðàçëè÷íûõ ïåðåìåííûõ {xi}, îäèíàêîâî. Ýòî ñîîòâåòñòâóåò òîìó, ÷òî â
ãðàôå G ñóùåñòâóåò íåñêîëüêî ìèíèìàëüíûõ ïîêðûòèé, êîòîðûå ëèáî
âîîáùå íå ïåðåñåêàþòñÿ, ëèáî ïåðåñåêàþòñÿ íà ïîäìíîæåñòâå âåðøèí,
ñîîòâåòñòâóþùèõ ïåðåìåííûì {xi}. Ê ñîæàëåíèþ, â ñëó÷àå, êîãäà åñòü
íåñêîëüêî íåïåðåñåêàþùèõñÿ ïîêðûòèé, ïðîöåäóðà A1 ìîæåò íå äàòü
îïòèìàëüíîãî ðåøåíèÿ, ò.å. ïðîöåäóðà äàåò ïðèáëèæåííîå ðåøåíèå çàäà-
÷è. Ïîýòîìó ïðåäñòàâëÿåò èíòåðåñ îöåíèòü ïîãðåøíîñòü åå ðàáîòû.
Òàêèì îáðàçîì, ïðîöåäóðà A1 ïîçâîëÿåò íàõîäèòü ïðèáëèæåííîå ðå-
øåíèå çàäà÷è (3), (5), à ñëåäîâàòåëüíî, è çàäà÷è (3), (4). ×èñëî óðàâíåíèé â
(3), (5) íå ïðåâûøàåò n, à ÷èñëî ïàð ñëàãàåìûõ â óðàâíåíèè m. Ïîñêîëüêó â
ïðîöåññå ðàáîòû ïðîöåäóðû ïðèäåòñÿ ïðîñìîòðåòü ñèñòåìó óðàâíåíèé íå
áîëåå ÷åì n ðàç, âðåìåííàÿ ñëîæíîñòü ðàáîòû ïðîöåäóðû íå ìîæåò ïðåâû-
ñèòü âåëè÷èíû O mn( )2 .
Ôîðìàëèçàöèÿ è ðåøåíèå ÇÍÏ. Çàäà÷à î íàèìåíüøåì ïîêðûòèè ìî-
æåò áûòü ñôîðìóëèðîâàíà êàê çàäà÷à ëèíåéíîãî áóëåâîãî ïðîãðàììèðîâà-
íèÿ [1, 8], ïîñòàíîâêà êîòîðîé â îáùåì âèäå èìååò âèä
L x j
j
n
� �
�
�
1
min (9)
ïðè îãðàíè÷åíèÿõ
�ij j
j
n
x
�
�
1
1, i m�1, ; �ij { , }0 1 ; x j { , }0 1 . (10)
Çàäà÷ó (9), (10) ìîæíî ðàññìàòðèâàòü êàê çàäà÷ó îïðåäåëåíèÿ ìèíè-
ìàëüíîãî ÷èñëà ñòîëáöîâ â áóëåâîé ìàòðèöå Â, ïîêðûâàþùåé åäèíèöàìè
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 35
âñå ñòðîêè äàííîé ìàòðèöû [2]. Ïðîèçâîëüíóþ áóëåâó ìàòðèöó Â áóäåì
ïðåäñòàâëÿòü â âèäå áóëåâîé ôóíêöèè f, çàäàííîé â êîíúþíêòèâíîé íîð-
ìàëüíîé ôîðìå [2, 6], â êîòîðîé ÷èñëî äèçúþíêòîâ ðàâíî ÷èñëó ñòðîê â
ìàòðèöå, à ÷èñëî ïåðåìåííûõ â êàæäîì äèçúþíêòå — ÷èñëó åäèíèö â
ñòðîêå ìàòðèöû Â. Òîãäà çàäà÷ó î ìèíèìàëüíîì ïîêðûòèè äëÿ ïðîèçâîëü-
íîé ìàòðèöû Â, çàäàâàåìîé íåêîòîðîé áóëåâîé ôóíêöèåé
f X X X X X X X X Xl m k s r t q d h�
( ... ) ( ... ) ...( ... ) , (11)
ìîæíî ðàññìàòðèâàòü êàê çàäà÷ó íàõîæäåíèÿ ìèíèìàëüíîãî íàáîðà ïåðå-
ìåííûõ{Xi = 1}, ïðè êîòîðûõ áóëåâà ôóíêöèÿ (11) âûïîëíèìà. Çàïèøåì åå
â âèäå
min{ }
i
iX �1 (12)
ïðè âûïîëíåíèè îãðàíè÷åíèé
( ... ) ( ... ) ...( ... )X X X X X X X X Xl m k s r t q d h
�1. (13)
Ïåðåéäÿ ê äâîéñòâåííîé áóëåâîé ôóíêöèè, ïîëó÷èì
min{ }
i
iX �0 , (14)
X X X X X X X X Xl m k s r t q d h... ... ... ...
�0. (15)
Èç óðàâíåíèé (14), (15) ñëåäóåò, ÷òî çàäà÷ó î íàèìåíüøåì ïîêðûòèè
ìîæíî ðàññìàòðèâàòü êàê çàäà÷ó íåëèíåéíîãî áóëåâîãî ïðîãðàììèðî-
âàíèÿ, çàêëþ÷àþùóþñÿ â íàõîæäåíèè íàèìåíüøåãî ÷èñëà ïåðåìåííûõ
{ }X i �0 , îáðàùàþùåãî â íóëü ëåâóþ ÷àñòü îãðàíè÷åíèÿ (15).
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå: åñëè ïåðåìåííàÿ X i q� âñòðå-
÷àåòñÿ â ñëàãàåìûõ îäèí ðàç, òî åå ìîæíî ïîëîæèòü â (15) ðàâíîé åäèíèöå,
ò.å. ïåðåìåííàÿ X i q� íå âõîäèò â ìèíèìàëüíîå ïîêðûòèå.
Ñïðàâåäëèâîñòü ýòîãî óòâåðæäåíèÿ âèäíà èç ïîñòàíîâêè çàäà÷è (12),
(13). Åñëè â (13) ïåðåìåííàÿ X i q� â äèçúþíêòàõ âñòðå÷àåòñÿ îäèí ðàç, òî
ýòî çíà÷èò, ÷òî âñå ïåðåìåííûå, ñòîÿùèå â ýòîì æå äèçúþíêòå, âñòðå÷àþò-
ñÿ õîòÿ áû äâà èëè áîëåå ðàç â äðóãèõ äèçúþíêòàõ, è, åñëè èõ ïîëîæèòü
ðàâíûìè åäèíèöå, òî îíè ïîêðîþò è òîò äèçúþíêò, â êîòîðîì íàõîäèòñÿ
ïåðåìåííàÿ X i q� , è åùå íåñêîëüêî äèçúþíêòîâ, â êîòîðûõ îíè ïðèñóòñò-
âóþò. Ñëåäîâàòåëüíî, ýòà ïåðåìåííàÿ íå ìîæåò ïðèíàäëåæàòü ìèíèìàëü-
íîìó ïîêðûòèþ è åå ìîæíî ïîëîæèòü â (13) ðàâíîé íóëþ. Ñîîòâåòñòâåííî
â äâîéñòâåííîé áóëåâîé ôóíêöèè îíà áóäåò ðàâíà åäèíèöå, ÷òî è òðåáîâà-
ëîñü ïîêàçàòü.
Ñëåäóåò çàìåòèòü, ÷òî åñëè â ðåçóëüòàòå ýòîãî â (15) ïîÿâèòñÿ ñëàãàå-
ìîå, ñîñòîÿùåå èç îäíîé ïåðåìåííîé, òî äàííàÿ ïåðåìåííàÿ äîëæíà âîéòè
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
36 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
â ìèíèìàëüíîå ïîêðûòèå, òàê êàê, åñëè ýòîãî íå ñäåëàòü, ðàâåíñòâî (15)
íèêîãäà íå áóäåò âûïîëíåíî.
Èñïîëüçóÿ äàííîå ñâîéñòâî, äëÿ ðåøåíèÿ çàäà÷è (14), (15) ïðåäëàãàåì
ñëåäóþùóþ ïðîöåäóðó, àíàëîãè÷íóþ ïðîöåäóðå A1.
Ïðîöåäóðà À2.
Ø à ã 1. Ïðîâåðÿåì, åñòü ëè â ñëàãàåìûõ ïåðåìåííûå, âñòðå÷àþùèåñÿ
îäèí ðàç. Åñëè äà, òî ïîëàãàåì ýòó ïåðåìåííóþ ðàâíîé åäèíèöe è ïåðåõî-
äèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 2. Ïðîâåðÿåì, åñòü ëè ñëàãàåìûå, ñîñòîÿùèå èç îäíîé ïåðåìåí-
íîé. Åñëè äà, òî ïîëàãàåì ýòè ïåðåìåííûå ðàâíûìè íóëþ è âíîñèì èõ â
ïîêðûòèå, åñëè íåò, òî ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 3. Ïðîâåðÿåì, âñå ñëàãàåìûå îáíóëåíû èëè íåò. Åñëè äà, òî
ïðîöåäóðà çàêàí÷èâàåò ðàáîòó, òàê êàê ìèíèìàëüíîå ïîêðûòèå ñôîðìèðî-
âàíî, åñëè èíà÷å, òî ïåðåõîäèì ê âûïîëíåíèþ ñëåäóþùåãî øàãà.
Ø à ã 4. Ñðåäè îñòàâøèõñÿ ñëàãàåìûõ íàõîäèì ïåðåìåííóþ, âñòðå-
÷àþùóþñÿ ÷àùå âñåãî (åñëè òàêèõ íåñêîëüêî, òî âûáèðàåì ëþáóþ èç íèõ),
ïîëàãàåì åå ðàâíîé íóëþ è âêëþ÷àåì â ïîêðûòèå, ïîñëå ÷åãî ïðîâåðÿåì,
âñå ëè ñëàãàåìûå îáíóëåíû. Åñëè äà, òî ïðîöåäóðà çàêàí÷èâàåò ðàáîòó, òàê
êàê ìèíèìàëüíîå ïîêðûòèå ñôîðìèðîâàíî, åñëè èíà÷å, òî ïåðåõîäèì ê
âûïîëíåíèþ øàãà 1.
Íàïðèìåð, ïóñòü çàäàíà ìàòðèöà Â âèäà
B �
1 2 3 4 5 6
1 1 1 0 0 0 1
2 0 0 1 0 1 1
3 0 1 0 0 1 0
4 1 1 1 0 0 0
5 0 0 1 1 0 0
.
Ïðåäñòàâèì åå â âèäå áóëåâîé ôóíêöèè:
f X X X X X X X X X X X X X�
( ) ( ) ( ) ( ) ( )1 2 6 3 5 6 2 5 1 2 3 3 4 .
Äâîéñòâåííàÿ áóëåâà ôóíêöèÿ èìååò âèä
f X X X X X X X X X X X X X�
1 2 6 3 5 6 2 5 1 2 3 3 4. (16)
Ïîñêîëüêó ïåðåìåííàÿ X 4 âñòðå÷àåòñÿ â ñëàãàåìûõ îäèí ðàç, ïîëàãàåì
X 4 1� , ïðè ýòîì îáðàçîâàëîñü ñëàãàåìîå ñ îäíîé ïåðåìåííîé X 3. Ïîëàãàåì
X 3 0� è âêëþ÷àåì ïåðåìåííóþ X 3 â ïîêðûòèå, ïîñëå ÷åãî îñòàëèñü ñëàãàå-
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 37
ìûå X X X X X1 2 6 2 5 0
� . Âûáèðàåì ïåðåìåííóþ, íàèáîëåå ÷àñòî âñòðå÷àþ-
ùóþñÿ â ñëàãàåìûõ, — ýòî X 2, ïîëàãàåì X 2 0� è âêëþ÷àåì åå â ïîêðûòèå.
Ïîñêîëüêó ïðè ýòîì âñå ñëàãàåìûå áóëåâîé ôóíêöèè (16) îáíóëåíû, ñôîð-
ìèðîâàííîå ïîêðûòèå èç ïåðåìåííûõ {X 2, X 3} ÿâëÿåòñÿ ìèíèìàëüíûì.
Ïðîàíàëèçèðóåì îïòèìàëüíîñòü ðàáîòû ïðîöåäóðû A2. Äëÿ ýòîãî ðàñ-
ñìîòðèì ñëåäóþùèõ òðè ñëó÷àÿ.
1. Ïðåäïîëîæèì, ÷òî íà êàæäîì øàãå ðàáîòû ïðîöåäóðû ïîÿâëÿþòñÿ
ñëàãàåìûå, ñîäåðæàùèå ïî îäíîé ïåðåìåííîé (òàêàÿ ñèòóàöèÿ âîçìîæíà,
êîãäà â äèçúþíêòàõ áóëåâîé ôóíêöèè ìàòðèöû Â ñîäåðæàòñÿ ïî äâå ïåðå-
ìåííûå, ÷òî ýêâèâàëåíòíî ðåøåíèþ ÇÍÂÏ â ïðîèçâîëüíûõ ãðàôàõ). Òîãäà
íà êàæäîì øàãå, â ñîîòâåòñòâèå ñ äîêàçàííûì óòâåðæäåíèåì, ïîäñîåäè-
íÿåì ê ïîêðûòèþ ïåðåìåííóþ, ãàðàíòèðîâàíî ïðèíàäëåæàùóþ ìèíè-
ìàëüíîìó ïîêðûòèþ. Ïîëó÷åííîå â ðåçóëüòàòå ðàáîòû ïðîöåäóðû A2
ïîêðûòèå áóäåò ìèíèìàëüíûì.
2. Ïðåäïîëîæèì, ÷òî äëÿ ìàòðèöû Â ñóùåñòâóåò îäíî ìèíèìàëüíîå ïî-
êðûòèå è íà êàæäîì øàãå 4 ðàáîòû ïðîöåäóðû A2 ñóùåñòâóåò îäíà ïåðå-
ìåííàÿ, êîòîðàÿ ÷àùå âñåãî âñòðå÷àåòñÿ â ïðîèçâåäåíèÿõ ñèñòåìû óðàâíåíèé.
Ïîêàæåì, ÷òî â äàííîì ñëó÷àå ïîêðûòèå òàêæå áóäåò ìèíèìàëüíûì.
Ïóñòü â äàííîì ñëó÷àå ïîñòðîåíî ïîêðûòèå ìîùíîñòè k. Ïðåäïîëî-
æèì, ÷òî äëÿ ìàòðèöû Â ñóùåñòâóåò ïîêðûòèå ìîùíîñòè k – 1, íî ýòî âîç-
ìîæíî òîëüêî â òîì ñëó÷àå, åñëè ñóùåñòâóåò ïåðåìåííàÿ, âñòðå÷àþùàÿñÿ
÷àùå, ÷åì ïåðåìåííûå, âêëþ÷åííûå â ïîêðûòèå ìîùíîñòè k. Îäíàêî ýòî
ïðîòèâîðå÷èò òîìó ôàêòó, ÷òî íà êàæäîì øàãå 4 ðàáîòû ïðîöåäóðû A2 â
ïîêðûòèå âêëþ÷àëàñü ïåðåìåííàÿ ñ ìàêñèìàëüíîé ÷àñòîòîé ïîÿâëåíèÿ â
ñëàãàåìûõ äâîéñòâåííîé áóëåâîé ôóíêöèè, è ñëåäîâàòåëüíî, ïîêðûòèå,
ïîëó÷åííîå â ýòîì ñëó÷àå, òàêæå áóäåò ìèíèìàëüíûì.
3. Ïðåäïîëîæèì, ÷òî â ìàòðèöå Â ñóùåñòâóåò íå îäíî ìèíèìàëüíîå
ïîêðûòèå. Ýòî îçíà÷àåò, ÷òî â ïðîöåññå ðàáîòû ïðîöåäóðû A2 âîçíèêàåò
ñèòóàöèÿ, êîãäà íà íåêîòîðîì øàãå åå ðàáîòû ìàêñèìàëüíîå ÷èñëî ðàçëè÷-
íûõ êîìáèíàöèé ïåðåìåííûõ, êîòîðîå ìîæåò áûòü îáíóëåíî âñëåäñòâèå
âûáîðà ïåðåìåííûõ {Õi}, îäèíàêîâî. Ýòî ñîîòâåòñòâóåò òîìó, ÷òî â Â ñó-
ùåñòâóåò íåñêîëüêî ìèíèìàëüíûõ ïîêðûòèé, è îíè ëèáî âîîáùå íå ïåðå-
ñåêàþòñÿ ëèáî ïåðåñåêàþòñÿ íà ïîäìíîæåñòâå ïåðåìåííûõ {Õi}. Ïîñêîëü-
êó ðàññóæäåíèå, ïðèâåäåííîå â ñëó÷àå 2, ìîæíî ïðèìåíèòü äëÿ êàæäîãî
ïîêðûòèÿ, ýòî îçíà÷àåò, ÷òî è â ýòîì ñëó÷àå ïðîöåäóðà A2 ïîñòðîèò ïî
êðàéíåé ìåðå îäíî èç ìèíèìàëüíûõ ïîêðûòèé. Îäíàêî, êîãäà ïîêðûòèÿ íå
ïåðåñåêàþòñÿ, êàê è â ÇÍÂÏ , âîçìîæíà ïîòåðÿ îïòèìàëüíîãî çíà÷åíèÿ.
Òàêèì îáðàçîì, ïðîöåäóðà A2 ïîçâîëÿåò íàõîäèòü ïðèáëèæåííîå ðå-
øåíèå çàäà÷è (14), (15), à ñëåäîâàòåëüíî, è çàäà÷è (12), (13). Íåòðóäíî
âèäåòü, ÷òî ïðè ÷èñëå ïåðåìåííûõ â äèçúþíêòàõ áóëåâîé ôóíêöèè, íå
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
38 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
ïðåâûøàþùåì äâóõ, ïðîöåäóðà A2 ôàêòè÷åñêè âûðîæäàåòñÿ â ïðîöåäóðó
A1. ×èñëî ñëàãàåìûõ â (14), (15) íå ïðåâûøàåò m, ÷èñëî ïåðåìåííûõ â
ñëàãàåìîì íå ïðåâûøàåò n, à ïîñêîëüêó â ïðîöåññå ðàáîòû ïðîöåäóðû
ïðèäåòñÿ ïðîñìîòðåòü ñëàãàåìûå íå áîëåå ÷åì n ðàç, òî âðåìåííàÿ ñëîæ-
íîñòü ðàáîòû ïðîöåäóðû íå ìîæåò ïðåâûñèòü Î (mn2).
Ýêñïåðèìåíòàëüíîå èññëåäîâàíèå ðàáîòû ïðîöåäóð A1 è A2. Äëÿ
ïðîâåðêè òî÷íîñòè ðåøåíèÿ ÇÍÂÏ íà îñíîâå ïðîöåäóðû A1 â êà÷åñòâå
ýòàëîííîãî èñïîëüçîâàí òî÷íûé àëãîðèòì ýêñïîíåíöèàëüíîé ñëîæíîñòè,
ïîñòðîåííûé íà îñíîâå èäåé ðàíãîâîãî ïîäõîäà [7, 15]. Ðàçìåðíîñòü ãðàôà
èçìåíÿëàñü îò 10 äî 30 âåðøèí, ãðàôû ãåíåðèðîâàëèñü ñ ðàçëè÷íîé ïëîò-
íîñòüþ ðåáåð Ï ïî ðàâíîìåðíîìó çàêîíó ðàñïðåäåëåíèÿ, íà êàæäóþ ðàç-
ìåðíîñòü ãðàôà ãåíåðèðîâàëèñü íå ìåíåå 100 ðåàëèçàöèé è ïðè ýòîì
èçìåðÿëàñü ïîãðåøíîñòü. Ïðîâåäåíà òàêæå îöåíêà â ñðåäíåì âðåìåííîé
ñëîæíîñòè àëãîðèòìà äëÿ ðàçìåðíîñòåé ãðàôîâ îò 10 äî 490 ïðè ðàçëè÷-
íûõ çíà÷åíèÿõ Ï â ãðàôå. Âñå çíà÷åíèÿ ïîëó÷åíû ñ äîâåðèòåëüíîé âåðîÿò-
íîñòüþ 0,95. Ãðàôèêè çàâèñèìîñòè ñðåäíåãî çíà÷åíèÿ ÷èñëà ýëåìåíòàð-
íûõ îïåðàöèé, âûïîëíÿåìûõ àëãîðèòìîì äëÿ ðàçëè÷íûõ ïëîòíîñòåé ðå-
áåð â ãðàôå, ïðèâåäåíû íà ðèñ. 2.
Çàâèñèìîñòè âåðîÿòíîñòè ðåøåíèÿ ÇÍÂÏ äëÿ ðàçëè÷íûõ ïëîòíîñòåé Ï çà
äîïóñòèìîå âðåìÿ, ðàâíîå 5 ìñ, ïðèâåäåíû íà ðèñ. 3, èç êîòîðîãî âèäíî, ÷òî â
ñðåäíåì âðåìåííàÿ ñëîæíîñòü àëãîðèòìà íå ïðåâûøàåò Î (n2), è â ñëó÷àå äî-
ïóñòèìîãî âðåìåíè ðåøåíèÿ, ðàâíîãî 5 ìñ, ìîãóò áûòü ýôôåêòèâíî ðåøåíû
çàäà÷è äëÿ ãðàôîâ ñ ÷èñëîì âåðøèí, íå ïðåâûøàþùåì 100.
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 39
0
500000
1000000
1500000
2000000
2500000
10 50 90 130 170 210 250 290 330 370 410 450 490 n
�
�
�
�
�
�
�
��
��
�
�
�
��
�
�
�
���
�
�
�
�
�������������������������
×
è
ñë
î
î
ï
åð
àö
è
é
1
2
3
4
5
6
Ðèñ. 2. Çàâèñèìîñòü ÷èñëà îïåðàöèé, âûïîëíÿåìûõ ïðîöåäóðîé A1 îò ÷èñëà âåðøèí â
ãðàôå ïðè ðàçëè÷íûõ çíà÷åíèÿõ Ï: 1 — y = n2 ; 2 — Ï = 0,9; 3 — Ï = 0,7; 4 — Ï = 0,5; 5 —
Ï = 0,3; 6 — Ï = 0,1
40 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
×èñëî ðåáåð ãðàôà
0
0,005
0,01
0,015
0,02
0,025
10 30 50 70 90
Î
òí
î
ñè
òå
ë
ü
í
àÿ
ï
î
ãð
åø
í
î
ñò
ü
1
3
2
Ðèñ. 4. Çàâèñèìîñòü îòíîñèòåëüíîé ïîãðåøíîñòè ïîèñêà ìèíèìàëüíîãî âåðøèííîãî ïîêðû-
òèÿ îò ÷èñëà ðåáåð â ãðàôå ïðè ðàçëè÷íîì ÷èñëå âåðøèí: 1 — n = 10; 2 — n = 20; 3 — n = 30
0
2000
4000
6000
8000
10000
12000
10 20 30 40 50 60 70 m
4
3
2
1
n = 30
×
è
ñë
î
î
ï
åð
àö
è
é
Ðèñ. 5. Çàâèñèìîñòü ÷èñëà âûïîëíÿåìûõ îïåðàöèé ïðîöåäóðîé À2 îò ðàçìåðíîñòè ìàòðè-
öû Â: 1 — n�m; 2 — Ï = 0,9; 3 — Ï = 0,7; 4 — Ï = 0,5
Â
åð
î
ÿ
òí
î
ñò
ü
â
û
ï
î
ë
í
åí
è
ÿ
àë
ãî
ð
è
òì
à
çà
5
ì
ñ
1
2
3
4
5
0
0,2
0,4
0,6
0,8
1,0
10 50 90 130 170 210 250 290 330 370 410 450 490 n
����
�
�
�
�
�
�
�
�
�
�
�
�
����� ������������������ ������ �
Ðèñ. 3. Âåðîÿòíîñòü ðåøåíèÿ çàäà÷è ïðîöåäóðîé A1 çà äîïóñòèìîå âðåìÿ 5 ìñ : 1 — Ï =
= 0,1; 2 — Ï = 0,3; 3 — Ï = 0,5; 4 — Ï = 0,7; 5 — Ï = 0,9
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 41
0
0,05
0,10
0,15
0,20
0,25
10 15 20 25 30 35
1
3
2
n
Î
òí
î
ñè
òå
ë
ü
í
àÿ
ï
î
ãð
åø
í
î
ñò
ü
Ðèñ. 7. Çàâèñèìîñòü îòíîñèòåëüíîé ïîãðåøíîñòè ðàáîòû ïðîöåäóðû À2 îò ÷èñëà ñòîëáöîâ
â ìàòðèöå  ïðè m = 30 è ðàçëè÷íûõ çíà÷åíèÿõ Ï: 1 — Ï = 0,1; 2 — Ï = 0,3; 3 — Ï = 0,5
0,6
0,8
1,0
20 40 60 80 100 120 140 160 180 200
t =ä 100 ìñ
t =ä 5 ìñ0
n
Â
åð
î
ÿ
òí
î
ñò
ü
ð
åø
åí
è
ÿ
Ðèñ. 6. Çàâèñèìîñòü âåðîÿòíîñòè ðåøåíèÿ ÇÍÏ ïðîöåäóðîé À2 îò ÷èñëà ñòîëáöîâ â
ìàòðèöå Â ïðè m = 300, Ï = 70 % è äîïóñòèìîì âðåìåíè ðåøåíèÿ tä
0
0,05
0,10
0,15
0,20
0,25
0,30
0,1 0,3 0,5 0,7 0,9 Ï
6
5
4
3
1
2
Ï
î
ãð
åø
í
î
ñò
ü
Ðèñ. 8. Çàâèñèìîñòü ïîãðåøíîñòè ðàáîòû ïðîöåäóðû À2 îò ïëîòíîñòè åäèíèö Ï â ìàòðèöå
 ïðè m = 40: 1 — n = 10; 2 — n = 15; 3 — n = 20; 4 — n = 25; 5 — n = 30; 6 — n = 35
Íà ðèñ. 4 ïðèâåäåíû çàâèñèìîñòè âåëè÷èíû ïîãðåøíîñòè ðàáîòû ïðî-
öåäóðû À1 îò ÷èñëà ðåáåð è âåðøèí ãðàôà, èç êîòîðûõ ñëåäóåò, ÷òî
âåëè÷èíà ïîãðåøíîñòè íå ïðåâûøàåò â ñðåäíåì 2,5 %. Ïðîâåðêà íà òåñ-
òîâûõ ïðèìåðàõ áîëüøîé ðàçìåðíîñòè ïîêàçàëà, ÷òî ñ óâåëè÷åíèåì ðàç-
ìåðíîñòè è ïëîòíîñòè ðåáåð â ãðàôå èìååòñÿ òåíäåíöèÿ ê óìåíüøåíèþ
âåëè÷èíû ïîãðåøíîñòè.
Íà ðèñ. 5—8 ïðåäñòàâëåíû ãðàôèêè, îòîáðàæàþùèå ðàáîòó ïðîöåäó-
ðû À2, ðåøàþùåé ÇÍÏ ïðè ÷èñëå ñòîëáöîâ n è ÷èñëå ñòðîê m â ìàòðèöå Â.
Êàê âèäíî èç ðèñ. 5, 6, âðåìåííàÿ ñëîæíîñòü ïðîöåäóðû À2 â ñðåäíåì íå
ïðåâûøàåò Î (mn). Òåñòîâûå ïðèìåðû ðåøåíèÿ çàäà÷ ïðè n
600, m = 400
ïîêàçàëè, ÷òî âðåìåííàÿ ñëîæíîñòü â ñðåäíåì íå ïðåâûøàëà Î (400mn).
Àíàëèç ïîãðåøíîñòè ðàáîòû ïðîöåäóðû À2 (ñì. ðèñ. 7, 8) ñâèäåòåëüñòâóåò
î òîì, ÷òî ïðè ïëîòíîñòÿõ çàïîëíåíèÿ åäèíèöàìè ìàòðèöû  áîëåå ÷åì íà
50 % ïîãðåøíîñòü íå ïðåâûøàåò 5 %.
Âûâîäû
Òàêèì îáðàçîì, ïðåäëîæåííûå ïðèáëèæåííûå àëãîðèòìû ðåøåíèÿ ÇÍÂÏ
â ïðîèçâîëüíûõ ãðàôàõ è ÇÍÏ íà îñíîâå ñâåäåíèÿ èõ ñîîòâåòñòâåííî ê
çàäà÷àì êâàäðàòè÷íîãî è íåëèíåéíîãî áóëåâîãî ïðîãðàììèðîâàíèÿ, ïîç-
âîëèëè ïîñòðîèòü àëãîðèòìû ñ âðåìåííîé ñëîæíîñòüþ, íå ïðåâûøàþùåé
Î (mn2), ãäå â ñëó÷àå ðåøåíèÿ ÇÍÂÏ n — ýòî ÷èñëî âåðøèí â ãðàôå, m —
÷èñëî ðåáåð â ãðàôå, à â ñëó÷àå ðåøåíèÿ ÇÍÏ n — ýòî ÷èñëî ñòîëáöîâ â
ìàòðèöå Â, m — ÷èñëî ñòðîê â ìàòðèöå Â. Ïîãðåøíîñòü ðåøåíèÿ ýòèõ çàäà÷
ïðîöåäóðàìè À1 è À2 ñîñòàâëÿåò 2,5—5% ïðè Ï
0,5 è èõ ñðåäíÿÿ âðåìåííàÿ
ñëîæíîñòü ñîñòàâëÿåò Î (n2) äëÿ ÇÍÂÏ è Î (mn) äëÿ ÇÍÏ, ÷òî î÷åíü âàæíî
ïðè ðåøåíèè çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ â ñîâðåìåííûõ GRID-ñèñòåìàõ.
Èç ðèñ. 3 è 6 âèäíî, ÷òî ïðåäëîæåííûå àëãîðèòìû ìîãóò áûòü èñïîëü-
çîâàíû äëÿ ýôôåêòèâíîãî ðåøåíèÿ çàäà÷ ïëàíèðîâàíèÿ ðàñïðåäåëåíèÿ
ðåñóðñîâ [2, 6] â ìàñøòàáå ðåàëüíîãî âðåìåíè, åñëè äîïóñòèìîå âðåìÿ
ïëàíèðîâàíèÿ íàõîäèòñÿ â äèàïàçîíå îò 5 äî 100 ìñ.
The authors propose approximate algorithms for solving the problem of the minimal vertex cov-
ering of arbitrary graphs and the problem of minimal coverage on the basis of their reduction, re-
spectively, to the problems of quadratic and nonlinear Boolean programming, their specificity al-
lowing to construct algorithms with time complexity not exceeding O (mn2), where in the case of
solving the problem of minimal vertex covering of arbitrary graphs n is the number of vertices in
the graph, m is the number of edges in the graph, and in the case of solving the problem of mini-
mal coverage n is the number of columns in the matrix, m is the number of rows in B. It is shown
that this error in the solution of these problems by the proposed procedures A1 and A2 does not
exceed 5 % at the density of rows of B matrix 0.5 or more.
The proposed algorithm can be used to effectively planning for the allocation of resources in
GRID-systems in real time with a rather severe restrictions on the time of solving problems, if al-
lowed time planning lies in range from 5 to 100 ms.
Ñ. Â. Ëèñòðîâîé, Ñ. Â. Ìèíóõèí
42 ISSN 0204–3572. Electronic Modeling. 2012. V. 34. ¹ 1
1. Êðèñòîôèäåñ Í. Òåîðèÿ ãðàôîâ. Àëãîðèòìè÷åñêèé ïîäõîä. — Ì. : Ìèð, 1978. — 309 ñ.
2. Ïîíàìîðåíêî Â. Ñ., Ëèñòðîâîé Ñ. Â. Ìåòîä ðåøåíèÿ çàäà÷è î ìèíèìàëüíîì ïîêðû-
òèè êàê ñðåäñòâî ïëàíèðîâàíèÿ â GRID // Ïðîáëåìû óïðàâëåíèÿ. — 2008. — ¹ 3. —
Ñ. 78—84.
3. Ëèïñêèé Â. Êîìáèíàòîðèêà äëÿ ïðîãðàììèñòîâ. — Ì. : Ìèð, 1988. — 203 ñ.
4. Øîð Í. Ç., Ñòåöåíêî Ñ. È. Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è íåäèôôåðåíöèðóå-
ìàÿ îïòèìèçàöèÿ. — Êèåâ : Íàóê. äóìêà, 1989. — 196 ñ.
5. Ïàïàäèìèòðèó Ê., Ñòàéãëèö Ì. Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæ-
íîñòü. — Ì. : Ìèð, 1985. — 512 ñ.
6. Ïîíîìàðåíêî Â. Ñ., Ëèñòðîâîé Ñ. Â., Ìèíóõèí Ñ. Â., Çíàõóð Ñ. Â. Ìåòîäû è ìîäåëè
ïëàíèðîâàíèÿ ðåñóðñîâ â GRID-ñèñòåìàõ.— Õàðüêîâ: ÈÄ «ÈÍÆÝÊ», 2008. — 408 ñ.
7. Ëèñòðîâîé Ñ. Â., Ãóëü À. Þ. Ìåòîä ðåøåíèÿ çàäà÷è î ìèíèìàëüíîì ïîêðûòèè íà
îñíîâå ðàíãîâîãî ïîäõîäà // Ýëåêòðîí. ìîäåëèðîâàíèå. — 1999. — 21, ¹ 1. — Ñ. 58 —
70.
8. Ëèñòðîâîé Ñ. Â., Ãóëü À. Þ., Ëèñòðîâàÿ Å. Ñ. Òî÷íûé àëãîðèòì ðåøåíèÿ çàäà÷è î
ìèíèìàëüíîì ïîêðûòèè // Ñá. íàó÷. òð. Èíôîðìàòèêà. Âûï. 5. — Êèåâ : Íàóê. äóìêà,
1998. — Ñ. 32 — 36.
9. Êîðìåí Ò., Ëåéçåðñîí ×., Ðèâåñò Ð. Àëãîðèòìû: ïîñòðîåíèå è àíàëèç. — Ì. :
ÌÖÍÌÎ, 2002. — 960 ñ.
10. Gandhi R., Khuller S., Srinivasan A. Approximation Algorithms for partial Covering Prob-
lems. // Journal of Algorithms. — 2004. — Vol. 53. — Issue 1. — P. 55—84.
11. Alon N., Awerbuch B., Azar, Y. et. al. The online set cover problem // Proc. STOC’03.
June 9—11, 2003. — San Diego, California, USA. — P. 100—105.
12. Chvàtal V. A greedy-heuristic for the set covering problem. // Math. Oper. Res. — 1979. —
¹ 4. — Ð. 233—235.
13. Slavik P. A tight analysis of the greedy algorithm for set cover //Journal of Algorithms. —
1997. — ¹ 25. — Ð. 237—254.
14. Hassin R., Levin A. A Better-than-greedy Approximation Algorithm for the Minimum Set
Cover Problem. // SIAM J. Computing.— 2005.— Vol. 35, ¹ 1. — Ð. 189—200.
15. Ëèñòðîâîé Ñ. Â., Ìèíóõèí Ñ. Â. Îáùèé ïîäõîä ê ðåøåíèþ çàäà÷ îïòèìèçàöèè â
ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è òåîðèè ïîñòðîåíèÿ èíòåëëåêòóàëüíûõ
ñèñòåì. — //Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2009. — ¹ 2. — Ñ. 47—63.
Ïîñòóïèëà 11.07.11;
ïîñëå äîðàáîòêè 28.10.11
ËÈÑÒÐÎÂÎÉ Ñåðãåé Âëàäèìèðîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû ñïåöèàëè-
çèðîâàííûõ êîìïüþòåðíûõ ñèñòåì Óêðàèíñêîé ãîñóäàðñòâåííîé àêàäåìèè æåëåçíîäîðîæ-
íîãî òðàíñïîðòà.  1972 ã. îêîí÷èë Õàðüêîâñêîå âûñøåå âîåííîå êîìàíäíî-èíæåíåðíîå
ó÷èëèùå. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — çàäà÷è äèñêðåòíîé îïòèìèçàöèè è òåîðèè ãðàôîâ
è èõ ïðèëîæåíèå ê àíàëèçó âû÷èñëèòåëüíûõ ñèñòåì è ñåòåé.
ÌÈÍÓÕÈÍ Ñåðãåé Âëàäèìèðîâè÷, êàíä. òåõí. íàóê, äîöåíò, ïðîôåññîð êàôåäðû èíôîðìà-
öèîííûõ ñèñòåì Õàðüêîâñêîãî íàöèîíàëüíîãî ýêîíîìè÷åñêîãî óíèâåðñèòåòà.  1976 ã. îêîí÷èë
Õàðüêîâñêèé èí-ò ðàäèîýëåêòðîíèêè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — îïòèìèçàöèÿ ïðî-
öåññîâ â ðàñïðåäåëåííûõ ñèñòåìàõ, èäåíòèôèêàöèÿ è óïðàâëåíèå â ñëîæíûõ ñèñòåìàõ, óïðàâ-
ëåíèå èíôîðìàöèîííî-âû÷èñëèòåëüíûìè ñèñòåìàìè.
Ìåòîä ðåøåíèÿ çàäà÷ î ìèíèìàëüíîì âåðøèííîì ïîêðûòèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2012. Ò. 34. ¹ 1 43
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-61809 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-30T10:55:20Z |
| publishDate | 2012 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Листровой, С.В. Минухин, С.В. 2014-05-11T17:40:56Z 2014-05-11T17:40:56Z 2012 Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61809 519.682.1 Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (mn²), где в случае решения ЗНВП в произвольных графах n — число вершин, а m — число ребер в графе, а в случае решения ЗНП n — число столбцов, а m — число строк в матрице В. Показано, что погрешность решения этих задач предложенными процедурами А₁ и А₂ не превышает 5 % при плотности строк матрицы В, равной 0,5 и более. Запропоновано наближені алгоритми розв’язування задачі про найменше вершинне покриття (ЗНВП) у довільних графах і задачі про найменше покриття (ЗНП), базовані на зведенні їх відповідно до задач квадратичного та нелінійного булевого програмування, специфіка яких дозволила побудувати алгоритми з часовою складністю, що не перевищує О (mn²), де у випадку розв’язування ЗНВП у довільних графах n — число вершин, а m — число ребер у графі, а при розв’язуванні ЗНП n — число стовпців, а m — число рядків у матриці В. Показано, що похибка розв’язку цих задач запропонованими процедурами А₁ і А₂ не перевищує 5 % при густині рядків матриці В, що дорівнює 0,5 і більше. The authors propose approximate algorithms for solving the problem of the minimal vertex covering of arbitrary graphs and the problem of minimal coverage on the basis of their reduction, respectively, to the problems of quadratic and nonlinear Boolean programming, their specificity allowing to construct algorithms with time complexity not exceeding O (mn²), where in the case of solving the problem of minimal vertex covering of arbitrary graphs n is the number of vertices in the graph, m is the number of edges in the graph, and in the case of solving the problem of minimal coverage n is the number of columns in the matrix, m is the number of rows in B. It is shown that this error in the solution of these problems by the proposed procedures A₁ and A₂ does not exceed 5 % at the density of rows of B matrix 0.5 or more. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Article published earlier |
| spellingShingle | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Листровой, С.В. Минухин, С.В. Математические методы и модели |
| title | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_fullStr | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full_unstemmed | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_short | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_sort | метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| topic | Математические методы и модели |
| topic_facet | Математические методы и модели |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| work_keys_str_mv | AT listrovoisv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii AT minuhinsv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii |