Рекуррентный алгоритм решения задачи о взвешенном паросочетании
Известная задача о взвешенном паросочетании в произвольном графе H с n вершинами сводится к одной из задач о паросочетании для двудольного графа с 2n вершинами. Максимальное паросочетание графа H с минимальной суммой весов ребер, заданных матрицей [cij]n , находится за время O(n³) после упорядоче...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2016 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/142019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Рекуррентный алгоритм решения задачи о взвешенном паросочетании / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 101-112. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860235137112866816 |
|---|---|
| author | Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| author_facet | Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| citation_txt | Рекуррентный алгоритм решения задачи о взвешенном паросочетании / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 101-112. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Известная задача о взвешенном паросочетании в произвольном графе H с n вершинами сводится к одной из задач о паросочетании для двудольного графа с 2n вершинами. Максимальное паросочетание графа H с минимальной суммой весов ребер, заданных матрицей [cij]n , находится за время O(n³) после упорядочения по неубыванию значений cij, расположенных над главной диагональю.
Відома задача про зважену паросполуку в довільному графі H з n вершинами зводиться до однієї із задач про паросполуку для двочасткового графа з 2n вершинами. Максимальна паросполука графа H з мінімальною сумою ваг ребер, заданих матрицею [cij]n , знаходиться за час O(n³) після впорядкування за неспаданням значень cij, розташованих над головною діагоналлю.
The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a of matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the minimum sum of weights of edges specified by matrix[cij]n is found in time O(n³) after ordering the values cij above the main diagonal in non-decreasing order.
|
| first_indexed | 2025-11-24T15:49:11Z |
| format | Article |
| fulltext |
ÓÄÊ 519.161
Î.Á. ÌÀÖÈÉ, À.Â. ÌÎÐÎÇÎÂ, À.Â. ÏÀÍÈØÅÂ
ÐÅÊÓÐÐÅÍÒÍÛÉ ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÇÀÄÀ×È
Î ÂÇÂÅØÅÍÍÎÌ ÏÀÐÎÑÎ×ÅÒÀÍÈÈ
Àííîòàöèÿ. Èçâåñòíàÿ çàäà÷à î âçâåøåííîì ïàðîñî÷åòàíèè â ïðîèçâîëüíîì
ãðàôå H ñ n âåðøèíàìè ñâîäèòñÿ ê îäíîé èç çàäà÷ î ïàðîñî÷åòàíèè äëÿ
äâóäîëüíîãî ãðàôà ñ 2n âåðøèíàìè. Ìàêñèìàëüíîå ïàðîñî÷åòàíèå ãðàôà H
ñ ìèíèìàëüíîé ñóììîé âåñîâ ðåáåð, çàäàííûõ ìàòðèöåé [ ]cij n , íàõîäèòñÿ
çà âðåìÿ O n( )3 ïîñëå óïîðÿäî÷åíèÿ ïî íåóáûâàíèþ çíà÷åíèé c
ij
, ðàñïîëî-
æåííûõ íàä ãëàâíîé äèàãîíàëüþ.
Êëþ÷åâûå ñëîâà: ïàðîñî÷åòàíèå, çàäà÷à î âçâåøåííîì ïàðîñî÷åòàíèè, äâó-
äîëüíûé ãðàô, óâåëè÷èâàþùèé ïóòü, çàäà÷à î íàçíà÷åíèÿõ.
ÂÂÅÄÅÍÈÅ
 ïðèëîæåíèÿõ òåîðèè ãðàôîâ øèðîêóþ èçâåñòíîñòü ïîëó÷èëà çàäà÷à î ïàðî-
ñî÷åòàíèè. Îíà ñîñòîèò â íàõîæäåíèè â çàäàííîì ãðàôå ïàðîñî÷åòàíèÿ ñ íàè-
áîëüøèì ÷èñëîì ðåáåð — ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ.  îáîáùåíèè ýòîé
çàäà÷è çàäàíû âåñà ðåáåð — íåîòðèöàòåëüíûå ÷èñëà, è òðåáóåòñÿ îïðåäåëèòü
ìàêñèìàëüíîå ïàðîñî÷åòàíèå ãðàôà, ñîäåðæàùåå ðåáðà ñ ìèíèìàëüíûì (ìàêñè-
ìàëüíûì) ñóììàðíûì âåñîì. Ñôîðìóëèðîâàííîå îáîáùåíèå íàçûâàåòñÿ çàäà-
÷åé î âçâåøåííîì ïàðîñî÷åòàíèè (ÇÂÏ).
Èçâåñòíî, ÷òî ÇÂÏ ïîëèíîìèàëüíî ðàçðåøèìà [1]. Êëàññè÷åñêèé àëãîðèòì
Ýäìîíäñà äëÿ íàõîæäåíèÿ íàèáîëüøåãî âçâåøåííîãî ïàðîñî÷åòàíèÿ â íåäâó-
äîëüíîì ãðàôå H V U� ( , ), èçëîæåííûé â [1], õàðàêòåðèçóåòñÿ òðóäîåìêîñòüþ
O V(| | )4 . Îñíîâíîé ïðè÷èíîé îòíîñèòåëüíî íåâûñîêîãî áûñòðîäåéñòâèÿ àëãî-
ðèòìà Ýäìîíäñà ÿâëÿåòñÿ ñóùåñòâîâàíèå â ãðàôå H öâåòêîâ — öèêëîâ, ñîäåðæà-
ùèõ 2 1k � âåðøèí è k ðåáåð íåêîòîðîãî ôèêñèðîâàííîãî ïàðîñî÷åòàíèÿ M .
Îáíàðóæåííûé öâåòîê íå ïîçâîëÿåò îðãàíèçîâàòü áûñòðûé ïîèñê ïàðîñî÷åòàíèÿ
ìîùíîñòè | |M �1 ñïîñîáîì, ïðèìåíÿåìûì äëÿ äâóäîëüíûõ ãðàôîâ. Äëÿ ðàáîòû
ñ ïðîèçâîëüíûìè ãðàôàìè àëãîðèòì Ýäìîíäñà ñîäåðæèò ïðîöåäóðó îáíàðóæå-
íèÿ öâåòêà è îïåðàöèþ åãî çàìåíû îäíîé âåðøèíîé, äîïóñòèìóþ â ïðîöåññå íà-
õîæäåíèÿ òåêóùåãî ïàðîñî÷åòàíèÿ.
Íàèáîëåå ýôôåêòèâíûå àëãîðèòìû íàõîæäåíèÿ ìàêñèìàëüíûõ ïàðîñî÷åòàíèé
â ïðîèçâîëüíûõ ãðàôàõ ïîñòðîåíû íà ðàçâèòèè èäåé Ýäìîíäñà î ñæàòèè íå÷åòíûõ
öèêëîâ.  íèõ âêëþ÷åíû ñïîñîáû õðàíåíèÿ äàííûõ è îðãàíèçàöèè ïðîöåññà âû-
÷èñëåíèé, ïîíèæàþùèå ñëîæíîñòü äî O V(| | )3 äëÿ ãðàôîâ ñ n âåðøèíàìè [1, 2].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÏÎÄÕÎÄ Ê ÅÅ ÐÅØÅÍÈÞ
 óñëîâèè ðàññìàòðèâàåìîé çäåñü ÇÂÏ çàäàí ãðàô H V U� ( , ), | |V n� , ãäå V —
ìíîæåñòâî âåðøèí, U — ìíîæåñòâî ðåáåð (íåóïîðÿäî÷åííûõ ïàð âåðøèí).
 ãðàôå êàæäîå ðåáðî { }i j U, � èìååò âåñ c Rij � �
0
, i j n, ,�1 ; R
0
� — ìíîæåñò-
âî íåîòðèöàòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë.  H íåäîïóñòèìû ïåòëè, ò.å. ðåá-
ðà âèäà { }� �, , � �V , è êðàòíûå èëè «ïàðàëëåëüíûå» ðåáðà. Ïàðîñî÷åòàíèåì
â ãðàôå H íàçûâàåòñÿ ïîäìíîæåñòâî ðåáåð, â êîòîðîì íèêàêèå äâà ðåáðà íå
èìåþò îáùèõ âåðøèí. Òðåáóåòñÿ íàéòè â ãðàôå H ìàêñèìàëüíîå ïàðîñî÷åòà-
íèå ñ ìèíèìàëüíîé ñóììîé âåñîâ ðåáåð.
 äàííîé ñòàòüå èçëàãàåòñÿ ìåòîä ðåøåíèÿ ïîñòàâëåííîé ÇÂÏ, êîððåêòíî âû-
