Нахождение одно-, двух- и трехэлементных разрезов графа

При моделировании структур сложных систем важная роль принадлежит таким комбинаторным конструкциям, как разрезы [1-4]. Если каждому разрезу поставить в соответствие некоторое число, например, количество содержащихся в разрезе элементов, то может быть выделено подмножество разрезов, содержащих минимальное число элементов, т.е. подмножество минимальных разрезов. Важными для практики и интересными для исследования с теоретической точки зрения являются как минимальные разрезы графов, разделяющих две выделенные вершины графа [5, 6], так и разрезы, близкие к минимальным (квазимини-мальные разрезы) [7, 8], в частности, одно-, двух- и трехэлементные разрезы [9, 10].

Являясь по сути промежуточным, этап определения разрезов при моделировании структур остается одним из самых трудоемких, и поэтому предъявляет особо высокие требования к эффективности используемых алгоритмов. В [10] отмечается, что «вся оптимизационная часть, заключающаяся в возможном сокращении времени расчетов, сводится к сокращению количества сочетаний элементов, при исключении которых схема подвергается проверке на связность».

Исследование теоретико-порядковых свойств минимальных разрезов позволило выявить структуру дистрибутивной решетки [11]. Рассмотрение дистрибутивной решетки минимальных разрезов дало принципиально новый подход к задаче перечисления множества минимальных разрезов, результатом чего явилась разработка оригинального эффективного комбинаторного алгоритма поиска минимальных разрезов. Созданный алгоритм явился основой для построения алгоритмов перечисления разрезов, близких к минимальным, в частности, перечисления одно-, двух и трехэлементных разрезов.

1.    Постановка задачи

Пусть Q(V,U) - ориентированный граф, где V = {v} - множество вершин графа, U = {и = (i,j) : i EV, j EV} - множество ориентированных дуг графа.

В графе Q выделим две вершины - источник s и сток t (s,t Е V, s ^ t }. Пусть А,В (АП В = @ ) некоторые подмножества множества вершин. Обозначим

(А, В) = {(i,j) : (i,j} EU,i Е A,j ЕВ} множество ориентированных дуг, ведущих из iEABjEB. Дополнительно предположим, что, во-первых, между любыми двумя вершинами i, j EV имеется не более одной ориентированной дуги (i,j) EU и одной ориентированной дуги (j, i) EU , и, во-вторых, отсутствуют петли (т.е. дуги вида (i,i)     ).

Разрезом [3], разделяющим вершины s,t графа б, называется множество дуг г = (В, R) С U, где RV\ R = $, RU R = V, s Е R, t Е R. Множество всех таких разрезов обозначим посредством R.

Каждому ребру u EU графа б поставим в соответствие неотрицательное число с(и) ^ О, которое назовем весом (пропускной способностью) ребра. Пропускную способность (вес) разреза г ER определим при помощи

c(r)=c(R,R) = У^ с(и).

uE(R,R)

Под одно-, двух- и трехэлементными разрезами графа Q(y,U) будем понимать соответственно разрезы веса один, два и три в случае, когда с(и) = 1 для всех и EU. Такое название оправдано тем, что одноэлементные (двухэлементные, трехэлементные) разрезы состоят из одного (двух, трех) элементов (дуг графа). Множества одно-, двух- и трехэлементных разрезов обозначим Mi, М2, М3 соответственно. Задача заключается в перечислении всех элементов указанных множеств.

2.    Дистрибутивная решетка минимальных разрезов

В множестве разрезов R графа б относительно функции веса с может быть выделено подмножество минимальных разрезов (разрезов минимального веса)

Л4_т1п,с = {т:т = arg minc(r)}.

ген

На множестве Mmin,c определяются бинарные операции V, Л. Для любых т^ = (Мг,Мг) Е Atmin,o * = ^Д) положим mi V m2 = (Mi U М2, Mi U М2), mi /\т,2 = (Mi П М2, Mi П М2).

Множество минимальных разрезов Mmm,c с веденными на нем операциями V, Л является дистрибутивной [12, 13] решеткой  [11].

Минимальный разрез р Е М_Шт,с дистрибутивной решетки называется неприводимым (V-неприводимым) [11], если для любых mi,rn,2 Е Ai min g из соотношения р = mi V m2 вытекает р = mi или р = m2- Обозначим через Р_с = Р = Рм_т^_с множество неприводимых разрезов решетки <.M_mi_n,_c; V, Л >. Очевидно, что Р_с является частично упорядоченным множеством как подмножество частично упорядоченного множества Л4_Шш,_с-

