Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
жүктеу/скачать 200,54 Kb.
|
- Бұл бет үшін навигация:
- 52-тұжырым
- Мысал-40
| &[εi v V ( aij& εj )] = 1 (49)
i=1 j=1 теңдеуге эквивалент ( [aij] = A(D) ). Егер әр бір белгіленген і нөмірде барлық jÎ{1,2,…,n} нүктелер aij=1 болатын мәндер жиыны деп қабылдасақ, онда (49) шартты мынадай жазуға болады: n & ( εi v V εj ) = 1 i=1 аij=1 n немесе F(Y1,…,Yn)=& ( Yi v V Yj ) i=1 aij=1 F( ε1,…,εn) = 1. (50) Сонымен біз мынадай тұжырымның ақиқат екендігін көрдік. 52-тұжырым. UÎ V жиын сырттан тұрақты болуы үшін (41) және (50) шарттардың орындалуы қажет және жеткілікті. Магу әдісі. D бграф төбелерінің минимал сырттан тұрақты жиынын табу үшін төмендегідей амалдар орындалады: 1) F логикалық формуланы & және V амалдарына сәйкес дистрибутивтік заңдар негізінде д.қ.ф. ретінде бейнелейміз. 2) Алынған д.қ.ф. ны (46) теңдіктер бойынша қысқарту амалдарын орындаймыз. 3) Табылған д.қ.ф. дағы әр бір мүше Yi1&Yi2&…&Yik үшін сәйкес болған {υi1,…,υik}- минимал сырттан тұрақты жиынды аламыз. Магу әдісі арқылы табылған кез келген жиын D бграф төбелерінің минимал сырттан тұрақты жиыны болады және ол барлық минимал сырттан тұрақты жиындарды бейнелейді. Мысал-40. 37-мысалдағы D бграфтың барлық минимал сырттан тұрақты төбелер жиынын Магу әдісі арқылы анықтаймыз. (50) шарт бойынша: 4 &(Yiv V Yj)=(Y1vY2vY3vY4)&(Y2vY1)&(Y3vY1)&(Y4vY3)= i=1 aij=1 [(46) және (47) теңдіктерді қолданамыз] =(Y2vY1)&(Y3vY1)&(Y4vY3)=(Y1vY2Y3)(Y4vY3)=Y1Y4vY1Y3v Y2Y3Y4 v Y2Y3 Y3 = Y1Y4 v Y1Y3 v Y2Y3 . Сонымен әрі қарай (46) теңдіктер арқылы қысқартуға мүмкін болмаған д.қ.ф. алынады. Демек D бграф төбелерінің ізделінген минимал сырттан тұрақты жиыны {υ1,υ4}, {υ1,υ3}, {υ2, υ3} және β(D)=2. Бағытталған граф ядросы . Айталық D=(V,X) бграф берілген. Егер NÎV жиын бір уақытта іштен және сырттан тұрақты жиын болса, яғни кез келген υÎ N ушін, N∩D(υ) = Ø; кез келген υÎ V \ N ушін, N∩D(υ)≠ Ø шарттар орындалса N жиын D бграфтың ядросы деп айтылады. Бграфта ядро болмауы да, біреу немесе бірнеше болуы да мүмкін. Егер D бграф N ядроға ие болса, онда барлық уақыт β(D) ≤│N│≤ α(D) теңсіздік ақиқат болады. Мысал-41. 40-сызбада бейнеленген бграфты қарастырамыз. Ол ядроға ие емес. Кез келген бір төбелі жиын сырттан тұрақты, ал кез келген екі немесе үш төбелі жиын іштен тұрақты болалмайды. υ2 υ1 υ3 40-cызба
жүктеу/скачать 200,54 Kb. Достарыңызбен бөлісу:
|