Разрезы в неориентированных графах. II
Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/190454 |
| 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: | Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-190454 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1904542025-02-09T14:45:51Z Разрезы в неориентированных графах. II Розрізи в неорієнтованих графах. IІ Cuts in undirected graphs. II Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков. Запропоновано два алгоритми перетворення поточної бази поліматроїда до нової з метою поліпшення значення цільової функції. Встановлено еквівалентність задачі максимального розрізу на заданому графі і задачі знаходження мінімального розрізу, що відокремлює джерело і стік в мережі, побудованої відносно деякої бази розширеного поліматроїда. Сформульовано необхідні та достатні умови оптимальності розв'язування задачі максимального розрізу на неорієнтованих графах в термінах теорії потоків. To improve the value of the objective function, two algorithms are proposed for transforming the current base into a new one. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on non-oriented graphs in terms of flow theory are formulated. 2020 Article Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190454 519.8 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Шарифов, Ф.А. Гуляницкий, Л.Ф. Разрезы в неориентированных графах. II Кибернетика и системный анализ |
| description |
Предложены 2 алгоритма преобразования текущей базы полиматроида в новую для улучшения значения целевой функции. Установлена эквивалентность задачи максимального разреза на заданном графе и задачи нахождения минимального разреза, отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полиматроида. Сформулированы необходимые и достаточные условия оптимальности решения задачи максимального разреза на неориентированных графах в терминах теории потоков. |
| format |
Article |
| author |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_sort |
Шарифов, Ф.А. |
| title |
Разрезы в неориентированных графах. II |
| title_short |
Разрезы в неориентированных графах. II |
| title_full |
Разрезы в неориентированных графах. II |
| title_fullStr |
Разрезы в неориентированных графах. II |
| title_full_unstemmed |
Разрезы в неориентированных графах. II |
| title_sort |
разрезы в неориентированных графах. ii |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2020 |
| topic_facet |
Системний аналіз |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/190454 |
| citation_txt |
Разрезы в неориентированных графах. II / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 5. — С. 70–79. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šarifovfa razrezyvneorientirovannyhgrafahii AT gulânickijlf razrezyvneorientirovannyhgrafahii AT šarifovfa rozrízivneoríêntovanihgrafahií AT gulânickijlf rozrízivneoríêntovanihgrafahií AT šarifovfa cutsinundirectedgraphsii AT gulânickijlf cutsinundirectedgraphsii |
| first_indexed |
2025-11-26T23:56:51Z |
| last_indexed |
2025-11-26T23:56:51Z |
| _version_ |
1849899261002514432 |
| fulltext |
ÓÄÊ 519.8
Ô.À. ØÀÐÈÔÎÂ, Ë.Ô. ÃÓËßÍÈÖÊÈÉ
ÐÀÇÐÅÇÛ Â ÍÅÎÐÈÅÍÒÈÐÎÂÀÍÍÛÕ ÃÐÀÔÀÕ. II1
Àííîòàöèÿ. Ïðåäëîæåíû äâà àëãîðèòìà ïðåîáðàçîâàíèÿ òåêóùåé áàçû ïî-
ëèìàòðîèäà â íîâóþ äëÿ óëó÷øåíèÿ çíà÷åíèÿ öåëåâîé ôóíêöèè. Óñòàíîâëå-
íà ýêâèâàëåíòíîñòü çàäà÷è ìàêñèìàëüíîãî ðàçðåçà íà çàäàííîì ãðàôå è çà-
äà÷è íàõîæäåíèÿ ìèíèìàëüíîãî ðàçðåçà, îòäåëÿþùåãî èñòî÷íèê è ñòîê
â ñåòè, ïîñòðîåííîé îòíîñèòåëüíî íåêîòîðîé áàçû ðàñøèðåííîãî ïîëèìàò-
ðîèäà. Ñôîðìóëèðîâàíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ îïòèìàëüíîñ-
òè ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà íà íåîðèåíòèðîâàííûõ ãðàôàõ
â òåðìèíàõ òåîðèè ïîòîêîâ.
Êëþ÷åâûå ñëîâà: ãðàôû, ðàçðåçû, âûïóêëàÿ ôóíêöèÿ, ñïåöèàëüíûå ìíîãîã-
ðàííèêè, ïîëèìàòðîèä.
ÂÂÅÄÅÍÈÅ
Íàñòîÿùàÿ ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì ðàáîòû [1], â êîòîðîé ìîäåëü çàäà-
÷è ìàêñèìàëüíîãî ðàçðåçà ñîäåðæèò ïåðåìåííûå äëÿ êàæäîé âåðøèíû ðàñ-
ñìàòðèâàåìîãî ãðàôà. Ñïåöèôèêà åå îãðàíè÷åíèé çàñëóæèâàåò âíèìàíèÿ, ïî-
ñêîëüêó îïðåäåëåíèå èñõîäíîãî äîïóñòèìîãî ðåøåíèÿ ìîæíî âûïîëíèòü ñ ïî-
ìîùüþ ãðèäè àëãîðèòìà çà âðåìÿ O m( ). Ïðè ýòîì îïðåäåëåííîå ðåøåíèå
ÿâëÿåòñÿ êðàéíåé òî÷êîé [2] ìíîãîãðàííèêà ee îãðàíè÷åíèé, ò.å. áàçîé [3] ïî-
ëèìàòðîèäà x B� ( )� (ñì. [1]). Ó÷èòûâàÿ ñïåöèôèêó öåëåâîé ôóíêöèè, ìîæíî
îïðåäåëèòü äîïóñòèìîå ðåøåíèå, â êîòîðîì öåëåâàÿ ôóíêöèÿ ïî÷òè äîñòèãàåò
ñâîåãî ìàêñèìóìà. Äëÿ ýòîãî íóæíî íàéòè îïòèìàëüíîå ëèíåéíîå óïîðÿäî÷å-
íèå âåðøèí (ñ ó÷åòîì òîïîëîãèè äàííîãî ãðàôà), â ñîîòâåòñòâèè ñ óñòàíîâëåí-
íûì â íåì ïîðÿäêîì ìíîãèì ïåðåìåííûì ïðèñâîèòü èõ ìàêñèìàëüíî äîïóñòè-
ìîå çíà÷åíèå. Òàêîå äîïóñòèìîå ðåøåíèå çàäà÷è ìîæíî íàéòè àëãîðèòìîì [4]
çà âðåìÿ O nm( ). Ïðè ýòîì êàæäîìó äîïóñòèìîìó ðåøåíèþ ñîîòâåòñòâóåò
îñòîâíîé äâóäîëüíûé ïîäãðàô (äëÿ êðàòêîñòè èíîãäà áóäåì ïèñàòü äâóäîëü-
íûé ïîäãðàô) çàäàííîãî ãðàôà, è îáðàòíîå òîæå âåðíî.
Ïîñêîëüêó çàäà÷à ìàêñèìàëüíîãî ðàçðåçà îòíîñèòñÿ ê êëàññó NP-òðóäíûõ
çàäà÷, îïðåäåëåíèå ëèíåéíîãî óïîðÿäî÷åíèÿ âåðøèí, ñ èñïîëüçîâàíèåì êîòîðîãî
îïòèìàëüíîå ðåøåíèå çàäà÷è ìîæíî íàéòè ãðèäè àëãîðèòìîì, ñîïðÿæåíî ñ áîëü-
øèìè òðóäíîñòÿìè. Ïðåäëîæåíî äâà àëãîðèòìà ïðåîáðàçîâàíèÿ óïîìÿíóòîãî èñ-
õîäíîãî äîïóñòèìîãî ðåøåíèÿ â äðóãîå ñ öåëüþ óëó÷øèòü çíà÷åíèå ôóíêöèè.
 ïåðâîì àëãîðèòìå âíà÷àëå îïðåäåëåííûì îáðàçîì îïðåäåëÿþòñÿ ïîäìíîæåñ-