В дистрибутивной решетке множество минимальных разрезов графа может быть аналитически описано [11],

Almin,c ⁼ IJ \J ^ai

ДеЖРА аед где А(РС) ~ множество антицепей А частично упорядоченного множества Рс.

Указанное представление служит основой нового декомпозиционного подхода к перечислению минимальных разрезов графа, состоящего, во-первых, из поиска только неприводимых минимальных разрезов в графе, и, во-вторых, из синтеза всего множества минимальных разрезов по частично упорядоченному подмножеству неприводимых разрезов в дистрибутивной решетке минимальных разрезов. Предлагаемый подход позволяет сократить поиск в графе (число проверок графа на связность) за счет выделения только подмножества неприводимых минимальных разрезов.

Ниже рассматривается построение алгоритма перечисления одно-, двух- и трехэлементных минимальных разрезов графа.

3.    Алгоритм поиска к-элементных разрезов графа

Рассмотрим алгоритм

KCUT{g(V,UY s, t; S; к-, Мк; Ri, Rz,... Rk)

перечисления множества fc-элементных (к = 1,2,3 ) реберных разрезов М_к, разделяющих вершины з и t (з, t Е V , s ^ t ) ориентированного графа g(V, И) и минимальных относительно функции веса cg(u) (с$(и) = оо, если и Е S, с$(и) = 1, если и € U\S ).

Входные данные: g(V, W) ; s, t; S ; к . Множество S QU есть подмножество дуг графа, на вхождение которых в разрезы наложен запрет; к - число элементов (дуг графа) в разрезе.

Выходные данные: М_к ; R^, R^, • • • , R_k- Множество М_к содержит /с-элементные разрезы графа G(y, U) между вершинами s л t, минимальные относительно функции веса cs(u). Если таких разрезов не существует, то М_к = 0. R^, R^, • • • > R_k ~ вспомогательные множества.

Промежуточные переменные: М; f(u), c(f)-, cs(u), S(u), и EU;P ^ P1UP2U.. .UP_k. M - множество помеченных вершин в методе пометок Форда - Фалкерсона [5, 6]; / - поток из з в t в форме узлы-дуги [6]; с(/) - величина потока / ; cs(u) - вес (пропускная способность) ребра; д(и) - текущее значение пропускной способности ребра w,P = P1UP2U.. .UP_k С М_к - представление частично упорядоченного множества неприводимых минимальных разрезов Р в виде объединения линейно упорядоченных множеств Pi , г = 1, 2, к.

Алгоритм поиска одноэлементных минимальных реберных разрезов KCUT(g(V,U)',8,t',9;l’,Mi',R{). Множество минимальных одноэлементных разрезов Mi может трактоваться как множество разрезов минимального веса (веса один), разделяющих вершины з и t во взвешенном графе g(V,U) с заданной функцией веса с(и) = 1 = с^(и) для всех и € U.

Шаг 1. Положить Mi := 0, Я} := 0. Для всех и EU положить ё(и) = с$(и), f(u) := 0.

Шаг 2. Применить метод пометок [5, 6]. Если t £ М, то искомых разрезов не существует. Return. Иначе увеличить величину потока на единицу.

Шаг 3. Применить метод пометок [5, 6]. Если t € М, то Return. Иначе получаем одноэлементный разрез m = (М,М).

Шаг 4- Запомнить одноэлементный разрез Mi := Mi U m. Для e = (M,M) положить Де) := оо, Д := Д} U е. Перейти к шагу 3.

В данном случае Mi = Р, и свойство дистрибутивности не используется. Предложенный алгоритм выделения множества одноэлементных разрезов ориентированного графа g = (УД) имеет временную сложность О(\Ы\).

Алгоритм поиска двухэлементных минимальных реберных разрезов KCUT(g(y,U)\s,t',$',‘2',M2',Ri,R%)- Множество минимальных двухэлементных разрезов М2 может трактоваться как множество разрезов минимального веса (веса два), разделяющих вершины з и t во взвешенном графе g(V,U) с заданной функцией веса с(и) = 1 = с^(и) для всех и £ U при отсутствии разрезов веса один (одноэлементных разрезов). Дистрибутивность решетки множества минимальных двухэлементных разрезов есть частный случай дистрибутивности решетки множества минимальных разрезов взвешенного графа, разделяющих вершины з и t.

