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


Бағытталған графтарда сыртқы тұрақтылық



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

Бағытталған графтарда сыртқы тұрақтылық  
Айталық D=(V,X) бграф берілген болсын. 
  2-анықтама.   Егер кез келген υ  V \ U үшін, 
                            U ∩ D(υ) ≠ Ø    ( 8)  
 шарт орындалса, яғни U ға тиісті болмаған кез келген  υ V төбе U дан алынған 
доғалар басталуының кемінде бір төбесіне байланысты болса, онда U V жиын сырттан 
тұрақты жиын деп айтылады. 
  3-анықтама.    Егер  U  V  сырттан  тұрақты  жиыннан  кез  келген  бір  төбені  алу 
нәтижесінде  сырттан  тұрақты  болмаған  жиын  құралса,  онда  U  минимал  сырттан  тұрақты 
жиын деп айтылады. 
Көбінесе  практикалық  мәселелерді  шешу  кезінде  сырттан  тұрақты  жиындардың 
төбелері минимал санды болған жиынды табу өте қажет болып есептеледі. Ал олар минимал 
сырттан тұрақты жиын ішінен табылады. 
ψ(D)  арқылы  D  бграфтың  барлық  минимал  сырттан  тұрақты    төбелер  жиынын 
белгілейміз. Онда  
                             β ( D ) = min │ U │   
                                                    
U ψ(D)
  
 сан D бграфтың сырттан тұрақтылық саны деп айтылады. 
                Минимал сырттан тұрақты жиындар үйірін  табу. 
Айталық  V={υ
1
,…,υ
n
}  болған  D=(V,X)  бграф  және  D  дан  алынған  кез  келген  U  V  
төбелер  жиыны берілген болсын. Тағыда алдынғы тақырыпта  қолданылған  Y
1
,…,Y
n
 бульдік 
айнымалыларға сәйкес  <ε
1
,…,ε
n
> бағалар тізімінен пайдаланамыз. 
Бұл жерде сырттан тұрақты U жиынның анықтамасындағы  ( 8) шарт  кез келген  
i {1,2,…,n} үшін кемінде төмендегі  шарттардың біреуіне теңдес екенін  байқаймыз: 
1) 
υ
i
  U 
2) 
U∩D(υ
i
) ≠ Ø (яғни j {1,2,…,n}:υ

 U, υ
j
 D(υ
i
)) 
және тағыда (41) шарт бойынша 
                               
n                  n
 


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




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

    Басты бет