11 / 16
Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
53
1
=1
>
=1
>
1
1
=
=
.
( 1)( 1)
( 1)( 1) ( 1)( 1)
p
p
i
i
p
i
i
i
i q
i
i q
p
a a pa
a a
a
p p q
p q
p q q
Согласно первому соотношению из системы
(8)
=1
>
=
,
( 1)
p
i
i
i
i q
pq
a a
c
p q
тогда
1
1
1
=
( ( 1)
).
( 1)( 1)
pq p q
pq
p
c c
c q a
p q
Очевидно, что
1
( 1)
= .
pq
p p
c q a a
Поэтому
1
1
= ( )
0.
pq p q
p q
c c
c
c
A
По-
скольку
( , ) ( )
( ) = max
= ,
tq
tr
t r T
c
c c
A
A
то
1
0.
pq p q
c c
Следовательно,
1
( ) = .
p q
c
c
A
Лемма 4 исключает из системы
(8)
последние два неравенства. Следователь-
но, если
( , ) ( )\ ( )
= max
,
tq
tr
t r T T n
c
c
A
то для значения
tq
c
заведомо имеет место
tq
q
c t a
и, учитывая замечание к лемме 4,
1
>
tq
q
c t a
(если
).
q n
Поэтому, из теоремы 8
и лемм 4 и 5 следует теорема 10 [12].
Теорема 10.
Пусть
,
n
A
где
1
> 0,
a
и
( ) .
A
Тогда
>
( , ) ( )
( ) = max
.
( 1)
i
i
i t
i r
t r T
a a
c
t r
A
A
Определение 7.
Сеть без петель — матрица
( ) =( )
ij
X x
A
— называется
равномерной, если справедливы два условия [12]: 1)
= ,
i
p
a a
= ,
j
q
a a
где
i j
и
p q
= ;
ij
pq
x x
2)
,
i
p
a a
,
j
q
a a
где
i j
и
p q
.
ij
pq
x x
Каждая неотрицательная симметричная матрица
=( ),
ij
X x
1 ,
,
i j n
где
= 0,
ii
x
задает вектор
,
A
для которого
=1
= ,
n
i
ij
j
a x
и
= ( ) ( ).
X X
A A
Будем гово-
рить, что матрица (сеть без петель)
X
задает вектор
.
A
Определение 8.
Cеть без петель (минимаксная) называется наследственно
минимаксной, если каждая ее подсеть без петель и каждая двудольная подсеть,
порожденные своими узлами, есть минимаксные.
Из теоремы 10 следует лемма, в которой заключен алгоритм построения
наследственно минимаксной сети без петель.
Лемма 6.
Пусть
n
A
и
( ) =( ) ( ; ( )),
ij
X x
c
A
A A
причем
( ) = .
kq
c
c
A
Тогда
для пары векторов
( ,
)
A A
и вектора
,
A
где
= ( )( 1),
i
i
a a c q
A
1
,
i k
= ,
i
i
a a
< ,
q i n
( )(
),
i
i
a a c q k
A
< ,
k i q
имеет место
,
,=
( ,
)
,
k n q
A A
q k
A
и
( ,
; ( ))
,
c
A A A
( ; ( )) .
c
A A