ïîëíÿþùèé äåéñòâèÿ ïî ïîñòðîåíèþ èñêîìîãî ïàðîñî÷åòàíèÿ â äâóäîëüíîì ãðàôå,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 101
© Î.Á. Ìàöèé, À.Â. Ìîðîçîâ, À.Â. Ïàíèøåâ, 2016
ñîîòâåòñòâóþùåì ãðàôó H . Ïîýòîìó îí íå ñîäåðæèò íåïðîñòûõ îïåðàöèé íàõîæäåíèÿ
è ñðåçàíèÿ öâåòêîâ, èñïîëüçóåìûõ â àëãîðèòìå Ýäìîíäñà è åãî ìîäèôèêàöèÿõ.
Ãðàôó H V U� ( , ) ÇÂÏ ñîîòâåòñòâóåò ñèììåòðè÷íàÿ ìàòðèöà ñòîèìîñòåé (âå-
ñîâ) ðåáåð C cij n� [ ] , ãäå c Rij � �
0
, åñëè { }i j U, � , è cij � � èíà÷å. Ýòà æå ìàòðèöà
îïðåäåëÿåò äâóäîëüíûé ãðàô D X Y E� ( , , ), ãäå X Y, — ìíîæåñòâî âåðøèí,
| | | | | |X Y V n� � � ; E i j i X j Y� � �{ }( , ) | , — ìíîæåñòâî ðåáåð ñ âåñàìè
c Rij � �
0
, | | | |E V� 2 . Îòñþäà ñëåäóåò, ÷òî äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è ïðè-
ìåíèìû èäåè ïîèñêà â øèðèíó â äâóäîëüíûõ ãðàôàõ [1].
Ðåáðî ïàðîñî÷åòàíèÿ M , ñâÿçûâàþùåå âåðøèíû � è u, îáîçíà÷èì [ , ]� u , ãäå
u ÿâëÿåòñÿ íàïàðíèêîì � . Ðåáðà, íå âõîäÿùèå â ïàðîñî÷åòàíèå M , íàçûâàþòñÿ
ñâîáîäíûìè. Âåðøèíà, ïðèíàäëåæàùàÿ ðåáðó ïàðîñî÷åòàíèÿ, îïðåäåëÿåòñÿ êàê
íàñûùåííàÿ. Îñòàëüíûå âåðøèíû ãðàôà íàçûâàþòñÿ íåíàñûùåííûìè, ò.å. ñâî-
áîäíûìè. Ìîùíîñòü ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ ãðàôà H ñ n âåðøèíàìè íå
ìîæåò áûòü áîëüøå � �n / 2 . Åñëè îíà ðàâíà � �n / 2 , òî ïàðîñî÷åòàíèå ñ÷èòàåòñÿ
ïîëíûì. Ïðè ÷åòíîì n ïîëíîå ïàðîñî÷åòàíèå íàñûùàåò âñå âåðøèíû ãðàôà H
è íàçûâàåòñÿ ñîâåðøåííûì.
Ïóñòü M — ïàðîñî÷åòàíèå â H . Ïðîñòîé ïóòü íàçûâàåòñÿ ÷åðåäóþùèìñÿ îò-
íîñèòåëüíî M , åñëè ðåáðà ïóòè ÷åðåäóþòñÿ ÷åðåç îäíî â M [2] . ×åðåäóþùèéñÿ
ïóòü, êîòîðûé íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ ðåáðàìè, íå ïðèíàäëåæàùèìè ïàðîñî-
÷åòàíèþ M , íàçûâàåòñÿ óâåëè÷èâàþùèì îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M .
Åñëè ( , , , , , , )� � � � � �1 2 3 2 2 2 1 2� k k k� � — óâåëè÷èâàþùèé ïóòü îòíîñèòåëü-
íî ïàðîñî÷åòàíèÿ M â ãðàôå H , òî P i j i j i jk k k� � �( , , , ..., , , )1 2 3 2 2 2 1 2 — óâåëè÷è-
âàþùèé ïóòü â äâóäîëüíîì ãðàôå D X Y E� ( , , ) îòíîñèòåëüíî ïàðîñî÷åòàíèÿ ñ
òåì æå êîëè÷åñòâîì ðåáåð, ÷òî è M . Ïóòü P íà÷èíàåòñÿ â íåíàñûùåííîé âåðøè-
íå i X1 � , çàêàí÷èâàåòñÿ â íåíàñûùåííîé âåðøèíå j Yk2 � è ñîäåðæèò k ñâîáîä-
íûõ ðåáåð ( , ), ( , ) ( , )i j i j i jk k1 2 3 4 2 1 2 �� . Îñòàëüíûå k ðåáåð ïóòè P îáðàçóþò ïà-
ðîñî÷åòàíèå { }[ , ], [ , ] [ , ]i j i j i jk k3 2 5 4 2 1 2 2 � �� . Íà ðèñ. 1, à èçîáðàæåí óâåëè÷è-
âàþùèé ïóòü â ãðàôå H V U� ( , ) îòíîñèòåëüíî ïàðîñî÷åòàíèÿ
{ }[ , ], [ , ]� � � �2 3 4 5 , à íà ðèñ. 1, á — ñîîòâåòñòâóþùèé åìó óâåëè÷èâàþùèé ïóòü
P â ãðàôå D X Y U� ( , , ) îòíîñèòåëüíî ïàðîñî÷åòàíèÿ { }[ , ], [ , ]i j i j3 2 5 4 . Çäåñü
k � 3. Ðåáðà ïàðîñî÷åòàíèé ïðåäñòàâëåíû óòîëùåííûìè ëèíèÿìè. Òîíêèìè ëè-
íèÿìè èçîáðàæåíû ðåáðà ãðàôà D , íå ïðèíàäëåæàùèå P.
Ïðîöåäóðà íàõîæäåíèÿ óâåëè÷èâàþùåãî ïóòè ÿâëÿåòñÿ âàðèàíòîì ïîèñêà â øè-
ðèíó, áàçèðóþùåìñÿ íà ñëåäóþùåì èçâåñòíîì ôàêòå: åñëè P — ìíîæåñòâî ðåáåð
óâåëè÷èâàþùåãî ïóòè îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M â ãðàôå H , òî M P
— ïà-
ðîñî÷åòàíèå ìîùíîñòè | |M �1. Íàïðèìåð, èç óâåëè÷èâàþùåãî ïóòè îòíîñèòåëüíî
ïàðîñî÷åòàíèÿ {[ , ],� �2 3 [ , ]� �4 5 } (ñì. ðèñ. 1, à) ñëåäóåò ïàðîñî÷åòàíèå {[ , ],� �1 2
[ , ], [ , ]� � � �3 4 5 6 }. Ìíîæåñòâî ðå-
áåð {[ , ], [ , ]i j i j1 2 3 2 , [ , ],i j3 4 [ , ]i j5 4 ,
[ , ]i j5 6 } îáðàçóåò óâåëè÷èâàþ-
ùèé ïóòü P i j i j i j� ( , , , , , )1 2 3 4 5 6
îòíîñèòåëüíî ïàðîñî÷åòàíèÿ
M i j i j� { }[ , ], [ , ]3 2 5 4 , ïðè ýòîì
îïðåäåëÿåòñÿ ïàðîñî÷åòàíèå
M P i j i j
� {[ , ], [ , ]1 2 3 4 , [ , ] .i j5 6 }
Ïóòü P i j i k� �( , , , ,1 2 2 1� j k2 )
â ãðàôå D ÿâëÿåòñÿ ïðîñòîé
öåïüþ, èçîìîðôíîé â ãðàôå H
öåïè ( , , , )� � �1 2 2� k ïðè ñîîò-
âåòñòâèè ( , ) ( , )� �s s s si j� ��1 1 ,
s k� �1 3 2 1, , ,� , è [ , ]� �2 2 1s s� �
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ðèñ. 1
�1 �2 �3 �4 �5 �6
i1 i2 i3 i4 i5 i6
j1 j2 j3 j4 j5 j6
à
á
� �[ , ]j is s2 1 2 , s k� �1 2 1, , ,� (ñì. ðèñ. 1) [3]. Ïàðîñî÷åòàíèå M è ïóòü P îáðàçó-
þò ïàðîñî÷åòàíèå M P i j i j
� {[ , ], [ , ],1 2 3 4 � , [ , ]i jk k2 1 2� }.
Äîïóñòèìîå ðåøåíèå ÇÂÏ — ýòî ìàêñèìàëüíîå ïàðîñî÷åòàíèå âçâåøåííîãî
ãðàôà H . Ïîèñê ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ â H ëþáûì ìåòîäîì çàâåðøàåòñÿ
âûïîëíåíèåì óñëîâèÿ òåîðåìû â ñëåäóþùåé ôîðìóëèðîâêå. Ïàðîñî÷åòàíèå M
â ãðàôå H ìàêñèìàëüíî òîãäà è òîëüêî òîãäà, êîãäà â H íå ñóùåñòâóåò óâåëè÷è-
âàþùåãî ïóòè îòíîñèòåëüíî M [1]. Óâåëè÷èâàþùèé ïóòü îòíîñèòåëüíî ïàðîñî-
÷åòàíèÿ M ãðàôà H íàçûâàåòñÿ êðàò÷àéøèì, åñëè åãî ñòîèìîñòü íå áîëüøå ñòîè-
ìîñòè ëþáîãî óâåëè÷èâàþùåãî ïóòè îòíîñèòåëüíî M . Ðåøåíèåì ÇÂÏ ÿâëÿåòñÿ
ìàêñèìàëüíîå ïàðîñî÷åòàíèå M opt ìèíèìàëüíîé ñòîèìîñòè â ãðàôå H .
Ïóñòü M i j i j i jk k k� � ��1 1 2 3 4 2 3 2 2{ }[ , ], [ , ], , [ , ]� — ïàðîñî÷åòàíèå ñ íàèìåíü-
øåé ñóììîé C M k( )�1 âåñîâ k �1 ðåáåð íà ìíîæåñòâå âñåõ ïàðîñî÷åòàíèé ìîùíîñòè
k �1 â äâóäîëüíîì ãðàôå D , k � 2.  ãðàôå H ïàðîñî÷åòàíèþ âçàèìíî-îäíîçíà÷íî
ñîîòâåòñòâóåò ïàðîñî÷åòàíèå {[ , ], [ , ], , [ , ]}� � � � � �1 2 3 4 2 3 2 2� k k� � . Ïîëîæèì
M i j i i j i i j i i jk l l k� ��1 1 1 2 2 1{[ , [ ]], [ , [ ]], , [ , [ ]], , [ ,� � [ ]]ik�1 }, i j il l
[ ], ãäå il —
íîìåð âåðøèíû ìíîæåñòâà X ; j il[ ] — íîìåð âåðøèíû ìíîæåñòâà Y . Â M k�1 âñå
2 2k � âåðøèí ïðîíóìåðîâàíû ðàçíûìè ÷èñëàìè ìíîæåñòâà { }1 2, , ,� n , � �k n� / 2 .
Îáîçíà÷èì M M i j i
k k k k
1
1� �� { }[ , [ ]] ïàðîñî÷åòàíèå, ñîäåðæàùåå ðåáðî
[ , [ ]]i j ik k ñ íàèìåíüøèì âåñîì ñðåäè âñåõ ðåáåð, êîòîðûå ìîæíî ïðèñîåäèíèòü
ê M k�1; Pk — êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü îòíîñèòåëüíî ïàðîñî÷åòàíèÿ
M k�1; M M P
k k k
2
1�
� ; C M
k
( )1 è C M
k
( )2 — ñòîèìîñòè ïàðîñî÷åòàíèé M
k
1 è M
k
2 .
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå, äîêàçàòåëüñòâî êîòîðîãî îòëè÷àåòñÿ
îò äîêàçàòåëüñòâà óòâåðæäåíèÿ â [4] òîëüêî îáîçíà÷åíèÿìè.
Ëåììà 1. Åñëè C M C M
k k
( ) ( )2 1� , òî C M C Mk k
( ) ( )� 2 , èíà÷å C M k( ) �
� C M
k
( )1 ; M k — ïàðîñî÷åòàíèå ñ ìèíèìàëüíîé ñóììîé âåñîâ k ðåáåð â ãðàôå D .
Î÷åâèäíî, äëÿ íåêîòîðîãî k ïàðîñî÷åòàíèå M k ìàêñèìàëüíî. Òîãäà
M M kopt � â ãðàôå H V U� ( , ). Ïðåäñòàâëåííûé ìåòîä ðåøåíèÿ ÇÂÏ ñîñòîèò
â ïîøàãîâîì íàõîæäåíèè â ãðàôå H ïàðîñî÷åòàíèé M k , k M�1, opt , ïóòåì ïî-
ñòðîåíèÿ â äâóäîëüíîì ãðàôå D êàæäîãî êðàò÷àéøåãî óâåëè÷èâàþùåãî ïóòè Pk
îòíîñèòåëüíî M k , íàõîæäåíèÿ ïàðîñî÷åòàíèé M
k�1
1 è M M P
k k k� �
1
2 è
âûáîðà èç íèõ M k�1.
ÎÑÍÎÂÍÀß ÈÄÅß ÀËÃÎÐÈÒÌÀ
Ïàðîñî÷åòàíèå M1 âêëþ÷àåò îäíî ðåáðî, âåñ êîòîðîãî ðàâåí ìèíèìàëüíîìó
çíà÷åíèþ â ìàòðèöå C . Åñëè ìàòðèöà C ñîäåðæèò íåñêîëüêî ýëåìåíòîâ ìèíè-
ìàëüíîãî âåñà, òî M i j i1 1 1� { }[ , [ ] , c c i j ni j i ij1 1
1[ ] | , ,� �min { }, i1 — íîìåð ïåð-
âîé ïî ïîðÿäêó ñòðîêè, êîòîðîé ïðèíàäëåæèò ci j i1 1[ ] .
 ìàòðèöå C ïàðîñî÷åòàíèå M 2 ñ ìèíèìàëüíîé ñóììîé âåñîâ äâóõ ðåáåð
C M( )2
� îïðåäåëÿåòñÿ ñîîòíîøåíèåì
C M C M C M( ) min ( ), ( )2 2
1
2
2� { }. (1)
Ïàðîñî÷åòàíèå M
2
1 âêëþ÷àåò ðåáðî [ , [ ]]i j i1 1 âåñîì ci j i1 1[ ] è ðåáðî [ , [ ]]i j i
1
1
1
1
ìèíèìàëüíîãî âåñà c
i j i1
1
1
1[ ]
â ïîäìàòðèöå, ïîëó÷åííîé óäàëåíèåì èç ìàòðèöû C
ñòðîê è ñòîëáöîâ ñ íîìåðàìè i j i1 1, [ ] : c c i j i j i
i j i ij
1
1
1
1 1 1[ ]
min | , , [ ]� �{ { }}. Â ïàðîñî-
÷åòàíèå M
2
2 âõîäèò ðåáðî [ , ]i s1 âåñîì c c j j ii s i j1 1 1�
min | [ ]{ } è ðåáðî [ , [ ]]r j i1
âåñîì c c i irj i ij i[ ] [ ]min |
1 1 1�
{ }:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 103
(2)
Êîãäà ìàòðèöà C ñîäåðæèò íå ìåíüøå äâóõ ýëåìåíòîâ ìèíèìàëüíîãî âåñà, âû-
áîð ýëåìåíòà ñ íàèìåíüøèì íîìåðîì ñòðîêè óñòðàíÿåò åäèíñòâåííûé ñëó÷àé ïîòåðè
îïòèìàëüíîãî ðåøåíèÿ M 2 . Çíà÷åíèå (1) ìîæåò íå äîñòè÷ü ìèíèìóìà, åñëè
c c c i j n l nl l l l ij, , min | , , ,� � �� � � � � �1 1 2 1 1 3{ } ,
c c c i j l ll l rs ij� � � �
� �2 3 1 2, min | , ,{ }.
Äåéñòâèòåëüíî, ïðè c ci j i l l1 1 1 2[ ] ,� � � ïàðîñî÷åòàíèå � � � �M l l r s2 1 2{ }[ , ], [ , ] ïî-
ëó÷èò âåñ C M c cl l r s( ) ., ,� � �� �2 1 2 Ýòîò âåñ áîëüøå âåñà ïàðîñî÷åòàíèÿ M
2
1 �
� � � �{[ , ], [ , ]}l l l l1 2 3 :
(3)
Íà ðèñ. 2, à èçîáðàæåíî ïàðîñî÷åòàíèå M
2
1 â äâóäîëüíîì ãðàôå D , íà
ðèñ. 2, á — ïîäãðàô ãðàôà D , âêëþ÷àþùèé ïàðîñî÷åòàíèå M M P
2
2
1 1�
, ãäå
P r j i i j i i s1 1 1 1 1� (( , [ ]), [ , [ ]] , ( , )) — ìíîæåñòâî ðåáåð êðàò÷àéøåãî óâåëè÷èâàþùåãî
ïóòè îòíîñèòåëüíî M
1
.
Òàêèì îáðàçîì, â äâóäîëüíîì ãðàôå D M M2 2
1� , åñëè C M ci j i( ) [ ]2
1
1 1
� �
� � � �c C M c c
i j i i s rj i
1
1
1
1
1 12
2
[ ] [ ]( ) , è â ñëó÷àå íåâûïîëíåíèÿ óñëîâèÿ M M2 2
2� .
Ïî ìàòðèöå Ñ è ïàðîñî÷åòàíèÿì M
2
1, M
2
2 íàéäåì ïàðîñî÷åòàíèå M 3 ñ ìè-
íèìàëüíîé ñóììîé C M( )3 âåñîâ òðåõ ðåáåð. Àíàëîãè÷íî (1) ïðåäñòàâèì
C M C M C M( ) min ( ), ( )3 3
1
3
2� { }.
×òîáû ïîëó÷èòü M 3 è C M( )3 , íàéäåì c c i j i j i i j ii j i ij2 2 1 1 1
1
1
1
[ ] min | , , [ ], , [ ]� �{ { }}.
Ïóñòü C M c c C M c ci j i i j i i s rj i( ) ( )[ ] [ ] [ ]2
1
2
2
1 1 1
1
1
1
1 1
� � � � � . Òîãäà äëÿ ïàðîñî÷åòà-
íèé M M i j i
3
1
2
1
2 2� �{ }[ , [ ]] è � � �M M i j i3 2
2
2 2{ }[ , [ ]] ñïðàâåäëèâî íåðàâåíñòâî
C M C M c C M c c ci j i i s rj i i j i( ) ( ) ( )[ ] [ ] [3
1
2
1
32 2 1 1 2 2
� � � � � � � ] .
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
i1 s j i[ ]1 j i[ ]
1
1
�
i1 � ci s1
ci j i1 1[ ]
i s1 � � c
i j i1
1
1
1[ ]
c j i i[ ]1 1
�
r j i� [ ]
1
1 crj i[ ]1
�
�
l �1 l �2 l �3
� crs
l � cl l, �1
l �1 � cl l� �1 2,
l �2 � cl l� �2 3,
�
�
Äëÿ âûáîðà áîëåå òî÷íîé âåðõíåé ãðàíèöû C M( )
3
1 ñòîèìîñòè C M( )3 îïòè-
ìàëüíîãî òåêóùåãî ðåøåíèÿ M 3 , ÷åì C M( )�3 , ïîñòðîèì êðàò÷àéøèé óâåëè÷èâà-
þùèé ïóòü P2 îòíîñèòåëüíî M
2
1, íàéäåì M M P
3
2
2
1
2�
è C M( )
3
2 . Î÷åâèäíî,
M M3 3
1� , åñëè C M C M( ) ( )
3
1
3
2� , â ñëó÷àå íåâûïîëíåíèÿ óñëîâèÿ M M3 3
2� .
Ïðåäïîëîæèì, ÷òî
C M c c C M c ci s rj i i j i i j i
( ) ( )[ ] [ ] [ ]2
2
2
1
1 1 1 1 1
1
1
1� � � � � .
Òàê êàê c c
i j i i j i
1
1
1
1
2 2[ ] [ ]� , òî ñòîèìîñòè ïàðîñî÷åòàíèé M M i j i
3
1
2
2
1
1
1
1� �{ }[ , [ ]]
è � � �M M i j i3 2
1
2 2{ }[ , [ ]] óäîâëåòâîðÿþò íåðàâåíñòâó C M C M( ) ( )
3
1
3� � . Ïîýòî-
ìó âåëè÷èíà C M( )
3
1 ÿâëÿåòñÿ áîëåå òî÷íîé îöåíêîé ñâåðõó C M( )3 , ÷åì
C M( )�3 . Äëÿ íàõîæäåíèÿ M 3 ïîñòðîèì êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü P2
îòíîñèòåëüíî M
2
2 , îïðåäåëèì ïàðîñî÷åòàíèå M M P
3
2
2
2
2�
è åãî ñòîèìîñòü
C M( )
3
2 . Ñëåäîâàòåëüíî, M M3 3
1� , åñëè C M C M( ) ( )
3
1
3
2� , è â ñëó÷àå íåâûïîë-
íåíèÿ óñëîâèÿ M M3 3
2� .
Èçëîæåííûé ñïîñîá íàõîæäåíèÿ M 3 è C M( )3 óêëàäûâàåòñÿ â ñõåìó ðåøå-
íèÿ ÇÂÏ ñ ïîìîùüþ ðàâåíñòâà
C M C M C M k Mk k k
( ) min ( ), ( ) , | |� � �{ } opt
1 2 2 . (4)
Ïðè k M� | |opt õîòÿ áû îäíî èç çíà÷åíèé C M
k
( )1 èëè C M
k
( )2 äîñòèãàåò ìèíè-
ìóìà; M Mk � opt , åñëè ïðè íåêîòîðîì k C M k( )
� , à ïðè k �1 C M
k
( )� �
1
1
� � ��C M
k
( )
1
2 .
ÑÕÅÌÀ ÐÅØÅÍÈß ÇÀÄÀ×È
Íàçîâåì âåðøèíó j Yl � îòîáðàæåíèåì â ãðàôå D íà÷àëà il ðåáðà [ [ [ ]]]i j il l ïà-
ðîñî÷åòàíèÿ M i j i i j i i j i i jk l l k� ��1 1 1 2 2 1{[ , [ ]], [ , [ ]] , , [ , [ ]] , , [ ,� � [ ]]ik�1 } è îáî-
çíà÷èì åå �jl . Âåðøèíó i Xm � íàçîâåì îòîáðàæåíèåì êîíöà âåðøèíû j il[ ]
ýòîãî ðåáðà è îáîçíà÷èì åå �im .
Ïóñòü I i l k J j i l kk l k l� �� � � � � �1 11 1 1 1{ } { }| , , [ ] | , — ìíîæåñòâà âåðøèí
ïàðîñî÷åòàíèÿ M k�1, à � �� �I Jk k1 1, — ìíîæåñòâà èõ îòîáðàæåíèé, I I Xk k� �� �1 1, ,
J J Yk k� �� �1 1, . Ïîñòðîåíèå M opt íà÷èíàåòñÿ ñ íàõîæäåíèÿ M i j i1 1 1� { }[ , [ ] è
óäàëåíèÿ ðåáåð, èíöèäåíòíûõ îòîáðàæåíèÿì �j1 è �i1 âåðøèí i1 è j i[ ]1 ñîîòâåò-
ñòâåííî.  ìàòðèöå C óäàëåííûå ðåáðà ïðèíèìàþò âåñ, ðàâíûé áåñêîíå÷íîñòè.
×òîáû èç (4) îïðåäåëèòü M k , ñíà÷àëà íàõîäèòñÿ M M i j i
k k k k
1
1� �� { }[ , [ ] ,
ãäå
c c i I I j J Ji j i ij k k k kk k[ ] min | ,� � � � � � �� � � �{ }1 1 1 1 , (5)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 105
Ðèñ. 2
1 2 3 4 5 6
1 2 3 4 5 6
j i[ ]1 j i[ ]1
1
i1 i1
1
s j i[ ]1
i1 r
à á
1 2 3 4 5 6
1 2 3 4 5 6
ãäå cij — ýëåìåíòû ìàòðèöû C . Â ïîäãðàôå ãðàôà D óäàëÿþòñÿ ðåáðà, èíöè-
äåíòíûå îòîáðàæåíèÿì � �j ik k, âåðøèí ik è j ik[ ] ñîîòâåòñòâåííî. Êàæäîå óäàëÿ-
åìîå ðåáðî ïîëó÷àåò â ìàòðèöå C âåñ, ðàâíûé áåñêîíå÷íîñòè.
×òîáû íàéòè M
k
2 , äëÿ êàæäîé âåðøèíû i I Ik k k� � �� �1 1 ôîðìèðóåòñÿ ïîäãðàô
D X Y Ei i i ik k k k
� ( , , ) ãðàôà D . Îí âêëþ÷àåò ïîäìíîæåñòâî E
ik
1 ñâîáîäíûõ ðåáåð
( , [ ])i j ik l , l k� �{ }1 2 1, , ,� , ïîäìíîæåñòâî E
ik
2 âñåõ ðåáåð, ñîåäèíÿþùèõ âåðøèíû
ìíîæåñòâà I k�1 ñ âåðøèíàìè ìíîæåñòâà Jk�1, è ïîäìíîæåñòâî E
ik
3 ñâîáîäíûõ ðå-
áåð ( , ),i j j jl s s k
, j Y J J j l ks k k k� � � � � � �� �{ { { }}} { }1 1 1 2 1, , , ,� , ñ âåñàìè
c c j Y J J ji j i j k k kl s l
� � � � � �� �min |{ { } { }}1 1 , (6)
îáðàçóþùèõ ìíîæåñòâî âåðøèí Y
ik
1 . Ñëåäîâàòåëüíî, ïîäãðàô D X Y Ei i i ik k k k
� ( , , )
âêëþ÷àåò ìíîæåñòâà âåðøèí X i I Y Y Ji k k i i kk k k
� � � �� �{ } 1
1
1, è ïîäìíîæåñòâà
ðåáåð E E E
i i ik k k
1 2 3� � .
Ïîäãðàô Dik
ïðåäñòàâëåí íà ðèñ. 3, à. Ñâîáîäíûå ðåáðà ( , [ ])i j ik 1 , ( , [ ])i j ik l ,
( , [ ])i j ik k�1 îáðàçóþò ïîäìíîæåñòâî E
ik
1 . Ðåáðà ( , [ ]), ( , ]), ( , [ ])i j i i j i j il k l1 1 1 1[ � ,
( , [ ]), ( , [ ])i j i i j il k k� �1 1 1 è âñå ðåáðà ïàðîñî÷åòàíèÿ M k�1 âõîäÿò â ïîäìíîæåñò-
âî E
ik
2 . Ïîäìíîæåñòâî E
ik
3 âêëþ÷àåò ðåáðà ( , ), ( , ), ( , )i j i j i js l r k r1 1� .  ïîäãðàôå
D X Y Ei i i ik k k k
� ( , , ) èìååì X i i i ii k l kk
� �{ }, , ,1 1 , Y j j
i s r
k
1 � { }, , Y Yi ik k
� �1 { j i[ ],1
j i j il k[ ], [ ]�1 }.
Ïîäãðàô Dik
ñòðîèòñÿ äëÿ íàõîæäåíèÿ â íåì ïóòè Pik
, êðàò÷àéøåãî ñðåäè
âñåõ óâåëè÷èâàþùèõ ïóòåé îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M k�1. Ýòîò ïóòü äîë-
æåí íà÷èíàòüñÿ â âåðøèíå ik è çàêàí÷èâàòüñÿ â íåêîòîðîé âåðøèíå j Ys ik
� 1 ,
j js k
. Åñëè ñóùåñòâóåò ïóòü Pik
, òî ñîãëàñíî ëåììå 1 M P Mi i kk k
�
�1 — ïà-
ðîñî÷åòàíèå, äîñòàâëÿþùåå ìèíèìàëüíóþ ñóììó âåñîâ k ðåáåð â ïîäãðàôå Dik
.
 èñõîäíîì ãðàôå H ïóòè Pik
ñîîòâåòñòâóåò ïàðîñî÷åòàíèå òîé æå ìîùíîñòè è
ñ òàêèìè æå âåñàìè ðåáåð, ÷òî è â Dik
. Ïîñòðîåíèå ïîäãðàôà Dik
è ïîèñê â íåì
ïóòè Pik
ïîâòîðÿåòñÿ äëÿ êàæäîé âåðøèíû i X I I
k k k� � � �� �{ }1 1 è çàâåðøàåòñÿ
âûáîðîì ïàðîñî÷åòàíèÿ M
k
2 ñòîèìîñòüþ
C M C M i I I
k i k k k
k
( ) min ( ) |2 2
1 1� � � �� �{ }. (7)
106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ðèñ. 3
ik il
ik�1
j r
i1 j s
à á
js jk j
1
' j i[ ]1 j
l
' j il[ ] j
k �1
' j ik[ ]�1 jr
is ik i1 �i1 il �il ik �1 � �ik 1 ir
Ïîèñê ïóòè Pik
óïðîùàåòñÿ âî âñïîìîãàòåëüíîì îðãðàôå ( , )Z Ai ik k
, ïîëó÷åí-
íîì â ðåçóëüòàòå ïðåîáðàçîâàíèÿ Dik
. Îðãðàô ( , )Z Ai ik k
âêëþ÷àåò ìíîæåñòâî âåð-
øèí Z i I Yi k k ik k
� � ��{ } 1
1 è ìíîæåñòâà äóã A A A Ai i i ik k k k
� � �1 2 3 . Â ïîäìíîæåñò-
âî A
ik
1 âõîäèò äóãà ( , )i ik l , i X I I i Ik k k l k� � � � �� � �{ }1 1 1, , òîãäà è òîëüêî òîãäà,
êîãäà âåðøèíà j il[ ] ðåáðà ( , [ ])i j ik l ÿâëÿåòñÿ íàïàðíèêîì âåðøèíû il . Äóãå ( , )i ik l
ïðèñâàèâàåòñÿ âåñ c i i c ck l i j i i j ik l l l
( , ) [ ] [ ]� � . Äóãà ( , ), ,i i i i Id l d l k� �1, âõîäèò â
A
ik
2 , åñëè è òîëüêî åñëè âåðøèíà j il[ ] ðåáðà ( , [ ])i j id l ÿâëÿåòñÿ íàïàðíèêîì âåð-
øèíû il . Äóãà ( , )i id l ïîëó÷àåò âåñ c i i c cd l i j i i j id l l l
( , ) [ ] [ ]� � . Ïîäìíîæåñòâî Ai3
ñîäåðæèò âñå äóãè ( , ), ,i j i I j Yl s l k s ik
� ��1
1 , åñëè âåðøèíû il è js ñîåäèíåíû ðåá-
ðîì â Dik
. Äóãà ( , )i jl s èìååò âåñ c i j cl s i jl s
( , ) � (ðèñ. 3, á). Íåòðóäíî óáåäèòüñÿ,
÷òî ïðè íåîòðèöàòåëüíûõ âåñàõ ðåáåð ãðàôà D ïóòü Pik
— êðàò÷àéøèé ñðåäè
âñåõ ïðîñòûõ ïóòåé èç âåðøèíû ik â âåðøèíû ìíîæåñòâà Y
ik
1 îðãðàôà ( , )Z Ai ik k
.
Ïîèñê Pik
âûïîëíÿåòñÿ àëãîðèòìîì Äåéêñòðû.
Îáîçíà÷èì � �D
k
ïîäãðàô äâóäîëüíîãî ãðàôà ( , , )X Y E , ïîðîæäåííûé ìíî-
æåñòâàìè âåðøèí I i l kk l� �{ }| ,1 è J j i l kk l� �{ }[ ] | ,1 ïàðîñî÷åòàíèÿ M k �
� �{ }[ , [ ]] | ,i j i l kl l 1 .
ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ
Ïðåäñòàâèì àëãîðèòì íàõîæäåíèÿ âî âçâåøåííîì ãðàôå H V U� ( , ) ìàêñèìàëüíî-
ãî ïàðîñî÷åòàíèÿ M opt ñ ìèíèìàëüíîé ñóììîé âåñîâ åãî ðåáåð; C cij n� [ ] —
ñèììåòðè÷íàÿ ìàòðèöà âåñîâ ðåáåð ãðàôà H , â êîòîðîé c c Rij ji� � �
0
, åñëè
{ }i j U, � , i j
, è c cij ji� � � â ïðîòèâíîì ñëó÷àå, R
0
� — ìíîæåñòâî íåîòðèöà-
òåëüíûõ äåéñòâèòåëüíûõ ÷èñåë. Ðåøåíèå M opt âçàèìíî-îäíîçíà÷íî ñîîòâåò-
ñòâóåò ìàêñèìàëüíîìó ïàðîñî÷åòàíèþ M i j i i j i l kk l l l l�
�{ }[ , [ ] | [ ], ,1 äâó-
äîëüíîãî âçâåøåííîãî ãðàôà ( , , )X Y E , | | | | | | , | | | |X Y V E U� � � 2 ,
i X j i Yl l� �, [ ] , ïîñòðîåííîãî äëÿ ìàòðèöû C.
 ìàòðèöå C íàéòè c c i j ni j i ij1 1
1[ ] min | , ,� �{ }, i1 — íîìåð ïåðâîé ïî ïîðÿäêó
ñòðîêè, ñîäåðæàùåé ìèíèìàëüíûé ýëåìåíò; M i j i1 1 1� { }[ , [ ] , I i1 1� { }, J j i1 1� { }[ ] ,
� � �I j i X1 1{ }[ ] , � � �J i Y1 1{ } ; óäàëèòü âñå ðåáðà, èíöèäåíòíûå âåðøèíàì
j i I[ ]1 1� � , i J1 1� � ; D1 — ïîäãðàô, ñîäåðæàùèé ðåáðî [ , [ ]]i j i1 1 , � � �D D1 1, k �1.
Àëãîðèòì ðåøåíèÿ ÇÂÏ ñîñòîèò èç ñëåäóþùèõ øàãîâ.
S1. k k� �1; åñëè � �k n� / 2 , òî M M kopt � �1.
S2. Íàéòè ci j ik k[ ] ïî ôîðìóëå (5); åñëè ci j ik k[ ] � � , òî êîíåö: M M kopt � �1;
M M i j i
k k k k
1
1� �� { }[ , [ ]] , âû÷èñëèòü C M
k
( )1 .
S3. Äëÿ êàæäîé âåðøèíû i X I Ik k k� � � �� �{ }1 1 ïîñòðîèòü ïîäãðàô Dik
è ïî-
ñëå ïðåîáðàçîâàíèÿ åãî âî âñïîìîãàòåëüíûé îðãðàô ( , )Z Ai ik k
íàéòè ïóòü Pik
,
êðàò÷àéøèé èç ïóòåé, ñîåäèíÿþùèõ âåðøèíó ik ñ âåðøèíàìè j Ys � �
� � � �� �{ } { }J J jk k k1 1 . Êàæäàÿ âåðøèíà js ÿâëÿåòñÿ êîíöîì ðåáðà ( , )i jl s ,
i I l kl k� � ��1 1 2 1, , , ,{ }� , âåñîì ci jl s
, ðàâíûì (6). Îïðåäåëèòü M P M
i i k
k k
2
1�
�
è C M
ik
( )2 . Åñëè â ãðàôå Dik
íå ñóùåñòâóåò ïóòè Pik
, òî ïîëîæèòü M
ik
2 � � . Èç (7)
íàéòè M
k
2 è C M
k
( );2 åñëè äëÿ âñåõ ik C M
ik
( )2 � � , òî C M
k
( )2 � � , M
k
2 � �.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 107
S4. Åñëè C M C M
k k
( ) ( )1 2� � � , òî êîíåö: M M kopt � �1, èíà÷å åñëè
C M C M
k k
( ) ( )1 2� , òî M Mk k
� 1, I I i J J j ik k k k k k� � � �� �1 1{ } { }, [ ] , � �I k
� � � ��I ik k1 { }, � � � ��J J jk k k' 1 { }, ãäå âåðøèíû � �i Xk è � �j Yk — îòîáðàæåíèÿ ñî-
îòâåòñòâåííî êîíöà j ik[ ] è íà÷àëà ik ðåáðà [ , [ ]];i j ik k óäàëèòü ðåáðà, èíöèäåíò-
íûå âåðøèíàì �ik è �jk ; ñôîðìèðîâàòü ïîäãðàô � �Dk , ïîðîæäåííûé ìíîæåñòâîì
âåðøèí I Jk k� , è ïåðåéòè ê øàãó S1, èíà÷å M Mk k
� 2 ; îïðåäåëèòü I k , Jk , � �I Jk k, ;
óäàëèòü âñå ðåáðà, èíöèäåíòíûå âåðøèíàì ìíîæåñòâà � � �I Jk k , è ñôîðìèðîâàòü
ïîäãðàô � �Dk , ïîðîæäåííûé ìíîæåñòâîì âåðøèí I Jk k� ; ïåðåéòè ê øàãó S1.
Àëãîðèòì ïðåäñòàâëåí ïîñëåäîâàòåëüíîñòüþ èòåðàöèé. Ïåðâàÿ èòåðàöèÿ àë-
ãîðèòìà çàâåðøàåòñÿ íà ïîäãîòîâèòåëüíîì ýòàïå íàõîæäåíèåì ìèíèìàëüíîãî
ýëåìåíòà â Ñ, îáðàçóþùåãî ïàðîñî÷åòàíèå M1. Êàæäàÿ ñëåäóþùàÿ èòåðàöèÿ
âêëþ÷àåò øàãè S2–S4 äëÿ ïîñòðîåíèÿ ïàðîñî÷åòàíèÿ M k , k M� 2, | |opt , ñ ìèíè-
ìàëüíîé ñóììîé Ñ M k( ) âåñîâ k ðåáåð.
Òåîðåìà 1. Ïîñëå óïîðÿäî÷åíèÿ ïî íåóáûâàíèþ çíà÷åíèé ýëåìåíòîâ, ðàñïî-
ëîæåííûõ íàä ãëàâíîé äèàãîíàëüþ ìàòðèöû ñòîèìîñòåé C cij n� [ ] ãðàôà H , ÇÂÏ
êîððåêòíî ðåøàåòñÿ çà âðåìÿ O n( )3 .
Äîêàçàòåëüñòâî. Ñîãëàñíî ëåììå 1 íóæíî ñíà÷àëà ïîêàçàòü, ÷òî M Mk k
� 2 ,
åñëè C M C M
k k
( ) ( )2 1� . Äåéñòâèòåëüíî, äëÿ êàæäîé ñâîáîäíîé âåðøèíû ik àëãî-
ðèòì ñòðîèò ïîäãðàô Dik
, âêëþ÷àþùèé ìíîæåñòâî âñåõ óâåëè÷èâàþùèõ ïóòåé
èç ik îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M k Mk� �1 2, , | |opt , âûáèðàåò ñðåäè íèõ êðàò-
÷àéøèé ïóòü Pik
è îïðåäåëÿåò M
ik
2 è C M
ik
( )2 . Êîððåêòíîñòü îäíîêðàòíîãî îáðàùåíèÿ
ê ik ñëåäóåò èç ïðèâåäåííîãî â [1] äîêàçàòåëüñòâà, ñîãëàñíî êîòîðîìó ïðè îòñóòñòâèè
â ãðàôå óâåëè÷èâàþùåãîñÿ ïóòè èç ñâîáîäíîé âåðøèíû íå ñóùåñòâóåò óâåëè÷èâàþùåãî
ïóòè èç ýòîé âåðøèíû íà âñåõ ïîñëåäóþùèõ ýòàïàõ ïîñòðîåíèÿ ïàðîñî÷åòàíèÿ.
Àëãîðèòì çàâåðøàåò ðàáîòó íà k-é èòåðàöèè. Åñëè � �k n� / 2 , òî ïîñòðîåí-
íîå ïàðîñî÷åòàíèå M k ìàêñèìàëüíî.  ïðîòèâíîì ñëó÷àå íå ñóùåñòâóåò ïóòè èç
êàæäîé ñâîáîäíîé âåðøèíû ik â ñîîòâåòñòâóþùåì åé îðãðàôå ( , )Z Ai ik k
, à â D íå
ñóùåñòâóåò óâåëè÷èâàþùèõ ïóòåé îòíîñèòåëüíî òåêóùåãî ïàðîñî÷åòàíèÿ M k�1.
Îòñþäà ñëåäóåò, ÷òî M k�1 ìàêñèìàëüíî [1].
Ðåøåíèå M opt ÇÂÏ îïðåäåëÿåòñÿ èç ìàòðèöû C , ñîîòâåòñòâóþùåé êàê äâó-
äîëüíîìó D X Y E� ( , , ), òàê è ïðîèçâîëüíîìó H V U� ( , ) ãðàôàì.
Îöåíèì ñâåðõó âðåìÿ ðàáîòû àëãîðèòìà. Îíî ìàêñèìàëüíî, êîãäà n-âåðøèí-
íûé ãðàô H ïîëíûé è, ñëåäîâàòåëüíî, � �| | /M nopt � 2 .
Åñëè óïîðÿäî÷èòü ïî íåóáûâàíèþ çíà÷åíèÿ ýëåìåíòîâ, ðàñïîëîæåííûõ íàä ãëàâ-
íîé äèàãîíàëüþ ìàòðèöû C , òî äëÿ âûïîëíåíèÿ ïîäãîòîâèòåëüíîãî ýòàïà àëãîðèòìà,
êîòîðûé îïðåäåëÿåò ci j i1 1[ ] , ïîòðåáóåòñÿ âðåìÿ O n n n n(( ( ) / ) log ( ( ) / ))� �1 2 1 2
2
.
Íàèáîëüøåå ÷èñëî îïåðàöèé ñðàâíåíèÿ íà øàãå S2 k-é èòåðàöèè,
� �k n� 2 2, / , ðàâíîå 2 2 1( ( ))n k� � , äîñòèãàåòñÿ íà ìàòðèöå C , â êîòîðîé
c ci j i12 1 1
� [ ] , c c c ci j i k k i j ik k34 2 1 22 2
� ��[ ] , [ ], ,� . ×òîáû îïðåäåëèòü � �n / 2 1� ýëå-
ìåíòîâ ìàòðèöû C , îáðàçóþùèõ âìåñòå ñ ýëåìåíòîì [ , [ ]]i j i1 1 ïàðîñî÷åòàíèå M
k
1,
� �k n� / 2 , íåîáõîäèìî âûïîëíèòü � �t n n n n1 2 2 2 4 2 2 2 1� � � � � � � �( ) ( ) ( ( / ))�
ñðàâíåíèé. Ñëåäîâàòåëüíî, t O n1
2� ( ).
Ïîñòðîåíèå ãðàôà Dik
íà øàãå S3 ïðè k � 2 òðåáóåò n � 4 ñðàâíåíèé äëÿ íà-
õîæäåíèÿ çíà÷åíèé ci jl s
è îäíó îïåðàöèþ ñëîæåíèÿ äëÿ âû÷èñëåíèÿ C M
ik
( )2 . Íà
ýòîì øàãå ïðè k � 2 íóæíî ïîñòðîèòü n �2 ãðàôîâ Dik
, âû÷èñëèòü n �2 ñîîòâåò-
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
ñòâóþùèõ èì çíà÷åíèé C M
ik
( )2 è íàéòè çíà÷åíèå C M
k
( )2 . Ïîýòîìó C M( )
2
2 îïðå-
äåëÿåòñÿ âûïîëíåíèåì ( )( ) ( )n n n n� � � � � � �3 2 3 2 12 îïåðàöèé. Äëÿ íàõîæäå-
íèÿ (1) íà øàãå S4 òðåáóåòñÿ îäíî ñðàâíåíèå. Òàêèì îáðàçîì, âû÷èñëåíèå C M( )2
è ïîñòðîåíèå M 2 âûïîëíÿåòñÿ çà âðåìÿ t O n2
2� ( ).
Äëÿ � �k n� 3 2, / íà øàãå S3 íóæíî ïîñòðîèòü n k� �2 1( ) ãðàôîâ Dik
. Ãðàô
Dik
ñòðîèòñÿ â ðåçóëüòàòå âûïîëíåíèÿ n k� � �2 1 2( ) ñðàâíåíèé ïî íàõîæäåíèþ (6)
äëÿ êàæäîé èç k �1 åãî âåðøèí i Il k� �1. Êðîìå òîãî, íà øàãå S3 ãðàô Dik
çà âðåìÿ
c k1 1( )� ïðåîáðàçóåòñÿ â îðãðàô ( , )Z Ai ik k
, â êîòîðîì ïðè òðóäîåìêîñòè c k2
21( )�
èùåòñÿ ïóòü Pik
, åãî äëèíà Ñ Pik
( ) è ïàðîñî÷åòàíèå M
ik
2 ñòîèìîñòüþ Ñ M
ik
( )2 ,
c c k1 2 1, � � . ×òîáû âûáðàòü M k , äîñòàòî÷íî n k� � �2 1 1( ) ñðàâíåíèé äëÿ íàõîæ-
äåíèÿ C M
k
( )2 è îäíó îïåðàöèþ ñðàâíåíèÿ C M
k
( )1 è C M
k
( )2 , âûïîëíÿåìóþ íà
øàãå S4. Øàã S4 çàâåðøàåòñÿ ôîðìèðîâàíèåì ãðàôà � �Dk çà âðåìÿ c k c k3 3, � .
Îïðåäåëèì ÷èñëî îïåðàöèé tk1, âûïîëíÿåìûõ íà øàãå S3, è ÷èñëî îïåðàöèé
tk2 , âûïîëíÿåìûõ íà øàãå S4, äëÿ � �k n� 3 2, / :
t n k k n k c k n k c kk1 1 32 1 1 2 1 2 1� � � � � � � � � � �[ ( )][( )( ) ( )] ( ) ,
t n k c kk2 2
22 1 1� � � �[ ( )] ( ) .
Òàê êàê äëÿ ëþáîãî n è � �k n� 3 2, /
[ ( )]( )( )n k k n k n� � � � �2 1 1 2 2 ,
[ ( )] ( ) [ ( )]( )n k c k n k k n� � � � � � � �2 1 1 2 1 11
2 2 ,
n k c k n k k c n c nk k� � � � � � � � �2 1 2 13
2
1 1( ) ( ) , ,
[ ( )] ( ) [ ( )]( ) ,n k c k n k k c n c nk k� � � � � � � � �2 1 1 2 1 12
2 3
2
2
2 ,
èìååì
t n c n O nk k1
2
1
22� � � ( ), t O nk2
2� ( ).
Òðóäîåìêîñòü âûïîëíåíèÿ � �n / 2 1� èòåðàöèé, íà÷èíàÿ ñî âòîðîé, îöåíèâà-
åòñÿ ÷èñëîì ýëåìåíòàðíûõ äåéñòâèé, ðàâíûì ñóììå, ñîñòîÿùåé èç � �2 2n / ñëàãà-
åìûõ,
� �
t t t t tk k
k
n
� � � �
�
�1 2 1 2
3
2
( )
/
, â êîòîðîé êàæäîå ñëàãàåìîå îãðàíè÷åíî ïîëè-
íîìîì âòîðîé ñòåïåíè. Ïîýòîìó t O n� ( )3 . �
Ðàññìîòèì ïðèìåð.
Äëÿ äåìîíñòðàöèè ðàáîòû àëãîðèòìà âûáðàí ïðèìåð ÇÂÏ èç [1] ñ ìàòðèöåé
ñòîèìîñòåé ïîëíîãî ãðàôà
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 109
1 2 3 4 5 6 7 8
1 � 19 8 8 18 18 25 29
2 19 � 0 8 10 4 15 18
3 8 0 � 4 8 2 15 18
C � 4 8 8 4 � 2 10 15 16
5 18 10 8 2 � 10 22 25
6 18 4 2 10 10 � 19 19
7 25 15 15 15 22 19 � 37
8 29 18 18 16 25 19 37 �
Îïðåäåëèì c c i jij23 1 8 0� � �min | , ,{ } , M1 2 3� { }[ , ] , I1 2� { }, J1 3� { },
� �I1 3{ }, � �J1 2{ }, C M c( )1 23 0� � . Â ãðàôå D óäàëèì ðåáðà, èíöèäåíòíûå âåð-
øèíàì 3 1� �I è 2 1� �J , îáðàçóÿ ïîäãðàô D1.
S1. k � 2.
S2. c c i jij45 2 3 2�
�min | , ,{ } , M M2
1
1 4 5 2 3 4 5� � �{ } { }[ , ] [ , ], [ , ] , C M( )2
1 2� .
S3. Äëÿ âåðøèí 1, 4, 5, 6, 7, 8, îáðàçóþùèõ ìíîæåñòâî X I I� � �( )1 1 , ñòðîÿò-
ñÿ ïîäãðàôû D D D D D D1 4 5 6 7 8, , , , , è ñîîòâåòñòâóþùèå èì îðãðàôû, â êîòîðûõ
âûïîëíÿåòñÿ ïîèñê êðàò÷àéøèõ óâåëè÷èâàþùèõ ïóòåé P1, P4 , P5 , P6 , P7 , P8 îò-
íîñèòåëüíî ïàðîñî÷åòàíèÿ M1. Äëÿ êàæäîãî ïóòè Pi , i X I I� � � �( )1 1 , åñëè îí ñó-
ùåñòâóåò, îïðåäåëÿåòñÿ ïàðîñî÷åòàíèå M i
2 è åãî ñòîèìîñòü C M i( )2 .
S4. Òàê êàê M M
2
1
2
2� , ê ïîäãðàôó D1 äîáàâëÿåòñÿ ðåáðî [ , ]4 5 , I 2 2 4� { , },
J2 3 5� { , }, � �I 2 3 5{ , }, � �J2 2 4{ , }, óäàëÿþòñÿ ðåáðà, èíöèäåíòíûå âåðøèíàì
5 2� �I , 4 2� �J . Â ðåçóëüòàòå ïîñòðîåí ãðàô � �D2 , ïîðîæäåííûé ìíîæåñòâîì âåð-
øèí I 2 è J2 (ðèñ. 4, à).
Ðàññìîòðèì ïîäãðàô D4 è ñîîòâåòñòâóþùèé åìó âñïîìîãàòåëüíûé îðãðàô
( , )Z A4 4 . Åäèíñòâåííîå ðåáðî ( , )2 6 â D4 îáðàçóåò ïîäìíîæåñòâî ñâîáîäíûõ ðå-
áåð E
4
3 . Åãî âåñ c26 4� îïðåäåëÿåòñÿ èç (6), Y
4
1 6� { }. Ìíîæåñòâî ðåáåð
{ }( , ), [ , ], ( , )4 3 2 3 2 6 ïóòè P Z A4 4 44 2 6� �( , , ) ( , ) è ïàðîñî÷åòàíèå M1 2 3� { }[ , ] îá-
ðàçóþò ïàðîñî÷åòàíèå M
4
2 4 3 2 6� { }[ , ], [ , ] ñòîèìîñòüþ C M( )
4
2 , ïîëó÷åííîé
èç (7). Òàêèì îáðàçîì, M M C M c c
2
2
4
2
2
2
43 16 4 4 8� � � � � �, ( ) .
Äëÿ k � 3 ïî ôîðìóëå (4) íàõîäèòñÿ c c i jij16 2 3 4 5 18�
�min | , , , , ,{ }
M M
3
1
2 1 6� �{ }[ , ] , C M c c c( )
3
1
23 45 16 0 2 18 20� � � � � � � (ðèñ. 4, á).
×òîáû îïðåäåëèòü M
3
2 , äëÿ âåðøèí i X I Ik � � � � �( ) , , ,3 3 1 6 7 8{ } ôîðìèðóþò-
ñÿ ïîäãðàôû D D Di ik k
, � � �2 , â êîòîðûõ ñ ïîìîùüþ îðãðàôîâ ( , )Z Ai ik k
íàõîäÿòñÿ
êðàò÷àéøèå óâåëè÷èâàþùèå ïóòè Pik
îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M 2 , ïàðîñî÷åòà-
íèÿ M
ik
2 è èõ ñòîèìîñòè C M
ik
( )2 . Ïîäãðàô D1 ñîäåðæèò êðàò÷àéøèé óâåëè÷èâàþ-
ùèé ïóòü îòíîñèòåëüíî M 2 , ñîîòâåòñòâóþùèé ïóòè P1 1 2 6� ( , , ) â îðãðàôå ( , )Z A1 1
è äîñòàâëÿþùèé ñòîèìîñòü ïàðîñî÷åòàíèÿ M
1
2 , íå áîëüøóþ ñòîèìîñòåé ïàðîñî÷å-
òàíèé M M M
6
2
7
2
8
2, , . Òàê êàê P1 1 3 2 3 2 6� { }( , ), [ , ], ( , ) , M 2 2 3 4 5� { }[ , ], [ , ] , òî
M
1
2 1 3 4 5 2 6� { }[ , ], [ , ], [ , ] , C M c c c C M C M( ) , ( ) ( )
1
2
13 45 26 3
2
1
38 2 4 14� � � � � � � � .
 ýòîì ñëó÷àå C M C M( ) ( )
3
2
3
1� , M M3 3
2� , I 3 1 4 2� { }, , , J3 3 5 6� { }, , ,
� �I 3 3 5 6{ }, , , � �J3 1 2 4{ }, , . Óäàëÿþòñÿ ðåáðà, èíöèäåíòíûå âåðøèíàì ìíîæåñòâà
�I 3 è �J3 . Íà ðèñ. 5, à èçîáðàæåí ïîäãðàô � �D3 , ïîðîæäåííûé ìíîæåñòâîì âåðøèí
I 3 è J3 .
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ðèñ. 4
1 2 3 4 5 6
1 2 3 4 5 6
2 2� �J 4 2� �J
3 2� �I 5 2� �I
à á
1 2 3 4 5 6
1 2 3 4 5 6
2 2� �J 4 2� �J
3 2� �I 5 2� �I
Äëÿ k � 4 èìååì c c i jij78 1 2 3 4 5 6 37�
�min | , , , , , ,{ } , M
4
1 1 3 2 6 4 5� {[ , ], [ , ], [ , ],
[ , ]7 8 }, Ñ M( )
4
1 3 4 2 37 51� � � � � (ðèñ. 5, á).
Íàõîæäåíèå ïàðîñî÷åòàíèÿ M
4
2 íà÷èíàåòñÿ ñ ïîñòðîåíèÿ äëÿ âåðøèí ìíî-
æåñòâà X I I� � � �( ) ,3 3 7 8{ } ïîäãðàôîâ D D7 8, è ñîîòâåòñòâóþùèõ èì îðãðàôîâ
( , ), ( , )Z A Z A7 7 8 8 . Íà ðèñ. 6, à èçîáðàæåí ïîäãðàô D8 , à íà ðèñ. 6, á — îðãðàô
( , )Z A8 8 .
Ïóòü P8 8 2 7� ( , , ) â îðãðàôå ( , )Z A8 8 ÿâëÿåòñÿ êðàò÷àéøèì.  ïîäãðàôå D8 îí
ïðåäñòàâëåí êàê êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü P8 8 6 2 6 2 7� (( , ), [ , ], ( , )) îòíî-
ñèòåëüíî ïàðîñî÷åòàíèÿ M 3 . Èç M P M
8
2
8 3 1 3 2 7 4 5 8 6�
� { }[ , ], [ , ], [ , ], [ , ] ñëåäó-
åò C M c c c c( )
8
2
13 27 45 86 8 15 2 19 44� � � � � � � � � . Ïîñëå íàõîæäåíèÿ â ãðàôå
D7 ïóòè P7 , ïàðîñî÷åòàíèÿ M
7
2 è åãî ñòîèìîñòè C M( )
7
2 âûÿñíÿåòñÿ, ÷òî
C M C M( ) ( )
7
2
8
2 44� � . Îòñþäà ñëåäóåò, ÷òî M M
4
2
8
2� , à òàê êàê C M C M( ) ( )
4
2
4
1� ,
òî M M4 8
2� . Ïîñêîëüêó � �k n� �/ 2 4, ïàðîñî÷åòàíèå M 4 1 3� {[ , ], [ , ],2 7
[ , ], [ , ]}4 5 8 6 ìàêñèìàëüíî è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ ðåøåíèåì ÇÂÏ. �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 111
1 2 3 4 5 6
1 2 3 4 5 6
7 8
7 8
1 2 3 4 5 6
1 2 3 4 5 6
Ðèñ. 5
1 3� �J 2 3� �J 4 3� �J
á
à
3 3� �I 5 3� �I 6 3� �I
1 3� �J 2 3� �J 4 3� �J
3 3� �I 5 3� �I 6 3� �I
Ðèñ. 6
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
8 2
4
7
1
à á
3 3� �I 5 3� �I 6 3� �I
1 3� �J 2 3� �J 4 3� �J
ÇÀÊËÞ×ÅÍÈÅ
Ìåòîä ðåøåíèÿ çàäà÷è î âçâåøåííîì ïàðîñî÷åòàíèè ïðåäñòàâëåí ïîñëåäîâà-
òåëüíîñòüþ èòåðàöèé, íà êàæäîé èç êîòîðûõ ñòðîèòñÿ ïàðîñî÷åòàíèå M k ,
k M�1, | |opt , õàðàêòåðèçóþùååñÿ ìèíèìàëüíîé ñóììîé âåñîâ k ðåáåð. Äîêà-
çàíà êîððåêòíîñòü ïðåäëîæåííîãî ìåòîäà è ïîêàçàíî, ÷òî ïîñëå óïîðÿäî÷åíèÿ
ïî íåóáûâàíèþ çíà÷åíèé, ðàñïîëîæåííûõ íàä ãëàâíîé äèàãîíàëüþ âõîäíîé
ìàòðèöû ñòîèìîñòè, ìåòîä êîððåêòíî ñòðîèò ðåøåíèå çàäà÷è çà âðåìÿ O n( )3 .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ: Àëãîðèòìû è ñëîæíîñòü. —
Ì.: Ìèð, 1985. — 510 ñ.
2. Ë î â à ñ Ë . , Ï ë à ì ì å ð Ì . Ïðèêëàäíûå çàäà÷è òåîðèè ãðàôîâ. Òåîðèÿ ïàðîñî÷åòàíèé â ìàòåìàòè-
êå, ôèçèêå, õèìèè. — Ì.: Ìèð, 1998. — 653 ñ.
3. Õ à ð à ð è Ô . Òåîðèÿ ãðàôîâ. — Ì.: Ìèð, 1973. — 300 ñ.
4. Ì à ö è é Î . Á . , Ì î ð î ç î â À . Â . , Ï à í è ø å â À . Â . Áûñòðûé àëãîðèòì íàõîæäåíèÿ 2-ôàêòîðà
ìèíèìàëüíîãî âåñà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2016. — 52, ¹ 3. — Ñ. 154–163.
Íàä³éøëà äî ðåäàêö³¿ 28.11.2015
Î.Á. Ìàöèé, À.Â. Ìîðîçîâ, À.Â. Ïàí³øåâ
ÐÅÊÓÐÅÍÒÍÈÉ ÀËÃÎÐÈÒÌ ÐÎÇÂ’ßÇÀÍÍß ÇÀÄÀײ ÏÐÎ ÇÂÀÆÅÍÓ ÏÀÐÎÑÏÎËÓÊÓ
Àíîòàö³ÿ. ³äîìà çàäà÷à ïðî çâàæåíó ïàðîñïîëóêó â äîâ³ëüíîìó ãðàô³ H ç n
âåðøèíàìè çâîäèòüñÿ äî îäí³º¿ ³ç çàäà÷ ïðî ïàðîñïîëóêó äëÿ äâî÷àñòêîâîãî
ãðàôà ç 2n âåðøèíàìè. Ìàêñèìàëüíà ïàðîñïîëóêà ãðàôà H ç ì³í³ìàëüíîþ
ñóìîþ âàã ðåáåð, çàäàíèõ ìàòðèöåþ [ ]cij n , çíàõîäèòüñÿ çà ÷àñ O n( )3 ï³ñëÿ
âïîðÿäêóâàííÿ çà íåñïàäàííÿì çíà÷åíü cij , ðîçòàøîâàíèõ íàä ãîëîâíîþ
ä³àãîíàëëþ.
Êëþ÷îâ³ ñëîâà: ïàðîñïîëóêà, çàäà÷à ïðî çâàæåíó ïàðîñïîëóêó, äâî÷àñòêî-
âèé ãðàô, çá³ëüøóþ÷èé øëÿõ, çàäà÷à ïðî ïðèçíà÷åííÿ.
O.B. Matsiy, A.V. Morozov, A.V. Panishev
A RECURRENT ALGORITHM TO SOLVE WEIGHTED MATCHING PROBLEM
Abstract. The well-known problem of weighted matching in an arbitrary graph
H with n vertices is reduced to a of matching problem for a bipartite graph with
2n vertices. The maximum matching of graph H with the minimum sum of
weights of edges specified by matrix [ ]cij n is found in time O n( )3 after ordering
the values cij above the main diagonal in non-decreasing order.
Keywords: matching, the problem of the weighted matching, bipartite graph,
increasing path, the assignment problem.
Ìàöèé Îëüãà Áîðèñîâíà,
àññèñòåíòêà Õàðüêîâñêîãî íàöèîíàëüíîãî àâòîìîáèëüíî-äîðîæíîãî óíèâåðñèòåòà, e-mail: om21@mail.ru.
Ìîðîçîâ Àíäðåé Âàñèëüåâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò, äåêàí Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëîãè÷åñêîãî óíèâåðñèòåòà,
e-mail: morozov.andriy@gmail.com.
Ïàíèøåâ Àíàòîëèé Âàñèëüåâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð, çàâåäóþùèé êàôåäðîé Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëî-
ãè÷åñêîãî óíèâåðñèòåòà, e-mail: pzs.ztu@gmail.com.
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-142019 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-24T15:49:11Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Маций, О.Б. Морозов, А.В. Панишев, А.В. 2018-09-20T18:02:52Z 2018-09-20T18:02:52Z 2016 Рекуррентный алгоритм решения задачи о взвешенном паросочетании / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 101-112. — Бібліогр.: 4 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/142019 519.161 Известная задача о взвешенном паросочетании в произвольном графе H с n вершинами сводится к одной из задач о паросочетании для двудольного графа с 2n вершинами. Максимальное паросочетание графа H с минимальной суммой весов ребер, заданных матрицей [cij]n , находится за время O(n³) после упорядочения по неубыванию значений cij, расположенных над главной диагональю. Відома задача про зважену паросполуку в довільному графі H з n вершинами зводиться до однієї із задач про паросполуку для двочасткового графа з 2n вершинами. Максимальна паросполука графа H з мінімальною сумою ваг ребер, заданих матрицею [cij]n , знаходиться за час O(n³) після впорядкування за неспаданням значень cij, розташованих над головною діагоналлю. The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a of matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the minimum sum of weights of edges specified by matrix[cij]n is found in time O(n³) after ordering the values cij above the main diagonal in non-decreasing order. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Рекуррентный алгоритм решения задачи о взвешенном паросочетании Рекурентний алгоритм розв’язання задачі про зважену паросполуку A recurrent algorithm to solve weighted matching problem Article published earlier |
| spellingShingle | Рекуррентный алгоритм решения задачи о взвешенном паросочетании Маций, О.Б. Морозов, А.В. Панишев, А.В. Системный анализ |
| title | Рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| title_alt | Рекурентний алгоритм розв’язання задачі про зважену паросполуку A recurrent algorithm to solve weighted matching problem |
| title_full | Рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| title_fullStr | Рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| title_full_unstemmed | Рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| title_short | Рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| title_sort | рекуррентный алгоритм решения задачи о взвешенном паросочетании |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/142019 |
| work_keys_str_mv | AT maciiob rekurrentnyialgoritmrešeniâzadačiovzvešennomparosočetanii AT morozovav rekurrentnyialgoritmrešeniâzadačiovzvešennomparosočetanii AT paniševav rekurrentnyialgoritmrešeniâzadačiovzvešennomparosočetanii AT maciiob rekurentniialgoritmrozvâzannâzadačíprozvaženuparospoluku AT morozovav rekurentniialgoritmrozvâzannâzadačíprozvaženuparospoluku AT paniševav rekurentniialgoritmrozvâzannâzadačíprozvaženuparospoluku AT maciiob arecurrentalgorithmtosolveweightedmatchingproblem AT morozovav arecurrentalgorithmtosolveweightedmatchingproblem AT paniševav arecurrentalgorithmtosolveweightedmatchingproblem |