АЛГЕБРАИЧЕСКИЙ МЕТОД ОПРЕДЕЛЕНИЯ ПОЛНОГО МНОЖЕСТВА ПРОСТЫХ РАЗРЕЗОВ В ДВУХПОЛЮСНЫХ СЕТЯХ
ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 519.1
В. Т. ТОЗИК
АЛГЕБРАИЧЕСКИЙ МЕТОД ОПРЕДЕЛЕНИЯ ПОЛНОГО МНОЖЕСТВА ПРОСТЫХ РАЗРЕЗОВ В ДВУХПОЛЮСНЫХ СЕТЯХ
Рассматривается задача поиска простых разрезов в двухполюсных структурносложных сетях. В основу предлагаемого метода положена алгебраическая модель сети, базирующаяся на алгебре кубических комплексов. Это позволяет предложить эффективную с точки зрения трудоемкости процедуру определения полного множества простых разрезов.
Ключевые слова: двухполюсная сеть, простой разрез, структурная функция, алгебра кубических комплексов.
Задача определения полного множества простых разрезов в двухполюсных сетях нетри-
виальна. Конструктивный метод ее решения предложен только для плоских графов путем по-
строения полного множества циклов в соответствующих двойственных графах. Однако для
достаточно больших графов с нетривиальной структурой (не сводимой к плоской) задача ста-
новится непреодолимо сложной ввиду комбинаторных трудностей полного перебора.
В основу предлагаемого в настоящей работе метода положена алгебраическая модель
графа, использующая введенную алгебру простых цепей [1] и алгебру кубических комплексов
[2], что позволяет предложить достаточно эффективную с точки зрения трудоемкости проце-
дуру определения простых разрезов.
Как было показано в работе [1], структура двухполюсной сети (α, β) может быть представлена булевой структурной функцией (СФ) в дизъюнктивной нормальной форме (ДНФ) с
помощью простых цепей (элементарных конъюнкций K j ранга r):
m mr
[ ]fαβ
=
V
j=1
K
j
=
V
j =1
Λxi
i=1
,
где m — число простых цепей сети.
(1)
Ту же функцию (1) можно представить в конъюнктивной нормальной форме (КНФ) с
помощью простых разрезов (элементарных дизъюнкций D j ранга s)
fαβ
=
t
Λ
j=1
Di
=
t
Λ
j=1
⎣⎢⎡iV=s1
xi
⎤ ⎥ ⎦
,
(2)
где t — число простых разрезов двухполюсной сети.
В работе [1] представлен алгоритм, позволяющий определить кубическое покрытие
∏ ( L1 ) , соответствующее ДНФ булевой СФ, записанной в виде простых цепей (1). Теперь
рассмотрим выражение (2). С помощью правила де Моргана [2] можно перейти к дизъюнк-
тивной форме отрицания булевой СФ:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 27
t
fαβ
=
V
j=1
D
j
,
(3)
D j = x1v x2v x2v…v xs = x1x2 … xs .
(4)
Отрицанию булевой СФ (3) соответствует покрытие ∏ ( L0 ) множества вершин
n-мерного куба L0 , на которых данная функция принимает нулевые значения, причем каждой
конъюнкции D j ранга s (4) соответствует некоторый куб C j ∈ ∏ ( L0 ) . Целью настоящей ра-
t
боты является создание метода определения полного множества таких кубов ∪ C j , каждый j =1
куб C j которого соответствует конъюнкции D j (4), поставленной в соответствие простому
разрезу. Приведем теоретико-множественное представление этой двойственной задачи: L1 — подмножество состояний связности сети (ƒαβ = 1):
∪ Vm m
L1 ⊆ П(L1)= C j ⇒ ƒ αβ = K j ,
j=1 j=1
Kj — конъюнкция, поставленная в соответствие простой цепи; L0 — подмножество состояний несвязности сети (ƒαβ = 0):
∪ Vt t
L0 ⊆ П(L0)= C j ⇒ f αβ = D j ,
j=1 j=1
D j — конъюнкция, поставленная в соответствие простому разрезу.
Введем некоторые определения, основанные на положениях работы [2].
Определение 1. Куб C = (a1, a2, …, an ) размерности n есть n-мерный вектор, каждая ко-
ордината которого ai принимает значения из множества {0, 1, X} . Координаты ai ∈{0,1} на-
зываются связанными, ai = X — свободными.
Определение 2. Кубы C j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn ) равны между собой
C j = Cs , если ∀i (ai = bi ) .
Определение 3. Кубы С j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn ) находятся в отношении
( )строгого включения C j ⊂ Cs , если ∃i (ai ∈{0,1} & bi = X) и не ∃i ai = X & bi ∈{0,1} v ai = bi .
Определение 4. Кубы C j и Cs находятся в отношении нестрогого включения C j ⊆ Cs ,
если C j = Cs или C j ⊂ Сs .
Определение 5. Множество кубов ∏ и множество вершин Li находятся в отношении нестрогого включения Li ⊆ ∏ , если любая вершина l ∈ Li включена в некоторый куб C ∈ ∏ , т.е. l ⊆ C . В дальнейшем будем говорить, что множество ∏ покрывает множество Li, если Li ⊆ ∏ .
( )Определение 6. Кубы C j и Cs несравнимы C j ~ Cs , если Cj ⊄ Cs и Cs ⊄ Cj.
Ниже дается определение операции объединения, которое отличается от приведенного в работе [2]. Чтобы различать эти две операции, будем обозначать определенную ниже опера-
+
цию символом “∪” .
Определение 7. Результат операции объединения двух кубов С j и Cs определяется как
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
28 В. Т. Тозик
∪C j
+
Cs
=
⎨⎧⎪⎪CC
j, s,
если Cs ⊆ C j ; если C j ⊆ Cs ;
{ }⎪
⎪⎩
Cs ,C j
,
если
C j ~ Cs .
+
Операция объединения ∪ обладает свойством коммутативности и ассоциативности. Резуль-
тат операции объединения двух множеств кубов ∏d и ∏e определяется как множество
+
∪∏ = ∏d ∏e , полученное объединением ∏d и ∏e в обычном теоретико-множественном смысле
с последующим удалением кубов C j таких, что C j ⊆ Cs , или Cs таких, что Cs ⊆ C j ; C j , Cs ∈ ∏ .
Объединение множества ∏ с самим собой приводит к множеству, в котором каждая па-
+
ра кубов несравнима. В дальнейшем, чтобы отобразить это свойство, будем писать: ∏ = ∪∏ .
Определение 8. Результат #-операции двух кубов C j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn )
определяется как
( )⎧C
⎪
j
,
если ∃i ai = bi ;
Сj
# Cs
=
⎪∅, ⎪
если C j
⎨⎪{C1, C2 , …, Ct , …,
⎪
⊆ Cs ;
Ck }, причем
каждой
паре
координат
n
∀(
i=1
ai
,
bi
)
таких,
что
( )⎪⎩ai = X, bi ≠ X, соответствует куб Ct = a1, a2 , …, ai−1,bi , ai+1, …, an−1, a n .
#-операция некоммутативна и неассоциативна. Для множества кубов и одного куба, а также
{ } { }для двух множеств кубов ∏d = C1d , C2d , …, Cmd и ∏e = C1e,C2e, , Cke #-операция опреде-
ляется следующим образом:
{ }∏d #C j = C1d # C j ,C2d #C j , C j , …, Cmd #C j ;
(( (( ) ) ) )∏d #∏e = … ∏d #C1e #C2e #… #Cke .
Определение 9. Максимальным для заданного множества кубов ∏d называется такой куб C j , что C j # ∏d = ∅ , и при замене в C j хотя бы одной связанной координаты на свобод-
ную C j # ∏d ≠ ∅ .
Множество, содержащее все максимальные для ∏d кубы, будем обозначать mах(Пd) Легко показать, что для ∏d множество mах (∏d ) единственное.
Определение 10. Простым кубом C j для булевой СФ называется такой, что
C j ∈ mах (∏ ( L1 )) либо C j ∈ max (∏ ( L0 )) . Иными словами, простым кубом называется такой
куб C j , для которого в ∏ ( L1 ) или ∏ ( L0 ) не существует Cs такой, что C j ⊆ Cs .
В дальнейшем множества простых кубов будем обозначать Z. Можно показать, что
+
∪( I #∏) = mах ( I #∏) ,
(5)
где I — куб размерности n, в котором все компоненты свободные.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 29
Поиск простых разрезов может быть осуществлен в два этапа. Вначале определяется полное множество простых цепей, а затем с помощью введенных выше операций и отношений алгебры кубов определяется полное множество простых разрезов.
В работе [1] было предложено осуществлять решение первой задачи на n-мерном кубическом комплексе S n , это позволило найти покрытие булевой СФ в виде множества кубов
∏ ( L1 ) = {C1,C2 , …, Cm} , соответствующих простым цепям.
Отрицанию булевой СФ (3) соответствует покрытие ∏ ( L0 ) множества вершин n-
мерного куба L0 , на которых данная функция принимает нулевые значения, причем каждой
конъюнкции D j (4) соответствует C j ∈ ∏(L0 ) .
Утверждение 1. Если куб C j ∈ ∏(L0 ) соответствует конъюнкции D j (4), поставленной в
соответствие j-му простому разрезу, то C j ∈ Z (L0 ) , т.е. C j является простым кубом для L0 . Д о к а з а т е л ь с т в о . Каждый простой разрез отличается от другого по крайней мере
одним элементом, поэтому любые две конъюнкции D j и Ds , поставленные в соответствие j-му и s-му простым разрезам, отличаются друг от друга по крайней мере одной буквой.
( )В соответствии с этим кубы C j и Cs несравнимы С j ~ Cs , т.е. C j ⊄ Cs и Cs ⊄ C j для
C j , Cs ∈ ∏(L0 ) . Поскольку в каждую конъюнкцию D j буквы входят только в инверсном виде и в силу того, что простой разрез является минимальным по включению множеством элементов, для любого куба C j ∈ ∏(L0 ) с ценой R j не существует куба Ct ∈ ∏(L0 ) с ценой
Rt ≤ Rt −1 такого, что C j ⊂ Ct . Таким образом, все кубы C j ∈ ∏(L0 ) являются простыми.
Утверждение 2. Множество простых кубов Z (L0 ) является покрытием ∏(L0 ) множества вершин n-мерного куба L0 , каждый куб C j ∈ ∏(L0 ) которого соответствует конъюнк-
ции D j , записанной с помощью простых разрезов.
Д о к а з а т е л ь с т в о . Предположим обратное. Без потери общности можно допустить,
что существует простой куб C j ∈ Z (L0 ) такой, что C j ∉ ∏(L0 ) . В соответствии с утвержде-
нием 1 все кубы C j ∈ ∏(L0 ) являются простыми. Отсюда ∏(L0 ) ⊆ Z ( L0 ) и можно записать
{ }Z ( L0 ) = ∏(L0 ), C j .
(6)
Так как оба множества простых кубов Z (L0 ) и ∏(L0 ) покрывают одно и то же множе-
ство вершин L0 , и только L0 , то
Z (L0 ) ≡ ∏( L0 ) .
(7)
Поскольку множество простых кубов для L0 единственно, то из (6) и (7) следует, что либо
C j ∉ Z (L0 ) , либо C j ∈ ∏(L0 ) . Полученное противоречие доказывает данное утверждение.
На основании вышеизложенного можно предложить алгоритм определения множества
кубов ∏(L0 ) , соответствующих множеству простых разрезов.
Алгоритм
1) определить множество кубов ∏(L1) , соответствующих множеству простых цепей, с
помощью алгоритма, предложенного в [1];
+
2) тогда ∏ ( L0 ) = ∪ ⎡⎣I # ∏ ( L1 )⎦⎤ ;
3) конец.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
30 В. Т. Тозик
Утверждение 3. В результате алгоритма получается множество кубов ∏(L0 ) , соответствующее полному множеству простых разрезов.
Д о к а з а т е л ь с т в о . Для полностью определенной булевой СФ множество простых кубов Z (L0 ) совпадает с множеством максимальных кубов для L0 . Поэтому из (5) следует
+
Z ( L0 ) = ∪ ⎡⎣I # ∏ ( L1 )⎤⎦ , а из утверждения 2 — ∏(L0 ) = Z ( L0 ) . Утверждение доказано.
+
Замечание. Выполнение ∪ -операции можно осуществлять как после заверше-
ния ⎡⎣I # ∏ ( L1 )⎦⎤ , так и после каждого #-вычитания куба C j ∈ П(L1) , проводимого на i-м шаге
алгоритма. В приведенном ниже примере используется вторая модификация выполнения
+
∪ -операции.
Пример. Рассмотрим предложенный метод на примере сети, представленной на рисун-
ке. Применение алгоритма определения полного множества
простых цепей к данной сети разобрано в [1]. Поэтому рассмотрим только работу алгоритма определения полного α
12 5β
множества простых разрезов, считая заданным исходное множество простых цепей и соответствующих им кубов
3
4
∏(L1) . Для упрощения примера предположим существование только реберных разрезов
⎧X X
1
1
X
⎫
C
1 1
∏( L1 )
=
∏1
=
⎪⎪ 1
⎨ ⎪
1
1 X
X X
X 1
X 1
⎪⎪ ⎬ ⎪
C12 C31
,
⎩⎪X 1 1 X 1 ⎭⎪C14
I = (X X X X X).
В соответствии со свойствами #-операции
∏2
=
I
# C11
=
⎧X ⎨⎩X
X X
0 X
X 0
X X
⎫ ⎬ ⎭
C12 C22
,
⎧0
∏3
=
∏2
#
C12
=
⎪⎪X
⎨ ⎪
0
⎪⎩X
X 0 X 0
0 0 X X
X X 0 0
X⎫
X⎪⎪
X
⎬ ⎪
X⎪⎭
C13 C23
C33 C43
⎪⎫ ⎬ ⎭⎪ ⎪⎫ ⎬ ⎪⎭
C12 C22
# C21 # C12
,
⎧0
⎪ ⎪
0
∏4
=
∏3
# C31
=
⎪X ⎪⎨X
X 0 0 0
0 0 0 0
X X 0 X
X ⎫ C14
X
⎪ ⎪
X⎪
= C13 C24 C34
# C31
= ⎫ ⎪⎪ ⎬
C13
0
⎬ ⎪
C44
⎪ ⎪⎭
C23 # C31,
⎪0 X X 0 X⎪
⎪⎩X
0
X
0
X
⎪ ⎭
С54
=
С
3 3
С64 = С43
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 31
⎧ 0 X 0 X X⎫ C15 = C14 ⊇ C24
∪∏5
=
+
∏4
=
⎪⎪X
⎨ ⎪
0
0 X
0 X
X 0
0 ⎪⎪
X
⎬ ⎪
C25 C35
= =
C44 C54
,
⎪⎩X 0 X 0 X⎪⎭ C45 = C64 ⊇ C34
⎧0
⎪ ⎪
X
∏6
=
∏5
# C41
=
⎪ ⎨ ⎪
0 0
X 0 0 X
0 0 X 0
X X 0 0
X⎫
0
⎪ ⎪
X⎪
X⎪⎬
C16 C26 C36 C46
= C15 = С25
⎫
⎪⎪ ⎬
C35
#
C41
,
⎪0
⎪ ⎩
X
X 0
X X
0 0
0⎪ X⎪⎭
С56 С66
⎪ ⎭⎪ =
С45
⎧ 0 X 0 X X⎫C17 = C16 ⊇ C46
∪∏( L0 ) = ∏7
=
+
∏6
=
⎪⎪X
⎨ ⎪
0
0 X
0 X
X 0
0 ⎪⎪
0
⎬ ⎪
C27 C37
= =
C26 C56
.
⎪⎩X 0 X 0 X⎭⎪C47 = C66 ⊇ C36
Покрытие ∏7 представляет собой множество кубов ∏ ( L0 ) , соответствующее полному
множеству простых разрезов: {(1,3), (2,3,5),(1, 4, 5),(2, 4)} .
Оценка трудоемкости метода. Как правило, наиболее эффективными являются алгоритмы с трудоемкостью, степенной относительно размерности задачи. Понятие „степенного“ алгоритма близко к принятому в зарубежной литературе определению „хорошего“ алгоритма. Степенная оценка наглядно поясняется с позиций программирования. Линейную оценку имеют алгоритмы, просматривающие информацию единственный раз. Квадратичная оценка связана с „циклом в цикле“. Дальнейший рост порядка оценки соответствует наличию в алгоритме более длинных цепочек вложенных друг в друга циклов.
Другой класс составляют переборные алгоритмы, связанные с просмотром возможных ситуаций — „кандидатов в ответ“ задачи. Обычно число ситуаций экспоненциально возрастает относительно размерности задачи. Тем самым экспоненциальная (а тем более факториальная) трудоемкость переборного алгоритма растет быстрее, чем любая степенная функция.
В работе [1] доказана теоретическая эффективность алгоритма определения простых цепей. Оценка трудоемкости для него, измеряемая числом ∆ -операций, ниже квадратичной относительно размерности задачи, представляемой числом простых цепей сети.
Трудоемкость алгоритма определения простых разрезов оценим по числу #-операций и
+
операций сравнения кубов при выполнении ∪ -операции. Число простых цепей будем по-
прежнему обозначать буквой m, а число простых разрезов буквой t. Размерность задачи определяется числом простых разрезов в сети.
Число #-операций может быть оценено как произведение числа кубов m в исходном по-
( )крытии ∏(L1) на среднее число кубов в покрытии ∏i при выполнении ∏i #C1j . Среднее
число кубов в ∏i может быть принято равным t, поскольку после выполнения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
32 Г. А. Польте, А. П. Саенко
∪( )+
∏i+1 = ∏i #C1j число кубов в ∏i+1 приблизительно равно t. Таким образом, число
#-операций при выполнении алгоритма приблизительно равно mt .
+
Число попарных операций сравнения при выполнении ∪∏i равно g ( g −1) 2 , где g —
число кубов в ∏i . Приняв поправочный коэффициент, учитывающий превышение числа ку-
( ) ( )+
∪бов в ∏i #C1j над ∏i #C1j , равным в среднем k, можно записать, что число сравнений
при
выполнении
+
∪ -операции
равно
kt (kt −1)
2 ≈ (kt )2
2.
Таким
образом,
общая
трудоем-
кость алгоритма может быть оценена как T ≅ mt + (kt )2 2 , т.е. трудоемкость алгоритма
пропорциональна квадрату размерности задачи. Таким образом, можно сделать вывод об эффективности предложенного метода определения полного множества простых разрезов в двухполюсных сетях. Представление структуры сети в виде кубов кубического комплекса позволяет возможность предложить черезвычайно эффективные методы поиска простых цепей и разрезов, поскольку множества кубов хорошо представляются в памяти компьютера массивами двоичных кодов, а операции над ними — соответствующими программными средствами. Предложенные методы алгоритмически просты и не накладывают никаких ограничений на структуру исследуемых сетей.
СПИСОК ЛИТЕРАТУРЫ
1. Тозик В. Т. Математический аппарат для анализа структурных свойств сетей // Изв. вузов. Приборостроение. 2010. Т. 53, № 12. С. 22—30.
2. Миллер Р. Теория переключательных схем. Т.1. М.: Наука, 1970. 416 с.
Вячеслав Трофимович Тозик
Сведения об авторе — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет информационных технологий, механики и оптики, кафедра инженерной и компьютерной графики; заведующий кафедрой; E-mail: tozik@mail.ifmo.ru
Рекомендована кафедрой инженерной и компьютерной графики
Поступила в редакцию 11. 02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
УДК 519.1
В. Т. ТОЗИК
АЛГЕБРАИЧЕСКИЙ МЕТОД ОПРЕДЕЛЕНИЯ ПОЛНОГО МНОЖЕСТВА ПРОСТЫХ РАЗРЕЗОВ В ДВУХПОЛЮСНЫХ СЕТЯХ
Рассматривается задача поиска простых разрезов в двухполюсных структурносложных сетях. В основу предлагаемого метода положена алгебраическая модель сети, базирующаяся на алгебре кубических комплексов. Это позволяет предложить эффективную с точки зрения трудоемкости процедуру определения полного множества простых разрезов.
Ключевые слова: двухполюсная сеть, простой разрез, структурная функция, алгебра кубических комплексов.
Задача определения полного множества простых разрезов в двухполюсных сетях нетри-
виальна. Конструктивный метод ее решения предложен только для плоских графов путем по-
строения полного множества циклов в соответствующих двойственных графах. Однако для
достаточно больших графов с нетривиальной структурой (не сводимой к плоской) задача ста-
новится непреодолимо сложной ввиду комбинаторных трудностей полного перебора.
В основу предлагаемого в настоящей работе метода положена алгебраическая модель
графа, использующая введенную алгебру простых цепей [1] и алгебру кубических комплексов
[2], что позволяет предложить достаточно эффективную с точки зрения трудоемкости проце-
дуру определения простых разрезов.
Как было показано в работе [1], структура двухполюсной сети (α, β) может быть представлена булевой структурной функцией (СФ) в дизъюнктивной нормальной форме (ДНФ) с
помощью простых цепей (элементарных конъюнкций K j ранга r):
m mr
[ ]fαβ
=
V
j=1
K
j
=
V
j =1
Λxi
i=1
,
где m — число простых цепей сети.
(1)
Ту же функцию (1) можно представить в конъюнктивной нормальной форме (КНФ) с
помощью простых разрезов (элементарных дизъюнкций D j ранга s)
fαβ
=
t
Λ
j=1
Di
=
t
Λ
j=1
⎣⎢⎡iV=s1
xi
⎤ ⎥ ⎦
,
(2)
где t — число простых разрезов двухполюсной сети.
В работе [1] представлен алгоритм, позволяющий определить кубическое покрытие
∏ ( L1 ) , соответствующее ДНФ булевой СФ, записанной в виде простых цепей (1). Теперь
рассмотрим выражение (2). С помощью правила де Моргана [2] можно перейти к дизъюнк-
тивной форме отрицания булевой СФ:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 27
t
fαβ
=
V
j=1
D
j
,
(3)
D j = x1v x2v x2v…v xs = x1x2 … xs .
(4)
Отрицанию булевой СФ (3) соответствует покрытие ∏ ( L0 ) множества вершин
n-мерного куба L0 , на которых данная функция принимает нулевые значения, причем каждой
конъюнкции D j ранга s (4) соответствует некоторый куб C j ∈ ∏ ( L0 ) . Целью настоящей ра-
t
боты является создание метода определения полного множества таких кубов ∪ C j , каждый j =1
куб C j которого соответствует конъюнкции D j (4), поставленной в соответствие простому
разрезу. Приведем теоретико-множественное представление этой двойственной задачи: L1 — подмножество состояний связности сети (ƒαβ = 1):
∪ Vm m
L1 ⊆ П(L1)= C j ⇒ ƒ αβ = K j ,
j=1 j=1
Kj — конъюнкция, поставленная в соответствие простой цепи; L0 — подмножество состояний несвязности сети (ƒαβ = 0):
∪ Vt t
L0 ⊆ П(L0)= C j ⇒ f αβ = D j ,
j=1 j=1
D j — конъюнкция, поставленная в соответствие простому разрезу.
Введем некоторые определения, основанные на положениях работы [2].
Определение 1. Куб C = (a1, a2, …, an ) размерности n есть n-мерный вектор, каждая ко-
ордината которого ai принимает значения из множества {0, 1, X} . Координаты ai ∈{0,1} на-
зываются связанными, ai = X — свободными.
Определение 2. Кубы C j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn ) равны между собой
C j = Cs , если ∀i (ai = bi ) .
Определение 3. Кубы С j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn ) находятся в отношении
( )строгого включения C j ⊂ Cs , если ∃i (ai ∈{0,1} & bi = X) и не ∃i ai = X & bi ∈{0,1} v ai = bi .
Определение 4. Кубы C j и Cs находятся в отношении нестрогого включения C j ⊆ Cs ,
если C j = Cs или C j ⊂ Сs .
Определение 5. Множество кубов ∏ и множество вершин Li находятся в отношении нестрогого включения Li ⊆ ∏ , если любая вершина l ∈ Li включена в некоторый куб C ∈ ∏ , т.е. l ⊆ C . В дальнейшем будем говорить, что множество ∏ покрывает множество Li, если Li ⊆ ∏ .
( )Определение 6. Кубы C j и Cs несравнимы C j ~ Cs , если Cj ⊄ Cs и Cs ⊄ Cj.
Ниже дается определение операции объединения, которое отличается от приведенного в работе [2]. Чтобы различать эти две операции, будем обозначать определенную ниже опера-
+
цию символом “∪” .
Определение 7. Результат операции объединения двух кубов С j и Cs определяется как
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
28 В. Т. Тозик
∪C j
+
Cs
=
⎨⎧⎪⎪CC
j, s,
если Cs ⊆ C j ; если C j ⊆ Cs ;
{ }⎪
⎪⎩
Cs ,C j
,
если
C j ~ Cs .
+
Операция объединения ∪ обладает свойством коммутативности и ассоциативности. Резуль-
тат операции объединения двух множеств кубов ∏d и ∏e определяется как множество
+
∪∏ = ∏d ∏e , полученное объединением ∏d и ∏e в обычном теоретико-множественном смысле
с последующим удалением кубов C j таких, что C j ⊆ Cs , или Cs таких, что Cs ⊆ C j ; C j , Cs ∈ ∏ .
Объединение множества ∏ с самим собой приводит к множеству, в котором каждая па-
+
ра кубов несравнима. В дальнейшем, чтобы отобразить это свойство, будем писать: ∏ = ∪∏ .
Определение 8. Результат #-операции двух кубов C j = (a1, a2, …, an ) и Cs = (b1, b2, …, bn )
определяется как
( )⎧C
⎪
j
,
если ∃i ai = bi ;
Сj
# Cs
=
⎪∅, ⎪
если C j
⎨⎪{C1, C2 , …, Ct , …,
⎪
⊆ Cs ;
Ck }, причем
каждой
паре
координат
n
∀(
i=1
ai
,
bi
)
таких,
что
( )⎪⎩ai = X, bi ≠ X, соответствует куб Ct = a1, a2 , …, ai−1,bi , ai+1, …, an−1, a n .
#-операция некоммутативна и неассоциативна. Для множества кубов и одного куба, а также
{ } { }для двух множеств кубов ∏d = C1d , C2d , …, Cmd и ∏e = C1e,C2e, , Cke #-операция опреде-
ляется следующим образом:
{ }∏d #C j = C1d # C j ,C2d #C j , C j , …, Cmd #C j ;
(( (( ) ) ) )∏d #∏e = … ∏d #C1e #C2e #… #Cke .
Определение 9. Максимальным для заданного множества кубов ∏d называется такой куб C j , что C j # ∏d = ∅ , и при замене в C j хотя бы одной связанной координаты на свобод-
ную C j # ∏d ≠ ∅ .
Множество, содержащее все максимальные для ∏d кубы, будем обозначать mах(Пd) Легко показать, что для ∏d множество mах (∏d ) единственное.
Определение 10. Простым кубом C j для булевой СФ называется такой, что
C j ∈ mах (∏ ( L1 )) либо C j ∈ max (∏ ( L0 )) . Иными словами, простым кубом называется такой
куб C j , для которого в ∏ ( L1 ) или ∏ ( L0 ) не существует Cs такой, что C j ⊆ Cs .
В дальнейшем множества простых кубов будем обозначать Z. Можно показать, что
+
∪( I #∏) = mах ( I #∏) ,
(5)
где I — куб размерности n, в котором все компоненты свободные.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 29
Поиск простых разрезов может быть осуществлен в два этапа. Вначале определяется полное множество простых цепей, а затем с помощью введенных выше операций и отношений алгебры кубов определяется полное множество простых разрезов.
В работе [1] было предложено осуществлять решение первой задачи на n-мерном кубическом комплексе S n , это позволило найти покрытие булевой СФ в виде множества кубов
∏ ( L1 ) = {C1,C2 , …, Cm} , соответствующих простым цепям.
Отрицанию булевой СФ (3) соответствует покрытие ∏ ( L0 ) множества вершин n-
мерного куба L0 , на которых данная функция принимает нулевые значения, причем каждой
конъюнкции D j (4) соответствует C j ∈ ∏(L0 ) .
Утверждение 1. Если куб C j ∈ ∏(L0 ) соответствует конъюнкции D j (4), поставленной в
соответствие j-му простому разрезу, то C j ∈ Z (L0 ) , т.е. C j является простым кубом для L0 . Д о к а з а т е л ь с т в о . Каждый простой разрез отличается от другого по крайней мере
одним элементом, поэтому любые две конъюнкции D j и Ds , поставленные в соответствие j-му и s-му простым разрезам, отличаются друг от друга по крайней мере одной буквой.
( )В соответствии с этим кубы C j и Cs несравнимы С j ~ Cs , т.е. C j ⊄ Cs и Cs ⊄ C j для
C j , Cs ∈ ∏(L0 ) . Поскольку в каждую конъюнкцию D j буквы входят только в инверсном виде и в силу того, что простой разрез является минимальным по включению множеством элементов, для любого куба C j ∈ ∏(L0 ) с ценой R j не существует куба Ct ∈ ∏(L0 ) с ценой
Rt ≤ Rt −1 такого, что C j ⊂ Ct . Таким образом, все кубы C j ∈ ∏(L0 ) являются простыми.
Утверждение 2. Множество простых кубов Z (L0 ) является покрытием ∏(L0 ) множества вершин n-мерного куба L0 , каждый куб C j ∈ ∏(L0 ) которого соответствует конъюнк-
ции D j , записанной с помощью простых разрезов.
Д о к а з а т е л ь с т в о . Предположим обратное. Без потери общности можно допустить,
что существует простой куб C j ∈ Z (L0 ) такой, что C j ∉ ∏(L0 ) . В соответствии с утвержде-
нием 1 все кубы C j ∈ ∏(L0 ) являются простыми. Отсюда ∏(L0 ) ⊆ Z ( L0 ) и можно записать
{ }Z ( L0 ) = ∏(L0 ), C j .
(6)
Так как оба множества простых кубов Z (L0 ) и ∏(L0 ) покрывают одно и то же множе-
ство вершин L0 , и только L0 , то
Z (L0 ) ≡ ∏( L0 ) .
(7)
Поскольку множество простых кубов для L0 единственно, то из (6) и (7) следует, что либо
C j ∉ Z (L0 ) , либо C j ∈ ∏(L0 ) . Полученное противоречие доказывает данное утверждение.
На основании вышеизложенного можно предложить алгоритм определения множества
кубов ∏(L0 ) , соответствующих множеству простых разрезов.
Алгоритм
1) определить множество кубов ∏(L1) , соответствующих множеству простых цепей, с
помощью алгоритма, предложенного в [1];
+
2) тогда ∏ ( L0 ) = ∪ ⎡⎣I # ∏ ( L1 )⎦⎤ ;
3) конец.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
30 В. Т. Тозик
Утверждение 3. В результате алгоритма получается множество кубов ∏(L0 ) , соответствующее полному множеству простых разрезов.
Д о к а з а т е л ь с т в о . Для полностью определенной булевой СФ множество простых кубов Z (L0 ) совпадает с множеством максимальных кубов для L0 . Поэтому из (5) следует
+
Z ( L0 ) = ∪ ⎡⎣I # ∏ ( L1 )⎤⎦ , а из утверждения 2 — ∏(L0 ) = Z ( L0 ) . Утверждение доказано.
+
Замечание. Выполнение ∪ -операции можно осуществлять как после заверше-
ния ⎡⎣I # ∏ ( L1 )⎦⎤ , так и после каждого #-вычитания куба C j ∈ П(L1) , проводимого на i-м шаге
алгоритма. В приведенном ниже примере используется вторая модификация выполнения
+
∪ -операции.
Пример. Рассмотрим предложенный метод на примере сети, представленной на рисун-
ке. Применение алгоритма определения полного множества
простых цепей к данной сети разобрано в [1]. Поэтому рассмотрим только работу алгоритма определения полного α
12 5β
множества простых разрезов, считая заданным исходное множество простых цепей и соответствующих им кубов
3
4
∏(L1) . Для упрощения примера предположим существование только реберных разрезов
⎧X X
1
1
X
⎫
C
1 1
∏( L1 )
=
∏1
=
⎪⎪ 1
⎨ ⎪
1
1 X
X X
X 1
X 1
⎪⎪ ⎬ ⎪
C12 C31
,
⎩⎪X 1 1 X 1 ⎭⎪C14
I = (X X X X X).
В соответствии со свойствами #-операции
∏2
=
I
# C11
=
⎧X ⎨⎩X
X X
0 X
X 0
X X
⎫ ⎬ ⎭
C12 C22
,
⎧0
∏3
=
∏2
#
C12
=
⎪⎪X
⎨ ⎪
0
⎪⎩X
X 0 X 0
0 0 X X
X X 0 0
X⎫
X⎪⎪
X
⎬ ⎪
X⎪⎭
C13 C23
C33 C43
⎪⎫ ⎬ ⎭⎪ ⎪⎫ ⎬ ⎪⎭
C12 C22
# C21 # C12
,
⎧0
⎪ ⎪
0
∏4
=
∏3
# C31
=
⎪X ⎪⎨X
X 0 0 0
0 0 0 0
X X 0 X
X ⎫ C14
X
⎪ ⎪
X⎪
= C13 C24 C34
# C31
= ⎫ ⎪⎪ ⎬
C13
0
⎬ ⎪
C44
⎪ ⎪⎭
C23 # C31,
⎪0 X X 0 X⎪
⎪⎩X
0
X
0
X
⎪ ⎭
С54
=
С
3 3
С64 = С43
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Алгебраический метод определения полного множества простых разрезов в двухполюсных сетях 31
⎧ 0 X 0 X X⎫ C15 = C14 ⊇ C24
∪∏5
=
+
∏4
=
⎪⎪X
⎨ ⎪
0
0 X
0 X
X 0
0 ⎪⎪
X
⎬ ⎪
C25 C35
= =
C44 C54
,
⎪⎩X 0 X 0 X⎪⎭ C45 = C64 ⊇ C34
⎧0
⎪ ⎪
X
∏6
=
∏5
# C41
=
⎪ ⎨ ⎪
0 0
X 0 0 X
0 0 X 0
X X 0 0
X⎫
0
⎪ ⎪
X⎪
X⎪⎬
C16 C26 C36 C46
= C15 = С25
⎫
⎪⎪ ⎬
C35
#
C41
,
⎪0
⎪ ⎩
X
X 0
X X
0 0
0⎪ X⎪⎭
С56 С66
⎪ ⎭⎪ =
С45
⎧ 0 X 0 X X⎫C17 = C16 ⊇ C46
∪∏( L0 ) = ∏7
=
+
∏6
=
⎪⎪X
⎨ ⎪
0
0 X
0 X
X 0
0 ⎪⎪
0
⎬ ⎪
C27 C37
= =
C26 C56
.
⎪⎩X 0 X 0 X⎭⎪C47 = C66 ⊇ C36
Покрытие ∏7 представляет собой множество кубов ∏ ( L0 ) , соответствующее полному
множеству простых разрезов: {(1,3), (2,3,5),(1, 4, 5),(2, 4)} .
Оценка трудоемкости метода. Как правило, наиболее эффективными являются алгоритмы с трудоемкостью, степенной относительно размерности задачи. Понятие „степенного“ алгоритма близко к принятому в зарубежной литературе определению „хорошего“ алгоритма. Степенная оценка наглядно поясняется с позиций программирования. Линейную оценку имеют алгоритмы, просматривающие информацию единственный раз. Квадратичная оценка связана с „циклом в цикле“. Дальнейший рост порядка оценки соответствует наличию в алгоритме более длинных цепочек вложенных друг в друга циклов.
Другой класс составляют переборные алгоритмы, связанные с просмотром возможных ситуаций — „кандидатов в ответ“ задачи. Обычно число ситуаций экспоненциально возрастает относительно размерности задачи. Тем самым экспоненциальная (а тем более факториальная) трудоемкость переборного алгоритма растет быстрее, чем любая степенная функция.
В работе [1] доказана теоретическая эффективность алгоритма определения простых цепей. Оценка трудоемкости для него, измеряемая числом ∆ -операций, ниже квадратичной относительно размерности задачи, представляемой числом простых цепей сети.
Трудоемкость алгоритма определения простых разрезов оценим по числу #-операций и
+
операций сравнения кубов при выполнении ∪ -операции. Число простых цепей будем по-
прежнему обозначать буквой m, а число простых разрезов буквой t. Размерность задачи определяется числом простых разрезов в сети.
Число #-операций может быть оценено как произведение числа кубов m в исходном по-
( )крытии ∏(L1) на среднее число кубов в покрытии ∏i при выполнении ∏i #C1j . Среднее
число кубов в ∏i может быть принято равным t, поскольку после выполнения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
32 Г. А. Польте, А. П. Саенко
∪( )+
∏i+1 = ∏i #C1j число кубов в ∏i+1 приблизительно равно t. Таким образом, число
#-операций при выполнении алгоритма приблизительно равно mt .
+
Число попарных операций сравнения при выполнении ∪∏i равно g ( g −1) 2 , где g —
число кубов в ∏i . Приняв поправочный коэффициент, учитывающий превышение числа ку-
( ) ( )+
∪бов в ∏i #C1j над ∏i #C1j , равным в среднем k, можно записать, что число сравнений
при
выполнении
+
∪ -операции
равно
kt (kt −1)
2 ≈ (kt )2
2.
Таким
образом,
общая
трудоем-
кость алгоритма может быть оценена как T ≅ mt + (kt )2 2 , т.е. трудоемкость алгоритма
пропорциональна квадрату размерности задачи. Таким образом, можно сделать вывод об эффективности предложенного метода определения полного множества простых разрезов в двухполюсных сетях. Представление структуры сети в виде кубов кубического комплекса позволяет возможность предложить черезвычайно эффективные методы поиска простых цепей и разрезов, поскольку множества кубов хорошо представляются в памяти компьютера массивами двоичных кодов, а операции над ними — соответствующими программными средствами. Предложенные методы алгоритмически просты и не накладывают никаких ограничений на структуру исследуемых сетей.
СПИСОК ЛИТЕРАТУРЫ
1. Тозик В. Т. Математический аппарат для анализа структурных свойств сетей // Изв. вузов. Приборостроение. 2010. Т. 53, № 12. С. 22—30.
2. Миллер Р. Теория переключательных схем. Т.1. М.: Наука, 1970. 416 с.
Вячеслав Трофимович Тозик
Сведения об авторе — канд. техн. наук, доцент; Санкт-Петербургский государственный уни-
верситет информационных технологий, механики и оптики, кафедра инженерной и компьютерной графики; заведующий кафедрой; E-mail: tozik@mail.ifmo.ru
Рекомендована кафедрой инженерной и компьютерной графики
Поступила в редакцию 11. 02.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3