òâà âåðøèí êàæäîé äîëè ýòîãî äâóäîëüíîãî ïîäãðàôà.  ðåçóëüòàòå èñêëþ÷åíèÿ
è âêëþ÷åíèÿ ýòèõ ïîäìíîæåñòâ â ðàçíûå äîëè ïîëó÷àåòñÿ íîâîå äîïóñòèìîå ðå-
øåíèå. Ïðè ýòîì, åñëè çíà÷åíèå öåëåâîé ôóíêöèè óëó÷øàåòñÿ, ïðîöåññ ïðîäîë-
æàåòñÿ îòíîñèòåëüíî òåêóùåãî ðåøåíèÿ, èíà÷å àëãîðèòì çàâåðøàåò ðàáîòó. Âî
âòîðîì àëãîðèòìå äëÿ ïîèñêà íîâîãî äîïóñòèìîãî ðåøåíèÿ èñïîëüçóåòñÿ
àëãîðèòì ïðåîáðàçîâàíèÿ îäíîé èç äâóõ ïðîèçâîëüíûõ áàç â äðóãóþ,
ïðåäëîæåííûé â [5].
 íàñòîÿùåé ñòàòüå ïîêàçàíà ýêâèâàëåíòíîñòü çàäà÷è ìàêñèìàëüíîãî ðàçðåçà
