Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез



Pdf көрінісі
бет24/131
Дата24.03.2022
өлшемі1,67 Mb.
#28682
1   ...   20   21   22   23   24   25   26   27   ...   131
Байланысты:
1-том, 113-240

     1-анықтама. Айталық  D=(V,X) бграф берілген болсын. Егер кез келген υ U ушін,      
U∩D(υ)= Ø     (40) , яғни D бграфта U дан алынған қандай  
болмасын екі төбені жалғастыратын доғалар болмаса, онда  U V жиын іштен тұрақты     
деп айтылады. 
σ(D)  арқылы  D  бграфтың  барлық  максимал  іштен  тұрақты  төбелер  жиынын 
белгілейміз.  Онда  
                                  α(D)=max | U |  
                                          
Uσ (D)
 
  D бграфтың ішкі тұрақтылық саны деп айтылады. 
 
                Максимал іштен тұрақты жиындар үйірін  табу. 
 
Айталық  D=(V,X)-бграф  берілген  болсын,  бұл  жерде  Х≠Ø,  V={v
1
,…,v
n
}.  Тағыда  D 
бграфтан  алынған  U   жиынды  (U  V)  қарастырамыз  және  υ
i
(i=1,2,…,n)  төбелерге  сәйкес  Y
i
 
бульдік айнымалылар еңгіземіз. 


~ 139 ~ 
 
{Y
1
,Y
2
,…,Y
n
} айнымалылар  тізімінің  бағаларын   <ε
1
, ε
2
,…,ε
n
>  ретінде қарастырамыз, 
бұл жерде     
                          1, егер  υ
i
 U; 
 
 
    
ε
і 
=                                                         ( 1)   
                          0, егер υ

¬ U, i= 1,2,…,n. 
Тағыды (1) шарт кез келген i,j {1,2,…,n} ушін  
                  [υ
i
 U, υ
j
 D(υ
i
)]=>υ

 ¬ U 
орындалуға  эквивалент  екендігін    ескереміз.  Ал  (1)  шарт  бойынша    ол  тағыда        кез 
келген i,j {1,2,…,n} үшін,                  (ε
i
 & a
ij
) → ¬ε
j
=1        ( 2)  
теңдеуге тең болады,  бұл жерде a
ij
-A(D) іргелес матрицаның  (і,j)-ы элементі. 
( 2) теңдеудің сол жағын  дизъюнкцияға  түрлендірсек,кез келген i,j{1,2,…,n} үшін, 
                      ¬а
ij   
v   ¬ε 
i   
v   ¬ε

= 1          ( 3) 
 теңдеуге ие боламыз.( 3) шартты мынадай жазуға болады: 
                         n      n 


Достарыңызбен бөлісу:
1   ...   20   21   22   23   24   25   26   27   ...   131




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет