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


Тұжырым.    U    V  жиын  сырттан  тұрақты    болуы  үшін  (1)  және  (10)  шарттардың  орындалуы қажет және жеткілікті



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

Тұжырым.    U    V  жиын  сырттан  тұрақты    болуы  үшін  (1)  және  (10)  шарттардың 
орындалуы қажет және жеткілікті. 
D  бграф  төбелерінің  минимал  сырттан  тұрақты  жиынын  табу  үшін  төмендегідей 
амалдар орындалады: 


~ 141 ~ 
 
1)  F  логикалық  формуланы  &  және  V  амалдарына  сәйкес  дистрибутивтік  заңдар 
негізінде  д.қ.ф. ретінде бейнелейміз. 
2) Алынған д.қ.ф. ны (6) теңдіктер бойынша қысқарту амалдарын  орындаймыз. 
3) Табылған д.қ.ф. дағы әр бір мүше Yi
1
&Yi
2
&…&Yi
k
 үшін сәйкес болған {υi
1
,…,υi
k
}- 
минимал сырттан тұрақты жиынды аламыз. 
Магу  әдісі  арқылы  табылған  кез  келген  жиын  D  бграф  төбелерінің  минимал  сырттан 
тұрақты жиыны болады және ол барлық минимал сырттан тұрақты жиындарды бейнелейді. 
Мысал ретінде  Магу әдісін қолданып, 1-сызбада  бейнеленген D бграф төбелерінің 
максимал іштен тұрақты жиынын анықтайық. 
Осы сызбаға сәйкес іргелестік матрицасын  жазамыз. 
 
 
 
 
 
 
 
      0 1 1 1  
 
    υ
1                                                   
v
2
   
 
 
 
A(D)=          1 0 0 0    
 
 
 
 
 
 
 
 
 
 
     1 0 0 0  
 
 
 
 
 
 
 
1-сызба 
 
 
 
      0 0 1 0     
                                                     υ
3
   
 
 
    υ

 
  
 
 
Сонда  
aij=1
&(¬Ү
i
v¬Үj) = ( ¬Ү
1
v¬Ү
2
)&( ¬Ү
1
v¬Ү
3
)&( ¬Ү
1
v¬Ү
4
)&( ¬Ү
2
v¬Ү
1
)& 
 (¬Ү
3
v¬Ү
1
)&( ¬Ү
4
v¬Ү
3
)= (¬Ү
1
v¬Ү
2
)( ¬Ү
1
v¬Ү
3
)( ¬Ү
1
v¬Ү
4
)( ¬Ү
4
v¬Ү
3
) =  
= (¬Ү
1
v¬Ү

 ¬Ү
3   
¬Ү
4
)( ¬Ү
4
v¬Ү
3
) =  ¬Ү
1
¬Ү
4
v¬Ү
1
¬Ү
3
v¬Ү

¬Ү

¬Ү

¬Ү

v ¬Ү

¬Ү

¬Ү

¬Ү
3
 =     
= ¬Ү

¬Ү
4
v ¬Ү

¬Ү
3
v¬Ү

¬Ү

¬Ү
4
  
Сонымен әрі қарай (6) теңдіктер арқылы қысқартуға мүмкін болмаған д.қ.ф. 
құрастырылады.  Демек D бграф төбелерінің ізделінген 
 максимал іштен тұрақты 
жиыны {υ
1

2
},{υ
2

4
},{υ
1
} болады және бұл жерде α(D)=2 . 


Достарыңызбен бөлісу:
1   ...   24   25   26   27   28   29   30   31   ...   131




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

    Басты бет