Шаг 1. Положить Л1г := 0- Для всех и Е U положить 6(и) = с$(и), f(u) := 0. Pi = Р₂ := 0, Ri = R₂ := 0. Построить максимальный поток / (получить максимальный поток в форме узлы-дуги) [6] . Если c(f) 7^ 2, то Return.

Шаг 2. Произвести цепное разложение потока / (получить максимальный поток в форме дуги-цепи) [5] и получить две цепи С_г = (Аг, £_г), i = 1,2, на каждой из которых поток равен единице (с(С_г) = 1)-

Шаг 3. Применить метод пометок [5,6]. Если t Е М, то перейти к шагу 5. Иначе получаем двухэлементный разрез т = (М,М).

Шаг 4- Запомнить двухэлементный разрез (включая порядок, т.е. последовательность получения разрезов) Pi := PiUm. Для е = mQ£i положить 6(e) := 00, R^ := RjUe. Перейти к шагу 3.

Шаг 5. Для всех е Е Ri положить 6(e) := cg(e).

Шаг 6. Применить метод пометок [5,6]. Если t Е М, то перейти к шагу 8. Иначе получаем двухэлементный разрез т = (М,М).

Шаг 7. Запомнить двухэлементный разрез (включая порядок, т.е. последовательность получения разрезов) Р2 := P₂Um. Для е — тГ\£₂ положить 6(e) := 00, R^ := R^Ue. Перейти к шагу 6.

На этапе выделения множества неприводимых трехэлементных разрезов построены линейно упорядоченные множества

R$ = {ai < а₂< ... < а_т} С 5i, R2 = {bi < Ь₂< ... < b_n} С £₂.

Здесь 1,2,...,тп; 1,2,..., п - порядковый номер соответствующего элемента в соответствующей цепи (порядковый номер получения элемента цепи на шагах 3-4 (множество R^ ) и 6-7 (множество R^ ) алгоритма). Аналогично линейный порядок может быть рассмотрен и в множествах

Р1 = {Р1 <Й < •■• <  Рт}, Р2 = {91 < 92 < • • • < 9п}.

Цепи Pi и Р2, в свою очередь, определяют частичный порядок в частично упорядоченном множестве V, т.к. для множества V число Дилуорса d(P) = 2. Таким образом, на шагах 3-7 алгоритма получена информация не только о составе множества Р, но и о частичном порядке в множестве Р.

Пусть < .М2; V,A > - дистрибутивная решетка; R^ х R^ — {(a,b) : а Е R^.b Е R^} декартово произведение цепей Ri,R2-, Р = Pi UP2 С Al 2 С R^ х R^; для всех г, s Е Ri х R^ бинарные операции V, Л задаются rVs = (га,гь) V (sa,sb) = (sup{re,sa},sup{rb,s6}), г Л s = (ra, гь) Л (sa, sb) = (inf{ra, sa}, inf{rft, s6});

а отношение порядка описывается

Множество Р есть подмножество V-неприводимых элементов решетки М₂, причем Pi = Q1 нулевой элемент решетки М₂. Нахождение множества .М2 заключается в синтезе множества минимальных разрезов (подмножества М₂\Р ) по частично упорядоченному подмножеству неприводимых минимальных разрезов Р в дистрибутивной решетке множества минимальных разрезов < АЛ2; V, Л >. Использование такого подхода позволяет найти множество .М2 по частично упорядоченному множеству Р без использования графа Q.

Алгоритм синтеза двухэлементных разрезов по подмножеству неприводимых элементов.

Шаг 8. М₂ := Р, i := 1.

Шаг 9. Выберем pi = (ai,0i) EPi-

Шаг 10. Для fit найдем порядковый номер j элемента q₃ = (а₃,0₃) € Р2 такого, что — 0г-

Шаг И. Если ai ^ а₃, то идти к шагу 15.

Шаг 12. Получить новый элемент решетки s = piV qj = (04,0₃) = (з_а,зь)- Запомнить полученный элемент .М2 “ Л<2 U s.

Шаг 13. j := j + 1.

Шаг 14- Если j ^ п, то идти к шагу 11.

Шаг 15. i := i + 1.

Шаг 16. Если i ^т, то идти к шагу 9.

Шаг 17. Return.

Предложенный алгоритм выделения множества неприводимых двухэлементных разрезов ориентированного графа Q = (V,U) имеет временную сложность О(\11\). При синтезе множества трехэлементных разрезов сложность алгоритма О(|Я2|). Таким образом, получена линейная оценка сложности O(max{|W|, I.M2I}) для алгоритма определения множества минимальных двухэлементных разрезов Мч графа Q = (У, И).

Алгоритм поиска трехэлементных минимальных реберных разрезов KCUT(Q(V,U);s,t-,^-,3-,M3‘,Rl,R^,Rl). Множество минимальных трехэлементных разрезов Л1з может трактоваться как множество разрезов минимального веса (веса три), разделяющих вершины s и t во взвешенном графе Q(y,U) с заданной функцией веса с(и) = 1 = с® (и) для всех и Ell при отсутствии разрезов веса один и два (одно- и двухэлементных разрезов). Дистрибутивность решетки множества минимальных трехэлементных разрезов есть частный случай дистрибутивности решетки множества минимальных разрезов взвешенного графа, разделяющих вершины s и t.

Шаг 1. Положить Мз := 0. Для всех и Ell положить 6(и) = cs(u), f(u) := 0. Pi =Рч — Рз := 0, Rf = R% = Rf := 0. Построить максимальный поток f (получить максимальный поток в форме узлы-дуги) [6] . Если c(f) ^ 3, то Return.

Шаг 2. Произвести цепное разложение потока / (получить максимальный поток в форме дуги-цепи) [5] и получить три цепи Ci = (Ai, Ci), i = 1,2,3, на каждой из которых поток равен единице (с(С_г) = 1 ).

Шаг 3. Применить метод пометок [5, 6]. Если t Е М, то перейти к шагу 5. Иначе получаем трехэлементный разрез m = (М, М).

Шаг 4- Запомнить трехэлементный разрез (включая порядок, т.е. последовательность получения разрезов) Pi := Pi Um. Для е = тГ\£\ положить 6(e) := 00, R^ := R₃tle. Перейти к шагу 3.

Шаг 5. Для всех е Е R± положить 6(e) := cs(e).

Шаг 6. Применить метод пометок [5,6]. Если t Е М, то перейти к шагу 8. Иначе получаем трехэлементный разрез m = (М, М).

Шаг 7. Запомнить трехэлементный разрез (включая порядок, т.е. последовательность получения разрезов) Р2 := Рч^т. Для е = тГ\£ч положить 6(e) := 00, R^ := R^e. Перейти к шагу 6.

Шаг 8. Для всех е Е R^ положить 6(e) := cs(e).

Шаг 9. Применить метод пометок [5, 6]. Если t Е М, то перейти к шагу 11. Иначе получаем трехэлементный разрез m = (М,М).

Шаг 10. Запомнить трехэлементный разрез (включая порядок, т.е. последовательность получения разрезов) Рз := PsUm. Для е = тГ)£з положить 6(e) := 00, Rf := RfUe. Перейти к шагу 9.

На этапе выделения множества неприводимых трехэлементных разрезов построены ли- нейно упорядоченные множества

Rl = {ai < а₂< ... < a_m} C 5_b R2 = {Ь_г< b₂< ... < Ь_п} С £₂,

R3 = {^С1 < ^с2 < • ■ ■ < ^k} Q ^з-

Здесь 1,2,..., m; 1,2,..., n; 1,2,..., А; - порядковый номер соответствующего элемента в соответствующей цепи (порядковый номер получения элемента цепи на шагах 3-4 (множество R^ ), 6-7 (множество R^ ) и 9-10 (множество Я3 ) алгоритма). Аналогично линейный порядок может быть рассмотрен и в множествах

Pi = {pi <Р2 < ■■■ < Рт}, Р2 = {qi < 42 < ■■■ < 4п},

Рз = {ri < г2 < ... < гк}.

Цепи Pi, Р2 и Рз, в свою очередь, определяют частичный порядок в частично упорядоченном множестве Р, т.к. для множества V число Дилуорса d(P) = 3. Таким образом, на шагах 310 алгоритма получена информация не только о составе множества Р, но и о частичном порядке в множестве Р.

Пусть <  Мз; V, Л > - дистрибутивная решетка;

