Нақты сандар облысында нольдің мынадай қасиеті бар екенін білеміз, ноль мен кез
Бағытталған графтарда сыртқы тұрақтылық
жүктеу/скачать 1,67 Mb. Pdf көрінісі
|
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}:υ j U, υ j D(υ i )) және тағыда (41) шарт бойынша n n жүктеу/скачать 1,67 Mb. Достарыңызбен бөлісу:
|