А.М. Андреев, Г.П. Можаров
4
и
,
1
,
e
v u
b m
k i
i
где равенство будет только при ,
n
меньшем, чем минимальное число
узлов и ребер, содержащихся в одном из главных разделяющих мно-
жеств размера
.
m i
Следовательно, для всех
m
коэффициенты
,
n
v u
C m
и
,
e
v u
C m
минимизируются на графах, имеющих минимальное число макси-
мально перекрывающихся главных разделяющих множеств размера
m
относительно любой пары узлов
v
и
u
.
Поэтому в качестве мер надежности заданной топологии КС
предлагается использовать следующие выражения:
,
,
,
,
max
,
max
.
n
n
v u
v u
e
e
v u
v u
X m X m
X m X m
Максимально надежной сетью является та, для которой
n
X m
и
e
X m
малы, насколько возможно для всех значений
.
m
Эти меры
не являются достаточно совершенными, поскольку не отражают сте-
пень перекрытия среди главных разделяющих множеств одинакового
размера, но тем не менее очевидно, они лучше тех, что применяются
в данное время.
Для
,
n
X m
e
X m
и
max ,
f
P v u
получены верхние и ниж-
ние границы, основанные на топологических свойствах сети [10, 12].
Для любого графа связностью
d
и диаметром
,
k
если каждый
d
разделяющих путей между любой парой узлов имеет максимальную
длину
,
l k
наиболее ненадежной является КС со следующими ха-
рактеристиками:
1
при
,
0 при
,
d
e
kl
m d
X m
m d
(2)
1
1 1 при
,
0 при
.
d
n
k
l
m d
X m
m d
(3)
Верхние границы для мер
n
X m
и
e
X m
(формулы (2) и (3))
следуют из того, что в худшем случае можно изолировать узлы
v
и
u
