Моделирование надежности компьютерной сети
3
где
,
e
v u
C i
и
,
n
v u
C i
— число комбинаций из
i
ребер (узлов), таких,
что удаление только этих ребер (узлов) из графа нарушает все пути
между узлами
v
и
u
.
Структура надежной компьютерной сети.
Рассмотрим струк-
туру графов, на которых коэффициенты
,
e
v u
C i
и
,
n
v u
C i
минимизи-
руются для всех
i
и всех пар узлов.
Определим главное разделяющее множество узлов (ребер)
m
относительно заданной пары узлов. В связном графе есть множество
таких узлов (ребер), что их удаление нарушает все пути между парой
узлов и нет соответствующего подмножества, которое имеет то же
свойство.
Заметим, что для графа связности
d
имеется по крайней мере
d
узлов или ребер в любом главном разделяющем множестве узлов или
ребер графа [10, 11].
Отсюда
,
,
0
n
e
v u
v u
C i
C i
при
,
,
n
v u
i d C d
и
,
e
v u
C d
равня-
ются числу главных разделяющих множеств узлов и ребер из
d
эле-
ментов относительно любой пары узлов
v
и
u
.
Кроме того, при
m d
коэффициент
,
n
v u
C m
равняется общему
числу разделяющих множеств узлов размера
m
относительно узлов
v
и
u
. Каждое из этих разделяющих множеств состоит из главного раз-
деляющего множества размера
m i
относительно узлов
v
и
u
плюс
дополнительные
i
узлов, выбранные случайно, где
0
.
i m d
Аналогично вычисляется коэффициент
,
.
e
v u
C m
Если обозначить
n
X m
число главных разделяющих множеств узлов размера
m d
и
e
X m
— число главных разделяющих множеств ребер размера
m
относительно пары узлов
v
и
u
, то
,
,
,
,
1
;
m d
n
n
n
n
v u
v u
v u
v u
i
C m X m k i X m i
,
,
,
,
1
,
m d
e
e
e
e
v u
v u
v u
v u
i
C m X m k i X m i
где произведения под знаками суммы являются числами различных раз-
деляющих множеств узлов (ребер) размера ,
m
каждое из которых обра-
зуется присоединением дополнительных
i
узлов к главному разделяю-
щему множеству узлов (ребер) размера
m i
относительно узлов
v
и
u
.
Отметим, что
,
2 1
n
v u
n m
k i
i