íà çàäàííîì ãðàôå çàäà÷å íàõîæäåíèÿ ìèíèìàëüíîãî ðàçðåçà, îòäåëÿþùåãî èñ-
70 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5
1Ïðîäîëæåíèå. Íà÷àëî â ¹ 4, 2020.
� Ô.À. Øàðèôîâ, Ë.Ô. Ãóëÿíèöêèé, 2020
òî÷íèê è ñòîê â ñåòè, ïîñòðîåííîé îòíîñèòåëüíî ðàññìîòðåííîé áàçû ðàñøèðåí-
íîãî ïîëèìàòðîèäà. Ñôîðìóëèðîâàíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ
îïòèìàëüíîñòè ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà íà íåîðèåíòèðîâàííûõ
ãðàôàõ â òåðìèíàõ òåîðèè ïîòîêîâ.
1. ÌÅÒÎÄ ÐÅØÅÍÈß ÇÀÄÀ×È ÌÀÊÑÈÌÀËÜÍÎÃÎ ÐÀÇÐÅÇÀ
Äëÿ ðàáîòû ïðèâåäåííûõ äàëåå àëãîðèòìîâ íåîáõîäèìî îïðåäåëèòü íà÷àëüíûå
çíà÷åíèÿ ïåðåìåííûõ çàäà÷è, ìîäåëü êîòîðîé ïðåäñòàâëåíà â [1], â ñëåäóþ-
ùåì âèäå:
MaxCut f x x d
V
*
max ( ) | |� � �
�
�
�
�
�
�
���
2 �
�
� , (1)
x B� (�� . (2)
Ïîñêîëüêó âûïóêëàÿ öåëåâàÿ ôóíêöèÿ (1) äîñòèãàåò ìàêñèìàëüíîãî çíà÷å-
íèÿ ïî êðàéíåé ìåðå â îäíîé èç êðàéíèõ òî÷åê (áàç) B ( )� [6], êîòîðûå ìîæíî
íàéòè ãðèäè àëãîðèòìîì çà âðåìÿ O m( ), ïðåäïî÷òèòåëüíûì ìåòîäîì ðåøåíèÿ çà-
äà÷è (1), (2) ÿâëÿþòñÿ ïðèâåäåííûå äàëåå äâà àëãîðèòìà ïðåîáðàçîâàíèÿ îäíîé
êðàéíåé òî÷êè â äðóãóþ êàê ñïîñîá ïðîäâèæåíèÿ ê ãëîáàëüíîìó ìàêñèìóìó.
Âõîäîì ýòèõ àëãîðèòìîâ ïðåîáðàçîâàíèÿ ÿâëÿåòñÿ êðàéíÿÿ òî÷êà x ìíîãîãðàííè-
êà B ( )� , îïðåäåëÿåìàÿ àëãîðèòìîì [4] çà âðåìÿ O nm( ).
Ïðè ýòîì òî÷êè x è y d x� � óäîâëåòâîðÿþò óñëîâèÿì
x
d
a V�
�
� �� � � �
2
ïðè , y
d
b w Vw
w
w� � � �
2
ïðè ,
(3)
ãäå a� è bw — íåîòðèöàòåëüíûå ÷èñëà. Èç ýòèõ óñëîâèé ñëåäóåò, ÷òî çíà÷åíèå
(1) â òî÷êå x íå ìîæåò ñóùåñòâåííî îòëè÷àòüñÿ îò ãëîáàëüíîãî ìàêñèìóìà öå-
ëåâîé ôóíêöèè. Äëÿ îïðåäåëåíèÿ äðóãîé êðàéíåé òî÷êè ìíîãîãðàííèêà B ( )�
ñ ëó÷øèì çíà÷åíèåì öåëåâîé ôóíêöèè (1) ðàññìîòðèì äîïîëíèòåëüíûå ñâîéñòâà
äëÿ òî÷êè x.
Ïîñêîëüêó x V y V y V x V( ) ( ) ( ) ( )� � � �� � � , èç íåðàâåíñòâà (3) äëÿ âåðøèíû
w V� � ïîëó÷àåì
x V y V y V x V
d V
b V x V( ) ( ) ( ) ( )
( )
( ) ( )� � � �
�
� �� � � � � �
2
.
Èç ýòîãî íåðàâåíñòâà ñëåäóåò, ÷òî y V E
d V
b V( ) | |
( )
( )�
�
�� � �
2
. Àíàëîãè÷íî
ìîæíî ïîêàçàòü, ÷òî x V E
d V
a V( ) | |
( )
( )�
�
�� � �
2
. Ñóììèðóÿ ýòè äâà íåðàâåíñòâà,
ïîëó÷àåì
x V y V E V( ) ( ) | | | |� �� � � � , (4)
ãäå ÷èñëî � �
�� �a V b V
V
( ) ( )
| |
íàçûâàåòñÿ ïëîòíîñòüþ ãðàôà G V E� ( , ) îòíîñè-
òåëüíî áàçû x. Îòìåòèì, ÷òî � �
| |
| |
E
V
è â (4) èìååì ðàâåíñòâî, åñëè G —
äâóäîëüíûé ãðàô. ×òîáû îïðåäåëèòü ìàêñèìàëüíûé ðàçðåç ïî äâîéñòâåííîìó ðàâå-
íñòâó, íåîáõîäèìî íàéòè áàçó x èç B ( )� , äëÿ êîòîðîé ïëîòíîñòü ìàêñèìàëüíà.
Ðàññìîòðèì îñòîâíîé äâóäîëüíûé ïîäãðàô H ñ ìíîæåñòâàìè âåðøèí V x� ( )
è V x� ( ) êàæäîé äîëè è ìíîæåñòâîì ðåáåð �( ( ))V x� . ßñíî, ÷òî çíà÷åíèå � áóäåò
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5 71
ìàêñèìàëüíûì, åñëè â ïîäãðàôå H ñòåïåíè âñåõ âåðøèí ñóùåñòâåííî îòëè÷íû
îò
d�
2
. Ïîýòîìó àëãîðèòìû èñêëþ÷åíèÿ è âêëþ÷åíèÿ âíà÷àëå âûäåëÿþò ïîäìíî-
æåñòâî V 0 âåðøèí, ñòåïåíè êîòîðûõ â ïîäãðàôå H îòëè÷íû îò
d�
2
íà ìèíèìàëü-
íóþ âåëè÷èíó. Íå íàðóøàÿ îáùíîñòè, ìîæíî ïðåäïîëîæèòü, ÷òî â íà÷àëå ðîáî-
òû ýòèõ àëãîðèòìîâV V0 � � . Ñîãëàñíî ëåììå 1 (ñì. [1]) â êðàéíåé òî÷êå x çíà÷å-
íèå ôóíêöèè (1) íå èçìåíèòñÿ, åñëè â ïîäãðàôå H íå ïðîèñõîäèò ïåðåìåùåíèÿ
íåêîòîðûõ âåðøèí èç îäíîé äîëè â äðóãóþ.
Òåïåðü ðàññìîòðèì ðàáîòó ïåðâîãî àëãîðèòìà èñêëþ÷åíèÿ è âêëþ÷åíèÿ.
Ïóñòü N w V w V( ) :( , ) ( )� � �� � � �{ } è W N ii k
�
�
( )
,...,
�
1� , ãäå W k0 � { , }� � �� � —
ìèíèìàëüíîå ïî âêëþ÷åíèþ ïîäìíîæåñòâî ìíîæåñòâà V 0 òàêîå, ÷òî
�f E E� � ��
�| | | |0 0. Çäåñü E�
� — ìíîæåñòâî ðåáåð ( , )� w ñ êîíå÷íûìè âåðøèíà-
ìè � �W0 , w V x W� � ( ) \ 0 èëè � �W, w V x W� � ( ) \ â ãðàôå G V E� ( , ) è E0 — ìíî-
æåñòâî ðåáåð ñ îäíîé êîíå÷íîé âåðøèíîé â W0 èëè W â äâóäîëüíîì ïîäãðàôå H .
Ïóñòü H1 — îñòîâíîé äâóäîëüíûé ãðàô ñ ìíîæåñòâîì ðåáåð �( )V�
1 è ìíîæåñòâà-
ìè âåðøèí V�
1 è V�
1 êàæäîé äîëè, ïîëó÷åííûé ïîñëå ïåðåìåùåíèÿ ïîäìíîæåñòâ
âåðøèí W è W0 èç îäíîé äîëè â äðóãóþ â ïîäãðàôå H . Ëåãêî ïîêàçàòü, ÷òî
f x f x f� �� �( ) ( )1 � äëÿ áàçû x B1 � ( )� , ïîðîæäåííîé ïî ëèíåéíîìó óïîðÿäî÷å-
íèþ L V V� � �( , )1 1 . Ðàçðåç �( )V�
1 ïîëó÷àåòñÿ ïîñëå èñêëþ÷åíèÿ ìíîæåñòâà E0 è
âêëþ÷åíèÿ E�
� â H1. Åñëè �f � 0 äëÿ íåêîòîðîãî ïîäìíîæåñòâà V V0 1� � èëè
V V0 1� � , òî äàííûé ïðîöåññ ñíîâà ïîâòîðÿåòñÿ äëÿ îñòîâíîãî äâóäîëüíîãî ïîä-
ãðàôà H1.  ïðîòèâíîì ñëó÷àå àëãîðèòì èñêëþ÷åíèÿ è âêëþ÷åíèÿ çàâåðøàåò
ðàáîòó.
Ýôôåêòèâíîñòü óêàçàííîãî àëãîðèòìà èñêëþ÷åíèÿ è âêëþ÷åíèÿ êàñàòåëüíî
ñõîäèìîñòè ê îïòèìàëüíîìó ðåøåíèþ çàâèñèò îò ïðàâèë âûáîðà âåðøèí äëÿ èñ-
êëþ÷åíèÿ èç îäíîé äîëè è âêëþ÷åíèÿ â äðóãóþ äîëþ òåêóùåãî îñòîâíîãî äâó-
äîëüíîãî ïîäãðàôà. Î÷åâèäíî, ÷òî åñëè êîìïîíåíòû áàçû x B� ( )� óäîâëåòâîðÿ-
þò óñëîâèþ x d� �� �0 äëÿ áîëüøîãî êîëè÷åñòâà âåðøèí � èç V , òî ïëîòíîñòü �
ãðàôà G V E� ( , ) ìàêñèìàëüíà. Èíûìè ñëîâàìè, âûðàæåíèå â ïðàâîé ÷àñòè ðàâåí-
ñòâà (4) ïðèíèìàåò ìèíèìàëüíîå çíà÷åíèå, åñëè íåðàâåíñòâî 0� �x d� �
âûïîëíÿåòñÿ, ïî ìåíüøåé ìåðå, äëÿ ìèíèìàëüíîãî ÷èñëà âåðøèí �.
Äàëåå ïîêàçàíî, ÷òî â îïòèìàëü-
íîì ðåøåíèè çàäà÷è ìàêñèìàëüíîãî
ðàçðåçà êîëè÷åñòâî ïåðåìåííûõ, óäîâ-
ëåòâîðÿþùèõ ýòèì íåðàâåíñòâàì,
äåéñòâèòåëüíî ìèíèìàëüíîå.
 êà÷åñòâå ïðèìåðà ðàññìîòðèì
çàäà÷ó (1), (2) íà ãðàôå, ïðåäñòàâëåí-
íîì íà ðèñ. 1, äëÿ ðåøåíèÿ êîòîðîé
ïðèìåíÿåòñÿ àëãîðèòì èñêëþ÷åíèÿ è
âêëþ÷åíèÿ.
Íà ýòàïå ïðîñìîòðà âåðøèí äëÿ âûáîðà âåðøèíû 4 àëãîðèòì O nm( ) [4] îïðå-
äåëÿåò ëèíåéíîå óïîðÿäî÷åíèå L L L L L L L L� { }4 7 2 3 1 6 5 8� � � � � � � âåð-
øèíû ãðàôà G è áàçó
x x x x x x x x x� � � � � � � � �( , , , , , , , )4 7 2 3 1 6 5 85 3 3 2 0 2 0 0 . (5)
72 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5
Ðèñ. 1. Ãðàô G V E� ( , )
Íåñëîæíî óáåäèòüñÿ, ÷òî áàçû x è y d x� � óäîâëåòâîðÿþò óñëîâèÿì (3), ïðè
ýòîì V� � { , , }4 7 2 è V� � { }1 3 5 6 8, , , , . Òàêèì îáðàçîì,
x V y V f x( ) , ( ) , ( )� � �� � �11 1 10,
y V x V f x( ) , ( ) , ( )� � �� � �14 4 10,
f x x V y V y V x V( ) ( ( ) ( )) ( ( ) ( ))� � � � �� � � � 20.
Íà ðèñ. 2 ïîêàçàí îñòîâíîé äâóäîëüíûé ïîäãðàô H ñ ìíîæåñòâàìè âåðøèí
V� , V� è ðåáåð �( )V� . Ïîñêîëüêó âåðøèíû � � � �{ }3 6 8 1, , V èìåþò ñòåïåíè
d�
2
è
ïðè ýòîì � f � 0 äëÿ ìèíèìàëüíîãî ïî âêëþ÷åíèþ ïîäìíîæåñòâà { }3 6, , âåðøè-
íû 3 6, ïåðåìåùàþòñÿ â äðóãóþ äîëþ, ñëåäîâàòåëüíî, âåðøèíà 4 òîæå äîëæíà ïå-
ðåìåùàòüñÿ.
 ðåçóëüòàòå îïðåäåëÿåòñÿ áàçà
x x x x x x x x x* * * * * * * * *( , , , , , , ,� � � � � � � � �7 2 3 6 1 5 8 42 3 4 4 0 0 0 2), (6)
îòíîñèòåëüíî êîòîðîé îïðåäåëåííûé ðàçðåç ñîäåðæèò ðåáðà, ïåðåñåêàþùèåñÿ
ñî øòðèõîâûìè ëèíèÿìè íà ðèñ. 3. Ëåãêî ïðîâåðèòü, ÷òî f x� �( )* 11,
f x� �( )* 11 è f x( )* � 22. Ðàçðåç, îïðåäåëåííûé áàçîé x * , ìàêñèìàëüíûé.
Âòîðîé àëãîðèòì ïðåîáðàçîâàíèÿ îñíîâàí íà ñëåäóþùåì âàæíîì ðåçóëüòà-
òå. Â [5] ïðåäëîæåí ýôôåêòèâíûé àëãîðèòì ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ îä-
íîé èç äâóõ ïðîèçâîëüíûõ áàç (íàïðèìåð, x è x1) èç B ( )� â äðóãóþ áàçó. Îïðåäå-
ëåíèå áàçû x x Bu w
1 � � � �
�( ) ( ) ïðåîáðàçîâàíèåì x B� ( )� îòíîñèòåëüíî
âåðøèíû w x u�dep( , ) íàçûâàåòñÿ ýëåìåíòàðíûì ïðåîáðàçîâàíèåì áàç x x, 1
(elementary transformations of bases), ãäå
� — õàðàêòåðèñòè÷åñêèé âåêòîð,
ñîîòâåòñòâóþùèé âåðøèíå � �V , è
dep { }( , ) ; , , ( ) ( )x u V x Bu� � � � � � �� �
��0 .
Òåîðåìà 1 [5]. Ïðåîáðàçîâàíèå îäíîé (íàïðèìåð, x) èç äâóõ ïðîèçâîëüíûõ
áàç x x B, ( )1 � � â äðóãóþ ( x1) ìîæíî âûïîëíèòü íå áîëåå ÷åì çà n2 4/ ýëåìåí-
òàðíûõ ïðåîáðàçîâàíèé òàêèì îáðà-
çîì, ÷òî íà êàæäîé èòåðàöèè êàæ-
äàÿ êîìïîíåíòà x� ìîíîòîííî
óâåëè÷èòñÿ, åñëè x x� �� 1 , è ìîíî-
òîííî óìåíüøèòñÿ, åñëè x x� �� 1 .
Âõîäîì äëÿ âòîðîãî àëãîðèòìà
ÿâëÿåòñÿ òàêæå áàçà x B� ( )� è ïîä-
ìíîæåñòâî âåðøèí { }� �1, ..., k ìíî-
æåñòâà V V x0 � � ( ). Äëÿ óñêîðåíèÿ
ðàáîòû àëãîðèòìà âåðøèíû
� �1, ,� k íåîáõîäèìî óïîðÿäî÷èòü
â ïîðÿäêå íåóáûâàíèÿ çíà÷åíèÿ x
i� .
Äàëåå äëÿ òåêóùåé áàçû x è êàæäîé
âåðøèíû � i â óñòàíîâëåííîì ïî-
ðÿäêå âûïîëíÿåòñÿ ýëåìåíòàðíîå
ïðåîáðàçîâàíèå [5] íå áîëåå k ðàç.
Ïîýòîìó ïðè ïåðåìåùåíèè íåêîòî-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5 73
Ðèñ. 3. Ìàêñèìàëüíûé ðàçðåç â ãðàôå G V E� ( , )
Ðèñ. 2. Ïîäãðàô H V V V� � � �( , , ( ))�
ðûõ âåðøèí w èç V x� ( ) ê V x� ( ) è � èç V x� ( ) ê V x� ( ) êîìïîíåíòû áàçû x ñ èíäåê-
ñàìè � òåêóùåé áàçû ìîíîòîííî âîçðàñòóò, à êîìïîíåíòû ñ èíäåêñàìè w ìîíî-
òîííî óìåíüøàòñÿ. Òàêèì îáðàçîì, ïîñëå âûïîëíåíèÿ íå áîëåå n2 4/ ýëåìåíòàð-
íûõ ïðåîáðàçîâàíèé îïðåäåëèòñÿ áàçà x1 è ïîäìíîæåñòâà V x� ( )1 è V x� ( )1 . Åñëè
f x f x� ��( ) ( )1 , òî ýòîò ïðîöåññ ñíîâà ïîâòîðÿåòñÿ îòíîñèòåëüíî áàçû x x� 1.
Âî ââåäåíèè [1] óïîìÿíóòûå àëãîðèòìû îïðåäåëÿþò ðåøåíèå çàäà÷è ìàêñè-
ìàëüíîãî ðàçðåçà ñ ðàçëè÷íûìè ïîãðåøíîñòÿìè ïðèáëèæåíèÿ ê ãëîáàëüíîìó
ìàêñèìóìó, êîòîðûå îáû÷íî îáóñëîâëåíû èñïîëüçîâàíèåì íåêîòîðîãî àïðèîð-
íîãî çíà÷åíèÿ äëÿ ïëîòíîñòè ãðàôà G V E� ( , ) â êà÷åñòâå êðèòåðèÿ îñòàíîâêè.
 àëãîðèòìå èñêëþ÷åíèÿ è âêëþ÷åíèÿ ïîãðåøíîñòü ïðèáëèæåíèÿ äëÿ ðåøåíèÿ
çàäà÷è (1), (2) ìîæíî îöåíèòü ñ èñïîëüçîâàíèåì ÷àñòî ïðèìåíÿåìûõ íà ïðàêòèêå
ñâîéñòâ âûïóêëûõ ìíîæåñòâ â êîíå÷íîìåðíîì ïðîñòðàíñòâå â òåðìèíàõ åâêëè-
äîâîé íîðìû. Äëÿ ýòîãî âíà÷àëå îïðåäåëèì âåðõíþþ ãðàíèöó ïî ôóíêöèîíà-
ëó (1) â ýòîé íîðìå. Äàëåå ñ ó÷åòîì òîãî, ÷òî öåëåâàÿ ôóíêöèÿ (1) ÿâëÿåòñÿ íîð-
ìîé â l1, îïðåäåëèì êîýôôèöèåíò ïðè íîðìå | .| òàê, ÷òî èçâåñòíîå îòíîøåíèå ýê-
âèâàëåíòíîñòè ìåæäó ýòîé è åâêëèäîâîé íîðìàìè â ôóíêöèîíàëüíîì àíàëèçå
âûïîëíèòñÿ êàê ðàâåíñòâî. Òàêèì îáðàçîì, ìîæíî îöåíèòü ïîãðåøíîñòü
ïðèáëèæåíèÿ ê ãëîáàëüíîìó ìàêñèìóìó öåëåâîé ôóíêöèè.
Ðàññìîòðèì îãðàíè÷åííîå âûïóêëîå ìíîæåñòâî T â n-ìåðíîì åâêëèäîâîì
ïðîñòðàíñòâå. Âàæíûìè ãåîìåòðè÷åñêèìè õàðàêòåðèñòèêàìè ìíîæåñòâà T ÿâëÿ-
þòñÿ åãî äèàìåòð è ðàäèóñ îïèñàííîãî øàðà. Åñëè åâêëèäîâî ðàññòîÿíèå
| | | | , /x z x z x z� �� � � �1 2 ìåæäó òî÷êàìè x è z, âåëè÷èíû a x zT
x z T
� �
�
sup | | | |
,
è
r x xT
x x T
� �
�
min sup| | | |
0
0
íàçûâàþòñÿ ñîîòâåòñòâåííî äèàìåòðîì ìíîæåñòâà T è ðàäè-
óñîì îïèñàííîãî øàðà ñ öåíòðîì â íåêîòîðîé òî÷êå x0 ïðîñòðàíñòâà. Î÷åâèäíî,
÷òî rT åñòü ðàäèóñ íàèìåíüøåãî øàðà, ñîäåðæàùåãî ìíîæåñòâî T . Ñóùåñòâîâà-
íèå òàêîãî øàðà ñëåäóåò èç íåïðåðûâíîñòè åâêëèäîâà ðàññòîÿíèÿ. (Äîêàçàòåëüñòâî
ýòîãî óòâåðæäåíèÿ ìîæíî íàéòè âî ìíîãèõ ó÷åáíèêàõ ïî òåîðèè âûïóêëîãî
àíàëèçà.) Ñëåäóþùèé ðåçóëüòàò ÿâëÿåòñÿ îñíîâíîé ÷àñòüþ èçâåñòíîé òåîðå-
ìû Þíãà.
Òåîðåìà 2. Äëÿ ëþáîãî îãðàíè÷åííîãî ìíîæåñòâà T â n-ìåðíîì åâêëèäîâîì
ïðîñòðàíñòâå ðàäèóñ îïèñàííîãî øàðà rT è äèàìåòð aT ìíîæåñòâà T óäîâëåòâî-
ðÿþò íåðàâåíñòâó
r
n
n
aT T�
�2 1( )
. (7)
Ìîæíî ïîêàçàòü, ÷òî åñëè êîìïàêòíîå âûïóêëîå ìíîæåñòâî T öåíòðàëü-
íî-ñèììåòðè÷íî, òî aT — ìàêñèìàëüíîå ðàññòîÿíèå ìåæäó ïàðàëëåëüíûìè
îïîðíûìè ãèïåðïëîñêîñòÿìè ìíîæåñòâà T . Îòìåòèì, ÷òî ìíîæåñòâî T íàçûâàåò-
ñÿ öåíòðàëüíî-ñèììåòðè÷íûì, åñëè T ñîäåðæèò íà÷àëî êîîðäèíàò n-ìåðíîãî åâ-
êëèäîâà ïðîñòðàíñòâà è èç x T� ñëåäóåò, ÷òî � �x T .
Èçâåñòíî, ÷òî ìíîãîãðàííèêè z EP� �( )� � è B ( )� ìîæíî ïðåäñòàâèòü êàê
âûïóêëóþ îáîëî÷êó êîíå÷íîãî ÷èñëà êðàéíèõ òî÷åê (áàç). Ýòî îçíà÷àåò èõ îãðà-
íè÷åííîñòü, åñëè äàæå ìíîæåñòâî, âûïóêëàÿ îáîëî÷êà êîòîðîãî ïðåäñòàâëÿåò
ýòè ìíîãîãðàííèêè, íå âñåãäà áóäåò ìèíèìàëüíûì ïî êîëè÷åñòâó âêëþ÷åíèé
ñ ýòèì ñâîéñòâîì. Èç òåîðèè âûïóêëîãî àíàëèçà èçâåñòíî, ÷òî ñðåäè ýòèõ òî÷åê
ñóùåñòâóþò òàêèå, â êîòîðûõ öåëåâàÿ ôóíêöèÿ (1), (2) äîñòèãàåò ñâîåãî ìàêñèìó-
ìà. Ñîãëàñíî óòâåðæäåíèÿì 1–3 (ñì. [1]) ëþáóþ òî÷êó z EP� �( )� � (áàçó z)
ìîæíî ïðåäñòàâèòü â âèäå z x y� � , ãäå x B� ( )� è y d x� � . Òàêæå èç
74 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5
y d x B� � � ( )� è x d y� � ñëåäóåò, ÷òî åñëè z EP� �( )� � , òî � � �z EP ( )� � .
Ïîýòîìó íà÷àëî êîîðäèíàò åâêëèäîâà n-ìåðíîãî ïðîñòðàíñòâà ëåæèò íà ñåðåäèíå
îòðåçêà, ñîåäèíÿþùåãî ïðîèçâîëüíûå òî÷êè z è �z èç EP ( )� �� . Çíà÷èò, íà÷àëî
êîîðäèíàò ÿâëÿåòñÿ öåíòðîì îïèñàííîãî øàðà äëÿ EP ( )� �� . Ñëåäîâàòåëüíî,
| | | |*z ÿâëÿåòñÿ ðàäèóñîì îïèñàííîãî øàðà äëÿ EP ( )� �� ïðè z x d* *� �2 , ãäå x *
— îïòèìàëüíîå ðåøåíèå çàäà÷è (1), (2). Äëÿ îïðåäåëåíèÿ âåðõíåãî çíà÷åíèÿ äèà-
ìåòðà EP ( )� �� îòìåòèì, ÷òî 0 � �z d� � èëè � � �d z� � 0 äëÿ âñåõ
z EP� �( )� � , òàê êàê ïðîèçâîëüíàÿ áàçà èç EP ( )� �� ïðåäñòàâèìà â âèäå
z x y� � , ãäå y d x� � .
Ðàññìîòðèì âåêòîð h h V� �( : )� � ñ êîìïîíåíòàìè h d� �� èëè h d� �� � äëÿ
âñåõ � �V . Èç öåíòðàëüíî-ñèììåòðè÷íîñòè ìíîãîãðàííèêà EP ( )� �� âûòåêàåò,
÷òî ñóùåñòâóþò ïàðàëëåëüíûå ãèïåðïëîñêîñòè ñ íîðìàëüíûìè âåêòîðàìè h è �h
òàêèå, ÷òî EP ( )� �� ëåæèò ìåæäó ýòèìè ãèïåðïëîñêîñòÿìè. Ñëåäîâàòåëüíî,
sup{ }| | | |; , ( ) | | ( )| | | | ( )| | | |z t z t EP h h d d� � � � � � � � � �� � 2 d| | ,
ò.å. âåëè÷èíà 2| | | |d ÿâëÿåòñÿ âåðõíåé ãðàíèöåé äëÿ äèàìåòðà ìíîãîãðàííèêà
EP ( )� �� . Ïîñêîëüêó z V( ) � 0 äëÿ âñåõ z èç EP ( )� �� , âûïóêëàÿ îáîëî÷êà
ýòèõ òî÷åê èç EP ( )� �� ëåæèò â (n �1)-ìåðíîì ïîäïðîñòðàíñòâå åâêëèäîâà
ïðîñòðàíñòâà. Ïîýòîìó èç (7) ñëåäóåò, ÷òî îïòèìàëüíîå ðåøåíèå x * (z *) çàäà-
÷è (1), (2) óäîâëåòâîðÿåò íåðàâåíñòâó
| | | | | | | |
( )
| | | |* *2
2 1
x d z
n
n
d� � �
�
. (8)
Èñïîëüçóÿ ýòî íåðàâåíñòâî, ìîæíî îïðåäåëèòü ïîãðåøíîñòü ïðèáëèæåíèÿ
ê ìàêñèìàëüíîìó çíà÷åíèþ öåëåâîé ôóíêöèè (1) ñëåäóþùèì îáðàçîì. Èç òåîðèè
ôóíêöèîíàëüíîãî àíàëèçà èçâåñòíî, ÷òî íîðìû || . | | è | . | ýêâèâàëåíòíû â êîíå÷-
íîìåðíîì ëèíåéíîì ïðîñòðàíñòâå. Ïîýòîìó äëÿ êàæäîãî z EP� �( )� �
ñóùåñòâóåò êîíå÷íîå ÷èñëî òàêîå, ÷òî
| | | | | |z z� . (9)
Òàêèì îáðàçîì, îïðåäåëèâ äëÿ êàæäîãî âåêòîðà z x d� �2 , ñãåíåðèðîâàííî-
ãî àëãîðèòìîì èñêëþ÷åíèÿ è âêëþ÷åíèÿ, ìîæíî îöåíèòü ïîãðåøíîñòè ïðèáëè-
æåíèÿ ê ìàêñèìàëüíîìó çíà÷åíèþ öåëåâîé ôóíêöèè ñîãëàñíî íåðàâåíñòâó (8).
 ñëó÷àå, êîãäà íåðàâåíñòâî (8) õàðàêòåðèçóåò íåñêîëüêî âåêòîðîâ êàê íàèëó÷-
øåå ïðèáëèæåíèå ê îïòèìàëüíîìó ðåøåíèþ çàäà÷è (1), (2), ñðåäè íèõ ñëåäóåò
âûáðàòü âåêòîð, äëÿ êîòîðîãî çíà÷åíèå ìèíèìàëüíîå â (9). Íàïðèìåð, ðàññìîò-
ðèì â (5) è (6) óêàçàííûå áàçû x è x * , äëÿ êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî
| | | | | | | |*2 2x d x d� � � , ò.å. | | | | | | | |*z z� . Ñ ó÷åòîì ýòîãî ðàâåíñòâà íåðàâåíñòâî (8)
áóäåò õàðàêòåðèçîâàòü áàçû x è x * êàê íàèëó÷øåå ïðèáëèæåíèå ê îïòèìàëüíîìó
ðåøåíèþ çàäà÷è (1), (2). Îäíàêî ïî íîðìå | .| ðåøåíèåì ýòîé çàäà÷è íà óêàçàííîì
íà ðèñ. 1 ãðàôå ÿâëÿåòñÿ òîëüêî áàçà x * ñ íàèëó÷øåé ïîãðåøíîñòüþ
ïðèáëèæåíèÿ, òàê êàê | | | |*z z� � �22 20 .
Îòìåòèì, ÷òî âåðõíÿÿ îöåíêà äëÿ | | | |*z íå ìîæåò áûòü óëó÷øåíà â (8).
Íàïðèìåð, ðàâåíñòâà â (8) èìåþò ìåñòî äëÿ z x d* *� �2 , ãäå x * — ðåøåíèå çàäà-
÷è (1), (2) íà ïðîñòîì ãðàôå ñ äâóìÿ âåðøèíàìè è îäíèì ðåáðîì.
Èòàê, ïîñêîëüêó ñîãëàñíî òåîðåìå 1 (ñì. [1]) êàæäîìó ðàçðåçó ìîæíî ñîïî-
ñòàâèòü áàçó èç B ( )� , âîçíèêàåò âîïðîñ, äîïóñòèìà ëè â çàäà÷å (1), (2) çàìåíà
ìàêñèìèçàöèè f x( ) ìèíèìèçàöèåé ôóíêöèè f x( ) äëÿ îïðåäåëåíèÿ ìèíèìàëüíîãî
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5 75
ðàçðåçà �( )
*
S ðåøåíèåì ïîëó÷åííîé çàäà÷è. Åñëè èãíîðèðîâàòü òðåáîâàíèÿ
î òîì, ÷òî â çàäà÷å ìèíèìàëüíîãî ðàçðåçà �( )
*
S ïîäìíîæåñòâî S
*
íå ìîæåò áûòü
ïóñòûì ìíîæåñòâîì è äîëæíî îòëè÷àòüñÿ îò ìíîæåñòâà âåðøèí ãðàôà, òî áàçà
x d� / 2 , ñîîòâåòñòâóþùàÿ ðàçðåçàì �( )� èëè �( )V , ÿâëÿåòñÿ ðåøåíèåì ïîëó÷åí-
íîé çàäà÷è ìèíèìèçàöèè, òàê êàê f d� �( / )2 0. Ïîýòîìó îïðåäåëåíèå �( )
*
S (ïðè
S V x
*
( )� � ) ñâîäèòñÿ ê íàõîæäåíèþ áàçû x ñ ìèíèìàëüíûì ïîëîæèòåëüíûì çíà-
÷åíèåì ôóíêöèè f x� ( ), ÷òî ýêâèâàëåíòíî çàäà÷å ìèíèìèçàöèè ñèììåòðè÷íîé
ôóíêöèè � �( ) ( )S S� (ñì. [7]), ðåøåíèåì êîòîðîé îïðåäåëÿåòñÿ íåñîáñòâåííîå
ïîäìíîæåñòâî � � �S V
*
.
2. ÑÅÒÅÂÀß ÌÎÄÅËÜ ÇÀÄÀ×È ÌÀÊÑÈÌÀËÜÍÎÃÎ ÐÀÇÐÅÇÀ
Ñîãëàñíî ëåììàì 1 è 2 (ñì. [1]) îäèí è òîò æå ðàçðåç ìîæíî îïðåäåëèòü ïî-
èñêîì íåêîòîðûõ ðàçëè÷íûõ áàç èç B ( )� , îäíàêî ñîãëàñíî òåîðåìå 1 (ñì. [1])
êîëè÷åñòâî áàç, ñîîòâåòñòâóþùèõ ðàçëè÷íûì ðàçðåçàì â ãðàôå G V E� ( , ),
ìîæíî ïðåäñòàâèòü âåëè÷èíîé ( )!n �1 . Ïîýòîìó âûáîð ïîäõîäÿùåãî ñïîñîáà
ëèíåéíîãî óïîðÿäî÷åíèÿ âåðøèí çàäàííîãî ãðàôà ÿâëÿåòñÿ ñëîæíîé çàäà÷åé.
Èñïîëüçîâàíèå äëÿ ýòèõ öåëåé ðåøåíèé, áëèçêèõ ê ðåøåíèþ çàäà÷è (1), (2),
à èìåííî îïðåäåëåíèå ìàêñèìàëüíîãî íåçàâèñèìîãî ìíîæåñòâà âåðøèí, íà-
õîæäåíèå ìèíèìàëüíîãî êîëè÷åñòâà êðàñîê äëÿ ðàñêðàñêè âåðøèí è ò.ä., íå-
ýôôåêòèâíî, òàê êàê â ýòîì ñëó÷àå îïðåäåëåíèå òðåáóåìîãî ëèíåéíîãî óïîðÿ-
äî÷åíèÿ âåðøèí è íàõîæäåíèå ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà ýêâèâà-
ëåíòíû ïî òðóäîåìêîñòè.
Äëÿ ðÿäà àëãîðèòìîâ (ñì. [8]) ïðåäëàãàëîñü èñïîëüçîâàòü ïðèáëèæåííîå ðå-
øåíèå ïîäçàäà÷, âñòðå÷àþùèõñÿ ïðè ðåøåíèè çàäà÷è ìàêñèìàëüíîãî ðàçðåçà,
äëÿ óìåíüøåíèÿ âðåìåíè íàõîæäåíèÿ åå ðåøåíèÿ. Âî ìíîãèõ ñëó÷àÿõ ïðèáëè-
æåííûå ðåøåíèÿ îïðåäåëÿëèñü ñ ïîìîùüþ ðåøåíèÿ çàäà÷è, ïîëó÷åííîé ïîñëå
ëèíåéíîé ðåëàêñàöèè èñõîäíîé. Îäíàêî èç [6] ñëåäóåò, ÷òî äàæå íåêîòîðûå ïî-
ëèíîìèàëüíî ðàçðåøèìûå çàäà÷è îïòèìèçàöèè íåâîçìîæíî ñôîðìóëèðîâàòü êàê
çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ ïðèåìëåìûì (ïîëèíîìèàëüíûì) êîëè÷åñ-
òâîì îãðàíè÷åíèé, çàäàþùèõ ìíîãîãðàííèê ñ öåëî÷èñëåííûìè âåðøèíàìè (êîì-
ïàêòíàÿ çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ). Õîòÿ ïðåäñòàâëåíèå çàäà÷è ìàê-
ñèìàëüíîãî ðàçðåçà â ãðàôå G V E� ( , ) êàê êîìïàêòíîé çàäà÷è ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ â íàñòîÿùåé ñòàòüå íå ðàññìàòðèâàåòñÿ, ìîæíî óòâåðæäàòü,
÷òî èç P NP� ñëåäóåò, ÷òî àíàëîãè÷íî íåâîçìîæíî ñôîðìóëèðîâàòü çàäà÷ó (1),
(2), êîòîðàÿ ÿâëÿåòñÿ çàäà÷åé ìàêñèìèçàöèè íåãëàäêîé ôóíêöèè íà ñïåöèàëüíîì
ìíîãîãðàííèêå. Íåñìîòðÿ íà òî, ÷òî ìåòîäû íàõîæäåíèÿ ýêñòðåìóìîâ íåãëàäêîé
ôóíêöèè èíòåíñèâíî èçó÷àëèñü ìíîãèìè ñïåöèàëèñòàìè, ïðåäëîæåííûå ìåòîäû
íåïðèãîäíû èëè ìàëîýôôåêòèâíû äëÿ ðåøåíèÿ çàäà÷è (1), (2).
Èçâåñòíî, ÷òî ïðè èññëåäîâàíèè îïåðàöèé, ñâÿçàííûõ ñ êîìáèíàòîðíûìè çà-
äà÷àìè, ïîëåçåí òåîðåòèêî-ãðàôîâûé ïîäõîä ê ñåòåâûì ïðåäñòàâëåíèÿì ýòèõ çà-
äà÷. Â ðàìêàõ ïîäîáíûõ èññëåäîâàíèé ðàçðàáîòàíû àëãîðèòìû, ïîçâîëÿþùèå ðå-
øèòü ïðàêòè÷åñêèå çàäà÷è ñ áîëüøèìè äàííûìè. Ðàññìîòðèì ñåòåâîå ïðåäñòàâ-
ëåíèå çàäà÷è ìàêñèìàëüíîãî ðàçðåçà.
Ïóñòü áàçà x ïîðîæäåíà ïî íåêîòîðîìó ëèíåéíîìó óïîðÿäî÷åíèþ L è
y d x� � . Ïîñêîëüêó z x d x y EP� � � � � �2 ( )� � è z V( ) � 0, ìîæíî îïðåäåëèòü
ïîäìíîæåñòâà âåðøèí V z V� � � �{ }� ��: ,0 è V z V� � � �{ }� ��: ,0 . Ïóñòü äóãè
àöèêëè÷åñêè îðèåíòèðîâàííîãî ãðàôà G V E� ( , ), ïîëó÷åííîãî ïîñëå çàìåíû âñåõ
ðåáåð äóãàìè ñîãëàñíî ëèíåéíîìó óïîðÿäî÷åíèþ L, èìåþò åäèíè÷íûå ïðî-
ïóñêíûå ñïîñîáíîñòè. Äàëåå ê ãðàôó G V E� ( , ) äîáàâëÿþòñÿ äóãè s� è rw
ñ ïðîïóñêíûìè ñïîñîáíîñòÿìè z� è | |zw äëÿ êàæäîé âåðøèíû � � �V è w V� �
ñîîòâåòñòâåííî.  ïîëó÷åííîé ñåòè G V Ez z z� ( , ) ìíîæåñòâà âûõîäÿùèõ èç âåð-
76 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5
øèí è âõîäÿùèõ â âåðøèíû äóã ïîäìíîæåñòâà S V� 0 îáîçíà÷àþòñÿ �� ( )S è
�� ( )S . Îòìåòèì, ÷òî ïðîïóñêíàÿ ñïîñîáíîñòü ðàçðåçà, îòäåëÿþùåãî ïîäìíîæåñòâî
âåðøèí S îò îñòàëüíûõ âåðøèí, îïðåäåëÿåòñÿ êàê ñóììà ïîòîêîâ íà äóãàõ, âûõî-
äÿùèõ èç âåðøèíû � �S , ìèíóñ ñóììà ïîòîêîâ íà äóãàõ, âõîäÿùèõ â âåðøèíó
� �S . Ðàçðåç ñ ìèíèìàëüíîé ïðîïóñêíîé ñïîñîáíîñòüþ íàçûâàåòñÿ ìèíèìàëüíûì
ðàçðåçîì.
Òåîðåìà 3.  ñåòè G V Ez z z� ( , ) çíà÷åíèåì ìàêñèìàëüíîãî ïîòîêà îò èñ-
òî÷íèêà s ê ñòîêó r ÿâëÿþòñÿ åäèíè÷íûå ïîòîêè íà âñåõ äóãàõ àöèêëè÷åñêîãî
îðèåíòèðîâàííîãî ãðàôà G V E� ( , ) è ïîòîêè ñî çíà÷åíèÿìè z� è | |zw íà äóãàõ s�
è rw ñîîòâåòñòâåííî.
Äîêàçàòåëüñòâî. Ñîãëàñíî ïîñòðîåíèþ ñåòè G z ðàâåíñòâî x y z� � �� � âû-
ïîëíÿåòñÿ äëÿ êàæäîé âåðøèíû � �V . Ýòî îçíà÷àåò, ÷òî ñóììû ïðîïóñêíûõ ñïî-
ñîáíîñòåé äóã èç ìíîæåñòâ � �� ( ) è � �� ( ) îäèíàêîâûå äëÿ êàæäîé âåðøèíû
� �V . Ïîýòîìó äëÿ ñîõðàíåíèÿ áàëàíñà ìåæäó âõîäÿùèìè è âûõîäÿùèìè ïîòî-
êàìè äëÿ êàæäîé âåðøèíû � �V çíà÷åíèå ìàêñèìàëüíîãî ïîòîêà íà äóãàõ àöèê-
ëè÷åñêè îðèåíòèðîâàííîãî ãðàôà G V E� ( , ) äîëæíî ðàâíÿòüñÿ åäèíèöå. Êðîìå
òîãî, èç z s x V y V y V x V z r( ( )) ( ) ( ) ( ) ( ) | ( ( ))|� �� � � � � �� � � � � ñëåäóåò, ÷òî z� è | |zw
ÿâëÿþòñÿ âåëè÷èíàìè ìàêñèìàëüíîãî ïîòîêà íà äóãàõ s� è rw ñîîòâåòñòâåííî. �
Ñîãëàñíî ýòîé òåîðåìå âåëè÷èíà ïîòîêà íà âñåõ äóãàõ ðàâíà ïðîïóñêíîé
ñïîñîáíîñòè äóã, çíà÷èò, ïðîèçâîëüíûé ðàçðåç, îòäåëÿþùèé èñòî÷íèê s è ñòîê r,
ÿâëÿåòñÿ ìèíèìàëüíûì ðàçðåçîì â ñåòè G V Ez z z� ( , ). Òàêèì îáðàçîì, ïîëó÷àåì,
÷òî f x� ( ) åñòü çíà÷åíèå ìàêñèìàëüíîãî ïîòîêà èç èñòî÷íèêà s â ñòîê r â ïîñòðî-
åííîé ñåòè G V Ez z z� ( , ) îòíîñèòåëüíî áàçû z x d EP� � � �2 ( )� � .
 êà÷åñòâå ïðèìåðà ðàññìîòðèì çàäà÷ó ìàêñèìàëüíîãî ðàçðåçà íà ãðàôå, ïî-
êàçàííîì íà ðèñ. 4.
Ïóñòü L � ( , , , , , )6 1 2 3 4 5 — ëèíåéíîå óïîðÿäî÷åíèå âåðøèí ýòîãî ãðàôà. Ðàñ-
ñìîòðèì áàçó x x x x x x x B� � � � � � � �( , , , , , ) ( )6 1 2 3 4 55 2 0 0 0 0 � , ïîðîæäåí-
íóþ ïî L. Òîãäà V� � { }1 6, ,V� � { }2 3 4 5, , , è ðàçðåç, îòäåëÿþùèé ýòè ïîäìíîæåñ-
òâà, ñîäåðæèò ðåáðà, êîòîðûå ïåðåñåêàþòñÿ ñî øòðèõîâîé ëèíèåé íà ðèñ. 4.
Ïðîñòîé ïðîâåðêîé ìîæíî óáåäèòüñÿ, ÷òî ýòîò ðàçðåç ÿâëÿåòñÿ ìàêñèìàëüíûì
ñ ìîùíîñòüþ, ðàâíîé øåñòè. Íà ðèñ. 5 ïîêàçàíà ñåòü G V Ez z z� ( , ), ïîñòðîåííàÿ
îòíîñèòåëüíî áàçû
x y z z z z z z z EP� � � � � � � � � � � � � � �( , , , , , ) ( )6 1 2 3 4 55 1 2 1 1 2 � � ,
ãäå y d x� � . Ëåãêî ïðîâåðèòü, ÷òî â ñåòè G z ïðîïóñêíàÿ ñïîñîáíîñòü ïðîèç-
âîëüíîãî ìèíèìàëüíîãî ðàçðåçà, îòäåëÿþùåãî èñòî÷íèê è ñòîê, ðàâíà ìîùíîñ-
òè ìàêñèìàëüíîãî ðàçðåçà â ïîêàçàííîì íà ðèñ. 4 ãðàôå.
Îïðåäåëåíèå 1. Â ñåòè G V Ez z z� ( , ), ïîñòðîåííîé äëÿ áàçû z x d� � �2
� �EP ( )� � , ïîòîêè íà äóãàõ �w íàçûâàþòñÿ òðàíçèòíûìè, åñëè âåðøèíû
�, ( )w V x� � èëè �, ( )w V x� � .
Òåîðåìà 4. Áàçà x B� ( )� ÿâëÿåòñÿ ðåøå-
íèåì çàäà÷è (1), (2) òîãäà è òîëüêî òîãäà, êîã-
äà ñóììàðíîå êîëè÷åñòâî òðàíçèòíûõ ïîòîêîâ
ÿâëÿåòñÿ ìèíèìàëüíûì â ïîñòðîåííîé ñåòè
G V Ez z z� ( , ) äëÿ z x d� �2 .
Äîêàçàòåëüñòâî. Ïóñòü áàçà x ïîðîæäåíà
ïî ëèíåéíîìó óïîðÿäî÷åíèþ L è ñåòü G z , ïî-
ñòðîåííàÿ äëÿ z x d� �2 , ñîäåðæèò ìèíèìàëü-
íîå êîëè÷åñòâî òðàíçèòíûõ ïîòîêîâ íà äóãàõ
�w. Èç îïðåäåëåíèÿ ðàçðåçà â ãðàôå G îòíîñè-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5 77
Ðèñ. 4. Ìàêñèìàëüíûé ðàçðåç äëÿ áàçû x
òåëüíî áàç x è y d x� � ñëåäóåò, ÷òî åñëè
�, ( )w V x� � , òî y V x( ( ))� , à åñëè
�, ( )w V x� � , òî x V x( ( ))� ÿâëÿþòñÿ ñóì-
ìàðíûì êîëè÷åñòâîì òðàíçèòíûõ ïîòî-
êîâ íà äóãàõ �w. Ïîýòîìó èç äâîéñòâåí-
íîãî ðàâåíñòâà (6) èç [1] ïîëó÷àåì, ÷òî
�( ( ))V x� ÿâëÿåòñÿ ìàêñèìàëüíûì
ðàçðåçîì â ãðàôå G.
Åñëè ó÷åñòü, ÷òî y V x x V x( ( )) ( ( ))� �� —
ñóììà òðàíçèòíûõ ïîòîêîâ â ñåòè G z , ïî-
ñòðîåííîé äëÿ ïðîèçâîëüíûõ áàç
z x d� �2 è x B� ( )� , òî îáðàòíîå óòâåðæäåíèå òàêæå ñëåäóåò èç äâîéñòâåííîãî
ðàâåíñòâà (6) èç [1]. �
Èíûìè ñëîâàìè, ýòà òåîðåìà óòâåðæäàåò, ÷òî åñëè â ðåøåíèè çàäà÷è (1), (2)
ìèíèìàëüíîå êîëè÷åñòâî ïåðåìåííûõ óäîâëåòâîðÿåò íåðàâåíñòâàì 0� �x d� � , òî
îïðåäåëåííûé îòíîñèòåëüíî x� ðàçðåç â ãðàôå G ìàêñèìàëüíûé. Íàïðèìåð, áàçà
x x x x x x x x x� � � � � � � � �( , , , , , , , )1 4 5 8 2 3 6 73 3 5 2 1 0 1 0 ÿâëÿåòñÿ îïòèìàëü-
íûì ðåøåíèåì çàäà÷è (1), (2) íà ãðàôå, ïðèâåäåííîì íà ðèñ. 1, à MaxCut
*
/ 2 �
� �f x( ) / 2 11. Íåòðóäíî óáåäèòüñÿ, ÷òî â ñåòè G z , ïîñòðîåííîé äëÿ áàçû z x d� �2 ,
ñóììàðíîå êîëè÷åñòâî òðàíçèòíûõ ïîòîêîâ íà äóãàõ �w ñ âåðøèíàìè èç �, ( )w V x� �
è �, ( )w V x� � ðàâíî y V x( ( ))� � 2 è x V x( ( ))� � 2 ñîîòâåòñòâåííî, ãäå
y y y y y y y y y� � � � � � � � �( , , , , , , , )1 4 5 8 2 3 6 70 2 0 0 3 4 3 3 .
Ëåãêî ïðîâåðèòü, ÷òî â ñåòè G z ïðîïóñêíûå ñïîñîáíîñòè âñåõ ìèíèìàëüíûõ
ðàçðåçîâ, îòäåëÿþùèõ èñòî÷íèêè è ñòîêè, òîæå ðàâíû 11.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿøåé ñòàòüå èçëîæåíû ðàíåå íåèçâåñòíûå ñâîéñòâà ìàêñèìàëüíîãî ðàç-
ðåçà â íåîðèåíòèðîâàííûõ ãðàôàõ â òåðìèíàõ òåîðèè âûïóêëîãî àíàëèçà, ïî-
òîêîâ è ïîëèìàòðîèäîâ, êîòðûå ïîêàçûâàþò, ÷òî ìîäåëü (1), (2) âûãîäíî îòëè-
÷àåòñÿ îò ïðåäñòàâëåííûõ â ïîñëåäíåå âðåìÿ ìîäåëåé. Äîêàçàííûå ñâîéñòâà
â òåðìèíàõ ðàçëè÷íûõ òåîðèé òàêæå ñïîñîáñòâóþò ïðèìåíåíèþ èçâåñòíûõ àë-
ãîðèòìîâ äëÿ ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà. Òåì íå ìåíåå, ïî ìíå-
íèþ àâòîðîâ, ïðèìåíåíèå àëãîðèòìîâ [4] è àëãîðèòìà èñêëþ÷åíèÿ è âêëþ÷å-
íèÿ ÿâëÿåòñÿ áîëåå ýôôåêòèâíûì äëÿ íàõîæäåíèÿ ìàêñèìàëüíîãî ðàçðåçà
â ïðàêòè÷åñêèõ çàäà÷àõ. Òàêæå çàñëóæèâàåò âíèìàíèÿ òî, ÷òî íà îñíîâå äîêà-
çàííûõ ñâîéñòâ ìîæíî ñîçäàòü ðàçëè÷íûå ñïîñîáû äëÿ îñóùåñòâëåíèÿ áîëåå
ýôôåêòèíîãî ïåðåìåùåíèÿ ïîäìíîæåñòà âåðøèí ìåæäó äîëÿìè òåêóùåãî äâó-
äîëüíîãî ïîäãðàôà â àëãîðèòìå èñêëþ÷åíèÿ è âêëþ÷åíèÿ.
Êðîìå ýòîãî, ñîãëàñíî òåîðåìå 3 çàäà÷à ìàêñèìèçàöèè êîëè÷åñòâà ïåðåäà-
âàåìîãî ïîòîêà â òðóáîïðîâîäíûõ ñåòÿõ íàçíà÷åíèåì âåðøèí â êà÷åñòâå èñòî÷-
íèêà èëè ñòîêà òàêæå ñâîäèòñÿ ê çàäà÷å ìàêñèìàëüíîãî ðàçðåçà. Íà ïðàêòèêå òà-
êàÿ çàäà÷à âîçíèêàåò â òðóáîïðîâîäíûõ ñåòÿõ ïðè íåîáõîäèìîñòè èñïîëüçîâàíèÿ
ïðîïóñêíîé ñïîñîáíîñòè ñåòè äëÿ ïåðåäà÷è ïîòîêîâ â ïðÿìîì èëè îáðàòíîì íà-
ïðàâëåíèÿõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Øàðèôîâ Ô.À., Ãóëÿíèöêèé Ë.Ô. Ðàçðåçû â íåîðèåíòèðîâàííûõ ãðàôàõ. I. Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. 2020. Ò. 56, ¹ 4. Ñ. 46–55.
2. Bazaraa M.S., Sherali H.D., Shetty M.C. Nonlinear programming: Theory and algorithms. New York: J.
Wiley and Sons, 1979. 583 p.
3. Satoru Iwata. Submodular function minimization. Math. Program. Ser. B. 2008. Vol. 112. P. 45–64.
78 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5
Ðèñ. 5. Ñåòü äëÿ áàçû z x y� �
4. Øàðèôîâ Ô.À. Íàõîæäåíèÿ ìàêñèìàëüíîãî ðàçðåçà ãðèäè àëãîðèòìîì. Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. 2018. Ò. 54, ¹ 5. Ñ. 61–67.
5. Fujishige S. Submodular function and optimization. Annals of Discrete Mathematics. 2005. Ð. 395.
6. Rothvoss T. The matching polytope has exponential extension complexity. ACM Symposium on the Theory
of Computing. 2014. P. 263–272.
7. Queyranne M. A combinatorial algorithm for minimizing symmetric submodular function. Math. Prog.
Ser. A. 1998. Vol. 82. Ð. 3–12.
8. Rendl F., Giovanni R., Wiegele A. Solving max-cut to optimality by intersecting semidefinite and
polyhedral relaxations. Mathematical Programming. 2010. Vol. 121, Iss. 2. P. 307.
Íàä³éøëà äî ðåäàêö³¿ 10.07.2019
Ô.À. Øàð³ôîâ, Ë.Ô. Ãóëÿíèöüêèé
ÐÎÇвÇÈ Â ÍÅÎвªÍÒÎÂÀÍÈÕ ÃÐÀÔÀÕ. I²
Àíîòàö³ÿ. Çàïðîïîíîâàíî äâà àëãîðèòìè ïåðåòâîðåííÿ ïîòî÷íî¿ áàçè
ïîë³ìàòðî¿äà äî íîâî¿ ç ìåòîþ ïîë³ïøåííÿ çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿. Âñòà-
íîâëåíî åêâ³âàëåíòí³ñòü çàäà÷³ ìàêñèìàëüíîãî ðîçð³çó íà çàäàíîìó ãðàô³
³ çàäà÷³ çíàõîäæåííÿ ì³í³ìàëüíîãî ðîçð³çó, ùî â³äîêðåìëþº äæåðåëî ³ ñò³ê
â ìåðåæ³, ïîáóäîâàíî¿ â³äíîñíî äåÿêî¿ áàçè ðîçøèðåíîãî ïîë³ìàòðî¿äà.
Ñôîðìóëüîâàíî íåîáõ³äí³ òà äîñòàòí³ óìîâè îïòèìàëüíîñò³ ðîçâ’ÿçóâàííÿ
çàäà÷³ ìàêñèìàëüíîãî ðîçð³çó íà íåîð³ºíòîâàíèõ ãðàôàõ â òåðì³íàõ òåîð³¿
ïîòîê³â.
Êëþ÷îâ³ ñëîâà: ãðàôè, ðîçð³çè, îïóêëà ôóíêö³ÿ, ñïåö³àëüí³ áàãàòîãðàííèêè,
ïîë³ìàòðî¿ä.
F. Sharifov, L. Hulianytskyi
CUTS IN UNDIRECTED GRAPHS. I²
Abstract. To improve the value of the objective function, two algorithms are
proposed for transforming the current base into a new one. It is shown that the
maximum cut problem on an undirected graph can be reduced to finding the
base of the extended polynomial, for which the value of the minimum cut that
separates the source and the sink is maximum. The necessary and sufficient
conditions for optimality of the solution of the maximum cut problem on
non-oriented graphs in terms of flow theory are formulated.
Keywords: graphs, cuts, convex function, special polyhedral, polymatroid.
Øàðèôîâ Ôèðäîâñè Àõóí-îãëû,
äîêòîð ôèç.-ìàò. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû, Êèåâ, e-mail: fasharifov@gmail.com.
Ãóëÿíèöêèé Ëåîíèä Ôåäîðîâè÷,
äîêòîð òåõí. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû,
Êèåâ, e-mail: lh_dar@hotmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 5 79
|