Разрезы в неориентированных графах. I
Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулиро...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2020 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/190421 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-190421 |
|---|---|
| record_format |
dspace |
| spelling |
Шарифов, Ф.А. Гуляницкий, Л.Ф. 2023-06-06T13:04:07Z 2023-06-06T13:04:07Z 2020 Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190421 519.8 Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции. Досліджено нові властивості розрізів у неорієнтованих графах, наведено різні моделі для задачі максимального розрізу на основі встановленої відповідності між розрізами в заданому графі і специфічними базами розширеного поліматроїда, асоційованого з цим графом. Для моделі, сформульовано ї як задача знаходження максимуму опуклої функції на компактній множині (розширеному поліматроїді), доведено, що локальні і глобальні максимуми збігаються за значенням цільової функції, тобто для розв'язання задачі максимального розрізу достатньо знайти базу розширеного поліматроїда як локальний або глобальний максимум цільової функції. This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as the maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maximum, i.e., to solve the maximum cut problem, it needs to find a base of the extended polymatroid as a local or global maximum of the objective function. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Разрезы в неориентированных графах. I Розрізи в неорієнтованих графах. І Cuts in undirected graphs. Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Разрезы в неориентированных графах. I |
| spellingShingle |
Разрезы в неориентированных графах. I Шарифов, Ф.А. Гуляницкий, Л.Ф. Системний аналіз |
| title_short |
Разрезы в неориентированных графах. I |
| title_full |
Разрезы в неориентированных графах. I |
| title_fullStr |
Разрезы в неориентированных графах. I |
| title_full_unstemmed |
Разрезы в неориентированных графах. I |
| title_sort |
разрезы в неориентированных графах. i |
| author |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| author_facet |
Шарифов, Ф.А. Гуляницкий, Л.Ф. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2020 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Розрізи в неорієнтованих графах. І Cuts in undirected graphs. |
| description |
Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими базами расширенного полиматроида, ассоциированного с этим графом. Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве - расширенном полиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции, т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида как локальный или глобальный максимум целевой функции.
Досліджено нові властивості розрізів у неорієнтованих графах, наведено різні моделі для задачі максимального розрізу на основі встановленої відповідності між розрізами в заданому графі і специфічними базами розширеного поліматроїда, асоційованого з цим графом. Для моделі, сформульовано ї як задача знаходження максимуму опуклої функції на компактній множині (розширеному поліматроїді), доведено, що локальні і глобальні максимуми збігаються за значенням цільової функції, тобто для розв'язання задачі максимального розрізу достатньо знайти базу розширеного поліматроїда як локальний або глобальний максимум цільової функції.
This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as the maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maximum, i.e., to solve the maximum cut problem, it needs to find a base of the extended polymatroid as a local or global maximum of the objective function.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/190421 |
| citation_txt |
Разрезы в неориентированных графах. I / Ф.А. Шарифов, Л.Ф. Гуляницкий // Кибернетика и системный анализ. — 2020. — Т. 56, № 4. — С. 46–55. — Бібліогр.: 20 назв. — рос. |
| work_keys_str_mv |
AT šarifovfa razrezyvneorientirovannyhgrafahi AT gulânickiilf razrezyvneorientirovannyhgrafahi AT šarifovfa rozrízivneoríêntovanihgrafahí AT gulânickiilf rozrízivneoríêntovanihgrafahí AT šarifovfa cutsinundirectedgraphs AT gulânickiilf cutsinundirectedgraphs |
| first_indexed |
2025-11-26T00:09:22Z |
| last_indexed |
2025-11-26T00:09:22Z |
| _version_ |
1850593549131710464 |
| fulltext |
ÓÄÊ 519.8
Ô.À. ØÀÐÈÔÎÂ, Ë.Ô. ÃÓËßÍÈÖÊÈÉ
ÐÀÇÐÅÇÛ Â ÍÅÎÐÈÅÍÒÈÐÎÂÀÍÍÛÕ ÃÐÀÔÀÕ. I
Àííîòàöèÿ. Èññëåäîâàíû íîâûå ñâîéñòâà ðàçðåçîâ â íåîðèåíòèðîâàííûõ
ãðàôàõ, ïðèâåäåíû ðàçëè÷íûå ìîäåëè äëÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà íà
îñíîâå óñòàíîâëåííîãî ñîîòâåòñòâèÿ ìåæäó ðàçðåçàìè â çàäàííîì ãðàôå è
ñïåöèôè÷åñêèìè áàçàìè ðàñøèðåííîãî ïîëèìàòðîèäà, àññîöèèðîâàííîãî
ñ ýòèì ãðàôîì. Äëÿ ìîäåëè, ñôîðìóëèðîâàííîé êàê çàäà÷à íàõîæäåíèÿ ìàê-
ñèìóìà âûïóêëîé ôóíêöèè íà êîìïàêòíîì ìíîæåñòâå — ðàñøèðåííîì ïî-
ëèìàòðîèäå, äîêàçàíî, ÷òî ëîêàëüíûå è ãëîáàëüíûå ìàêñèìóìû ñîâïàäàþò
ïî çíà÷åíèþ öåëåâîé ôóíêöèè, ò.å. äëÿ ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàç-
ðåçà äîñòàòî÷íî íàéòè áàçó ðàñøèðåííîãî ïîëèìàòðîèäà êàê ëîêàëüíûé èëè
ãëîáàëüíûé ìàêñèìóì öåëåâîé ôóíêöèè.
Êëþ÷åâûå ñëîâà: ãðàôû, ðàçðåçû, âûïóêëàÿ ôóíêöèÿ, ñïåöèàëüíûå ìíî-
ãîãðàííèêè.
ÂÂÅÄÅÍÈÅ
Ðàññìàòðèâàåìûå íîâûå ñâîéñòâà ðàçðåçîâ â íåîðèåíòèðîâàííûõ ãðàôàõ ìî-
ãóò áûòü ïîëîæåíû â îñíîâó íîâûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ íàõîæäåíèÿ
ðàçëè÷íûõ ðàçðåçîâ. Ìíîæåñòâî ðåáåð, óäàëåíèå êîòîðûõ ïðèâîäèò ê íåñâÿ-
çàííîìó ãðàôó, ÿâëÿåòñÿ ðàçðåçîì ñâÿçíîãî ãðàôà. Âî âçâåøåííîì íåîðèåí-
òèðîâàííîì ãðàôå, åñëè ñóììà âåñîâ óäàëåííûõ ðåáåð ìàêñèìàëüíà (ìèíè-
ìàëüíà), ðàçðåç íàçûâàåòñÿ ìàêñèìàëüíûì (ìèíèìàëüíûì). Î÷åâèäíî, ÷òî
óäàëåíèå âñåõ ðåáåð, íå ïðèíàäëåæàùèõ ðàçðåçó, ïðèâîäèò ê îñòîâíîìó äâó-
äîëüíîìó ïîäãðàôó. Ïðè ýòîì äîïóñêàåòñÿ, ÷òî äâóäîëüíûé ïîäãðàô ìîæåò
ñîäåðæàòü èçîëèðîâàííûå âåðøèíû. Ïîýòîìó çàäà÷ó íàõîæäåíèÿ ìàêñèìàëü-
íîãî (ìèíèìàëüíîãî) ðàçðåçà ìîæíî ñôîðìóëèðîâàòü êàê îïðåäåëåíèå îñòîâ-
íîãî äâóäîëüíîãî ïîäãðàôà ìàêñèìàëüíîãî (ìèíèìàëüíîãî) âåñà. Ðàçëè÷íûå
ïðèëîæåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà ïðè ïðîåêòèðîâàíèè ÑÁÈÑ, â ñòà-
òèñòè÷åñêîé ôèçèêå [1] è äðóãèõ îáëàñòÿõ ðàññìàòðèâàþòñÿ èìåííî â òàêîé
ïîñòàíîâêå. Ýòà çàäà÷à ÿâëÿåòñÿ NP-òðóäíîé äàæå â ñëó÷àå, êîãäà âåñà âñåõ
ðåáåð îäèíàêîâû [2–4].
Îáùèì ó èçâåñòíûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷è ìèíèìàëüíîãî ðàçðåçà ÿâ-
ëÿåòñÿ òî, ÷òî îíè ïðåäíàçíà÷åíû äëÿ ìàêñèìèçàöèè êîëè÷åñòâà ïîòîêîâ íà ðåá-
ðàõ, ò.å. äëÿ îïðåäåëåíèÿ îïòèìàëüíîãî ðåøåíèÿ ïðÿìîé è äâîéñòâåííîé çàäà÷.
Ïðè ýòîì âðåìåííûå çàòðàòû ìîæíî ïðåäñòàâèòü, â îñíîâíîì, êóáè÷åñêîé ôóíê-
öèåé îò ÷èñëà âåðøèí.  îòëè÷èå îò çàäà÷è ìèíèìàëüíîãî ðàçðåçà, äëÿ ðåøåíèÿ
çàäà÷è ìàêñèìàëüíîãî ðàçðåçà â íàñòîÿùåå âðåìÿ íå ñóùåñòâóåò ïîëèíîìèàëü-
íûõ àëãîðèòìîâ, õîòÿ è ïðåäëîæåíî ìíîãî ìåòîäîâ. Îäíàêî íè îäèí èç íèõ íå
èìååò òàêèõ ïðåèìóùåñòâ, ÷òîáû åãî ìîæíî áûëî ñ÷èòàòü áîëåå ýôôåêòèâíûì
ñðåäñòâîì ðåøåíèÿ ýòîé çàäà÷è.
Ìåòîäû öåëî÷èñëåííîãî èëè íåëèíåéíîãî ïðîãðàììèðîâàíèÿ, êàê ïðàâèëî,
ïðèìåíÿþòñÿ äëÿ ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà. Íàïðèìåð, â [5] îíà
ôîðìóëèðóåòñÿ êàê çàäà÷à ëèíåéíîãî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ ñ áóëå-
âûìè ïåðåìåííûìè, à â [6] — êàê çàäà÷à êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ
â òåðìèíàõ ïåðåìåííûõ, ïðèíèìàþùèõ îäíî èç äâóõ äèñêðåòíûõ çíà÷åíèé â çà-
âèñèìîñòè îò ïðèíàäëåæíîñòè âåðøèí ê äîëÿì äâóäîëüíîãî îñòîâíîãî ïîäãðàôà.
46 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4
� Ô.À. Øàðèôîâ, Ë.Ô. Ãóëÿíèöêèé, 2020
Îäíàêî â óïîìÿíóòûõ è äðóãèõ ïóáëèêàöèÿõ â ïðèìåíÿåìûõ àëãîðèòìàõ ñïåöè-
ôèêà çàäà÷ ÿâíî íå ó÷èòûâàåòñÿ.  îòëè÷èå îò ïðèâåäåííûõ ïîäõîäîâ, â ïîëèíî-
ìèàëüíûõ àëãîðèòìàõ äëÿ ðåøåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà íà ïëàíàðíûõ
[7–9] è ïî÷òè äâóäîëüíûõ ãðàôàõ [10, 11], à òàêæå íà ñåðèéíî-ïàðàëëåëüíûõ ãðà-
ôàõ [12] ñïåöèôèêè ýòèõ ãðàôîâ ó÷òåíû.
Ìåòîäû àïïðîêñèìàöèè äëÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà ñ ãàðàíòèåé ðå-
øåíèÿ çà ïîëèíîìèàëüíîå âðåìÿ äåòàëüíî èçëîæåíû â [13]. Ñâîéñòâà ýòîé çàäà-
÷è íà îñíîâå õàðàêòåðèñòèêè ñîáñòâåííûõ ÷èñåë ìàòðèöû ñìåæíîñòè èçó÷åíû
â [14]. Ôîðìóëèðîâêà â [15] çàäà÷è ìàêñèìàëüíîãî ðàçðåçà êàê çàäà÷è ïîëóîï-
ðåäåëåííîãî ïðîãðàììèðîâàíèÿ ïðåäñòàâëÿåò èíòåðåñ, ïîñêîëüêó íàéäåííîå
ðåøåíèå ïðåäëîæåííûì àëãîðèòìîì ãàðàíòèðóåò 0.887 òî÷íîñòè. Àíàëèç âðå-
ìåííîé ñëîæíîñòè ðåøåíèé ñòàíäàðòíûõ òåñòîâûõ çàäà÷ íà ñëó÷àéíî ãåíåðè-
ðîâàííûõ ãðàôàõ [16] ïîêàçàë, ÷òî òðóäîåìêîñòü àëãîðèòìà [15] ñèëüíî óâåëè-
÷èâàåòñÿ ïðè ðåøåíèè çàäà÷è íà áîëüøèõ ãðàôàõ (ñ ÷èñëîì âåðøèí áîëåå 500).
Òàêæå êîíñòàòèðóåòñÿ, ÷òî, èñïîëüçóÿ ïðèáëèæåííîå ðåøåíèå ïîäçàäà÷ íà êàæ-
äîé èòåðàöèè, ìîæíî ñóùåñòâåííî óëó÷øèòü áûñòðîäåéñòâèå àëãîðèòìà [16],
ïðè÷åì çíà÷åíèå öåëåâîé ôóíêöèè ïðè ðåøåíèè òåñòîâûõ çàäà÷ áóäåò òàêèì
æå, êàê è ïðè èõ ðåøåíèè àëãîðèòìîì [15]. Îäíàêî óòâåðæäàåòñÿ, ÷òî àëãîðèòì
[16] òåîðåòè÷åñêè ãàðàíòèðóåò òîëüêî 0.39 òî÷íîñòè ðåøåíèÿ çàäà÷è ìàêñè-
ìàëüíîãî ðàçðåçà.
Öåëü íàñòîÿùåé ðàáîòû — ïîêàçàòü íîâûå ñâîéñòâà çàäà÷è ìàêñèìàëüíîãî è
ìèíèìàëüíîãî ðàçðåçîâ, à òàêæå ðàññìîòðåòü îñîáåííîñòè ïîñòðîåíèÿ èññëåäî-
âàííîé â [17] ìîäåëè.
Äàëåå ïðè îïèñàíèè ñâîéñòâà ðàññìàòðèâàåìîé çàäà÷è âìåñòî òåðìèíîâ
«áàçà», «ïîëèìàòðîèä» è «ðàñøèðåííûé ïîëèìàòðîèä» ÷àñòî èñïîëüçóþòñÿ òåð-
ìèíû «êðàéíÿÿ òî÷êà» è «ìíîãîãðàííèê». Êðîìå ýòîãî, â çàâèñèìîñòè îò êîíòåê-
ñòà | |V è | |E çàìåíåíû n è m ñîîòâåòñòâåííî. Òàêæå äîêàçàíî, ÷òî ïðèâåäåííàÿ
â [17] ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è ìàêñèìàëüíîãî ðàçðåçà êàê íàõîæäåíèå
ìàêñèìóìà âûïóêëîé ôóíêöèè íà ìíîãîãðàííèêå íå èìååò ëîêàëüíûõ ýêñòðåìó-
ìîâ â òîì ñìûñëå, ÷òî ëîêàëüíûå è ãëîáàëüíûå ýêñòðåìóìû ñîâïàäàþò ïî çíà÷å-
íèþ öåëåâîé ôóíêöèè. Ïîýòîìó íåîáõîäèìîå óñëîâèå îïòèìàëüíîñòè ðåøåíèÿ
çàäà÷è ìàêñèìàëüíîãî ðàçðåçà â òåðìèíàõ ñóáãðàäèåíòîâ öåëåâîé ôóíêöèè ìîæ-
íî âûðàçèòü òàê æå, êàê è â âûïóêëîì ïðîãðàììèðîâàíèè. Êàê ñëåäñòâèå ýòîãî
ôàêòà ïîêàçàíî, ÷òî äëÿ îòûñêàíèÿ îïòèìàëüíîãî ðåøåíèÿ çàäà÷è ìîæíî ïðèìå-
íèòü èòåðàöèîííóþ ñõåìó, àíàëîãè÷íóþ èñïîëüçóåìûì â ñóáãðàäèåíòíûõ ìåòî-
äàõ. Òàêæå ïîêàçàíî, ÷òî äëÿ çàäàííîãî ãðàôà ìîæíî ïîñòðîèòü íåêîòîðóþ ñåòü,
â êîòîðîé ïðîïóñêíàÿ ñïîñîáíîñòü ïðîèçâîëüíîãî ìèíèìàëüíîãî ðàçðåçà, îòäå-
ëÿþùåãî èñòî÷íèê îò ñòîêà, ðàâíà ìîùíîñòè ìàêñèìàëüíîãî ðàçðåçà â ýòîì ãðà-
ôå. Ïîëó÷åíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ îïòèìàëüíîñòè ðåøåíèÿ çà-
äà÷è ìàêñèìàëüíîãî ðàçðåçà â íåîðèåíòèðîâàííîì ãðàôå â òåðìèíàõ òåîðèè ïî-
òîêîâ. Ðàññìîòðåíû ïðèìåðû çàäà÷è.
1. ÎÏÐÅÄÅËÅÍÈß È ÂÑÏÎÌÎÃÀÒÅËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Ïóñòü çàäàí ïðîñòîé íåîðèåíòèðîâàííûé ñâÿçíûé ãðàô G V E� ( , ) ñ ìíîæåñòâàìè
âåðøèí V è ðåáåð E, à òàêæå íåîòðèöàòåëüíûå âåñà ce ðåáåð e E� . Äëÿ ïðîèç-
âîëüíîãî S V� ðàññìîòðèì ïîäìíîæåñòâà �( )S è � ( )S , ñîäåðæàùèå ðåáðà
õîòÿ áû ñ îäíîé è ñ îáåèìè êîíå÷íûìè âåðøèíàìè â S ñîîòâåòñòâåííî.
Èç îïðåäåëåíèÿ ýòèõ ïîäìíîæåñòâ ñëåäóåò, ÷òî ìíîæåñòâî ðåáåð èç
� � �( ) ( ) \ ( )S S S� ÿâëÿåòñÿ ðàçðåçîì, îïðåäåëåííûì ïîäìíîæåñòâîì âåðøèí
S V� . Îáîçíà÷èì R RV E( ) ìíîæåñòâî { }( ( ): ) : ( ) ,u V u R V� � � �� � � ({( ( ):u e
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4 47
e E u e E e E� � �): ( ) , )} . Äëÿ ïðîèçâîëüíûõ T V� , T E� è u R V� , u R E� âìåñ-
òî u
kk T�� èñïîëüçóåì îáîçíà÷åíèå u T( ).
Ïóñòü c S( ( ))� è c S( ( ))� — ñóììû âåñîâ ðåáåð èç �( )S è � ( )S . Èçâåñòíî, ÷òî
� �( ) ( ( ))S c S� — ñóáìîäóëÿðíàÿ ôóíêöèÿ, ò.å.
� � � �( ) ( ) ( ) ( )S T S T S T� � �
,
è � �( ) ( ( ))S c S� — ñóïåðìîäóëÿðíàÿ ôóíêöèÿ, ò.å.
� � � �( ) ( ) ( ) ( )S T S T S T� � �
,
äëÿ ïðîèçâîëüíûõ ïîäìíîæåñòâ S è T ìíîæåñòâà V . Àññîöèèðîâàííûå ñ ýòè-
ìè ôóíêöèÿìè ìíîãîãðàííèêè
P x R x x S S S VV( ) : , ( ) ( ),� �� � � � �{ }0 ,
Q y R y y S S S VV( ) : , ( ) ( ),� �� � � � �{ }0
íàçûâàþòñÿ ïîëèìàòðîèäîì è ñóïåðïîëèìàòðîèäîì ñîîòâåòñòâåííî. Èç îïðå-
äåëåíèé �( )S , �( )S ñëåäóåò, ÷òî îíè ìîíîòîííûå ôóíêöèè è �( )V �
� ��( ) ( )V c E . Âåêòîðû x P� ( )� è y Q� ( )� ÿâëÿþòñÿ áàçàìè P ( )� è Q( )� ,
åñëè x V c E( ) ( )� è y V c E( ) ( )� . Èçâåñòíî, ÷òî îòíîñèòåëüíî êàæäîãî ëèíåéíîãî
óïîðÿäî÷åíèÿ L âåðøèí ãðàôà G V E� ( , ) ãðèäè àëãîðèòì îïðåäåëÿåò ñîîòâåò-
ñòâóþùèå áàçû x PL � ( )� è y QL � ( )� . Äàëåå äëÿ êðàòêîñòè áóäåì ñ÷èòàòü,
÷òî áàçû x è y ïîðîæäåíû ïî ëèíåéíîìó óïîðÿäî÷åíèþ L.  äàëüíåéøåì,
åñëè ýòî íå ïðèâåäåò ê íåîäíîçíà÷íîìó òðàêòîâàíèþ, âìåñòî x L è yL èñïîëü-
çóåì îáîçíà÷åíèÿ x è y.
Ñîãëàñíî ëèíåéíîìó óïîðÿäî÷åíèþ L âåðøèí ìîæíî îðèåíòèðîâàòü ðåáðà
ãðàôà G V E� ( , ) òàêèì îáðàçîì, ÷òî ïîëó÷åííûé îðãðàô áóäåò àöèêëè÷åñêèì
îðèåíòèðîâàííûì ãðàôîì. Äëÿ ýòîãî íóæíî çàìåíèòü êàæäîå ðåáðî ( , )� u äóãîé
�u, åñëè � � L u, èëè äóãîé u�, åñëè u L� �. Îáðàòíîå òîæå âåðíî, ò.å. êàæäîå
àöèêëè÷åñêîå îðèåíòèðîâàíèå ðåáåð ãðàôà G V E� ( , ) îïðåäåëÿåò ëèíåéíîå óïî-
ðÿäî÷åíèå L âåðøèí.  àöèêëè÷åñêîì îðèåíòèðîâàííîì ãðàôå G V E� ( , )
ñ âåñàìè c w� íà äóãàõ ìíîæåñòâî âõîäÿùèõ è âûõîäÿùèõ èç âåðøèíû � ðåáåð
îáîçíà÷èì � �� ( ) è � �� ( ) ñîîòâåòñòâåííî. Èç íàõîæäåíèÿ áàç x P� ( )� è
y Q� ( )� ãðèäè àëãîðèòìîì ñëåäóåò, ÷òî
c x Vu
u
�
� �
� �
� �
� � �
( )
, , (1)
c y Vu
u
�
� �
� �
� �
� � �
( )
, , (2)
â àöèêëè÷åñêîì îðèåíòèðîâàííîì ãðàôå G V E� ( , ), ãäå x� — ñóììà âåñîâ íà
äóãàõ, âûõîäÿùèõ èç âåðøèíû �, è y� — ñóììà âåñîâ íà äóãàõ, âõîäÿùèõ
â âåðøèíó �. Ðàâåíñòâà (1), (2) âûïîëíÿþòñÿ äëÿ ïðîèçâîëüíûõ áàç x P� ( )� è
y Q� ( )� , ïîðîæäåííûõ ïî ïðîèçâîëüíîìó ëèíåéíîìó óïîðÿäî÷åíèþ L âåðøèí
ãðàôà G V E� ( , ). Òàêèì îáðàçîì, äîêàçûâàåòñÿ ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 1. Ïóñòü áàçû ïîðîæäåíû ïî ëèíåéíîìó óïîðÿäî÷åíèþ L
âåðøèí ãðàôà G V E� ( , ). Òîãäà x y d� � , ãäå d d V� �( ; )� � — n-ìåðíûé âåêòîð
è d ñ d ww E� ��
� �� �
��( ( ))
( , )
äëÿ âñåõ âåðøèí � �V .
48 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4
Ïóñòü L n� ( , , ,� � �1 2 � ) è I n� ( )� � �, , ,� 2 1 — ëèíåéíûå óïîðÿäî÷åíèÿ
âåðøèí ãðàôà G V E� ( , ). Ðàññìîòðèì äâà àöèêëè÷åñêèõ îðèåíòèðîâàííûõ ãðàôà,
ïîëó÷åííûõ ñîîòâåòñòâåííî ïîñëå îðèåíòàöèè êàæäîãî ðåáðà ( , )� �i j èç E ñ ó÷å-
òîì ïîðÿäêà âåðøèí � i è � j â óïîðÿäî÷åíèÿõ L è I . Èç ðàâåíñòâ (1) è (2), ðàñ-
ñìîòðåííûõ äëÿ ýòèõ àöèêëè÷åñêèõ îðèåíòèðîâàííûõ ãðàôîâ, íåïîñðåäñòâåííî
ñëåäóåò äîêàçàòåëüñòâî ïðèâåäåííîãî äàëåå óòâåðæäåíèÿ.
Óòâåðæäåíèå 2. Ïóñòü y d x1 1� � è y d x2 2� � , ãäå áàçû x P1 � ( )� è
x P2 � ( )� ïîðîæäåíû ïî ëèíåéíîìó óïîðÿäî÷åíèþ L è I ñîîòâåòñòâåííî. Òîãäà
x y Q2 1� � ( )� è x y Q1 2� � ( )� .
Ôóíêöèÿ � �( ) ( )S S� íàçûâàåòñÿ ðàçðåçíîé, à èç îïðåäåëåíèÿ ôóíêöèé �(. )
è �(. ) ñëåäóåò, ÷òî îíà ñóáìîäóëÿðíàÿ è c S S S( ( )) ( ) ( )� � �� � . Ñëåäóþùèé ìíî-
ãîãðàííèê, àññîöèèðîâàííûé ñ ýòîé ôóíêöèåé,
EP z R z S S S S VV( ) : ( ) ( ) ( ),� � � �� � � � � �{ }
íàçûâàåòñÿ ðàñøèðåííûì ïîëèìàòðîèäîì (extended polymatroid) [22]. Èç
óòâåðæäåíèé 1, 2 ñëåäóåò, ÷òî åñëè áàçû x è y ïîðîæäåíû ïî ëèíåéíîìó óïî-
ðÿäî÷åíèþ L, òî âåêòîð z x y EP� � � �( )� � è z V( ) � 0, òàê êàê � �( ) ( )V V� �
� c E( ). Òàêîé âåêòîð z íàçûâàåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðîèäà
EP ( )� �� , êîòîðàÿ òàêæå ìîæåò áûòü ïîðîæäåííîé ïî ëèíåéíîìó óïîðÿäî÷å-
íèþ L. Íåòðóäíî âèäåòü, ÷òî ïðîèçâîëüíàÿ áàçà z ðàñøèðåííîãî ïîëèìàòðîèäà
ïðåäñòàâèìà â âèäå z x y� � . Èç z V( ) � 0 ñëåäóåò, ÷òî ðàâåíñòâî ( : )z z� ��
�0
� � �� ( : )z z� � 0 âûïîëíÿåòñÿ äëÿ áàçû z x y� � ðàñøèðåííîãî ïîëèìàòðîèäà
E ( )� �� , êîòîðîå íàçîâåì íóëåâîé ñóììîé.
Óòâåðæäåíèå 3. Áàçû x P� ( )� , y Q� ( )� è z EP� �( )� � ìîãóò áûòü ïîðîæ-
äåííûìè ïî ïðîèçâîëüíîìó ëèíåéíîìó óïîðÿäî÷åíèþ L çà âðåìÿ O m( ).
Äîêàçàòåëüñòâî. Ïóñòü L n� ( , ,� �1 � ) è Li i� ( , ,� �1 � ) äëÿ i n�1, ,� . Ïî
ôîðìóëàì ãðèäè àëãîðèòìà x L L c
i i i i� � � � �� � � �� �( ) ( ) ( ( ))1 0, ò.å. x
i� ÿâëÿåò-
ñÿ ñóììîé âåñîâ ðåáåð ( , )� �i j E� , äëÿ êîòîðûõ � �i L j� â L. Òàêèì îáðàçîì,
ïðè îïðåäåëåíèè áàçû x êàæäîå ðåáðî ó÷èòûâàåòñÿ îäèí ðàç, ïîýòîìó òðåáóåìîå
âðåìÿ ðàâíî O m( ). Ïîñêîëüêó áàçû y d x Q� � � ( )� è z x y EP� � � �( )� � òàêæå
ïîðîæäåíû ïî ëèíåéíîìó óïîðÿäî÷åíèþ L, èõ òîæå ìîæíî îïðåäåëèòü çà âðå-
ìÿ O m( ). �
2. ÐÀÇÐÅÇÛ È ÁÀÇÛ ÏÎËÈÌÀÒÐÎÈÄÀ
Ïîêàæåì, ÷òî ñóùåñòâóåò îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ðàçðåçàìè â ãðàôå
G V E� ( , ) è íåêîòîðûìè áàçàìè èç ðàñøèðåííîãî ïîëèìàòðîèäà EP ( )� �� , ãäå
ôóíêöèè � è � îïðåäåëåíû ðàíåå íà ïîäìíîæåñòâàõ ìíîæåñòâà âåðøèí ýòîãî
ãðàôà. Îáîçíà÷èì S V S� \ äëÿ êàæäîãî íåïóñòîãî ïîäìíîæåñòâà S V� . ßñíî,
÷òî ïîñëå óäàëåíèÿ ðåáåð èç ìíîæåñòâ � ( )S è � ( )S ïîëó÷åííûé îñòîâíîé ïîä-
ãðàô H S S A� ( , , ) äâóäîëüíûé, ïðè÷åì äîïóñêàåòñÿ, ÷òî â H ìîãóò áûòü èçî-
ëèðîâàííûå âåðøèíû. Èíûìè ñëîâàìè, ïîäìíîæåñòâî ðåáåð A ÿâëÿåòñÿ ðàçðå-
çîì �( )S â íåîðèåíòèðîâàííîì ãðàôå G V E� ( , ). Ïóñòü dH ( )� îáîçíà÷àåò ñóì-
ìó âåñîâ ðåáåð ñ êîíå÷íîé âåðøèíîé � â ïîäãðàôå H . Êàæäîìó ðàçðåçó �( )S
â ãðôå G V E� ( , ) ñîïîñòàâèì âåêòîð z z VS S� �( ( ): )� � , ãäå
z
d S
d S
S
H
H
( )
( ), ,
( ), .
�
� �
� �
�
�
� �
�
�
�
åñëè
åñëè
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4 49
Òåîðåìà 1. Äëÿ ïðîèçâîëüíîãî íåïóñòîãî ïîäìíîæåñòâà âåðøèí S V� âåê-
òîð zS , ñîîòâåòñòâóþùèé ðàçðåçó �( )S , ÿâëÿåòñÿ áàçîé ðàñøèðåííîãî ïîëèìàòðî-
èäà EP ( )� �� .
Äîêàçàòåëüñòâî. Ðàññìîòðèì ëèíåéíîå óïîðÿäî÷åíèå âåðøèí L S S� ( , ),
ò.å. � � L w äëÿ êàæäîé âåðøèíû � �S è w S� . Íå íàðóøàÿ îáùíîñòè, ìîæåì
ïðåäïîëàãàòü, ÷òî � � �1 2� � � �L L L p, , è � �p L L n�1 � � �, , â S è S ñîîòâåò-
ñòâåííî. ßñíî, ÷òî z x y EP1 1 1� � � �( )� � äëÿ áàç x P1 � ( )� è y Q1 � ( )� , ïîðîæ-
äåííûõ ïî L.
Òåïåðü ðàññìîòðèì ëèíåéíîå óïîðÿäî÷åíèå âåðøèí I S S� ( , ), â êîòîðîì
âåðøèíû â S è S óïîðÿäî÷åíû â îáðàòíîì ïîðÿäêå, ò.å. � �p L L� � �, , 1 è
� �n L L p� � �, , �1. Èìååì z x y EP2 2 2� � � �( )� � äëÿ áàç x P2 � ( )� è
y Q2 � ( )� , ïîðîæäåííûõ ïî I .
Ðàññìîòðèì àöèêëè÷åñêèå îðèåíòèðîâàííûå ãðàôû G1 è G2 , ïîëó÷åííûå ïî-
ñëå çàìåíû êàæäîãî ðåáðà èç E äóãîé â ñîîòâåòñòâèè ñ ëèíåéíûì óïîðÿäî÷åíèåì
âåðøèí L è I . Åñëè â G1 äóãà � �i j ñ êîíå÷íûìè âåðøèíàìè � �i j S, � èëè
� �i j S, � íàïðàâëåíà èç âåðøèíû � i â âåðøèíó � j , òî â G2 îíà íàïðàâëåíà èç
� j â � i . Ïðè ýòîì â ãðàôàõ G1 è G2 êàæäîå ðåáðî ðàçðåçà �( )S çàìåíÿåòñÿ äó-
ãîé, íàïðàâëåííîé èç âåðøèí S ê âåðøèíàì S . Ïîýòîìó x yu u
1 2� è x yu u
2 1� äëÿ
èçîëèðîâàííûõ âåðøèí u â ïîäãðàôå H . Åñëè âåðøèíû � �S è w S� íåèçîëèðî-
âàííûå, òî èç (1) è (2) ñëåäóåò, ÷òî x y dH� � �1 2� � ( ) è x y dH� � �2 1� � ( ), à òàêæå
x y d ww w H
1 2� � ( ) è x y d ww w H
2 1� � ( ). ßñíî, ÷òî dH ( )� � 0 äëÿ èçîëèðîâàííûõ âåð-
øèí â H . Ïîýòîìó
z
x y x y z z
EPS �
�
�
�
�
�
� �
1 1 2 2 1 2
2 2 2
( )� � ,
÷òî è äîêàçûâàåò òåîðåìó. �
Íåñìîòðÿ íà òî, ÷òî âî ìíîãèõ âû÷èñëèòåëüíûõ àëãîðèòìàõ äëÿ ðåøåíèÿ çà-
äà÷ íà ñåòÿõ áàçû ðàñøèðåííîãî ïîëèìàòðîèäà â ÿâíîì âèäå íå èñïîëüçóþòñÿ, íà
ñàìîì äåëå â ïðîöåññå èõ ðàáîòû òîæå îïðåäåëÿåòñÿ íåêîòîðîå ëèíåéíîå óïîðÿ-
äî÷åíèå âåðøèí, ïî êîòîðîìó ïîðîæäåííàÿ áàçà ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíè-
åì. Íàïðèìåð, àëãîðèòì [18] ðåøåíèÿ çàäà÷è ìèíèìàëüíîãî ðàçðåçà îïðåäåëÿåò
ïðàâèëüíûé ïîðÿäîê (legal ordering) âåðøèí G V E� ( , ) óïîðÿäî÷åíèåì âåðøèí �
ïî âîçðàñòàíèþ çíà÷åíèÿ z x y� � �� � , ò.å. íà òåêóùåì øàãå âûáèðàåòñÿ âåðøèíà
�, äëÿ êîòîðîé çíà÷åíèå y� ìàêñèìàëüíîå, à x� ìèíèìàëüíîå. Ïîýòîìó ïðàâèëü-
íûé ïîðÿäîê âåðøèí ìîæíî îïðåäåëèòü çà âðåìÿ O m( ). Îäíàêî, îñíîâûâàÿñü íà
òåîðåìå 1 è ñëåäóþùåé ïðîñòîé ëåììå, äëÿ îïðåäåëåíèÿ ìèíèìàëüíîãî ðàçðåçà
â íåîðèåíòèðîâàííîì ãðàôå G V E� ( , ) ìîæíî óïîðÿäî÷èòü âåðøèíû ðàçëè÷íûìè
ñïîñîáàìè.
Ëåììà 1. Åñëè L S S� ( , ) — ïðîèçâîëüíîå ëèíåéíîå óïîðÿäî÷åíèå òàêîå,
÷òî âåðøèíû � �S è w S� óäîâëåòâîðÿþò óñëîâèþ � � L w, òî c S( ( ))� �
� �x S y S( ) ( ), ãäå x P� ( )� è y Q� ( )� — áàçû, ïîðîæäåííûå ïî L.
Äîêàçàòåëüñòâî. Èç îïðåäåëåíèÿ ôóíêöèé �( )S è �( )S ñëåäóåò, ÷òî
� � �( ) ( ) ( ( ))S S c S� � . Ïîýòîìó x S y S S S( ) ( ) ( ) ( )� � �� � äëÿ L S S� ( , ). �
Ñîãëàñíî ëåìå 1 äëÿ îïðåäåëåíèÿ c S( ( ))� äîñòàòî÷íî, ÷òîáû S SL� â ëèíåé-
íîì óïîðÿäî÷åíèè L, ò.å. âåðøèíû èç S è S ìîãóò ïîÿâëÿòüñÿ â ïðîèçâîëüíîì ïî-
50 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4
ðÿäêå âíóòðè ýòèõ ïîäìíîæåñòâ. Òàêàÿ ïðîñòàÿ èäåÿ, èñïîëüçóåìàÿ âî ìíîãèõ èç-
âåñòíûõ àëãîðèòìàõ ïðè ðåøåíèè çàäà÷è ìèíèìàëüíîãî ðàçðåçà, çàêëþ÷àåòñÿ
â òîì, ÷òî ïîäìíîæåñòâà S è S èíäóöèðóþò ñâÿçíûå êîìïîíåíòû ãðàôà G V E� ( , ).
Ëåãêî ïîêàçàòü, ÷òî ýòî ñâîéñòâî íåïðèìåíèìî äëÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà.
Òîëüêî íà ñïåöèàëüíûõ ãðàôàõ ìîæíî îïðåäåëèòü íóæíûé ïîðÿäîê ïðîñìîòðà
âåðøèí çà ïîëèíîìèàëüíîå âðåìÿ ïðè ðåøåíèè çàäà÷è ìàêñèìàëüíîãî ðàçðåçà.
Äëÿ ïðèìåðà ðàññìîòðèì äâóäîëüíûé ãðàô H W U A� ( , , ) ñ íåîòðèöàòåëüíû-
ìè âåñàìè ðåáåð èç A, ãäå A — ìíîæåñòâî ðåáåð, W è U — ìíîæåñòâà âåðøèí
äîëè ãðàôà. Äîïóñòèì, ÷òî P ( )� è Q( )� àíàëîãè÷íî îïðåäåëåíû îòíîñèòåëüíî
ãðàôà H . Ïóñòü dH ( )� — ñóììà âåñîâ íà ðåáðàõ, èíöèäåíòíûõ ê âåðøèíå
� � W U . Âåêòîðû x è y ïðè x dH� �� ( ) äëÿ � �W, xu � 0 äëÿ u U� è y� � 0 äëÿ
� �W, y d uu H� ( ) äëÿ u U� ÿâëÿþòñÿ áàçàìè P ( )� è Q( )� , ïîðîæäåííûìè ïî ëè-
íåéíîìó óïîðÿäî÷åíèþ L W U� ( , ). Ïî îïðåäåëåíèþ ýòèõ áàç ñóììà
| |x y
W U
�
�
�
�
� � îçíà÷àåò óäâîåííûé âåñ ìàêñèìàëüíîãî ðàçðåçà, ðàçäåëÿþùåãî
ìíîæåñòâà W è U â ãðàôå H .
3. ÎÑÍÎÂÍÛÅ ÑÂÎÉÑÒÂÀ ÇÀÄÀ×È ÌÀÊÑÈÌÀËÜÍÎÃÎ ÐÀÇÐÅÇÀ
Îïðåäåëåíèå ìàêñèìàëüíîãî ðàçðåçà â ãðàôå G V E� ( , ) ñ åäèíè÷íûìè âåñàìè
ðåáåð îñîáåííî âàæíî, ïîñêîëüêó ëþáîé ýôôåêòèâíûé àëãîðèòì ðåøåíèÿ
ýòîé NP-òðóäíîé çàäà÷è ìîæåò áûòü ïîëîæåí â îñíîâó ìåòîäà ðåøåíèé äðó-
ãèõ ñëîæíûõ çàäà÷ íà ãðàôàõ.  äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ce �1 äëÿ
âñåõ ðåáåð e E� èëè ÷òî c ce �
0. Ïîýòîìó äëÿ ïðîèçâîëüíîãî F E� ïîä
c F( ) áóäåì ïîíèìàòü | |F .
Ìîäåëü [17] ýòîé çàäà÷è, ñôîðìóëèðîâàííàÿ êàê çàäà÷à ìàêñèìèçàöèè ñïå-
öèàëüíîé íåãëàäêîé âûïóêëîé ôóíêöèè íà âûïóêëîé îáîëî÷êå áàç ïîëèìàòðîè-
äà P ( )� , ÿâëÿåòñÿ ñëåäñòâèåì òåîðåìû 1. Äåéñòâèòåëüíî, ïîñêîëüêó x x d1 2� � è
| ( ) ( ) ( )| | ( )|x S x S d S z SS
1 2� � � äëÿ áàç x1 è x 2 , ðàññìîòðåííûõ â äîêàçàòåëüñòâå
òåîðåìû 1, óäâîåííîé ìîùíîñòüþ ìàêñèìàëüíîãî ðàçðåçà â G ñ åäèíè÷íûìè âå-
ñàìè ðåáåð ÿâëÿåòñÿ MaxCut x S d S x S d S
*
( ) ( ) | ( ) ( )|� � � �2 21 1 . Ñ ó÷åòîì òîãî,
÷òî âûïóêëàÿ îáîëî÷êà áàç ïîëèìàòðîèäà P ( )� çàäàåòñÿ ìíîãîãðàííèêîì
B x x x P x V V( ) ; , ( ), ( ) ( )� � �� � � �{ }0 [19, 22], íàõîæäåíèå ìàêñèìàëüíîãî ðàç-
ðåçà â ãðàôå G V E� ( , ) ôîðìóëèðóåòñÿ êàê ñëåäóþùàÿ çàäà÷à âûïóêëîãî ïðî-
ãðàììèðîâàíèÿ
MaxCut f x x d
V
*
max ( ) | |� � �
�
�{ }2 �
�
� (3)
ïðè îãðàíè÷åíèÿõ
x B� ( )� . (4)
 îòëè÷èå îò óïîìÿíóòûõ âî ââåäåíèè ìîäåëåé, ïðåèìóùåñòâî çàäà÷è (3),
