Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез
жүктеу/скачать 1,67 Mb. Pdf көрінісі
|
| 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, егер υ i ¬ U, i= 1,2,…,n. Тағыды (1) шарт кез келген i,j {1,2,…,n} ушін [υ i U, υ j D(υ i )]=>υ j ¬ 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 ¬ε j = 1 ( 3) теңдеуге ие боламыз.( 3) шартты мынадай жазуға болады: n n жүктеу/скачать 1,67 Mb. Достарыңызбен бөлісу:
|