Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
жүктеу/скачать 64,16 Kb.
|
14-лекция
| Мысал-36. 35-мысалда келтірілген U1, U2, U3 жиындардан пайдаланамыз. Бұл жерде U1={υ1} жиын максимал іштен тұрақты жиын болмайды, өйткені U1 жиынға υ3 төбені қоссақ тағыда іштен тұрақты болған U2 жиын аламыз. Бірақта U2, U3 жиындар максимал іштен тұрақты болады.
σ(D) арқылы D бграфтың барлық максимал іштен тұрақты төбелер жиынын белгілейміз. Онда α(D)=max | U | UÎσ (D) D бграфтың ішкі тұрақтылық саны деп айтылады. Максимал іштен тұрақты жиындар үйірін табудың Магу әдісі . Айталық D=(V,X)-бграф берілген болсын, бұл жерде Х≠Ø, V={v1,…,vn}. Тағыда D бграфтан алынған U жиынды (UÎ V) қарастырамыз және υi(i=1,2,…,n) төбелерге сәйкес Yi бульдік айнымалылар еңгіземіз. {Y1,Y2,…,Yn} айнымалылар тізімінің бағаларын <ε1, ε2,…,εn> ретінде қарастырамыз, бұл жерде 1, егер υiÎ U; εі = (41) 0, егер υi ¬Î U, i= 1,2,…,n. Тағыды (40) шарт кез келген i,jÎ {1,2,…,n} ушін [υiÎ U, υjÎ D(υi)]=>υj ¬Î U орындалуға эквивалент екендігін ескереміз. Ал (41) шарт бойынша ол тағыда кез келген i,jÎ {1,2,…,n} үшін, (εi & aij) → ¬εj=1 (42) теңдеуге тең болады, бұл жерде aij-A(D) іргелес матрицаның (і,j)-ы элементі. (42) теңдеудің сол жағын дизъюнкцияға түрлендірсек кез келген i,jÎ{1,2,…,n} үшін, ¬аij v ¬ε i v ¬εj = 1 (43) теңдеуге ие боламыз.(43) шартты мынадай жазуға болады: n n & &(¬аij v ¬εi v ¬εj ) = 1 . (44) i=1 j=1 Осы теңдеуден aij=0 болғанда ¬аijv ¬εiv ¬§j = 1 теңдіктің барлық уақыт орындалуын байқаймыз, ал аij=1 болғанда ¬аij v ¬εi v ¬εj = ¬εi v ¬εj ақиқат. Сондықтан (44) шартты мынадай жазуға болады: & ( ¬εi v ¬εj ) = 1 aij=1 немесе F(Y1,…,Yn) = & ( ¬Үi v ¬Үj), аij=1 F( ε1,…,εn) = 1. (45) Сонымен біз төмендегі тұжырымның ақиқат екендігін көрсеттік. жүктеу/скачать 64,16 Kb. Достарыңызбен бөлісу:
|