R^xR^x R^ = {(a, b,c) : а е Rf,b е R%, с € Л3} декартово произведение цепей Rf, R^, Я^;

Р = p!UP₂UP₃CM3QRl* R₂* Аз!

для всех г, s € R^ х R% х R% бинарные операции V, Л задаются

ГУ 8 = (ra,rb,rc) V (sa,sb,sc) = (sup{ra,so},sup{r6,s6},sup{rc,sc}), г Л s = (ra, rb, rc) Л (sa, sb, sc) = (inf{ro, sa}, inf{rb, sj, inf{rc, sc});

а отношение порядка описывается

Множество P есть подмножество V-неприводимых элементов решетки Мз , причем Р1 = 91 = П ^_ нулевой элемент решетки Мз . Нахождение множества Мз заключается в синтезе множества минимальных разрезов (подмножества Мз\Р ) по частично упорядоченному подмножеству неприводимых минимальных разрезов Р в дистрибутивной решетке множества минимальных разрезов <  Мз', V, Л > . Использование такого подхода позволяет найти множество М.3 по частично упорядоченному множеству Р без использования графа

Алгоритм синтеза трехэлементных разрезов по подмножеству неприводимых элементов.

Шаг 11. М3 := Р, i := 1.

Шаг 12. Выберем р^ = (ai,Pi,7i) е Pi-

Шаг 13. Для Д найдем порядковый номер j элемента q₃ = (а₃,fy,^j) 6 Р₂ такого, что Рз ⁼ Pi-

Шаг 1J. Если ai < aj, то идти к шагу 23.

Шаг 15. Получить новый элемент решетки s =р{У 4₃ = (щ, P₃,s_c) = (s_o, s_b, s_c).

Шаг 16. Для s_c найдем порядковый номер I элемента ri = (ai,Pt,7i) € Рз такого, что 71 = 8_С.

Шаг 17. Если s_a< оц или s_b< /3i, то идти к шагу 21.

Шаг 18. Получить новый элемент решетки t = Pi У Qj У ri = (з^зь,^). Запомнить полученный элемент Мз := М3 U t.

Шаг 19. l:=l + l.

Шаг 20. Если I ^ к, то идти к шагу 17.

Шаг 21. j := j + 1.

Шаг 22. Если j ^ п, то идти к шагу 14.

Шаг 23. i := i + 1.

Шаг 2J. Если г ^ т, то идти к шагу 12.

Шаг 25. Return.

Предложенный алгоритм выделения множества неприводимых трехэлементных разрезов ориентированного графа Q = (V,U) имеет временную сложность О(|7/|). При синтезе множества трехэлементных разрезов сложность алгоритма 0({|Л4з|}). Таким образом, получена линейная оценка сложности O(max{|W|, |Л1з|}) для алгоритма определения множества минимальных трехэлементных разрезов Мз графа Q = (VM) [14].

4.    Дистрибутивные решетки подмножеств квазиминимальных разрезов

Пусть S = {и : и Е U} СЦ, причем для любого m € Aiming => mQS ^ 9. Рассмотрим функцию с$ : U R⁺, которую определим следующим образом:

{ оо, если и € S, с(и), если и G U\S.

Построенная функция веса запрещает все минимальные разрезы относительно функции веса с, т.к. по меньшей мере одно ребро указанного разреза имеет вес оо. Для заданных cs множество минимальных разрезов графа Q, обозначим M_mi_Q,_Cs-

Рассмотрим совокупность всевозможных множеств § = {5} для Япцп,с5.

Множество квазиминимальных (следующих за минимальными, ближайших к минимальным) разрезов есть

A4min+i,c = { arg min c(r)}.

Представленное соотношение позволяет рассмотреть множество квазиминимальных разрезов как совокупность дистрибутивных решеток, поскольку для некоторого S* С S

Дшш+1,с = [J -A^min,cs-

SeS*

Иными словами, множество квазиминимальных разрезов (не обладающее свойством дистрибутивной решетки) может быть представлено в виде объединения подмножеств, каждое из которых обладает структурой дистрибутивной решетки.

Соответственно, множество квазиминимальных разрезов допускает представление

■^mm+l,c ⁼ [J [J \j О,

SeS* AeA(Pcs) аеА где A(PCs) есть множество антицепей подмножества неприводимых разрезов PCs С Mmin,cs дистрибутивной решетки .

Полученное соотношение сводит поиск квазиминимальных разрезов к целенаправленному и эффективному поиску минимальных разрезов последовательности графов Q с модифицированной функцией веса cs для совокупности множеств {5} = §* [15].

Ниже рассматриваются вопросы построения множества S* при перечислении квазиминимальных трехэлементных разрезов.

5.    Алгоритм поиска одно-, двух- и трехэлементных разрезов графа

Перечисление указанных разрезов может быть сведено к последовательности задач перечисления минимальных одно-, двух- и трехэлементных разрезов.

Перечисление двухэлементных (трехэлементных) разрезов при существовании одноэлементных разрезов (и отсутствии двухэлементных разрезов). Двухэлементные (трехэлементные) разрезы в данном случае минимальными не являются. Множество дуг графа Q, образующих одноэлементные разрезы, есть R^. Очевидно, что любое такое ребро не может входить в двухэлементный (трехэлементный) разрез. Придавая указанным ребрам разрезов достаточно большие веса (запрещая вхождение соответствующих ребер графа в минимальные разрезы), можно добиться того, что двухэлементные (трехэлементные) разрезы будут минимальными. Т.е.

§* = {Я}},

Л12 Almin+1,с = А/ц-Щ ^min,cs>

(Дз = Дтш+1,с = Дтш,^)'

И нахождение двухэлементных (трехэлементных) разрезов может быть осуществлено на основе

KCUT(G(V,W); s,t; 1?};2; A^; Rl,R^)

(KCUT(g(V,U); s, t; Д]; 3; M\; Rl Rl Rl)).

Перечисление трехэлементных разрезов при существовании двухэлементных и отсутствии одноэлементных разрезов. Трехэлементные разрезы в данном случае минимальными не являются. Трехэлементный разрез может: 1) не содержать дуг двухэлементных разрезов, 2) содержать одну дугу двухэлементного разреза, 3) содержать по одной дуге двух различных двухэлементных разрезов.

