Быстрый алгоритм нахождения 2-фактора минимального веса
Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудн...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2016 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/133690 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-133690 |
|---|---|
| record_format |
dspace |
| spelling |
Маций, О.Б. Морозов, А.В. Панишев, А.В. 2018-06-05T06:10:15Z 2018-06-05T06:10:15Z 2016 Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/133690 519.161 Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг. Розглянуто задачу мінімізації у графі H = (V, U) суми ваг ребер підмножини U' ⊂ U, що утворюють сукупність простих циклів, які не перетинаються у вершинах v ∈ V і покривають V. Розглянута задача (задача 2-f) може бути поліноміально розв’язана алгоритмами, які характеризуються технічними труднощами, що перешкоджають прискоренню процесу обчислень. Розв’язок задачі 2-f знаходиться зведенням її до більш простого двочасткового випадку. Результат представлено досконалою паросполукою двочасткового графа, відповідною розв’язку задачі про призначення, у цикловому розвиненні якої кожний контур містить не менше трьох дуг. The paper considers the minimization of the sum of weights of edges forming a subset of the set of disjoint simple cycles at the vertices in the graph H = (V, U) and cover V. This problem (2-f problem) is solvable in polynomial algorithms, which are characterized by technical difficulties that hinder accelerate computing. The solution of 2-f is reducing it to a simple bipartite case. The desired result is represented by a perfect matching of a bipartite graph corresponding to the solution of the assignment problem, in which each expansion cycle circuit comprises at least three arcs. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Быстрый алгоритм нахождения 2-фактора минимального веса Швидкий алгоритм знаходження 2-фактора мінімальної ваги Fast algorithm to find the 2-factor of minimum weight Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Быстрый алгоритм нахождения 2-фактора минимального веса |
| spellingShingle |
Быстрый алгоритм нахождения 2-фактора минимального веса Маций, О.Б. Морозов, А.В. Панишев, А.В. Системный анализ |
| title_short |
Быстрый алгоритм нахождения 2-фактора минимального веса |
| title_full |
Быстрый алгоритм нахождения 2-фактора минимального веса |
| title_fullStr |
Быстрый алгоритм нахождения 2-фактора минимального веса |
| title_full_unstemmed |
Быстрый алгоритм нахождения 2-фактора минимального веса |
| title_sort |
быстрый алгоритм нахождения 2-фактора минимального веса |
| author |
Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| author_facet |
Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2016 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Швидкий алгоритм знаходження 2-фактора мінімальної ваги Fast algorithm to find the 2-factor of minimum weight |
| description |
Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг.
Розглянуто задачу мінімізації у графі H = (V, U) суми ваг ребер підмножини U' ⊂ U, що утворюють сукупність простих циклів, які не перетинаються у вершинах v ∈ V і покривають V. Розглянута задача (задача 2-f) може бути поліноміально розв’язана алгоритмами, які характеризуються технічними труднощами, що перешкоджають прискоренню процесу обчислень. Розв’язок задачі 2-f знаходиться зведенням її до більш простого двочасткового випадку. Результат представлено досконалою паросполукою двочасткового графа, відповідною розв’язку задачі про призначення, у цикловому розвиненні якої кожний контур містить не менше трьох дуг.
The paper considers the minimization of the sum of weights of edges forming a subset of the set of disjoint simple cycles at the vertices in the graph H = (V, U) and cover V. This problem (2-f problem) is solvable in polynomial algorithms, which are characterized by technical difficulties that hinder accelerate computing. The solution of 2-f is reducing it to a simple bipartite case. The desired result is represented by a perfect matching of a bipartite graph corresponding to the solution of the assignment problem, in which each expansion cycle circuit comprises at least three arcs.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/133690 |
| citation_txt |
Быстрый алгоритм нахождения 2-фактора минимального веса / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 154-163. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT maciiob bystryialgoritmnahoždeniâ2faktoraminimalʹnogovesa AT morozovav bystryialgoritmnahoždeniâ2faktoraminimalʹnogovesa AT paniševav bystryialgoritmnahoždeniâ2faktoraminimalʹnogovesa AT maciiob švidkiialgoritmznahodžennâ2faktoramínímalʹnoívagi AT morozovav švidkiialgoritmznahodžennâ2faktoramínímalʹnoívagi AT paniševav švidkiialgoritmznahodžennâ2faktoramínímalʹnoívagi AT maciiob fastalgorithmtofindthe2factorofminimumweight AT morozovav fastalgorithmtofindthe2factorofminimumweight AT paniševav fastalgorithmtofindthe2factorofminimumweight |
| first_indexed |
2025-11-25T21:22:22Z |
| last_indexed |
2025-11-25T21:22:22Z |
| _version_ |
1850551061490696192 |
| fulltext |
ÓÄÊ 519.161
Î.Á. ÌÀÖÈÉ, À.Â. ÌÎÐÎÇÎÂ, À.Â. ÏÀÍÈØÅÂ
ÁÛÑÒÐÛÉ ÀËÃÎÐÈÒÌ ÍÀÕÎÆÄÅÍÈß 2-ÔÀÊÒÎÐÀ
ÌÈÍÈÌÀËÜÍÎÃÎ ÂÅÑÀ
Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à ìèíèìèçàöèè â ãðàôå H V U� ( , ) ñóììû âå-
ñîâ ðåáåð ïîäìíîæåñòâà � �U U , îáðàçóþùèõ ñîâîêóïíîñòü íåïåðåñåêàþùèõ-
ñÿ â âåðøèíàõ � �V ïðîñòûõ öèêëîâ è ïîêðûâàþùèõ V . Ðàññìàòðèâàåìàÿ çà-
äà÷à (çàäà÷à 2- f ) ïîëèíîìèàëüíî ðàçðåøèìà àëãîðèòìàìè, êîòîðûå õàðàêòå-
ðèçóþòñÿ òåõíè÷åñêèìè òðóäíîñòÿìè, ïðåïÿòñòâóþùèìè óñêîðåíèþ ïðîöåññà
âû÷èñëåíèé. Ðåøåíèå çàäà÷è 2- f íàõîäèòñÿ ñâåäåíèåì åå ê áîëåå ïðîñòîìó
äâóäîëüíîìó ñëó÷àþ. Ðåçóëüòàò ïðåäñòàâëåí ñîâåðøåííûì ïàðîñî÷åòàíèåì
äâóäîëüíîãî ãðàôà, ñîîòâåòñòâóþùèì ðåøåíèþ çàäà÷è î íàçíà÷åíèÿõ, â öèê-
ëîâîì ðàçëîæåíèè êîòîðîé êàæäûé êîíòóð ñîäåðæèò íå ìåíåå òðåõ äóã.
Êëþ÷åâûå ñëîâà: 2-ôàêòîð, çàäà÷à î íàçíà÷åíèÿõ, ïàðîñî÷åòàíèå, äâóäîëü-
íûé ãðàô, óâåëè÷èâàþùèé ïóòü.
ÂÂÅÄÅÍÈÅ
Ïîäìíîæåñòâî � �U U ðåáåð ãðàôà H V U� ( , ) íàçûâàåòñÿ 2-ôàêòîðîì, åñëè
êàæäàÿ âåðøèíà � �V èíöèäåíòíà ðîâíî äâóì ðåáðàì. Ïîäìíîæåñòâî M U�
ðåáåð ãðàôà H V U� ( , ) íàçûâàåòñÿ ïàðîñî÷åòàíèåì (ñîâåðøåííûì ïàðîñî÷åòà-
íèåì), åñëè êàæäàÿ âåðøèíà � �V èíöèäåíòíà íå áîëåå (ðîâíî) îäíîìó ðåáðó.
Çàäà÷à íàõîæäåíèÿ 2-ôàêòîðà ìèíèìàëüíîãî âåñà (çàäà÷à 2- f ) ôîðìóëèðóåò-
ñÿ ñëåäóþùèì îáðàçîì. Çàäàí ãðàô H V U� ( , ) , ãäå V — ìíîæåñòâî âåðøèí,
| |V n� , à U — ìíîæåñòâî ðåáåð, â êîòîðîì êàæäîå ðåáðî { }i j, èìååò âåñ
c Rij � �
0
, R
0
� — ìíîæåñòâî íåîòðèöàòåëüíûõ äåéñòâèòåëüíûõ ÷èñåë.
Òðåáóåòñÿ íàéòè â ãðàôå H 2-ôàêòîð ñ ìèíèìàëüíîé ñóììîé âåñîâ ðåáåð.
Ïîñòàâëåííàÿ çàäà÷à äëÿ ïîëíîãî ãðàôà H n âñåãäà èìååò ðåøåíèå.  [1] èç-
ëîæåí àëãîðèòì, îïðåäåëÿþùèé â n-âåðøèííîì ïîëíîì ãðàôå 2-ôàêòîð ìèíè-
ìàëüíîãî âåñà çà âðåìÿ O n( )3 . Èç [2] èçâåñòíî, ÷òî äëÿ îñòîâíîãî ïîäãðàôà H
ïîëíîãî ãðàôà H n çàäà÷à 2- f ðåøàåòñÿ ïóòåì åå ñâåäåíèÿ ê çàäà÷å íàõîæäåíèÿ
ïàðîñî÷åòàíèÿ ìèíèìàëüíîãî âåñà â ãðàôå ñ ñóùåñòâåííî áîëüøèì ÷èñëîì âåð-
øèí è ðåáåð, ÷åì â H . Ïîèñê ïàðîñî÷åòàíèÿ âûïîëíÿåòñÿ çà âðåìÿ O n( )4 àëãî-
ðèòìîì Ýäìîíäñà èëè åãî ìîäèôèêàöèÿìè, âêëþ÷àþùèìè ïðîöåäóðó îáíàðóæå-
íèÿ öâåòêà — öèêëà ñ 2 1k � âåðøèíàìè, â êîòîðîì k ðåáåð îáðàçóþò ïàðîñî÷åòà-
íèå, è ïðîöåäóðó ñðåçàíèÿ öâåòêà — åãî çàìåíó îäíîé âåðøèíîé [3].
Ïîñêîëüêó ñâÿçíûé 2-ôàêòîð ïðåäñòàâëÿåò ñîáîé ãàìèëüòîíîâ öèêë ãðàôà H n ,
ðåøåíèå ïîñòàâëåííîé çàäà÷è èñïîëüçóåòñÿ ïðè ðàçðàáîòêå ýôôåêòèâíûõ àëãî-
ðèòìîâ ñ ãàðàíòèðîâàííûìè îöåíêàìè äëÿ çàäà÷ êëàññà êîììèâîÿæåðà, îáëàäàþ-
ùèõ øèðîêèì ñïåêòðîì ïðèëîæåíèé [3]. Áîëüøèíñòâî ýòèõ àëãîðèòìîâ õàðàêòå-
ðèçóåòñÿ òàêîé æå îöåíêîé òðóäîåìêîñòè, êàê è ó àëãîðèòìà Ýäìîíäñà. Âîçìîæ-
íîñòü íàõîæäåíèÿ 2-ôàêòîðà ìèíèìàëüíîãî âåñà çà ïîëèíîìèàëüíîå âðåìÿ
ÿâëÿåòñÿ îñíîâàíèåì äëÿ âûáîðà ñôîðìóëèðîâàííîé çàäà÷è â êà÷åñòâå ðåëàêñà-
öèè, îáåñïå÷èâàþùåé íà ñåãîäíÿøíèé äåíü íàèáîëåå áëèçêèå ê îïòèìóìó íèæ-
íèå îöåíêè â òî÷íûõ àëãîðèòìàõ ðåøåíèÿ ñèììåòðè÷íîé çàäà÷è êîììèâîÿæå-
ðà (ÑÇÊ), ïîñòðîåííûõ ïî ìåòîäó âåòâåé è ãðàíèö [4, 5]. Îñíîâíàÿ ïðè÷èíà, çà-
òðóäíÿþùàÿ âû÷èñëåíèå íèæíèõ ãðàíèö àëãîðèòìîì Ýäìîíäñà â òî÷íûõ
ìåòîäàõ ðåøåíèÿ ÑÇÊ, ñîñòîèò â ñëîæíîñòè ïðîöåäóð îáíàðóæåíèÿ è ñðåçàíèÿ
öâåòêà, íåîäíîêðàòíîå âûïîëíåíèå êîòîðûõ ïðèâîäèò ê îùóòèìûì âðåìåííûì
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
© Î.Á. Ìàöèé, À.Â. Ìîðîçîâ, À.Â. Ïàíèøåâ, 2016
çàòðàòàì. Â äàííîé ðàáîòå ïðåäëàãàåòñÿ ìåòîä íàõîæäåíèÿ â ãðàôå H V E� ( , )
2-ôàêòîðà ìèíèìàëüíîãî âåñà, íå ñîäåðæàùèé äåéñòâèé ñ öâåòêàìè. Åãî òðóäî-
åìêîñòü îöåíèâàåòñÿ âåëè÷èíîé O n( )3 .
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Â ÒÅÐÌÈÍÀÕ ÏÀÐÎÑÎ×ÅÒÀÍÈÉ
ÄËß ÄÂÓÄÎËÜÍÛÕ ÃÐÀÔÎÂ
Ìåòîä âûïîëíÿåò ïîèñê â äâóäîëüíîì ãðàôå ñ 2n âåðøèíàìè ñîâåðøåííîãî
ïàðîñî÷åòàíèÿ ñ ìèíèìàëüíûì ñóììàðíûì âåñîì ðåáåð, ñîîòâåòñòâóþùåãî
â ãðàôå H 2-ôàêòîðó ìèíèìàëüíîãî âåñà, èñïîëüçóÿ ïîíÿòèå êðàò÷àéøåãî óâå-
ëè÷èâàþùåãî ïóòè è ñïîñîá åãî ïîñòðîåíèÿ.
Âçâåøåííûé ãðàô H V U� ( , ) ñ n âåðøèíàìè ìíîæåñòâà V , ïîìå÷åííûìè
÷èñëàìè èç ìíîæåñòâà { }1 2, , ,� n , íå ñîäåðæàùèé ïåòåëü { }i i, , ïîëíîñòüþ îïðå-
äåëÿåòñÿ ìàòðèöåé ñòîèìîñòåé (âåñîâ) ðåáåð C cij n� [ ] , â êîòîðîé c Rij � �
0
, åñëè
{ }i j U, � , è cij � � èíà÷å. Çàìåíà êàæäîãî ðåáðà { }i j, èç H ïàðîé äóã ( , )i j è ( , )j i
ñ âåñàìè cij è c ji , c cij ji� , äàåò âçâåøåííûé îðãðàô G V E� ( , ) . Ïîäãðàô
� � �G V E( , ) îðãðàôà G V E� ( , ), � �E E , íàçûâàåòñÿ êîíòóðíûì ïîêðûòèåì,
åñëè êàæäàÿ âåðøèíà ïîäãðàôà �G èìååò ïîëóñòåïåíè çàõîäà è èñõîäà, ðàâíûå
åäèíèöå.
Åñëè â îðãðàôå G ïîñòðîåíî êîíòóðíîå ïîêðûòèå K K K K� { }1 2, , ,� � ,
â êîòîðîì êàæäîå ïîäìíîæåñòâî K ii , ,�1 � , ñîäåðæèò íå ìåíåå òðåõ âåðøèí, òî
â ãðàôå H ïîñòðîåí 2-ôàêòîð èç òåõ æå � ïîäìíîæåñòâ âåðøèí. Íî êîíòóðíîå
ïîêðûòèå ñîâïàäàåò ñ öèêëîâûì ðàçëîæåíèåì ïåðåñòàíîâêè � ìíîæåñòâà
{ }1 2, , ,� n íîìåðîâ ñòîëáöîâ ìàòðèöû ñòîèìîñòåé C , äëÿ êîòîðîé � çàäàåò äî-
ïóñòèìîå ðåøåíèå çàäà÷è î íàçíà÷åíèÿõ (ÇÍ). Îòñþäà âûòåêàåò ôîðìóëèðîâêà
çàäà÷è 2-ôàêòîðà â òåðìèíàõ ÇÍ [5].
Äëÿ ñèììåòðè÷íîé ìàòðèöû ñòîèìîñòåé (âåñîâ) C cij n� [ ] , â êîòîðîé cij � �
ïðè i j� è c Rij � �
0
èëè cij � � ïðè i j� , i j n, ,�1 , òðåáóåòñÿ íàéòè
C c i
i
n
( ) min [ ]�
�
�
�
1
. (1)
Çäåñü � � � �� ( [ ], [ ], , [ ])1 2 � n — ïåðåñòàíîâêà ìíîæåñòâà { }1 2, , ,� n íîìåðîâ
ñòîëáöîâ ìàòðèöû C , îïðåäåëåííàÿ íà ìíîæåñòâå ïåðåñòàíîâîê � � �� ( [ ], [ ],1 2 �
� , [ ])� n , â êàæäîé èç êîòîðûõ öèêëîâîå ðàçëîæåíèå ïðåäñòàâëåíî êîíòóðàìè,
ñîäåðæàùèìè íå ìåíåå òðåõ âåðøèí.
Ñëåäóåò çàìåòèòü, ÷òî çàäà÷à 2-ôàêòîð ñ ìàòðèöåé ñòîèìîñòåé, âêëþ÷àþùåé
ýëåìåíòû cij � � , ìîæåò íå èìåòü ðåøåíèÿ.  ýòîì ñëó÷àå íåîáõîäèìî ïîêàçàòü,
÷òî ìíîæåñòâî ïåðåñòàíîâîê � ïóñòî.
Áóäåì èñêàòü � , ïîøàãîâî óâåëè÷èâàÿ íà åäèíèöó ÷èñëî k ýëåìåíòîâ ïîñëåäî-
âàòåëüíîñòè, îáðàçóþùåé îïðåäåëåííóþ ÷àñòü äîïóñòèìîãî ðåøåíèÿ çàäà÷è 2- f .
Îòìåòèì îñîáåííîñòè ýòîé ïîñëåäîâàòåëüíîñòè.
Ïåðâûì k ýëåìåíòàì äîïóñòèìîãî ðåøåíèÿ � çàäà÷è 2- f ïîñòàâèì â ñîîòâåò-
ñòâèå ïîäìàòðèöó ïîðÿäêà k ìàòðèöû C è ðåøåíèå ÇÍ äëÿ äàííîé ïîäìàòðèöû,
óäîâëåòâîðÿþùåå ñëåäóþùåìó îãðàíè÷åíèþ: åãî öèêëîâîå ðàçëîæåíèå íå ñîäåð-
æèò êîíòóðîâ ñ äâóìÿ âåðøèíàìè. Íàçîâåì òàêîå ðåøåíèå ÇÍ îãðàíè÷åííûì.
Ïóñòü íà ìíîæåñòâå âñåõ îãðàíè÷åííûõ ðåøåíèé ÇÍ èç k ýëåìåíòîâ ìàòðè-
öû C ðåøåíèå � � � �k ki i i� ( [ ], [ ], , [ ])1 2 � èìååò ìèíèìàëüíóþ ñòîèìîñòü. Òîã-
äà (1) íàõîäèòñÿ çà n èòåðàöèé, êàæäàÿ èç êîòîðûõ ïðåîáðàçóåò ïîñëåäîâàòåëü-
íîñòü �k â ïîñëåäîâàòåëüíîñòü �k�1, k n�
1 1, .
Èçëîæåííûå ñîîáðàæåíèÿ îòêðûâàþò âîçìîæíîñòü ïðèìåíåíèÿ äëÿ íàõîæäå-
íèÿ (1) îñíîâíûõ ðåçóëüòàòîâ òåîðèè ïàðîñî÷åòàíèé äëÿ äâóäîëüíûõ ãðàôîâ [3].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 155
Ñèììåòðè÷íîé ìàòðèöå ñòîèìîñ-
òåé C îðãðàôà G V E� ( , ), ïîñòðîåííîãî
èç H V U� ( , ), âçàèìíî îäíîçíà÷íî ñîîò-
âåòñòâóåò äâóäîëüíûé ãðàô D X Y E� ( , , ) ,
ãäå X , Y — ìíîæåñòâà âåðøèí,
| | | |X Y� � | |V � � , E i j� {( , ) | i X� ,
j Y� } — ìíîæåñòâî ðåáåð ñ âåñàìè
c Rij � �
0
, i j� , èç ìàòðèöû C ,
| | | |E U� 2 .
Ðåáðî ( , )i j , i j� , ãðàôà D , âêëþ-
÷åííîå â ïàðîñî÷åòàíèå, îáîçíà÷èì
[ , ]i j . Ðåáðà, íå âõîäÿùèå â ïàðîñî÷åòà-
íèå, íàçûâàþòñÿ ñâîáîäíûìè. Âåðøè-
íà, ïðèíàäëåæàùàÿ ðåáðó ïàðîñî÷åòàíèÿ, îïðåäåëÿåòñÿ êàê íàñûùåííàÿ, îñòàëü-
íûå âåðøèíû ãðàôà íàçûâàþòñÿ íåíàñûùåííûìè èëè ñâîáîäíûìè.
Ìàêñèìàëüíîå ïàðîñî÷åòàíèå — ýòî ïàðîñî÷åòàíèå ñ íàèáîëüøèì ÷èñëîì ðåáåð.
Ïàðîñî÷åòàíèå, íàñûùàþùåå âñå âåðøèíû ãðàôà, íàçûâàåòñÿ ñîâåðøåííûì. Ñî-
âåðøåííîå ïàðîñî÷åòàíèå ãðàôà D X Y E� ( , , ) èìååò ìàêñèìàëüíóþ ìîùíîñòü,
ðàâíóþ n. Ðåøåíèå çàäà÷è 2- f â äâóäîëüíîì ãðàôå D — ñîâåðøåííîå ïàðîñî÷å-
òàíèå � ñ ìèíèìàëüíîé ñóììîé âåñîâ ðåáåð, â êîòîðîì åñëè [ , ]i j �� , i X� , j Y� ,
òî ðåáðî ( , )j i , j X� , i Y� , íå ÿâëÿåòñÿ ðåáðîì ïàðîñî÷åòàíèÿ � .
Ïóñòü â ãðàôå H çàôèêñèðîâàíî ïàðîñî÷åòàíèå M . Ïðîñòîé ïóòü íàçûâàåòñÿ
÷åðåäóþùèìñÿ îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M , åñëè ðåáðà ïóòè ÷åðåç îäíî ñî-
äåðæàòñÿ â M [2]. ×åðåäóþùèéñÿ ïóòü, êîòîðûé íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ ðåá-
ðàìè, íå ïðèíàäëåæàùèìè ïàðîñî÷åòàíèþ M , íàçûâàåòñÿ óâåëè÷èâàþùèì
îòíîñèòåëüíî ïàðîñî÷åòàíèÿ M .
Åñëè â ãðàôå D çàôèêñèðîâàòü ïàðîñî÷åòàíèå � ��k i j i j{[ , ], [ , ],3 2 4 3 �
� , [ , ], [ , ]i j i jk k k k2 2 2 3 2 1 2 2
}, òî åãî îáúåäèíåíèþ ñî ñâîáîäíûìè ðåáðàìè
( , )i j1 2 è ( , )i jk k2 1 2
(ðèñ. 1, à) ñîîòâåòñòâóåò â ãðàôå H ïðîñòàÿ öåïü ( , ,� �1 2
� � �3 2 1 2, , , )� k k
, k � 3 (ðèñ. 1, á).
Ïàðîñî÷åòàíèþ �� �
�k k k ki j i j i j i j{ }[ , ], [ , ], , [ , ], [ , ]3 2 4 3 2 2 2 3 2 2 2� ãðàôà D ,
äîïîëíåííîìó ñâîáîäíûìè ðåáðàìè ( , )i j1 2 è ( , )i jk k2 2 2 1
(ðèñ. 2, à), ñîîòâåò-
ñòâóåò â ãðàôå H ïîäãðàô, âêëþ÷àþùèé ïðîñòîé öèêë ( , , ,� � �2 2 2 2 3k k
�
� , , )� �3 2 è äâà ðåáðà ( , )� �1 2 , ( , )� �2 2 2 1k k
, k � 3 (ðèñ. 2, á).
Ïàðîñî÷åòàíèå ��k èëè ���k ñîãëàñóåòñÿ ñ ÷àñòüþ íåêîòîðîãî äîïóñòèìîãî ðå-
øåíèÿ çàäà÷è 2- f . Ïîýòîìó ïîèñê 2-ôàêòîðà ìèíèìàëüíîãî âåñà â ãðàôå H ñîñòî-
èò â íàõîæäåíèè ïàðîñî÷åòàíèÿ â äâóäîëüíîì ãðàôå D . Ê ìîìåíòó íà÷àëà ðåøå-
íèÿ çàäà÷è 2- f â ãðàôå D íå çàôèêñèðîâàíî ïàðîñî÷åòàíèÿ, ñîîòâåòñòâóþùåãî
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Ðèñ. 1
i1 i2 i3 i4 i5 i6
j1 j2 j3 j4 j5 j6
�1 �2 �3 �4 �5 �6
à
á
Ðèñ. 2
i1 i2 i3 i4 i5 i6
j1 j2 j3 j4 j5 j6
à
�1 �2
�3
�4
�5
á
÷àñòè èñêîìîé ïîñëåäîâàòåëüíîñòè � . Åñëè ëþáîå ðåáðî â D îïðåäåëèòü êàê óâå-
ëè÷èâàþùèé ïóòü îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �, òî èñõîäíóþ ïîñëåäîâàòåëü-
íîñòü �1, ñîîòâåòñòâóþùóþ îïòèìàëüíîìó îãðàíè÷åííîìó ðåøåíèþ ÇÍ èç îäíî-
ãî ýëåìåíòà, îáðàçóåò ðåáðî ìèíèìàëüíîãî âåñà, âçÿòîãî íà ìíîæåñòâå çíà÷åíèé
cij , i j n, ,�1 , i j
, ìàòðèöû C .
ÎÁÎÑÍÎÂÀÍÈÅ È ÎÏÈÑÀÍÈÅ ÀËÃÎÐÈÒÌÀ ÐÅØÅÍÈß ÇÀÄÀ×È 2- f
Ïóñòü íà ìíîæåñòâå �k âñåõ ïàðîñî÷åòàíèé � � �k l l l l� {[ , [ ]], [ , [ ]],1 1 2 2 �
� �, [ , [ ]], , [ , [ ]]}l l l lm m k k� � ãðàôà D X Y E� ( , , ) , â êîòîðûõ íåò ðåáåð, ñîåäè-
íÿþùèõ âåðøèíû �[ ]l Xm � è l Ym � , l lm m� �[ ], m k�1, , ïîñòðîåíî ïàðîñî÷å-
òàíèå � k l l k ki j i j i j i j� {[ , ], [ ], , [ , ], , [ , ]},1 1 2 2 � � ìèíèìàëüíîé ñòîèìîñòè. Óäà-
ëèâ â ãðàôå D ðåáðà ( , ), ( , ), , ( , ), , ( , )j i j i j i j il l k k1 1 2 2 � � , j Xl � , i Yl � , è ïî-
ëîæèâ èõ âåñà â ìàòðèöå C ðàâíûìè � , ïîëó÷èì îñòîâíîé ïîäãðàô Dk ãðàôà D .
 ãðàôå Dk ïðåîáðàçóåì �k â ïàðîñî÷åòàíèå �k l li j i j i j� � � � � � � �1 1 1 2 2{[ , ], [ , ], [ , ],�
� , [ , ], [ , ]� � � �� �i j i jk k k k1 1 }, äîñòàâëÿþùåå ìèíèìàëüíûé ñóììàðíûé âåñ ðåáåð
C k( )� �1 íà ìíîæåñòâå �k�1 âñåõ ïàðîñî÷åòàíèé � k�1.
Ïàðîñî÷åòàíèå �k ðàçáèâàåò ìíîæåñòâà X è Y ñîîòâåòñòâåííî íà ïîäìíî-
æåñòâà íàñûùåííûõ âåðøèí I i i i ik l k� { }1 2, , , , ,� � , J j j j jk l k� � � � �{ }1 2, � �
è íà ìíîæåñòâà ñâîáîäíûõ âåðøèí X I i i i ik k k p n
� � �{ }1 2, , , , ,� � , Y Jk
�
� � �{ }j j j jk k g n1 2, , , , ,� � . Íàéäåì ñâîáîäíîå ðåáðî âåñîì
c c i X I j Y J m s Dms ij k k� �
�
�min | , }, ( , ){ , (2)
è, ïðèñîåäèíèâ åãî ê ïàðîñî÷åòàíèþ �k , ïîëó÷èì ïàðîñî÷åòàíèå �
k�
�
1
1
� ��k m s[ , ] ñòîèìîñòüþ MIN C ck ms1 � �( )� . Åñëè �
k�1
1 íå äîñòàâëÿåò ìèíèìàëü-
íîé ñóììû âåñîâ ðåáåð íà ìíîæåñòâå �k�1, òî åå äîñòàâëÿåò �
k�1
2 �
� �
�k k1 1
1{ }�
ñòîèìîñòüþ MIN C
k
2
1
2�
�
( )� . Òàêèì îáðàçîì, C k( )� �1 � min ,{ }MIN MIN1 2 .
Ëåììà 1. Ïóñòü � �k k k� � �
�
1 1 1
1� { }. Òîãäà � � �k k k k kP P� � �� � �
�1 1 1( )
�
�( )�k kP 1 , ãäå Pk�1 — êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü îòíîñèòåëüíî ïàðî-
ñî÷åòàíèÿ �k â ïîäãðàôå Dk .
Äîêàçàòåëüñòâî ëåììû ïîâòîðÿåò äîêàçàòåëüñòâî ëåììû èç [5], îïðåäåëÿþ-
ùåé ñïîñîá ïðåîáðàçîâàíèÿ � k â ïàðîñî÷åòàíèå � k�1 â ðåêóððåíòíîì ìåòîäå
ðåøåíèÿ ÇÍ.
Ïóñòü â Dk âåðøèíà j J r kr k� �, , , ,{ }1 2 � , ÿâëÿåòñÿ êîíöîì ñâîáîäíîãî
ðåáðà ( , )i jl r ñ ìèíèìàëüíûì âåñîì ñðåäè âñåõ ðåáåð ( , ),i j i Is r s k� , à âåðøèíà
i I f kf k� �, , , ,{ }1 2 � , — íà÷àëîì ñâîáîäíîãî ðåáðà ( , )i jf p ñ ìèíèìàëüíûì âå-
ñîì ñðåäè âñåõ ðåáåð ( , ),i j j Jf g g k� .
Îáîçíà÷èì X k ìíîæåñòâî ñâîáîäíûõ âåðøèí il , èíöèäåíòíûõ íàéäåííûì ðåá-
ðàì ( , ), | |i j X kl r k � . Ñîîòâåòñòâåííî Yk — ìíîæåñòâî ñâîáîäíûõ âåðøèí jp , èí-
öèäåíòíûõ ðåáðàì ( , ), | |i j Y kf p k � . Íåòðóäíî âèäåòü, ÷òî êðàò÷àéøèé óâåëè÷èâà-
þùèé ïóòü Pk�1 îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �k íà÷èíàåòñÿ â íåêîòîðîé âåðøèíå
ìíîæåñòâà X k è çàêàí÷èâàåòñÿ â íåêîòîðîé âåðøèíå ìíîæåñòâà Yk ïîäãðàôà � �Dk ,
ïîðîæäåííîãî ìíîæåñòâîì âåðøèí X I J Yk k k k� � � ïîäãðàôà Dk [6].
Ïðåîáðàçóåì ïîäãðàô � �Dk âî âçâåøåííûé îðãðàô ( , )Z A , ñ ïîìîùüþ êîòî-
ðîãî âûïîëíÿåòñÿ ïîèñê êðàò÷àéøåãî óâåëè÷èâàþùåãî ïóòè Pk�1 îòíîñèòåëüíî
ïàðîñî÷åòàíèÿ �k [3].
Ãðàô ( , )Z A ñîñòîèò èç ìíîæåñòâà âåðøèí Z i X J Yk k k� � � �{ }0 è ìíîæåñò-
âà äóã A A A A A� � � �0 1 2 3 . Ïîäìíîæåñòâî A0 ñîäåðæèò | |X k äóã ( , )i il0 íóëå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 157
âîãî âåñà, i Xl k� . Â ïîäìíîæåñòâî A1 âõîäèò äóãà ( , )i il r , i X i Il k r k� �, , åñëè è
òîëüêî åñëè âåðøèíà jr ðåáðà ( , )i jl r — íàïàðíèê âåðøèíû ir â ïàðîñî÷åòàíèè
�k . Äóãå ( , )i il r ïðèñâàèâàåòñÿ âåñ c i i c cl r i j i jl r r r
( , ) � � . Äóãà ( , ),i id l i i Xd l k, � ,
âõîäèò â A2 òîãäà è òîëüêî òîãäà, êîãäà âåðøèíà j
l
ðåáðà ( , )i jd l , j Jl k� , ÿâëÿåò-
ñÿ íàïàðíèêîì âåðøèíû il â ïàðîñî÷åòàíèè �k . Äóãà ( , )i id l ïîëó÷àåò âåñ
c i i c cd l i j i jd l l l
( , ) � � . Ïîäìíîæåñòâî A3 âêëþ÷àåò äóãè ( , ),i jf p i I j Yf k p k� �, ,
åñëè âåðøèíû i f è jp ñîåäèíåíû â ïîäãðàôå � �Dk ðåáðîì ( , )i jf p . Äóãå ( , )i jf p
ïðèñâàèâàåòñÿ âåñ c i j cf p i jf p
( , ) � .
Íà ðèñ. 3, à ïðåäñòàâëåí ïîäãðàô � �D4 ñ ïàðîñî÷åòàíèåì �4 2 3 3 4� {[ , ], [ , ],i j i j
[ , ], [ , ]i j i j4 5 5 6 } .
Âñïîìîãàòåëüíûé îðãðàô ( , )Z A , ïîñòðîåííûé äëÿ ïîäãðàôà � �D4 , èçîáðà-
æåí íà ðèñ. 3, á. Â íåì ìíîæåñòâî äóã A îáðàçóþò ïîäìíîæåñòâà A i i0 0 1� {( , ),
( , ), ( , )i i i i0 6 0 7 }, A i i i i i i i i1 1 3 6 2 7 4 7 5� { }( , ), ( , ), ( , ), ( , ) , A i i2 2 3� {( , ), ( , ), ( , )i i i i3 5 5 2 },
A i j i j i j i j3 2 1 3 1 4 7 5 7� { }( , ), ( , ), ( , ), ( , ) .
Èç ñïîñîáà ïîñòðîåíèÿ îðãðàôà ( , )Z A ñëåäóåò, ÷òî ìíîæåñòâî ïðîñòûõ ïóòåé
èç âåðøèíû i0 âî âñå âåðøèíû ìíîæåñòâà Yk ñîâïàäàåò ñ ìíîæåñòâîì óâåëè÷èâà-
þùèõ ïóòåé îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �k , ñîåäèíÿþùèõ â ïîäãðàôå � �Dk âåð-
øèíû ìíîæåñòâà X k ñ âåðøèíàìè ìíîæåñòâà Yk .
Äîêàçàòåëüñòâî ñëåäóþùåãî óòâåðæäåíèÿ íå âûçûâàåò çàòðóäíåíèé.
Óòâåðæäåíèå 1. Êðàò÷àéøèé ïóòü èç ëþáîé âåðøèíû i Xl k� â ëþáóþ âåð-
øèíó j Yp k� — ïðîñòîé ïóòü â îðãðàôå ( , )Z A è óâåëè÷èâàþùèé îòíîñèòåëüíî
ïàðîñî÷åòàíèÿ �k â ïîäãðàôå � �Dk .
Óòâåðæäåíèå 2. Åñëè îðãðàô ( , )Z A íå ñîäåðæèò ïóòåé, íà÷èíàþùèõñÿ
â ïðîèçâîëüíîé âåðøèíå i Xl k� è çàêàí÷èâàþùèõñÿ â ïðîèçâîëüíîé âåðøèíå
j Yp k� , òî �k — ìàêñèìàëüíîå ïàðîñî÷åòàíèå ïîäãðàôà � �Dk .
Äîêàçàòåëüñòâî. Èç óñëîâèÿ è äîêàçàòåëüñòâà óòâåðæäåíèÿ 1 ñëåäóåò, ÷òî
â îðãðàôå ( , )Z A íåò ïðîñòûõ ïóòåé ñ íà÷àëüíîé âåðøèíîé èç X k è êîíå÷íîé
âåðøèíîé èç Yk , à ïîäãðàô � �Dk íå ñîäåðæèò óâåëè÷èâàþùèõ ïóòåé îòíîñèòåëü-
íî ïàðîñî÷åòàíèÿ �k . Òàêèì îáðàçîì, äëÿ ïîäãðàôà � �Dk âûïîëíÿåòñÿ íåîáõîäè-
ìîå è äîñòàòî÷íîå óñëîâèå òîãî, ÷òî ïàðîñî÷åòàíèå �k ìàêñèìàëüíî â Dk [3]. �
Åñëè ïàðîñî÷åòàíèå �k ìàêñèìàëüíî â Dk , òî ñîãëàñíî ëåììå â Dk íå ñó-
ùåñòâóåò ïàðîñî÷åòàíèÿ �
k�1
2 , ðàçâèâàþùåãî ïðîöåññ ïîñòðîåíèÿ 2-ôàêòîðà
ìèíèìàëüíîãî âåñà.
Ïðåäïîëîæèì, ÷òî â îðãðàôå ( , )Z A ìíîæåñòâî ïóòåé, ñîåäèíÿþùèõ ïàðû
âåðøèí ( , ), ,i j i X j Yl p l k p k� � , íåïóñòî. Ðåçóëüòàòîì ïîñòðîåíèÿ êðàò÷àéøåãî
èç íèõ ÿâëÿåòñÿ êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü Pk�1 îòíîñèòåëüíî ïàðîñî÷å-
òàíèÿ �k l l k ki j i j i j i j� { }[ , ], [ , ], ..., [ , ], ..., [ , ]1 1 2 2 . Òîãäà � �
k k kP
� �� �
1
2
1 .
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Ðèñ. 3
i1 i2 i3 i4 i5 i6
j1 j2 j3 j4 j5 j6
i7
j7
à á
i0 i2
i5
i7
i6 j1
i4 j7
i3i1
×òîáû îïðåäåëèòü �k�1, êîãäà �k ìàêñèìàëüíî, ñëåäóåò íàéòè â ïîäãðàôå
Dk ðåáðî âåñîì, ðàâíûì (2), è ïðèñîåäèíèòü åãî ê �k . Åñëè òàêîãî ðåáðà íåò, òî
çàäà÷à 2- f íå èìååò ðåøåíèÿ.
Àëãîðèòì ðåøåíèÿ çàäà÷è 2- f âêëþ÷àåò ñëåäóþùèå äåéñòâèÿ.
Øàã 0. Àëãîðèòì ïîèñêà â ãðàôå H Y U� ( , ) 2-ôàêòîðà ìèíèìàëüíîãî âåñà.
Çäåñü C cij n� [ ] — ñèììåòðè÷íàÿ ìàòðèöà ñòîèìîñòåé ðåáåð ãðàôà H , â êîòîðîé
c c Rij ji� � �
0
, åñëè { }i j U, � , è c cij ji� � � èíà÷å, R
0
� — ìíîæåñòâî äåéñòâè-
òåëüíûõ íåîòðèöàòåëüíûõ ÷èñåë. Ðåøåíèå çàäà÷è 2- f ïðåäñòàâëåíî ïåðåñòàíîâ-
êîé � � ([ ], [ ], , [ ])1 2 � n ìíîæåñòâà { }1 2, , ,� n íîìåðîâ ñòîëáöîâ ìàòðèöû C
ñ ìèíèìàëüíîé ñóììîé âåñîâ ðåáåð C c ci
i
n
i( ) ,[ ] [ ]� � � �
�
1
, i n�1, , ñðåäè âñåõ òà-
êèõ ïåðåñòàíîâîê ñòåïåíè n , â öèêëîâûõ ðàçëîæåíèÿõ êîòîðûõ êàæäûé êîíòóð
ñîäåðæèò íå ìåíåå òðåõ âåðøèí. Èñêîìûé 2-ôàêòîð îïðåäåëÿåòñÿ êàê ñîâåðøåí-
íîå ïàðîñî÷åòàíèå �n äâóäîëüíîãî ãðàôà D X Y E� ( , , ), ãäå X , Y — ìíîæåñòâî
âåðøèí, | | | |X Y n� � , E i j i X j Y� � �{( , ) | , } — íåïóñòîå ìíîæåñòâî ðåáåð ( , )i j
ñ âåñàìè c Rij � �
0
èç ìàòðèöû C , | | | |E U� 2 , cij � � , åñëè ( , )i j E� .
Ïîëîæèòü k �1, íàéòè ðåáðî ( , )i jk k âåñîì c c i j ni j ijk k
� �min | , , }{ 1 ,
I ik k� { }, J jk k� { }, �k k ki j� { }[ , ] , C ck i jk k
( )� � , Dk — îñòîâíîé ïîäãðàô ãðàôà D ,
ïîëó÷åííûé èç D óäàëåíèåì ðåáðà ( , )j ik k , j Xk � , i Yk � , â ìàòðèöå C ïîëîæèòü
c j ik k
� � .
Øàã 1. Ïîëîæèì k k� �1; åñëè k n� , òî êîíåö: ïîñòðîåíî ðåøåíèå � �� n
çàäà÷è 2- f .
Øàã 2. Â ïîäãðàôå Dk
1 íàéòè c c i X I j Y Ji j ij k kl l
� �
�
min | ,{ }1 1 ;
åñëè ci jl l
� � , òî ïîëîæèòü MIN 1 � � , èíà÷å � �
k k l li j1
1� �
[ , ], MIN C
k
1 1� �( )�
� �
C ck i jl l
( )� 1 , cj il l
� � , D D j ik k l l�
1 ( , ) , I I ik k l� �
1 { }, J J jk k l� �
1 { }.
Øàã 3. Äëÿ êàæäîé âåðøèíû j Jr k�
1 â Dk
1 íàéòè ðåáðà ( , )i jm r ñ âåñàìè
c c i X I Ri j ij km r r
� �
�
�min |{ }1 0
è ñôîðìèðîâàòü èç âåðøèí im ìíîæåñòâî X k ;
åñëè X k � �, òî ïîëîæèòü MIN 2 � � è ïåðåéòè ê øàãó 6.
Øàã 4. Äëÿ êàæäîé âåðøèíû i If k�
1 â Dk
1 íàéòè ðåáðà ( , )i jf p ñ âåñàìè
c c j Y J Ri j i j kf p f
� �
�
�min |{ }1 0
è ñôîðìèðîâàòü èç âåðøèí jp ìíîæåñòâî Yk ;
åñëè Yk � �, òî ïîëîæèòü MIN 2 � � è ïåðåéòè ê øàãó 6.
Øàã 5. Îïðåäåëèòü ïîäãðàô � �Dk , ïîðîæäåííûé ìíîæåñòâîì âåðøèí
X I J Yk k k k� � �
1 1 ïîäãðàôà Dk
1; äëÿ � �Dk ïîñòðîèòü âñïîìîãàòåëüíûé
âçâåøåííûé îðãðàô ( , )Z A , Z i X I Yk k k� � � �
{ }0 1 , è âûïîëíèòü â íåì ïîèñê
ïóòè, êðàò÷àéøåãî íà ìíîæåñòâå âñåõ ïóòåé â âåðøèíû Yk , äîñòèæèìûå èç i0 ;
åñëè ïîñòðîåí òàêîé ïóòü, òî â ïîäãðàôå � �Dk íàéòè ñîîòâåòñòâóþùèé åìó óâåëè-
÷èâàþùèé ïóòü Pk îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �k
1, à òàêæå � �
k k kP2
1�
�
( )
�
( )�k kP1 , MIN C
k
2 2� ( )� , èíà÷å ïîëîæèòü �
k
2 � � , MIN 2 � � .
Øàã 6. Åñëè MIN MIN1 2� � � , òî êîíåö: äëÿ ãðàôà H Y U� ( , ) ñ ìàòðèöåé
âåñîâ ðåáåð C cij n� [ ] çàäà÷à 2- f íå èìååò ðåøåíèÿ; åñëè MIN1 � � èëè
MIN 2 � � , òîãäà åñëè MIN MIN1 2� , òî � �k k
� 1 , c j il l
� � , è ïåðåéòè ê øàãó 1,
èíà÷å � �k k
� 2 , �k l li j l k� �{ }[ , ] | ,1 , I i l kk l� �{ }| ,1 , J j l kk l� �{ }| ,1 , îáðàçî-
âàòü ïîäãðàô Dk , óäàëèâ â � �Dk ðåáðà ( , )j il l , j Il k� , i Jl k� , â ìàòðèöå C ïîëî-
æèòü cj il l
� � , l k�{ }1 2, , ,� , è ïåðåéòè ê øàãó 1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 159
Òåîðåìà 1. Àëãîðèòì êîððåêòíî âûïîëíÿåò çà âðåìÿ O V(| | )3 ïîèñê ðåøå-
íèÿ çàäà÷è 2- f â ãðàôå H Y U� ( , ) ñ íåîòðèöàòåëüíûìè âåñàìè ðåáåð.
Äîêàçàòåëüñòâî. Àëãîðèòì îñòàíàâëèâàåòñÿ, êîãäà â äâóäîëüíîì ãðàôå
D X Y V� ( , , ), | | | | | |X Y V n� � � , ïîñòðîåíî ìàêñèìàëüíîå ïàðîñî÷åòàíèå �k
1,
k n� 2, . Ïàðîñî÷åòàíèå �k
1 ìàêñèìàëüíî, åñëè: à) ïîäãðàô Dk ãðàôà D íå ñî-
äåðæèò íè îäíîãî ðåáðà, êîòîðîå ìîæíî áûëî áû ïðèñîåäèíèòü ê �k
1, ÷òîáû
ïîëó÷èòü �
k
1 ; á) ïîäãðàô � �Dk ãðàôà D íå ñîäåðæèò óâåëè÷èâàþùåãî ïóòè îòíî-
ñèòåëüíî ïàðîñî÷åòàíèÿ �k
1 äëÿ ïîñòðîåíèÿ �
k
2 . Òðåáîâàíèå á) âûïîëíÿåòñÿ, ïî-
ñêîëüêó ñîãëàñíî óòâåðæäåíèþ 2 äëÿ ìàêñèìàëüíîãî ïàðîñî÷åòàíèÿ �k
1 äîñòà-
òî÷íî, ÷òîáû âñïîìîãàòåëüíûé îðãðàô ( , )Z A íå ñîäåðæàë ïóòåé èç âåðøèí ìíî-
æåñòâà X k â âåðøèíû ìíîæåñòâà Yk .
Òðóäîåìêîñòü àëãîðèòìà îöåíèâàåòñÿ ñ ó÷åòîì òîãî, ÷òî îíà ìàêñèìàëüíà,
ò.å. òîãäà, êîãäà èñõîäíûé ãðàô ïîëíûé. Ïðîöåññ ïîñòðîåíèÿ îïòèìàëüíîãî ðå-
øåíèÿ � �� n âêëþ÷àåò n ýòàïîâ. Ïåðâûé ýòàï çàâåðøàåòñÿ íà øàãå 0 ïîñòðîåíè-
åì �1 çà n n( ) /
1 2 îïåðàöèé. Íà îñòàëüíûõ ýòàïàõ íàõîäÿòñÿ ïàðîñî÷åòàíèÿ �
k
1 è
�
k
2 , k n� 2, . Ïîñòðîåíèå �
k
1 òðåáóåò ( )( ) /n k n k
�
1 2 îïåðàöèé. Äëÿ íàõîæäåíèÿ
�
k
1 íóæíî âûïîëíèòü 2 1( )n k
îïåðàöèé äëÿ ïîèñêà âåðøèí ìíîæåñòâ X k è Yk ,
k n�
1 1, , íå áîëåå ÷åì O n( ) îïåðàöèé äëÿ ïîñòðîåíèÿ ïîäãðàôà � �Dk è âñïîìî-
ãàòåëüíîãî îðãðàôà ( , )Z A , O n( )2 äåéñòâèé äëÿ ïîñòðîåíèÿ â ( , )Z A àëãîðèòìîì
Äåéêñòðû êðàò÷àéøåãî ïóòè Pk è íå áîëåå ÷åì O n( ) îïåðàöèé ñ ìíîæåñòâàìè ðå-
áåð Pk è ðåáåð òåêóùåãî ïàðîñî÷åòàíèÿ �k
1. Òàêèì îáðàçîì, êàæäûé ýòàï àëãî-
ðèòìà õàðàêòåðèçóåòñÿ êâàäðàòè÷íîé âðåìåííîé ñëîæíîñòüþ, à òðóäîåìêîñòü ðå-
øåíèÿ çàäà÷è 2- f îöåíèâàåòñÿ âåëè÷èíîé O n( )3 . �
ÏÐÈÌÅÐ ÐÅØÅÍÈß ÇÀÄÀ×È
Ãðàô H Y U� ( , ) , â êîòîðîì òðåáóåòñÿ îïðåäåëèòü 2-ôàêòîð ìèíèìàëüíîãî
âåñà, ïðåäñòàâëåí íà ðèñ. 4, à, à åãî ìàòðèöà ñòîèìîñòåé C — íà ðèñ. 4, á.
Øàã 0. Ïîëîæèì k �1, c c i jij12 1 6 1� � �min | , ,{ } , I1 1� { }, J1 2� { },
�1 1 2� { }[ , ] , C c( )�1 12 1� � , D1 — ïîäãðàô, ïîëó÷åííûé èç ãðàôà D X Y E� ( , , ) ,
ñîîòâåòñòâóþùåãî ìàòðèöå C , óäàëåíèåì ðåáðà (2, 1), c21 � � .
Øàã 1. Ïîëîæèì k � 2 .
Øàã 2. Â D1 c c i jij25 1 2 1� � � �min | ,{ } , � �
2
1
1 2 5 1 2 2 5� � �[ , ] [ , ], [ , ]{ },
MIN C c c1 1 1 22
1
12 25� � � � � �( )� , c52 � � , D D2 1 5 2�
( , ) , I 2 1 2� { }, , J2 2 5� { }, .
Øàã 3. Äëÿ âåðøèíû 2 1� J ðåáðî (5, 2) èìååò íàèìåíüøèé âåñ:
c c ii25 2 1 1� � �min |{ } , X 2 5� { }.
Øàã 4. Äëÿ âåðøèíû 1 �I1 ðåáðî (1, 6) èìååò íàèìåíüøèé âåñ:
c c jj16 1 2 1� � �min |{ } , Y
2
6� { }.
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
Ðèñ. 4
2 51
1 61
3 41 11
2
2
4
3
à á
1 2 3 4 5 6
1 � 1 3 � � 1
2 1 � 2 � 1 �
3 3 2 � 1 � �
4 � � 1 � 4 2
5 � 1 � 4 � 1
6 1 � � 2 1 �
j
i
Øàã 5. Ïîäãðàô � �D2 è ïîñòðîåííûé äëÿ íåãî îðãðàô ( , )Z A èçîáðàæåíû íà
ðèñ. 5, à è ðèñ. 5, á ñîîòâåòñòâåííî. Øòðèõîâîé ëèíèåé îáîçíà÷åíî ðåáðî, óäà-
ëåííîå èç ãðàôà ( , , )X Y E , æèðíîé — ðåáðî ïàðîñî÷åòàíèÿ �1. Ýòè ðåáðà îáðàçó-
þò êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü P2 îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �1;
� � �
2
2
1 2 2 1 5 2 1 6�
�
�( ) ( ) [ , ], [ , ]P P { }, MIN C c c2
2
2
52 16� � � �( )� 1 1 2� � .
Øàã 6. Òàê êàê MIN MIN1 2� , � �2 2
1� èëè �
2
2 . Ïóñòü � �2 2
1 1 2 2 5� � { }[ , ], [ , ] .
Ïðè k � 3 �
3
1 1 2 2 5 3 4� { }[ , ], [ , ], [ , ] , MIN C c c c1 1 1 1 3
3
1
12 25 34� � � � � � � �( )� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 161
Ðèñ. 5
áà
1 2 5
1 2 6
i0 61
6 � Y 2
1 2 3
1 2 3
5 6
5 6
i0
32
3 � Y 3
61
6 � Y 3
3
6
â ã
1 2 3
1 2 3
4 5
4 5
6
6
åä
i0
61
6 � Y4
32
3 � Y4
3
6
1
1 � Y4
1 2 3
1 2 3
4 5
4 5
6
6 i0
1
32
3 � Y5
3
4
5 6
æ ç
êè
i0
6
35
3 � Y6
4 31
1 2 3
1 2 3
4 5
4 5
6
6
Ïîäãðàô � �D3 äëÿ íàõîæäåíèÿ �
3
2 èçîáðàæåí íà ðèñ. 5, â, ñîîòâåòñòâóþùèé åìó
îðãðàô ( , )Z A — íà ðèñ. 5, ã. Â ( , )Z A âåñà äóã (3, 1), (6, 2), ( , )1 6 3�Y , ( , )2 3 3�Y îïðå-
äåëÿþòñÿ òàê: c c c( , )3 1 2 1 332 12� � � � � , c c c( , )6 2 1 1 265 25� � � � � , c ( , )1 6 1� ,
c ( , )2 3 2� .  îðãðàôå ( , )Z A ñîäåðæàòñÿ äâà êðàò÷àéøèõ ïóòè èç âåðøèí ìíîæåñ-
òâà X 3 3 6� { }, â âåðøèíû ìíîæåñòâà Y3 3 6� { }, : ( , , )3 1 6 3�Y , ( , , )6 2 3 3�Y . Âûáå-
ðåì ëþáîé èç íèõ, íàïðèìåð ( , , )3 1 6 3�Y . Â ïîäãðàôå � �D3 åìó ñîîòâåòñòâóåò
êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü P3 îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �2 1 2 2 5� { }[ , ], [ , ] ,
âêëþ÷àþùèé ðåáðà (3, 2), [1, 2], (1, 6). Ñëåäîâàòåëüíî, � �3
2
3 2�
�( )P
�
� � �( ) [ , ], [ , ] [ , ] [ , ], [ , ], [ , ]� 2 3 1 6 3 2 2 5 1 6 2 5 3 1P { } { } { }, MIN C2 1
3
2� � �( )� 1 2 4� � .
Ïîñêîëüêó MIN MIN1 2� , � �3 3
1 1 2 2 5 3 4� � { }[ , ], [ , ], [ , ] , I 3 1 2 3� { }, , , J 3 2 4 5� { }, , ,
â ïîäãðàôå D2 óäàëÿåòñÿ ðåáðî (4, 3).  ðåçóëüòàòå ïîëó÷èì ïîäãðàô D3
( )c c c21 52 43� � � � .
Ïîëîæèì k � 4 . Ïàðîñî÷åòàíèå �
4
1 ìîæíî ïîëó÷èòü ïðèñîåäèíåíèåì ê �3
ðåáðà (6, 1) èëè (5, 6). Èõ âåñà, ðàâíûå 1, ìèíèìàëüíû íà øàãå 2. Ïóñòü
�
4
1 1 2 2 5 3 4 6 1� { }[ , ], [ , ], [ , ], [ , ] . Ñëåäîâàòåëüíî, MIN C1 1 1 1 1 4
4
1� � � � � �( )� . Äëÿ
ïîñòðîåíèÿ �
4
2 ôîðìèðóþòñÿ ìíîæåñòâà X 4 6� { }, Y4 1 3 6� { }, , è ïîäãðàô � �D4
(ðèñ. 5, ä). Âñïîìîãàòåëüíûé îðãðàô ( , )Z A , ïîñòðîåííûé äëÿ � �D4 , ïðåäñòàâëåí
íà ðèñ. 5, å.  íåì êðàò÷àéøèé ïóòü ( , , )6 2 3 4�Y âêëþ÷àåò ðåáðà (6, 5), [ , ]2 5 , (2, 3)
êðàò÷àéøåãî óâåëè÷èâàþùåãî ïóòè P4 îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �3 â � �D4 .
Òàêèì îáðàçîì, �
4
2 1 2 2 3 3 4 6 5� { }[ , ], [ , ], [ , ], [ , ] , MIN C2 1 2 1 1 5
4
2� � � � � �( )� . Ïî-
ñ êîëüêó MIN MIN1 2
, èìååì � �4 4
1� , I 4 1 2 3 6� { }, , , , J4 1 2 4 5� { }, , , ,
D D4 3 1 6�
( , ) , c16 � � (ðèñ. 5, æ).
Ïîëîæèì k � 5. Çäåñü �5
1 1 2 2 5 3 4 5 6 6 1� { }[ , ], [ , ], [ , ], [ , ], [ , ] , C ( )� 5
1 5� ,
X 5 4 5� { }, , Y5 3� { }. Êðàò÷àéøèé ïóòü â îðãðàôå ( , )Z A ( , , )4 2 3 5�Y (ðèñ. 5, ç) ñî-
äåðæèò ðåáðà (4, 5), [2, 5], (2, 3), îáðàçóþùèå êðàò÷àéøèé óâåëè÷èâàþùèé ïóòü P5
îòíîñèòåëüíî ïàðîñî÷åòàíèÿ �4 â ïîäãðàôå � �D5 (ðèñ. 5, è); �
5
2 1 2 2 3� {[ , ], [ , ],
[ , ], [ , ], [ , ]3 4 4 5 6 1 }, MIN C2 1 2 1 4 1 9
5
2� � � � � � �( )� ; MIN MIN1 2
, � �5 5
1� ,
I 5 1 2 3 5 6� { }, , , , , J5 1 2 4 5 6� { }, , , , , D D5 4 1 6�
( , ) , c16 � � (ðèñ. 5, ê).
Ïîëîæèì k � 6. Çäåñü MIN1 � � , ïîñêîëüêó X I
�5 4{ }, Y J
�5 3{ },
à c43 � � ; X 6 4� { }, Y6 3� { }. Ïîýòîìó ïîëàãàåì � �5 5
2 1 2 2 3 3 4� � {[ , ], [ , ], [ , ],
[ , ], [ , ]4 5 6 1 }, I 5 1 2 3 4 6� { }, , , , , J5 2 3 4 5 1� { }, , , , , c c c c c21 32 43 54 61� � � � � � .
Íà øàãå 3 ïîñòðîåíèÿ �6 åäèíñòâåííûì ðåáðîì, êîòîðîå ìîæíî ïðèñîåäèíèòü
ê ïàðîñî÷åòàíèþ �5 , ÿâëÿåòñÿ ðåáðî (5, 6), c56 1� . Ñëåäîâàòåëüíî, � �6 6
1� �
� { }[ , ], [ , ], [ , ], [ , ], [ , ], [ , ]1 2 2 3 3 4 4 5 6 1 5 6 , MIN1 1 2 1 4 1 1 9� � � � � � � .
Ðåøåíèå çàäà÷è 2- f ïðåäñòàâëåíî ãàìèëüòîíîâûì öèêëîì (1, 2, 3, 4, 5, 6, 1). �
ÇÀÊËÞ×ÅÍÈÅ
Ïîèñê ðåøåíèÿ çàäà÷è 2- f â ïðîèçâîëüíîì âçâåøåííîì ãðàôå H V U� ( , )
ñ ìàòðèöåé ñòîèìîñòåé C êîððåêòíî âûïîëíÿåòñÿ â äâóäîëüíîì ãðàôå
D X Y E� ( , , ) , | | | | | |X Y V� � , | | | |E U� 2 , çàäàâàåìîì òîé æå ìàòðèöåé C . Çà-
äà÷à 2- f ôîðìóëèðóåòñÿ êàê îãðàíè÷åííàÿ âåðñèÿ çàäà÷è î íàçíà÷åíèÿõ. Åå
ðåøåíèå ïðåäñòàâëåíî ïåðåñòàíîâêîé ñòîëáöîâ ìàòðèöû C ñ öèêëîâûì ðàçëî-
æåíèåì, â êîòîðîì êàæäûé êîíòóð ñîäåðæèò íå ìåíåå òðåõ äóã. Îïòèìàëüíîå
ðåøåíèå ÿâëÿåòñÿ ñîâåðøåííûì ïàðîñî÷åòàíèåì, ïîëó÷åííûì â ðåçóëüòàòå ïî-
øàãîâîãî âûáîðà ðåáåð ãðàôà D , íà÷èíàÿ ñ ðåáðà ìèíèìàëüíîãî âåñà. Íà êàæ-
äîì øàãå ñòðîèòñÿ äîïóñòèìîå ïàðîñî÷åòàíèå �k , k n�
1 1, , ñ íàèìåíüøåé
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3
ñóììîé âåñîâ k ðåáåð. Î÷åðåäíîå ïàðîñî÷åòàíèå �k�1 íàõîäèòñÿ ëèáî ïîñòðî-
åíèåì êðàò÷àéøåãî óâåëè÷èâàþùåãî ïóòè îòíîñèòåëüíî �k , ëèáî äîáàâëåíèåì
ê �k ðåáðà, âåñîì íå áîëüøèì âåñà ëþáîãî ðåáðà, êîòîðîå îáðàçóåò �k�1.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. G a b o w H . N . A good algorithm for smallest spanning trees with a degree constraint // Networks. —
1978. — 8, N 3. — P. 201–208.
2. Ë î â à ñ Ë . , Ï ë à ì ì å ð Ì . Ïðèêëàäíûå çàäà÷è òåîðèè ãðàôîâ. Òåîðèÿ ïàðîñî÷åòàíèé â ìàòåìàòè-
êå, ôèçèêå, õèìèè. — Ì.: Ìèð, 1998. — 653 ñ.
3. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæíîñòü. —
Ì.: Ìèð, 1985. — 510 ñ.
4. Ñ å ð ã å å â Ñ . È . Ñèììåòðè÷íàÿ çàäà÷à êîììèâîÿæåðà. II. Íîâûå íèæíèå ãðàíèöû // Àâòîìàòèêà
è òåëåìåõàíèêà. — 2010. — ¹ 4. — Ñ. 150–167.
5. Ë å â ÷ å í ê î À . Þ . , Ì î ð î ç î â À .  . , Ï à í è ø å â À .  . Áûñòðûé àëãîðèòì ðåøåíèÿ çàäà÷è
î íàçíà÷åíèÿõ äëÿ íàõîæäåíèÿ íèæíåé ãðàíèöû ñòîèìîñòè ìàðøðóòà êîììèâîÿæåðà // Èñêóññòâåí-
íûé èíòåëëåêò. — 2011. — Âûï. 4. — Ñ. 406–416.
6. Õ à ð à ð è Ô . Òåîðèÿ ãðàôîâ. — Ì.: Ìèð, 1973. — 300 ñ.
Íàä³éøëà äî ðåäàêö³¿ 08.06.2015
Î.Á. Ìàöèé, À.Â. Ìîðîçîâ, À.Â. Ïàí³øåâ
ØÂÈÄÊÈÉ ÀËÃÎÐÈÒÌ ÇÍÀÕÎÄÆÅÍÍß 2-ÔÀÊÒÎÐÀ ̲ͲÌÀËÜÍί ÂÀÃÈ
Àíîòàö³ÿ. Ðîçãëÿíóòî çàäà÷ó ì³í³ì³çàö³¿ ó ãðàô³ H = (V, U) ñóìè âàã ðåáåð
ï³äìíîæèíè � �U U , ùî óòâîðþþòü ñóêóïí³ñòü ïðîñòèõ öèêë³â, ÿê³ íå ïåðå-
òèíàþòüñÿ ó âåðøèíàõ � �V ³ ïîêðèâàþòü V. Ðîçãëÿíóòà çàäà÷à (çàäà÷à 2-f)
ìîæå áóòè ïîë³íîì³àëüíî ðîçâ’ÿçàíà àëãîðèòìàìè, ÿê³ õàðàêòåðèçóþòüñÿ
òåõí³÷íèìè òðóäíîùàìè, ùî ïåðåøêîäæàþòü ïðèñêîðåííþ ïðîöåñó îá÷èñ-
ëåíü. Ðîçâ’ÿçîê çàäà÷³ 2-f çíàõîäèòüñÿ çâåäåííÿì ¿¿ äî á³ëüø ïðîñòîãî äâî-
÷àñòêîâîãî âèïàäêó. Ðåçóëüòàò ïðåäñòàâëåíî äîñêîíàëîþ ïàðîñïîëóêîþ äâî-
÷àñòêîâîãî ãðàôà, â³äïîâ³äíîþ ðîçâ’ÿçêó çàäà÷³ ïðî ïðèçíà÷åííÿ, ó öèêëî-
âîìó ðîçâèíåíí³ ÿêî¿ êîæíèé êîíòóð ì³ñòèòü íå ìåíøå òðüîõ äóã.
Êëþ÷îâ³ ñëîâà: 2-ôàêòîð, çàäà÷à ïðî ïðèçíà÷åííÿ, ïàðîñïîëóêà, äâî÷àñòêîâèé
ãðàô, çá³ëüøóâàëüíèé øëÿõ.
O.B. Matsiy, A.V. Morozov, A.V. Panishev
FAST ALGORITHM TO FIND THE 2-FACTOR OF MINIMUM WEIGHT
Abstract. The paper considers the minimization of the sum of weights of edges
forming a subset of the set of disjoint simple cycles at the vertices in the graph
H = (V, U) and cover V. This problem (2-f problem) is solvable in polynomial
algorithms, which are characterized by technical difficulties that hinder
accelerate computing. The solution of 2-f is reducing it to a simple bipartite
case. The desired result is represented by a perfect matching of a bipartite graph
corresponding to the solution of the assignment problem, in which each
expansion cycle circuit comprises at least three arcs.
Keywords: 2-factor, the assignment problem, matching, bipartite graph,
increasing path.
Ìàöèé Îëüãà Áîðèñîâíà,
àññèñòåíòêà Õàðüêîâñêîãî íàöèîíàëüíîãî àâòîìîáèëüíî-äîðîæíîãî óíèâåðñèòåòà,
e-mail: om21@mail.ru.
Ìîðîçîâ Àíäðåé Âàñèëüåâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò, äåêàí ôàêóëüòåòà Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëîãè÷åñêîãî
óíèâåðñèòåòà, e-mail: morozov.andriy@gmail.com
Ïàíèøåâ Àíàòîëèé Âàñèëüåâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð, çàâåäóþùèé êàôåäðîé Æèòîìèðñêîãî ãîñóäàðñòâåííîãî òåõíîëî-
ãè÷åñêîãî óíèâåðñèòåòà, e-mail: pzs.ztu@gmail.com.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 3 163
|