МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ АНАЛИЗА СТРУКТУРНЫХ СВОЙСТВ СЕТЕЙ
22
УДК 519.1
В. Т. ТОЗИК
МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ АНАЛИЗА СТРУКТУРНЫХ СВОЙСТВ СЕТЕЙ
Предложен математический аппарат для анализа свойств сетевых структур. В основу положена модель сети, базирующаяся на алгебре кубических комплексов. Это позволяет предложить эффективную с точки зрения трудоемкости процедуру определения полного множества простых цепей в двухполюсных структурно сложных сетях. Ключевые слова: двухполюсная сеть, простая цепь, структурная функция, алгебра кубических комплексов.
Введение. Задачи структурного анализа сетей возникают во многих приложениях теории графов: это и поиск наикратчайших путей, и построение маршрутов сетевых перевозок с минимальной стоимостью, и анализ надежности информационно-вычислительных сетей, и распределение информационных потоков для последующей многопроцессорной обработки в вычислительных сетях. В основе решения многих вышеперечисленных задач лежат процедуры поиска полного множества простых цепей (и/или разрезов) в двухполюсных сетях. Эти задачи имеют экспоненциально возрастающую трудоемкость решения при использовании методов перебора.
В основу предлагаемого математического аппарата положена алгебраическая модель графа, использующая введенную Ротом алгебру кубических комплексов [1], что позволяет предложить достаточно эффективные с точки зрения трудоемкости процедуры определения простых цепей и разрезов. Представление структуры графа в виде множества кубов позволяет формализовать и автоматизировать процесс поиска простых цепей и разрезов с помощью соответствующих компьютерно-ориентированных алгоритмов, поскольку аппарат кубов эффективно отображается на структуру памяти и систему команд современных компьютеров.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
23
В настоящей работе предлагается конструктивный (алгебраический) метод определения полного множества простых цепей с оценкой трудоемкости лучше квадратичной.
Алгебра простых цепей
Определение 1. Сетью G (V , E ) называется связный граф без петель и кратных ребер [2].
Множество узлов V сети G имеет мощность w узлов, а множество ребер Е сети — мощность z ребер. Множество всех элементов сети G имеет мощность n = w + z . В сети G выделя-
ется пара узлов (α,β) , называемых в дальнейшем полюсами.
Определение 2. Цепь K = (α = v1, e2 , v3, …, er−1, vr = β) , связывающая полюсы (α,β)
сети G, называется простой, если в последовательности узлов и ребер, по которым проходит
( )цепь, все узлы различны [2]. Здесь vi — обозначение i-го узла, es = vi , vg s — обозначение
s-го ребра сети. Определение 3. Простым разрезом D сети G называется минимальное по включению
множество элементов (узлов и ребер), удаление которых из сети делает несвязной пару полю-
сов (α,β) сети [2].
Введем алгебру простых цепей сети G. Пусть задано множество простых цепей
{ }An = (v1, e2 , v3, …, er−1, vr ) сети G размерности n. Дадим на множестве простых цепей An
определение двух операций. Первая является обычным теоретико-множественным объединением простых цепей и обознается символом „ ∪ “, она обладает следующими свойствами:
1) K j ∪ Ks = Ks ∪ K j (коммутативность);
( )2) K j ∪ ( Ks ∪ Kt ) = K j ∪ Ks ∪ Kt (ассоциативность);
3) существует элемент O (пустое множество) такой, что Kj ∪О =О∪Kj = Kj;
( )4) если K j , Ks ∈ An , то K j ∪ Ks ∈ An (замкнутость).
Вторую операцию — умножение простых цепей, обозначенную символом „∆“, — опре-
делим на множестве простых цепей An следующим образом. Пусть K j = (v1, e2 , v3, …, vr ) ,
( ) ( ) ( )Ks = vγ , eγ+1, …, vg — простые цепи K j , Ks ∈ An . Если vr = vγ , ∀i∀µ vi ≠ vµ , причем
i = 1, r −1, µ = γ + 1, g , то по определению 2:
( ) ( ) ( )Kt = v1,e2 , …, vr ∆ vγ , eγ+1, …, vg = v1, e2 , …, vr = vγ , eγ+1, …, vg .
В противном случае Kt = ∅ . Можно легко показать, что вновь получаемая цепь Kt = K j ∆ Ks удовлетворяет опреде-
( )лению 2, т.е. является простой цепью Kt ∈ An , а операция ∆-умножения — замкнутой опе-
рацией. Данная операция, позволяющая из двух простых цепей образовывать третью, обладает следующими свойствами:
1) K j ∆ Ks ≠ Ks ∆ K j (некоммутативность);
( )2) K j ∆ ( Ks ∆ Kt ) = K j ∆ Ks ∆ Kt (ассоциативность);
3) K j ∆ ( Ks ∪ Kt ) =K j ∆ Ks ∪ K j ∆ Kt (дистрибутивность);
4) существует единичный элемент 1 (цепь нулевой длины) такой, что K j ∆1 = K j .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
24 В. Т. Тозик
( )5) если K j , Ks ∈ An , то K j ∆ Ks ∈ An (замкнутость).
Разобьем множество простых цепей An на классы простых цепей с фиксированными полюсами:
An
= {(v1, e2 , … ,
er−1, vr
)} =
⎪⎧ ⎨
∪
∪⎡
⎢
h
(η, e2 , v3, …,
er −1 , ρ )⎥⎤ ⎫⎪⎬
=
⎧⎪ ⎨
∪
aηρ
⎪⎫ ⎬
,
⎩⎪η,ρ∈V ⎣⎢i=1
⎥⎦⎪⎭ ⎪⎩η,ρ∈V ⎪⎭
где aηρ ⊆ An , aηρ — подмножество всех простых цепей, начинающихся в узле η и заканчи-
вающихся в узле ρ, h — число простых цепей в aηρ .
Операция ∆-умножения простых цепей с фиксированными полюсами удовлетворяет всем свойствам, сформулированным выше для произвольных простых цепей. Существенным для дальнейшего рассмотрения является то, что aαγ ∆aγβ ⊆ aαβ . Левая часть данного выраже-
ния определяется в соответствии со свойством дистрибутивности операции ∆-умножения, это позволяет любые две простые цепи из заданных классов переводить в один класс.
Теперь покажем, что исходное множество простых цепей с фиксированными полюсами
(η,ρ) , заданное множеством ребер графа G с помощью ( w × w )-матрицы смежности
Aw = aη0ρ , может быть преобразовано посредством применения введенного математическо-
го аппарата в полный класс простых цепей с фиксированными полюсами α и β. Утверждение 1. Если простые цепи из трех классов с фиксированными полюсами aηρ ,
aηγ , aγρ проходят через одни и те же внутренние узлы, а указанные классы полны (т.е. содержат все множество простых цепей с фиксированными полюсами η и ρ, проходящих через
{ }одинаковые внутренние узлы), то aηρ ∪ aηγ ∆ aγρ — полный класс простых цепей с фикси-
рованными полюсами η и ρ , проходящих через то же множество внутренних узлов, а также через узел γ.
Справедливость данного утверждения следует из свойств введенных операций. Пусть
aηkρ — множество простых цепей, соединяющих пару полюсов (η,ρ) , проходящих не более
чем через k внутренних узлов сети. При k = 0 (исходная матрица смежности) aη0ρ состоит из одного элемента — ребра между η и ρ. Тогда в алгебре простых цепей может быть составлена следующая система уравнений при условии γ ≠ α,β :
1) a1ηρ = aη0ρ ∪ aη0γ ∆ aγ0ρ ,
η, ρ = 1, w −1; ⎫ ⎪
2) aη2ρ = a1ηρ ∪ a1ηγ ∆ a1γυ ,
η, ρ = 1, w − 2;⎪ ⎪
.................................................................
⎪
k ) aηkρ = aηkρ−1 ∪ aηkγ−1∆ aγkρ−1,
⎬ η, ρ = 1, w − k; ⎪
.................................................................
⎪ ⎪
w − 2) aηwρ−2 = aαwβ−2 = aαwβ−3 ∪ aαwγ−3∆ aγwβ−3 , η = α, ρ = β.⎪⎭
(1)
Неизвестными в данной системе уравнений являются множества простых цепей aηkρ , k = 1, w − 2 . Таким образом, проблема нахождения всех простых цепей между парой уз-
лов (α,β) в сети G сводится к проблеме решения системы уравнений (1). Для ее решения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
25
предлагается использовать метод последовательного удаления γ-узлов из сети G ( γ ≠ α,β) ,
аналогичный методу Гаусса, заключающемуся в последовательном исключении неизвестных из системы линейных уравнений.
Утверждение 2. В результате последовательного решения системы уравнений (1) полу-
чим полный класс простых цепей между парой узлов (α,β) графа G.
Справедливость этого утверждения доказывается с помощью индуктивного вывода для предложенного метода последовательного удаления внутренних узлов, начиная с k = 0 (исходная матрица смежности) и заканчивая k = w − 2 внутренних узлов, относительно к полюсов α, β.
Можно видеть, что разработанный математический аппарат позволяет решить задачу
определения полного множества простых цепей между выделенной парой узлов (α,β) . Те-
перь необходимо подобрать такую форму представления простых цепей, чтобы введенные операции („ ∪ “ и „∆“) легко отображались на структуру памяти и систему команд современ-
ных компьютеров для повышения эффективности процесса поиска простых цепей в графе. Булевы функции и алгебра кубов. Структура двухполюсной сети может быть описана
с помощью аппарата булевых функций следующим образом [3]. Предположим, что двухполюсная сеть может находиться только в двух состояниях: связности (существует по крайней
мере одна простая цепь K j между парой (α,β) полюсов сети) или разреза (не существует ни
одной простой цепи Kj между парой (α,β) полюсов сети). Состояние сети, таким образом,
может быть представлено булевой функцией
fαβ = f ( x1, x2 , …, xn ) ,
(2)
принимающей значение 1, если сеть находится в состоянии связности, и 0 — если несвязно-
сти (разреза). Здесь xi — булева переменная, обозначающая состояние i-го элемента сети,
причем xi = 1, если i-й элемент находится в состоянии связности (работоспособности);
xi = 0 , если i-й элемент несвязности (отказа).
В терминах теории потоков понятия „связности“ и „несвязности“ соответствуют по-
нятиям „способен пропускать поток“ и „не способен пропускать поток“.
Каждой простой цепи ставится в соответствие конъюнктивный терм ранга r
Kj
=
r
Λ
i=1
xiσi
;
∀i (σi
= 1) ,
(3)
который принимает значение 1, если все элементы цепи находятся в состоянии связности
(работоспособности), и 0 — во всех остальных случаях. При этом в соотношение (3) все пе-
ременные xiσi входят в прямой (не инверсной) форме (σi = 1) . Булева функция (2), в дальнейшем называемая структурной функцией (СФ) сети, может
быть записана в дизъюнктивной нормальной форме (ДНФ) с помощью простых цепей (3):
fαβ
=
m
V
j=1
K
j
=
m
V
j=1
⎡⎢⎣iΛ=r1
xi
⎤ ⎥ ⎦
,
где m — число простых цепей сети.
Число векторов состояний сети
(4)
l = ( x1, x2 , …, xn ) ,
(5)
на которых определена булева функция (2), равно 2n . Множество векторов состояний (5), обозначаемое L, разбивается на два непересекающихся подмножества: L1 — подмножество
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
26 В. Т. Тозик
( )состояний связности сети fαβ = 1 и L0 — подмножество состояний несвязности сети
( fαβ = 0) .
Чрезвычайно эффективным математическим аппаратом для представления и преобразования булевых СФ является алгебра кубов [1]. Множеству наборов значений аргументов
функции fαβ (множеству векторов состояний) ставится в соответствие множество L вершин
n-мерного куба такое, что вершинам, относящимся к подмножеству L1, соответствуют набо-
( )ры аргументов, на которых fαβ = 1 , а вершинам, относящимся к подмножеству L0 , соответ-
( )ствуют наборы аргументов, на которых fαβ = 0 .
Определение 4. Куб C = (a1, a2 , …, an ) размерности n есть n-мерный вектор, каждая
координата которого ai принимает значения из множества {0, 1, X}. Координаты ai ∈{0, 1}
называются связанными, ai = X — свободными. Любая дизъюнктивная нормальная форма булевой СФ может быть представлена неко-
торым множеством кубов размерности n, причем каждая конъюнкция соответствует некоторому кубу. Если i-я переменная конъюнкции входит с инверсией (σi = 0) , то i-я координата
куба имеет значение 0, если без инверсии (σi = 1) — 1, а в случае, если i-я переменная отсутствует в конъюнкции, то i-я координата куба является свободной (равна X).
В дальнейшем множество всех кубов (комплекс кубов) размерности n будем обозначать
S n , подмножества комплекса кубов — буквой Π с различными индексами, а кубы — буквой C с различными индексами.
Так как булева СФ является полностью определенной, то для ее задания достаточно од-
ного множества кубов: либо множества единичных кубов ∏ ( L1 ) , являющегося покрытием
единичных наборов L1, либо множества кубов ∏ ( L0 ) , покрывающего нулевые наборы L0 .
Процедура поиска простых цепей. ДНФ булевой СФ может быть поставлено в соот-
ветствие множество кубов ∏ ( L1 ) , покрывающих исходное множество единичных наборов
L1. Так как каждой простой цепи, соединяющей полюсы (α,β) , поставлена в соответствие
( )некоторая конъюнкция ДНФ булевой СФ fαβ , то и каждый куб C j ∈ ∏ L1 соответствует не
только этой конъюнкции, но и простой цепи. Данное соответствие проиллюстрировано на
рис. 1. Таким образом, задача нахождения всех простых цепей между парой узлов (α,β) в
Простая цепь
Конъюнктивный графе G может быть сведена к задаче нахождения
( )терм множества кубов ∏ L1 = {C1, C2 , …, Cm } посред-
ством отображения множества простых цепей An
Куб на n-мерный кубический комплекс S n . Устанавли-
Рис. 1
ваемое отображение является гоморфизмом алгебры
простых цепей на n-мерный кубический комплекс относительно введенных операций, так как для
( )∀K j K j → C j , K j ∈ An , С j ∈ S n , выполняются ∪ ( K1, K2 , …, Km ) → ∪ (C 1 , C2 , …, Cm ) и
∆ ( K, K2 , …, Km ) → ∆ (C1, C 2 , …, Cm ) . Это означает, что операции объединения простых
цепей графа соответствует операция объединения кубов, которая также понимается в теоре-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
27
тико-множественном смысле, а операции ∆-умножения простых цепей графа соответствует
операция ∆-умножения кубов кубического комплекса. Каждой простой цепи графа G с n элементами поставлен в соответствие некоторый куб
комплекса S n размерности n по следующему правилу. Элементам
7
простой цепи (узлам и ребрам) поставлены в соответствие единичные компоненты куба в позициях, номера которых соответствуют номерам элементов простой цепи. Остальные компоненты куба остаются α=6
1
2 5 β=9
свободными. Так, например, простой цепи (6, 1, 7, 2, 9) графа G с 9 элементами (рис. 2) соответствует куб (11XXX11X1), а простой цепи единичной длины, состоящей из ребер 5, соответствует куб (XXXX1XXXX).
34 8
Рис. 2
Определение 5. Результат операции ∆-умножения двух кубов C j = (a1, a2 , ..., an ) и
Cs = (b1, b2 , ..., bn ) определяется как
⎧∅, если ∃i (ai = 0 ∨ bi = 0 ∨ ai = bi = 1);
Cj
∆ Cs
=
⎪⎪(a1 ⎨ ⎪
∆ b1, a2 ∆ b2 , ..., an ∆ bn ) — ai ∆ bi = 1, если одна из
в противном случае, причем координат имеет значение 1,
⎪⎩ ai ∆ bi = X, если ai = bi = X.
Можно видеть, что в результате попарного сравнения i-х компонентов кубов выявление
непростых цепей происходит мгновенно (ai = bi = 1) .
Операции над кубами (объединение и ∆-умножение) обладают теми же свойствами, что и операции над простыми цепями. Так как при поиске простых цепей предполагается, что они представлены в виде кубов, дадим определение исходного задания структуры сети — матрицы смежности в кубическом виде.
Определение 6. Кубической матрицей смежности Aw = aη0ρ сети G (V , E ) с w узлами
называется ( w × w )-матрица, элементами которой являются кубы
aηρ
⎧( a1
⎪ =⎨
= X, …, ai−1 = X, ai = 1, ai+1 = X, …, an = X), если η ≠ ρ и между парой узлов (η,ρ) существует
i-е ребро;
⎪⎩(a1 = 0, a2 = 0, …, an = 0) Z в противном случае.
Предполагается, что i-ориентированное ребро направлено от η к ρ . Если ребро ориен-
тировано от ρ к η, то aηρ = (a1 = 0, a2 = 0, …, an = 0) .
Теперь на основании утверждения 2 можно привести алгоритм нахождения множества
кубов ∏ ( L1 ) , соответствующих простым цепям между выделенной парой узлов (α,β) .
Алгоритм
1) Представить сеть G (V , E ) исходной кубической ( w × w )-матрицей смежности
Aw = aη0ρ . Положить k = 1 .
2) Сформировать кубическую ( w − k ) × ( w − k ) -матрицу Aw-k = aηkρ посредством уда-
ления γ-строки и γ-столбца из матрицы Aw−k+1 . Элементы новой матрицы Aw−k вычисляются следующим образом: если η = ρ , то aηkρ = ∅ , в противном случае
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
28 В. Т. Тозик
aηkρ = aηkρ−1 ∪ aηkγ−1∆ aγkρ−1∆ Cγ ,
(6)
где γ ≠ α,β; Cγ = (a1 = X, a2 = X, ..., aγ−1 = X, aγ = 1, aγ+1 = X, ..., an = X) , γ — удаляемый узел.
3) Если k = w − 2 , т.е. Aw−k — ( 2 × 2 )-матрица, то перейти к п. 4, иначе — положить
k = k + 1 и перейти к п. 2.
4) ∏(L1) = aαwβ−2∆ Cα∆ Cβ , где Сα и Сβ — кубы, в которых соответственно координаты α
и β равны единице, остальные координаты — свободные.
5) Конец.
В случае неориентированных сетей G для любой матрицы Aw−k элементы aηkρ и aρkη
равны, поэтому на шаге 2 достаточно вычислять только один из них, например aηkρ , а второй
aρkη = aηkρ .
Оценка трудоемкости алгоритма. Под оценкой трудоемкости будем понимать верх-
нюю оценку числа „стандартных“ операций алгоритма, асимптотическую относительно раз-
мерности задачи. Размерность задачи определяется числом простых цепей в исходном двух-
полюсном графе G (см. выражение (6)), т.е. числом ∆-операций, необходимых для нахожде-
ния всех простых цепей между выделенной парой узлов в полном графе. (Полным называется
граф, в котором любая пара узлов соединена ребром.)
Определим общее число простых цепей между любой парой полюсов полного графа,
для которого это число является функцией числа узлов w. Все множество простых цепей ра-
зобьем на классы цепей, проходящих через одинаковое число внутренних узлов. Рассмотрим
некоторый подграф полного графа, включающий k внутренних узлов. Для данного подграфа
число простых цепей, проходящих через 0 узлов, равно Yk0 , проходящих через 1 узел — Yk1,
проходящих
через
µ
узлов
—
Ykµ ,
где
Ykµ
—
число
размещений
k по µ :
Ykµ
=
(
k
k!
− µ)!
.
Так
как каждый куб, принадлежащий множеству aηkρ (6), соответствует простой цепи, проходящей не более чем через k внутренних узлов, то число таких кубов (цепей)
∑gk
=
aηk ρ
=
k µ=0
(
k
k −
! µ
)!
.
Общее число простых цепей полного графа между любой парой полюсов
∑g
=
gw−2
=
w−2 µ=0
(w (w−
− 2)! 2 − µ)!
.
(7)
На каждой k -й итерации алгоритма число ∆-операций (см. выражение (6)) может быть определено как
Ik = aηkγ−1 ⋅ aγkρ−1 = gk2−1 .
Общее число ∆-операций алгоритма
{ }w−2
∑ ∑ ∑I = k −1
⎡⎣(w − k )2 − (w − k )⎦⎤ Ik
=
w−2 k =1
⎧
⎨⎪⎪⎩⎣⎡( w
−
k
)2
−
(w
−
k
)⎦⎤
⎡ k −1 ⎢ ⎣⎢µ=0
(
(k
k−
−1)! ⎤2 1 − µ)!⎥⎥⎦
⎫ ⎪ ⎬ ⎭⎪
.
(8)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
29
Численные значения параметров, определяемых выражениями (7) и (8), сведены в таблицу.
wg
I
32
2
45
14
5 16
86
... ...
...
∞
e(w − 2)!
2[e(w − 3)!]2
Рассмотрим асимптотическое поведение функций (7), (8) при w → ∞ :
lim
w→∞
g
=
e(w − 2)!,
а
lim I
w→∞
=
2 ⎣⎡e (w − 3)!⎦⎤2
=
2 ⎛⎝⎜
g ⎞2 w − 2 ⎠⎟
УДК 519.1
В. Т. ТОЗИК
МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ АНАЛИЗА СТРУКТУРНЫХ СВОЙСТВ СЕТЕЙ
Предложен математический аппарат для анализа свойств сетевых структур. В основу положена модель сети, базирующаяся на алгебре кубических комплексов. Это позволяет предложить эффективную с точки зрения трудоемкости процедуру определения полного множества простых цепей в двухполюсных структурно сложных сетях. Ключевые слова: двухполюсная сеть, простая цепь, структурная функция, алгебра кубических комплексов.
Введение. Задачи структурного анализа сетей возникают во многих приложениях теории графов: это и поиск наикратчайших путей, и построение маршрутов сетевых перевозок с минимальной стоимостью, и анализ надежности информационно-вычислительных сетей, и распределение информационных потоков для последующей многопроцессорной обработки в вычислительных сетях. В основе решения многих вышеперечисленных задач лежат процедуры поиска полного множества простых цепей (и/или разрезов) в двухполюсных сетях. Эти задачи имеют экспоненциально возрастающую трудоемкость решения при использовании методов перебора.
В основу предлагаемого математического аппарата положена алгебраическая модель графа, использующая введенную Ротом алгебру кубических комплексов [1], что позволяет предложить достаточно эффективные с точки зрения трудоемкости процедуры определения простых цепей и разрезов. Представление структуры графа в виде множества кубов позволяет формализовать и автоматизировать процесс поиска простых цепей и разрезов с помощью соответствующих компьютерно-ориентированных алгоритмов, поскольку аппарат кубов эффективно отображается на структуру памяти и систему команд современных компьютеров.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
23
В настоящей работе предлагается конструктивный (алгебраический) метод определения полного множества простых цепей с оценкой трудоемкости лучше квадратичной.
Алгебра простых цепей
Определение 1. Сетью G (V , E ) называется связный граф без петель и кратных ребер [2].
Множество узлов V сети G имеет мощность w узлов, а множество ребер Е сети — мощность z ребер. Множество всех элементов сети G имеет мощность n = w + z . В сети G выделя-
ется пара узлов (α,β) , называемых в дальнейшем полюсами.
Определение 2. Цепь K = (α = v1, e2 , v3, …, er−1, vr = β) , связывающая полюсы (α,β)
сети G, называется простой, если в последовательности узлов и ребер, по которым проходит
( )цепь, все узлы различны [2]. Здесь vi — обозначение i-го узла, es = vi , vg s — обозначение
s-го ребра сети. Определение 3. Простым разрезом D сети G называется минимальное по включению
множество элементов (узлов и ребер), удаление которых из сети делает несвязной пару полю-
сов (α,β) сети [2].
Введем алгебру простых цепей сети G. Пусть задано множество простых цепей
{ }An = (v1, e2 , v3, …, er−1, vr ) сети G размерности n. Дадим на множестве простых цепей An
определение двух операций. Первая является обычным теоретико-множественным объединением простых цепей и обознается символом „ ∪ “, она обладает следующими свойствами:
1) K j ∪ Ks = Ks ∪ K j (коммутативность);
( )2) K j ∪ ( Ks ∪ Kt ) = K j ∪ Ks ∪ Kt (ассоциативность);
3) существует элемент O (пустое множество) такой, что Kj ∪О =О∪Kj = Kj;
( )4) если K j , Ks ∈ An , то K j ∪ Ks ∈ An (замкнутость).
Вторую операцию — умножение простых цепей, обозначенную символом „∆“, — опре-
делим на множестве простых цепей An следующим образом. Пусть K j = (v1, e2 , v3, …, vr ) ,
( ) ( ) ( )Ks = vγ , eγ+1, …, vg — простые цепи K j , Ks ∈ An . Если vr = vγ , ∀i∀µ vi ≠ vµ , причем
i = 1, r −1, µ = γ + 1, g , то по определению 2:
( ) ( ) ( )Kt = v1,e2 , …, vr ∆ vγ , eγ+1, …, vg = v1, e2 , …, vr = vγ , eγ+1, …, vg .
В противном случае Kt = ∅ . Можно легко показать, что вновь получаемая цепь Kt = K j ∆ Ks удовлетворяет опреде-
( )лению 2, т.е. является простой цепью Kt ∈ An , а операция ∆-умножения — замкнутой опе-
рацией. Данная операция, позволяющая из двух простых цепей образовывать третью, обладает следующими свойствами:
1) K j ∆ Ks ≠ Ks ∆ K j (некоммутативность);
( )2) K j ∆ ( Ks ∆ Kt ) = K j ∆ Ks ∆ Kt (ассоциативность);
3) K j ∆ ( Ks ∪ Kt ) =K j ∆ Ks ∪ K j ∆ Kt (дистрибутивность);
4) существует единичный элемент 1 (цепь нулевой длины) такой, что K j ∆1 = K j .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
24 В. Т. Тозик
( )5) если K j , Ks ∈ An , то K j ∆ Ks ∈ An (замкнутость).
Разобьем множество простых цепей An на классы простых цепей с фиксированными полюсами:
An
= {(v1, e2 , … ,
er−1, vr
)} =
⎪⎧ ⎨
∪
∪⎡
⎢
h
(η, e2 , v3, …,
er −1 , ρ )⎥⎤ ⎫⎪⎬
=
⎧⎪ ⎨
∪
aηρ
⎪⎫ ⎬
,
⎩⎪η,ρ∈V ⎣⎢i=1
⎥⎦⎪⎭ ⎪⎩η,ρ∈V ⎪⎭
где aηρ ⊆ An , aηρ — подмножество всех простых цепей, начинающихся в узле η и заканчи-
вающихся в узле ρ, h — число простых цепей в aηρ .
Операция ∆-умножения простых цепей с фиксированными полюсами удовлетворяет всем свойствам, сформулированным выше для произвольных простых цепей. Существенным для дальнейшего рассмотрения является то, что aαγ ∆aγβ ⊆ aαβ . Левая часть данного выраже-
ния определяется в соответствии со свойством дистрибутивности операции ∆-умножения, это позволяет любые две простые цепи из заданных классов переводить в один класс.
Теперь покажем, что исходное множество простых цепей с фиксированными полюсами
(η,ρ) , заданное множеством ребер графа G с помощью ( w × w )-матрицы смежности
Aw = aη0ρ , может быть преобразовано посредством применения введенного математическо-
го аппарата в полный класс простых цепей с фиксированными полюсами α и β. Утверждение 1. Если простые цепи из трех классов с фиксированными полюсами aηρ ,
aηγ , aγρ проходят через одни и те же внутренние узлы, а указанные классы полны (т.е. содержат все множество простых цепей с фиксированными полюсами η и ρ, проходящих через
{ }одинаковые внутренние узлы), то aηρ ∪ aηγ ∆ aγρ — полный класс простых цепей с фикси-
рованными полюсами η и ρ , проходящих через то же множество внутренних узлов, а также через узел γ.
Справедливость данного утверждения следует из свойств введенных операций. Пусть
aηkρ — множество простых цепей, соединяющих пару полюсов (η,ρ) , проходящих не более
чем через k внутренних узлов сети. При k = 0 (исходная матрица смежности) aη0ρ состоит из одного элемента — ребра между η и ρ. Тогда в алгебре простых цепей может быть составлена следующая система уравнений при условии γ ≠ α,β :
1) a1ηρ = aη0ρ ∪ aη0γ ∆ aγ0ρ ,
η, ρ = 1, w −1; ⎫ ⎪
2) aη2ρ = a1ηρ ∪ a1ηγ ∆ a1γυ ,
η, ρ = 1, w − 2;⎪ ⎪
.................................................................
⎪
k ) aηkρ = aηkρ−1 ∪ aηkγ−1∆ aγkρ−1,
⎬ η, ρ = 1, w − k; ⎪
.................................................................
⎪ ⎪
w − 2) aηwρ−2 = aαwβ−2 = aαwβ−3 ∪ aαwγ−3∆ aγwβ−3 , η = α, ρ = β.⎪⎭
(1)
Неизвестными в данной системе уравнений являются множества простых цепей aηkρ , k = 1, w − 2 . Таким образом, проблема нахождения всех простых цепей между парой уз-
лов (α,β) в сети G сводится к проблеме решения системы уравнений (1). Для ее решения
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
25
предлагается использовать метод последовательного удаления γ-узлов из сети G ( γ ≠ α,β) ,
аналогичный методу Гаусса, заключающемуся в последовательном исключении неизвестных из системы линейных уравнений.
Утверждение 2. В результате последовательного решения системы уравнений (1) полу-
чим полный класс простых цепей между парой узлов (α,β) графа G.
Справедливость этого утверждения доказывается с помощью индуктивного вывода для предложенного метода последовательного удаления внутренних узлов, начиная с k = 0 (исходная матрица смежности) и заканчивая k = w − 2 внутренних узлов, относительно к полюсов α, β.
Можно видеть, что разработанный математический аппарат позволяет решить задачу
определения полного множества простых цепей между выделенной парой узлов (α,β) . Те-
перь необходимо подобрать такую форму представления простых цепей, чтобы введенные операции („ ∪ “ и „∆“) легко отображались на структуру памяти и систему команд современ-
ных компьютеров для повышения эффективности процесса поиска простых цепей в графе. Булевы функции и алгебра кубов. Структура двухполюсной сети может быть описана
с помощью аппарата булевых функций следующим образом [3]. Предположим, что двухполюсная сеть может находиться только в двух состояниях: связности (существует по крайней
мере одна простая цепь K j между парой (α,β) полюсов сети) или разреза (не существует ни
одной простой цепи Kj между парой (α,β) полюсов сети). Состояние сети, таким образом,
может быть представлено булевой функцией
fαβ = f ( x1, x2 , …, xn ) ,
(2)
принимающей значение 1, если сеть находится в состоянии связности, и 0 — если несвязно-
сти (разреза). Здесь xi — булева переменная, обозначающая состояние i-го элемента сети,
причем xi = 1, если i-й элемент находится в состоянии связности (работоспособности);
xi = 0 , если i-й элемент несвязности (отказа).
В терминах теории потоков понятия „связности“ и „несвязности“ соответствуют по-
нятиям „способен пропускать поток“ и „не способен пропускать поток“.
Каждой простой цепи ставится в соответствие конъюнктивный терм ранга r
Kj
=
r
Λ
i=1
xiσi
;
∀i (σi
= 1) ,
(3)
который принимает значение 1, если все элементы цепи находятся в состоянии связности
(работоспособности), и 0 — во всех остальных случаях. При этом в соотношение (3) все пе-
ременные xiσi входят в прямой (не инверсной) форме (σi = 1) . Булева функция (2), в дальнейшем называемая структурной функцией (СФ) сети, может
быть записана в дизъюнктивной нормальной форме (ДНФ) с помощью простых цепей (3):
fαβ
=
m
V
j=1
K
j
=
m
V
j=1
⎡⎢⎣iΛ=r1
xi
⎤ ⎥ ⎦
,
где m — число простых цепей сети.
Число векторов состояний сети
(4)
l = ( x1, x2 , …, xn ) ,
(5)
на которых определена булева функция (2), равно 2n . Множество векторов состояний (5), обозначаемое L, разбивается на два непересекающихся подмножества: L1 — подмножество
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
26 В. Т. Тозик
( )состояний связности сети fαβ = 1 и L0 — подмножество состояний несвязности сети
( fαβ = 0) .
Чрезвычайно эффективным математическим аппаратом для представления и преобразования булевых СФ является алгебра кубов [1]. Множеству наборов значений аргументов
функции fαβ (множеству векторов состояний) ставится в соответствие множество L вершин
n-мерного куба такое, что вершинам, относящимся к подмножеству L1, соответствуют набо-
( )ры аргументов, на которых fαβ = 1 , а вершинам, относящимся к подмножеству L0 , соответ-
( )ствуют наборы аргументов, на которых fαβ = 0 .
Определение 4. Куб C = (a1, a2 , …, an ) размерности n есть n-мерный вектор, каждая
координата которого ai принимает значения из множества {0, 1, X}. Координаты ai ∈{0, 1}
называются связанными, ai = X — свободными. Любая дизъюнктивная нормальная форма булевой СФ может быть представлена неко-
торым множеством кубов размерности n, причем каждая конъюнкция соответствует некоторому кубу. Если i-я переменная конъюнкции входит с инверсией (σi = 0) , то i-я координата
куба имеет значение 0, если без инверсии (σi = 1) — 1, а в случае, если i-я переменная отсутствует в конъюнкции, то i-я координата куба является свободной (равна X).
В дальнейшем множество всех кубов (комплекс кубов) размерности n будем обозначать
S n , подмножества комплекса кубов — буквой Π с различными индексами, а кубы — буквой C с различными индексами.
Так как булева СФ является полностью определенной, то для ее задания достаточно од-
ного множества кубов: либо множества единичных кубов ∏ ( L1 ) , являющегося покрытием
единичных наборов L1, либо множества кубов ∏ ( L0 ) , покрывающего нулевые наборы L0 .
Процедура поиска простых цепей. ДНФ булевой СФ может быть поставлено в соот-
ветствие множество кубов ∏ ( L1 ) , покрывающих исходное множество единичных наборов
L1. Так как каждой простой цепи, соединяющей полюсы (α,β) , поставлена в соответствие
( )некоторая конъюнкция ДНФ булевой СФ fαβ , то и каждый куб C j ∈ ∏ L1 соответствует не
только этой конъюнкции, но и простой цепи. Данное соответствие проиллюстрировано на
рис. 1. Таким образом, задача нахождения всех простых цепей между парой узлов (α,β) в
Простая цепь
Конъюнктивный графе G может быть сведена к задаче нахождения
( )терм множества кубов ∏ L1 = {C1, C2 , …, Cm } посред-
ством отображения множества простых цепей An
Куб на n-мерный кубический комплекс S n . Устанавли-
Рис. 1
ваемое отображение является гоморфизмом алгебры
простых цепей на n-мерный кубический комплекс относительно введенных операций, так как для
( )∀K j K j → C j , K j ∈ An , С j ∈ S n , выполняются ∪ ( K1, K2 , …, Km ) → ∪ (C 1 , C2 , …, Cm ) и
∆ ( K, K2 , …, Km ) → ∆ (C1, C 2 , …, Cm ) . Это означает, что операции объединения простых
цепей графа соответствует операция объединения кубов, которая также понимается в теоре-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
27
тико-множественном смысле, а операции ∆-умножения простых цепей графа соответствует
операция ∆-умножения кубов кубического комплекса. Каждой простой цепи графа G с n элементами поставлен в соответствие некоторый куб
комплекса S n размерности n по следующему правилу. Элементам
7
простой цепи (узлам и ребрам) поставлены в соответствие единичные компоненты куба в позициях, номера которых соответствуют номерам элементов простой цепи. Остальные компоненты куба остаются α=6
1
2 5 β=9
свободными. Так, например, простой цепи (6, 1, 7, 2, 9) графа G с 9 элементами (рис. 2) соответствует куб (11XXX11X1), а простой цепи единичной длины, состоящей из ребер 5, соответствует куб (XXXX1XXXX).
34 8
Рис. 2
Определение 5. Результат операции ∆-умножения двух кубов C j = (a1, a2 , ..., an ) и
Cs = (b1, b2 , ..., bn ) определяется как
⎧∅, если ∃i (ai = 0 ∨ bi = 0 ∨ ai = bi = 1);
Cj
∆ Cs
=
⎪⎪(a1 ⎨ ⎪
∆ b1, a2 ∆ b2 , ..., an ∆ bn ) — ai ∆ bi = 1, если одна из
в противном случае, причем координат имеет значение 1,
⎪⎩ ai ∆ bi = X, если ai = bi = X.
Можно видеть, что в результате попарного сравнения i-х компонентов кубов выявление
непростых цепей происходит мгновенно (ai = bi = 1) .
Операции над кубами (объединение и ∆-умножение) обладают теми же свойствами, что и операции над простыми цепями. Так как при поиске простых цепей предполагается, что они представлены в виде кубов, дадим определение исходного задания структуры сети — матрицы смежности в кубическом виде.
Определение 6. Кубической матрицей смежности Aw = aη0ρ сети G (V , E ) с w узлами
называется ( w × w )-матрица, элементами которой являются кубы
aηρ
⎧( a1
⎪ =⎨
= X, …, ai−1 = X, ai = 1, ai+1 = X, …, an = X), если η ≠ ρ и между парой узлов (η,ρ) существует
i-е ребро;
⎪⎩(a1 = 0, a2 = 0, …, an = 0) Z в противном случае.
Предполагается, что i-ориентированное ребро направлено от η к ρ . Если ребро ориен-
тировано от ρ к η, то aηρ = (a1 = 0, a2 = 0, …, an = 0) .
Теперь на основании утверждения 2 можно привести алгоритм нахождения множества
кубов ∏ ( L1 ) , соответствующих простым цепям между выделенной парой узлов (α,β) .
Алгоритм
1) Представить сеть G (V , E ) исходной кубической ( w × w )-матрицей смежности
Aw = aη0ρ . Положить k = 1 .
2) Сформировать кубическую ( w − k ) × ( w − k ) -матрицу Aw-k = aηkρ посредством уда-
ления γ-строки и γ-столбца из матрицы Aw−k+1 . Элементы новой матрицы Aw−k вычисляются следующим образом: если η = ρ , то aηkρ = ∅ , в противном случае
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
28 В. Т. Тозик
aηkρ = aηkρ−1 ∪ aηkγ−1∆ aγkρ−1∆ Cγ ,
(6)
где γ ≠ α,β; Cγ = (a1 = X, a2 = X, ..., aγ−1 = X, aγ = 1, aγ+1 = X, ..., an = X) , γ — удаляемый узел.
3) Если k = w − 2 , т.е. Aw−k — ( 2 × 2 )-матрица, то перейти к п. 4, иначе — положить
k = k + 1 и перейти к п. 2.
4) ∏(L1) = aαwβ−2∆ Cα∆ Cβ , где Сα и Сβ — кубы, в которых соответственно координаты α
и β равны единице, остальные координаты — свободные.
5) Конец.
В случае неориентированных сетей G для любой матрицы Aw−k элементы aηkρ и aρkη
равны, поэтому на шаге 2 достаточно вычислять только один из них, например aηkρ , а второй
aρkη = aηkρ .
Оценка трудоемкости алгоритма. Под оценкой трудоемкости будем понимать верх-
нюю оценку числа „стандартных“ операций алгоритма, асимптотическую относительно раз-
мерности задачи. Размерность задачи определяется числом простых цепей в исходном двух-
полюсном графе G (см. выражение (6)), т.е. числом ∆-операций, необходимых для нахожде-
ния всех простых цепей между выделенной парой узлов в полном графе. (Полным называется
граф, в котором любая пара узлов соединена ребром.)
Определим общее число простых цепей между любой парой полюсов полного графа,
для которого это число является функцией числа узлов w. Все множество простых цепей ра-
зобьем на классы цепей, проходящих через одинаковое число внутренних узлов. Рассмотрим
некоторый подграф полного графа, включающий k внутренних узлов. Для данного подграфа
число простых цепей, проходящих через 0 узлов, равно Yk0 , проходящих через 1 узел — Yk1,
проходящих
через
µ
узлов
—
Ykµ ,
где
Ykµ
—
число
размещений
k по µ :
Ykµ
=
(
k
k!
− µ)!
.
Так
как каждый куб, принадлежащий множеству aηkρ (6), соответствует простой цепи, проходящей не более чем через k внутренних узлов, то число таких кубов (цепей)
∑gk
=
aηk ρ
=
k µ=0
(
k
k −
! µ
)!
.
Общее число простых цепей полного графа между любой парой полюсов
∑g
=
gw−2
=
w−2 µ=0
(w (w−
− 2)! 2 − µ)!
.
(7)
На каждой k -й итерации алгоритма число ∆-операций (см. выражение (6)) может быть определено как
Ik = aηkγ−1 ⋅ aγkρ−1 = gk2−1 .
Общее число ∆-операций алгоритма
{ }w−2
∑ ∑ ∑I = k −1
⎡⎣(w − k )2 − (w − k )⎦⎤ Ik
=
w−2 k =1
⎧
⎨⎪⎪⎩⎣⎡( w
−
k
)2
−
(w
−
k
)⎦⎤
⎡ k −1 ⎢ ⎣⎢µ=0
(
(k
k−
−1)! ⎤2 1 − µ)!⎥⎥⎦
⎫ ⎪ ⎬ ⎭⎪
.
(8)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Математический аппарат для анализа структурных свойств сетей
29
Численные значения параметров, определяемых выражениями (7) и (8), сведены в таблицу.
wg
I
32
2
45
14
5 16
86
... ...
...
∞
e(w − 2)!
2[e(w − 3)!]2
Рассмотрим асимптотическое поведение функций (7), (8) при w → ∞ :
lim
w→∞
g
=
e(w − 2)!,
а
lim I
w→∞
=
2 ⎣⎡e (w − 3)!⎦⎤2
=
2 ⎛⎝⎜
g ⎞2 w − 2 ⎠⎟