Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
жүктеу/скачать 200,54 Kb.
|
14-лекция
| 51-тұжырым: UÎ V жиынның іштен тұрақты болуы үшін <ε1,…,εn> бағалар (41) шартты қанағаттандырғанда (45) теңдеудің орындалуы қажет және жеткілікті.
Магу әдісі . D бграф төбелерінің максимал іштен тұрақты жиынын табу үшін төмендегідей амалдар орындалады: 1) F логикалық формуланы & және v үшін дистрибутивтік заңдар негізінде д.қ.ф.да бейнелейміз; 2) Осы д.қ.ф. да төмендегі теңдіктер негізінде мүмкін болғанша қысқарту амалдарын орындаймыз: Av(A&B)=A, AvA=A, A&A=A, (46) ABvA¬B=A, (AvB)&(AvC)&…&(AvD)=AV(B&C&…&D), бұл жерде A,B,C,…,D-логикалық алгебраның кез келген формуласы. 3) Табылған д.қ.ф. дағы әр бір ┐Үi1&┐Үi2&…&┐Үik мүшеге максимал іштен тұрақты V \ {υi1, υi2,…,υik} жиынды сәйкес қоямыз. Сонда –{j1,…,jl}={1,2,…,n}\{i1,…,ik}, k+l=n, U={υj1, υj2,…,υjl}. Сонымен Магу әдісі арқылы табылған кез келген жиын D бграф төбелерінің максимал іштен тұрақты жиыны болады және ол барлық максимал іштен тұрақты жиынды бейнелейді. Мысал-37. Магу әдісін қолданып, 39-сызбада бейнеленген D бграф төбелерінің максимал іштен тұрақты жиынын анықтаймыз. Осы сызбаға сәйкес іргелестік матрицасын жазамыз. 0 1 1 1 υ1 υ2 A(D)= 1 0 0 0 1 0 0 0 39-сызба 0 0 1 0 υ3 υ4 Сонда
аij=1 (¬Ү3v¬Ү1)&(¬Ү4v¬Ү3) = (¬Ү1v¬Ү2)(¬Ү1v¬Ү3)(¬Ү1v¬Ү4)(¬Ү4v¬Ү3) = (¬Ү1v¬Ү2 ¬Ү3 ¬Ү4)(¬Ү4v¬Ү3) = ¬Ү1¬Ү4v¬Ү1¬Ү3v¬Ү2 ¬Ү3 ¬Ү4 ¬Ү4 v ¬Ү2 ¬Ү3 ¬Ү4 ¬Ү3= ¬Ү1 ¬Ү4v¬Ү1 ¬Ү3v¬Ү2 ¬Ү3 ¬Ү4 . Сонымен әрі қарай (46) теңдіктер арқылы қысқартуға мүмкін болмаған д.қ.ф. құрастырылады. Демек D бграф төбелерінің ізделінген максимал іштен тұрақты жиыны{υ3,υ2},{υ2,υ4},{υ1} болады және бұл жерде α(D)=2 . Бағытталған графтарда сыртқы тұрақтылық . Айталық D=(V,X) бграф берілген болсын. жүктеу/скачать 200,54 Kb. Достарыңызбен бөлісу:
|