(4) ñîñòîèò â âû÷èñëèòåëüíîé ýôôåêòèâíîñòè óæå ðàçðàáîòàííûõ àëãîðèòìîâ åå
ðåøåíèÿ. Íàïðèìåð, ïðîñòîé O nm( ) àëãîðèòì [17] äëÿ îïðåäåëåíèÿ áàçû èç B ( )�
â êà÷åñòâå ðåøåíèÿ çàäà÷è (3), (4) ÿâëÿåòñÿ ãðèäè àëãîðèòìîì, â ïðîöåññå ðàáîòû
êîòîðîãî ó÷èòûâàþòñÿ îñíîâíûå òîïîëîãè÷åñêèå ñâîéñòâà çàäàííîãî ãðàôà â ÿâ-
íîì âèäå. Òàêàÿ âû÷èñëèòåëüíàÿ ýôôåêòèâíîñòü íà ïðàêòèêå òàêæå ÿâëÿåòñÿ ïî-
ëåçíûì èíñòðóìåíòîì äëÿ ïîèñêà ïðèáëèæåííûõ ðåøåíèé êëàññîâ çàäà÷ ðåàëü-
íîé ðàçìåðíîñòè.  îáùåì ñëó÷àå òî÷íîñòü íàéäåííîãî ðåøåíèÿ àëãîðèò-
ìîì [17] ìîæíî ïîâûñèòü ñ ïîìîùüþ ïðîöåäóð èñêëþ÷åíèÿ è âêëþ÷åíèÿ èëè
ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ áàç (ñì. äàëåå), ïðè îïèñàíèè êîòîðûõ áóäåì èñ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4 51
ïîëüçîâàòü ñëåäóþùèå îáîçíà÷åíèÿ:
f x x d
V x
�
�
� �
�
�( ) ( )
( )
2 �
�
� ,
f x d x
V x
�
�
� �
�
�( ) ( )
( )
�
�
�2 ,
ãäå V x V x d� � � �
( ) ;{ }� � �2 0 è V x V x d� � � � �( ) ;{ }� � �2 0 äëÿ ïðîèçâîëüíîé
áàçû x B f� ( ). Âíà÷àëå ïðèâåäåì íåêîòîðûå ïîëåçíûå ñâîéñòâà çàäà÷è (3), (4).
Ñëåäóþùàÿ ëåììà ïîçâîëÿåò ñôîðìóëèðîâàòü ðàçëè÷íûå çàäà÷è, ýêâèâàëåí-
òíûå (3), (4), à òàêæå íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ îïòèìàëüíîñòè ðå-
øåíèÿ çàäà÷è ìàêñèìàëüíîãî ðàçðåçà.
Ëåììà 2. Äëÿ ïðîèçâîëüíîãî x B� ( )� èìååì f x f x f x( ) ( ) ( )� �� �2 2 .
Äîêàçàòåëüñòâî. Èç ðàâåíñòâà
f x f x x d
V
� �
�
� � � ��( ) ( ) ( )2 0�
�
�
ñëåäóåò, ÷òî f x f x f x f x( ) ( ) ( ) ( )� � � �� � �0 2 , f x f x f x f x( ) ( ) ( ) ( )� � � �� � �0 2 . �
Òàêèì îáðàçîì, MaxCut f x f x f x f x
*
* * * *( ) ( ) ( ) ( )� � � �� � � �2 2 , ãäå x * —
îïòèìàëüíîå ðåøåíèå çàäà÷è (3), (4).
Ñîãëàñíî óòâåðæäåíèÿì 1–3 ïðîèçâîëüíàÿ áàçà z EP� �( )� � ïðåäñòàâèìà
â âèäå z x y x d� � � �2 , ãäå x B� ( )� è y d x� � . Ðàññìîòðèì âåêòîð z � ïðè
z z� �
� � max ,{ }0 äëÿ âñåõ � �V . Èç ýòîé ëåììû òàêæå ñëåäóåò, ÷òî çàäà÷à
max ( ): ( ){ }z V z EP� � �� � ýêâèâàëåíòíà çàäà÷å (3), (4). Êðîìå ýòîé çàäà÷è, ìîæ-
íî ñôîðìóëèðîâàòü ìèíèìàêñíûå îòíîøåíèÿ äëÿ çàäà÷è (3), (4). Íàïðèìåð,
äâîéñòâåííîå ðàâåíñòâî
max ( ): ( ) | | min ( ) ( ), ( ),{ } {f x x B E x V y V x B y d x� � �� � � � � � �� � } (5)
òàêæå ÿâëÿåòñÿ ñëåäñòâèåì ëåììû 2.
Çàäà÷ó, ñòîÿùóþ â ïðàâîé ÷àñòè ðàâåíñòâà (5), áóäåì íàçûâàòü äâîéñòâåí-
íîé ê çàäà÷å ìàêñèìàëüíîãî ðàçðåçà (3), (4). Êðîìå çàäà÷è (5), ìîæíî âûâåñòè
ðàçëè÷íûå âàðèàíòû äâîéñòâåííîé çàäà÷è. Äëÿ ýòîãî âíà÷àëå îïðåäåëèì âåêòîð
z � ïðè z z� �
� � min ,{ }0 äëÿ âñåõ � �V . Èç ëåììû 2 ñëåäóåò, ÷òî, íàïðèìåð, çàäà÷à
min ( ); ( ){ }z V z EP� � �� � ýêâèâàëåíòíà äâîéñòâåííîé çàäà÷å (5).
Çàäà÷à (3), (4) ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì îáùåé çàäà÷è ìàêñèìèçàöèè âûïóê-
ëîé ôóíêöèè íà âûïóêëîì ìíîæåñòâå.  îòëè÷èå îò ñëó÷àÿ îòûñêàíèÿ ìèíèìóìà,
íàõîæäåíèå ìàêñèìóìà âûïóêëîé ôóíêöèè çíà÷èòåëüíî áîëåå òðóäíàÿ çàäà÷à, òàê
êàê âîçìîæíî, ÷òî íåêîòîðûå äîïóñòèìûå ðåøåíèÿ äîñòàâëÿþò ëîêàëüíûé ìàêñè-
ìóì.  îáùåì ñëó÷àå èíôîðìàöèÿ î ëîêàëüíûõ ìàêñèìóìàõ, ñóùåñòâîâàíèå êîòî-
ðûõ ìàëîâåðîÿòíî, íå ïîìîãàåò ïåðåéòè ê ëó÷øåé òî÷êå äëÿ ïðîäâèæåíèÿ ê ãëî-
áàëüíîìó ìàêñèìóìó, ÷òî òàêæå ñâèäåòåëüñòâóåò î òðóäíîðàçðåøèìîñòè çàäà÷è.
Âïðî÷åì, ìàëàÿ âåðîÿòíîñòü ñóùåñòâîâàíèÿ ëîêàëüíûõ ìàêñèìóìîâ â îáùåì ñëó-
÷àå íå îçíà÷àåò èõ îòñóòñòâèå. Ïðåäïîëîæèì, ÷òî íåêîòîðûå äîïóñòèìûå ðåøåíèÿ
èç B ( )� ÿâëÿþòñÿ òî÷êàìè ëîêàëüíîãî ìàêñèìóìà ôóíêöèè (3) îòíîñèòåëüíî íåêî-
òîðîé åå îêðåñòíîñòè â åâêëèäîâîé íîðìå. Ìîæíî ïîêàçàòü, ÷òî òî÷êè ëîêàëüíûõ
ìàêñèìóìîâ ëåæàò íà ãðàíè ìíîãîãðàííèêà B ( )� ðàçìåðíîñòè, íå áîëüøåé n �2.
Äëÿ çàäà÷è (3), (4) ïîêàæåì, ÷òî òî÷êè ëîêàëüíûõ ìàêñèìóìîâ ÿâëÿþòñÿ îäíî-
âðåìåííî òî÷êàìè ãëîáàëüíûõ ìàêñèìóìîâ öåëåâîé ôóíêöèè (3).
52 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4
Òåîðåìà 2.  çàäà÷å (3), (4) âñå ëîêàëüíûå ìàêñèìóìû ÿâëÿþòñÿ îäíîâðå-
ìåííî ãëîáàëüíûìè ìàêñèìóìàìè.
Äîêàçàòåëüñòâî. Ïóñòü f x( )* — ãëîáàëüíûé ìàêñèìóì ôóíêöèè â òî÷êå
x B* ( )� � è f x( ) — ëîêàëüíûé ìàêñèìóì â òî÷êå x B� ( )� . Ðàññìîòðèì ñëó÷àé,
êîãäà ïåðåñå÷åíèÿ V x� ( )* è V x� ( ) ÿâëÿþòñÿ ïóñòûì ìíîæåñòâîì.  ýòîì ñëó÷àå
ïîëó÷èì, ÷òî V x V x� ��( ) ( )* , òàê êàê óñëîâèå V x V x� ��( ) ( )* ïðîòèâîðå÷èò
òîìó, ÷òî f x( )* — ãëîáàëüíûé ìàêñèìóì. Ñëåäîâàòåëüíî, f x f x� ��( ) ( )*
ñîãëàñíî ëåììå 1 èëè f x f x( ) ( )*� , ò.å. ëîêàëüíûé è ãëîáàëüíûé ìàêñèìóìû
ôóíêöèè îäèíàêîâû.  ñëó÷àå V x V x� ��( ) ( )* ëîêàëüíûé è ãëîáàëüíûé ìàêñè-
ìóìû ôóíêöèè f x( ) òîæå ñîâïàäàþò ïî çíà÷åíèþ öåëåâîé ôóíêöèè. Ïîýòîìó
ðàññìîòðèì ñëó÷àé, êîãäà ïåðåñå÷åíèå V x� ( )* è V x� ( ) — íåïóñòîå ìíîæåñòâî è
V x V x� ��( ) ( )* . Åñëè x ÿâëÿåòñÿ ëîêàëüíûì ìàêñèìóìîì âûïóêëîé ôóíêöèè (4)
íà ìíîãîãðàííèêå B ( )� , òî
( ( ), )g x x x� � 0 � �x B ( )� , (6)
ãäå g x( ) — ëþáîé ñóáãðàäèåíò ôóíêöèè â òî÷êå x B� ( )� [20]. ßñíî, ÷òî âåê-
òîð g, êîìïîíåíòû êîòîðîãî g x� ( ) � 2, åñëè 2x d� �
, è g x� ( ) � �2, åñëè
2x d� �� , à òàêæå g x� ( ) � 0, åñëè 2x d� �� , ÿâëÿåòñÿ ñóáãðàäèåíòîì ôóíêöèè (3).
Ïóñòü S V x V x0 �
� �( ) ( )* , T V x V x0 �
� �( ) ( )* , S V x S T� �� ( ) \ ,*
0
� �V x T( ) \*
0 .
Âî-ïåðâûõ, íå íàðóøàÿ îáùíîñòè, äëÿ âåðøèí � �S 0 è � �T0 ñîãëàñíî ëåì-
ìå 1 ìîæíî ïîëîæèòü x x� �� * , ò.å. g x x x� � �( )( )� � 0. Âî-âòîðûõ, î÷åâèäíî, ÷òî
f x f y( ) ( )* *� äëÿ y d x B* * ( )� � � � . Ïîýòîìó
f x f y f x f x d x x d
S
( ) ( ) ( ) ( ) ( )* * *� � � � � � � �
�
� �
�
� � �2 2
� � � � � � � �
�
� ( ) ( ( ), )* *2 2 0
�
� � � �
T
x d d x g x y x ,
ãäå ïîñëåäíåå ðàâåíñòâî ÿâëÿåòñÿ ðåçóëüòàòîì çàìåíû d x y� � �* * äëÿ âñåõ
âåðøèí � �S è � �T . Òàê êàê ëîêàëüíûé ìàêñèìóì íå ìîæåò ïðåâûøàòü ãëî-
áàëüíîãî, èç f x f y( ) ( )*� ñëåäóåò, ÷òî f x f y( ) ( )*� . �
Íåñìîòðÿ íà ýòîò ðåçóëüòàò, ââèäó ýêñïîíåíöèàëüíîãî êîëè÷åñòâà îãðàíè÷å-
íèé, çàäàþùèõ ìíîãîãðàííèê B ( )� , ïðèìåíåíèå ñóùåñòâóþùèõ àëãîðèòìîâ íå-
ãëàäêîé îïòèìèçàöèè äëÿ ðåøåíèÿ çàäà÷è (3), (4) ñîïðÿæåíî ñ áîëüøèìè âû÷èñ-
ëèòåëüíûìè òðóäíîñòÿìè, òàê êàê òðåáóåòñÿ êîäèðîâàòü êàæäîå îãðàíè÷åíèå
â íåêîòîðîì ôîðìàòå.
ÇÀÊËÞ×ÅÍÈÅ
×àñòî íà ïðàêòèêå çàäà÷è ïîèñêà ðàçëè÷íûõ ðàçðåçîâ â íåîðèåíòèðîâàííûõ
ãðàôàõ èìåþò ëèíåéíûå îãðàíè÷åíèÿ. Òàê, â ñëó÷àå çàäà÷è ìèíèìàëüíîãî ðàç-
ðåçà îñîáåííîñòè îãðàíè÷åíèé ïîçâîëÿþò óñïåøíî ïðèìåíÿòü ýôôåêòèâíûå
ñòðîãî ïîëèíîìèàëüíûå àëãîðèòìû êîìáèíàòîðíîé îïòèìèçàöèè.  ñëó÷àå çà-
äà÷è ìàêñèìàëüíîãî ðàçðåçà, íåñìîòðÿ íà òî, ÷òî ÷èñëî îãðàíè÷åíèé â (4) âû-
ðàæàåòñÿ ýêñïîíåíöèàëüíî îò êîëè÷åñòâà âåðøèí ãðàôà, ñ ó÷åòîì îñîáåííîñòåé
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4 53
îãðàíè÷åíèé ìîæíî ïîñòðîèòü ïðîñòîé ýôôåêòèâíûé àëãîðèòì íà áàçå èçâåñ-
òíûõ ñâîéñòâ ïîëèìàòðîèäîâ. Íàïðèìåð, ïðîñòîé ïîëèíîìèàëüíûé àëãîðèòì
â [17] çà ïîëèíîìèàëüíîå âðåìÿ îïðåäåëÿåò òî÷íîå ðåøåíèå çàäà÷è ìàêñè-
ìàëüíîãî ðàçðåçà â ïîëíûõ è íåêîòîðûõ äðóãèõ ãðàôàõ ñ åäèíè÷íûìè âåñàìè
íà ðåáðàõ. Äëÿ ïîâûøåíèÿ òî÷íîñòè ðåøåíèÿ, ïîëó÷åííîãî àëãîðèòìîì [17],
òðåáóåòñÿ ðàçðàáîòàòü àëãîðèòì, îñóùåñòâëÿþùèé ïåðåõîä îò îäíîé áàçû ê
äðóãîé ñ ëó÷øèì çíà÷åíèåì öåëåâîé ôóíêöèè (3).  ñëåäóþùåé ÷àñòè ñòàòüè
ïðåäëîæåí îäèí èç òàêèõ àëãîðèòìîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Barahona F., Grotschel�� M., Junger�� M., Reinelt G. An application of combinatorial optimization to
statistical physics and circuit layout design. Operations Research. 1988. Vol. 36, N 3. P. 493–513.
2. Karp R.M. Reducibility among combinatorial problems. Miller R.E., Thatcher J.W., Bohlinger J.D.
(Eds.). Complexity of Computer Computations. New York: Plenum Press, 1972. P. 85–103.
3. Garey M.R., Johnson D.S., Stockmeyer L. Some simplified NP-complete graph problems. Theoret.
Comput. Sci. 1976. Vol. 1, Iss. 3. P. 237–267.
4. Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness.
New York: W.H. Freeman and Company, 1979.
5. Boros E., Hammer P.L. Pseudo-Boolean optimization. Discrete Applied. Mathematics. 2002. Vol. 123,
Iss. 1–3. P. 155–225.
6. Bertoni A., Campadelli P., Grossi G. An approximation algorithm for the maximum cut problem and
its experimental analysis. Discrete Applied Mathematics. 2001. Vol. 110, Iss. 1. P. 3–12.
7. Orlova G.I., Dorfman Y.G. Finding the maximal cut in a graph. Engineering Cybernetics. 1972.
Vol. 10. P. 502–504.
8 Hadlock F.O. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on
Computing. 1975. Vol. 4, Iss. 3. P. 221–225.
9. Shih K., Wu S., Kuo Y.S. Unifying maximum cut and minimum cut of a planar graph. IEEE
Transactions on Computers. 1990. Vol. 39, Iss. 5. P. 694–697.
10. Grotschel�� M., Pulleyblank W.R. Weakly bipartite graphs and the max-cut problem. Operat. Res. Lett.
1981. Vol. 1, Iss. 1. P. 23–27.
11. Barahona F. The max-cut problem in graphs is not contractible to K5. Operat. Res. Lett. 1983.
Vol. 2, Iss. 3. P. 107–111.
12. Brahim Chaourar. A linear time algorithm for a variant of the MAX CUT problem in series parallel
graphs. 2017. Vol. 2017. Article ID 1267108. 4 p. https://doi.org/10.1155/2017/1267108.
13. Ben-Ameur W., Mahjoub A.R., Neto J. The maximum cut problem. In: Paradigms of combinatorial
optimization. In Problems and New Approaches. Ch. 6. Paschos V.T. (Ed.). J. Wiley and Sons,
USA, 2nd edition, 2014.
14. Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. American Mathematical Society. 1995.
Vol. 20. P. 181–244.
15. Goemans M.X., Williamson D.P. Improved approximation algorithms for MAX-CUT and
satisfiability problems using semidefinite programming. Journal of ACM. 1995. Vol. 42, N 6.
P. 1115–1145.
16. Rendl F., Rinaldi G., Wiegele A. Solving MAX-CUT to optimality by intersecting semidefinite and
polyhedral relaxations. Math. Program. Publ. Online: May 6, 2008. 33 p. URL:
17. Øàðèôîâ Ô.À. Íàõîæäåíèÿ ìàêñèìàëüíîãî ðàçðåçà ãðèäè àëãîðèòìîì. Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. 2018. Ò. 54, ¹ 5. C. 48–54.
18. Stoer M., Wagner F. A simple min cut algorithm. Journal of ACM. 1997. Vol. 44, N 4. P. 583–591.
19. Iwata S. Submodular function minimization. Math. Program. Ser. A–B. 2008. Vol. 112, N 1. P. 45–64.
20. Bazaraa M.S., Sherali H.D., Shetty M.C. Nonlinear programming: Theory and algorithms. New
York: J. Wiley and Sons, 1979. 583 p.
Íàä³éøëà äî ðåäàêö³¿ 10.07.2019
54 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4
Ô.À. Øàð³ôîâ, Ë.Ô. Ãóëÿíèöüêèé
ÐÎÇвÇÈ Â ÍÅÎвªÍÒÎÂÀÍÈÕ ÃÐÀÔÀÕ. ²
Àíîòàö³ÿ. Äîñë³äæåíî íîâ³ âëàñòèâîñò³ ðîçð³ç³â ó íåîð³ºíòîâàíèõ ãðàôàõ,
íàâåäåíî ð³çí³ ìîäåë³ äëÿ çàäà÷³ ìàêñèìàëüíîãî ðîçð³çó íà îñíîâ³ âñòàíîâ-
ëåíî¿ â³äïîâ³äíîñò³ ì³æ ðîçð³çàìè â çàäàíîìó ãðàô³ ³ ñïåöèô³÷íèìè áàçàìè
ðîçøèðåíîãî ïîë³ìàòðî¿äà, àñîö³éîâàíîãî ç öèì ãðàôîì. Äëÿ ìîäåë³, ñôîð-
ìóëüîâàíî¿ ÿê çàäà÷à çíàõîäæåííÿ ìàêñèìóìó îïóêëî¿ ôóíêö³¿ íà êîì-
ïàêòí³é ìíîæèí³ (ðîçøèðåíîìó ïîë³ìàòðî¿ä³), äîâåäåíî, ùî ëîêàëüí³ ³ ãëî-
áàëüí³ ìàêñèìóìè çá³ãàþòüñÿ çà çíà÷åííÿì ö³ëüîâî¿ ôóíêö³¿, òîáòî äëÿ ðîç-
â’ÿçàííÿ çàäà÷³ ìàêñèìàëüíîãî ðîçð³çó äîñòàòíüî çíàéòè áàçó ðîçøèðåíîãî
ïîë³ìàòðî¿äà ÿê ëîêàëüíèé àáî ãëîáàëüíèé ìàêñèìóì ö³ëüîâî¿ ôóíêö³¿.
Êëþ÷îâ³ ñëîâà: ãðàôè, ðîçð³çè, îïóêëà ôóíêö³ÿ, ñïåö³àëüí³ áàãàòîãðàííèêè.
F. Sharifov, L. Hulianytskyi
CUTS IN UNDIRECTED GRAPHS. I
Abstract. This part of the paper analyzes new properties of cuts in undirected
graphs, presents various models for the maximum cut problem, based on the
established correspondence between the cuts in this graph and the specific bases
of the extended polymatroid associated with this graph. With respect to the
model, formulated as the maximization of the convex function on the compact
set (extended polymatroid), it was proved that the objective function has the
same value at any local and global maximum, i.e., to solve the maximum cut
problem, it needs to find a base of the extended polymatroid as a local or global
maximum of the objective function.
Keywords: graphs, cuts, convex function, special polyhedra.
Øàðèôîâ Ôèðäîâñè Àõóí-îãëû,
äîêòîð ôèç.-ìàò. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû, Êèåâ, e-mail: fasharifov@gmail.com.
Ãóëÿíèöêèé Ëåîíèä Ôåäîðîâè÷,
äîêòîð òåõí. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû,
Êèåâ, e-mail: lh_dar@hotmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 4 55
|