Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов

10 / 16

П.С. Селин, В.И. Цурков, А.А. Гурченков
52 ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
Согласно первому соотношению из системы (8)
=1 > 1
1 = ,
t
i i
i i q
tq
a a
c tq


  
поэтому справедливо 1 1 1
1 =( ).
( 1) tq tq tq q c c c t a
t q     

Предположим, что 1 < .
tq q c t a  Тогда 1 1
1 < ( )
1 tq tq tq tq c c c c
q    

и
1 ( ) < 0,
1 tq tq
q
c c
q  

что противоречит условию леммы.
Пусть 1 = .
tq q c t a  Тогда 1 ( ) = 0,
1 tq tq
q
c c
q  

что справедливо тогда и только
тогда, когда 1 = .
tq tq c c 
2. Пусть > 2. q Предположим > .
tq q c t a Тогда для разности 1 tq tq c c   получим
=1 > =1 > 1
1 =
( 1) ( 2)
t t
i i i i
i i q i i q
tq tq
a a a a
c c
t q t q


 
 
 
   
=1 >
( 1)
1= =
( 1)( 2)
t
i i q
i i q
a a q a
t q q
   
 
 
1 1
= = ( ) < 0,
2 ( 2)
tq q
q tq
c t a a c t
q t t q
  
 
что противоречит условию леммы.
Пусть = 2 q . Тогда =1t (так как ( , ) ( ) \ ( ) t r T T nA ). Из (1) следует 1
=2
n
i
i
a a 
и 1 2
3
.
n
i
i
a a a

  Теперь очевидно
1
>2
12 2 = .
1 (2 1)
i
i
a a
c a


 

Лемма доказана. ►
Замечание 4. Согласно лемме 4, в системе (8) второй индекс r можно рассматри-
вать только в случае  1 >
r r a a (если  ). r n
Лемма 5. Пусть , n A    где ( )   A и 1 >0. a Если = ( )
pq c c A и 1 = ,
p p a a 
то 1 = ( ).
p q c c
 A
◄ Рассмотрим разность 1 ,
pq p q c c   где > : q p
1
1
=1 > =1 >
= ( 1) ( 1)( 1) =
p p
pq p q i i i i
i i q i i q
c c a a p q a a p q

           
1
=1 > =1 >
( 1) ( 1)
= =
( 1)( 1)
p p
i i i i
i i q i i q
p a p a p a p a
p p q

    
 
   