Случай 1. Множество дуг графа Q, образующих двухэлементные разрезы, есть R^UR^. Очевидно, что любое такое ребро не может входить в требуемый трехэлементный разрез. И нахождение трехэлементных разрезов может быть осуществлено на основе

KCUT(Q(V,UY s, t; Rl U Rl; 3; Ml; R^ R%, Rf).

Случай 2. При получении двухэлементных разрезов были выделены две цепи Ci = (Ai,£i), С2 = (Л,^) и совокупности дуг Rl С Ei (Rl С £2 ) первой (второй) цепи. Для любого двухэлементного разреза m € М2 справедливо mHRl у^ 0 , mHRl ^ 0 , причем RlCiR^ = 0. Соответственно, множество трехэлементных разрезов Ml (Atg), которые содержат дугу двухэлементного разреза из множества R^ (Rl ), может быть найдено при помощи

KCUT(g(V,и\ з, t; Rl;3; М33; R^ R^, R^

(KCUT(G(V,U);s, t; R^; 3; At^; R^ R^ R^.

Действительно, придание бесконечных весов дугам R^ (Ri запрещает все двухэлементные разрезы, поскольку для любого т € М2 справедливо тП R² ^ 0 (т П R₂ ^ 0 ), однако использование дуг R^ (Ri) при конструировании трехэлементных разрезов возможно.

Случай 3. Будем последовательно перебирать все дуги и € Ri Для конструирования трехэлементных разрезов, которые содержат дугу и Е R² л какую-то из дуг 1^ нужно: 1) запретить вхождение дуг R²\u (они не могут входить в трехэлементный разрез одновременно с дугой it); 2) запретить двухэлементные разрезы, одной из дуг которых является дуга и, при этом разрешив вхождение дуги и, что достигается путем выделения множества дуг

R2^u = {y-y^ Rl (и, у) G М₂}-

Таким образом, запрещение множества

Su = (Rl \u) U Rf позволяет найти все требуемые трехэлементные разрезы с дугой и. Т.е.

§* = {5_U = (R^ \u)UR^^u:ue R^,

•М3 U -Mmin,C5o , где .Мтт,с5ш находится на основе

KCUT(g(V,U); s, t; S_u; 3; M_min,_CSu; Rf, Ri Ri'}.

Следовательно,

S* = {^ U Ri Ri R²₂} (J (Rl \ u) U T^.

uER^

В действительности, чтобы получать неповторяющиеся сечения, достаточно выбрать