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

~ 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
   
 
 
    υ
4 
 
  
 
 
Сонда  
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¬Ү
2 
 ¬Ү
3   
¬Ү
4
)( ¬Ү
4
v¬Ү
3
) =  ¬Ү
1
¬Ү
4
v¬Ү
1
¬Ү
3
v¬Ү
2 
¬Ү
3 
¬Ү
4 
¬Ү
4 
v ¬Ү
2 
¬Ү
3 
¬Ү
4 
¬Ү
3
 =     
= ¬Ү
1 
¬Ү
4
v ¬Ү
1 
¬Ү
3
v¬Ү
2 
¬Ү
3 
¬Ү
4
  
Сонымен әрі қарай (6) теңдіктер арқылы қысқартуға мүмкін болмаған д.қ.ф. 
құрастырылады.  Демек D бграф төбелерінің ізделінген 
 максимал іштен тұрақты 
жиыны {υ
1
,υ
2
},{υ
2
,υ
4
},{υ
1
} болады және бұл жерде α(D)=2 . 

жүктеу/скачать 1,67 Mb.

Достарыңызбен бөлісу: