9 / 16
Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
51
> ( ; ( ))
( ; ( )) = ( ) ( ( ; ( )) 1)
= 0.
p
p
i
i
i p
i l
c p
c
c p l
c
a
a
A A
A A A A A
Поэтому
> ( ; ( ))
( ; ( ))
( ) =
=
.
( ( ; ( )) 1)
p
i
i
i p i l
c p
pl
c
p
a
a
c
c
p l
c
A A
A A
A
A A
Из соотношений
( , ) ( )
max
( )
tr
t r T
c
c
A
A
и
( ; ( ))
( ) =
p
pl
c
c A c
A A
следует утверждение
теоремы 8.
►
Определение 6.
Сети без петель (матрицы) из множества
( ; ( ))
c
A A
назы-
ваются минимаксными.
Приведенная ниже теорема характеризует минимаксные матрицы [3–5].
Теорема 9.
Если
n
A
и
( ; ( )) = 0,
p
c
A A
где
,
p
c cp a c
то для
( ) =( ) ( ; ( ))
ij
X x
c
A
A A
имеет место
( ),( , ) {( , ) :
, 1 ,
}
=
{( , ) :1
, < }
ij
p
c A i j
i j i j
i j p
x
i j
i p p j l
{( , ) : < , 1
}; 0,( , )
p
i j p i l
j p i j
{( , ) : < ,
< } {( , ) : < , < } {( , ) : = , < }.
p
p
p
p
i j p i n l
j n i j l
i n p j l
i j i j p i l
Упростим вычисление минимакса
( ).
c
A
Обозначим
( ) = {( , ) : 2
}
T n i i
i n
и
1
1
( ) = {( , ) ( ) : < ; > , = ; > , = }.
i
i
j
j
T A i j T A i j a a i n a a j n
Покажем, что при нахож-
дении минимакса можно удалить последние два неравенства из системы
(8)
и при
вычислении минимакса
( )
c
A
рассматривать только пары индексов из
( ) = ( )
( ).
T T n T
A
A
Для этого докажем две леммы.
Лемма 4.
Пусть
,
n
A
где
( ) ,
A
1
> 0,
a
и
=1
>
=1
>
1<
( , ) ( )\ ( )
max
=
=
.
( 1)
( 1)
t
t
i
i
i
i
i
i q
i
i r
tq
r n
t r T T n
a a
a a
c
t r
t q
A
Тогда 1)
1
tq
q
c t a
(если
<
q n
), причем
1
1
=
= ,
tq
q
tq tq
c t a c c
2)
.
tq
q
c t a
◄
1. Пусть
< .
q n
Для разности
1
tq tq
c c
имеем
=1
>
=1
> 1
1
=
=
( 1)
t
t
i
i
i
i
i
i q
i
i q
tq tq
a a a
a
c c
t q
tq
1
=1
> 1
=1
> 1
1
1
1
=
=
.
( 1)
( 1)
t
t
i
i
q
i
i
i
i q
i
i q
q
a
a qa
a
a
a
t
q q
t q
q