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