Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер



бет5/10
Дата06.12.2022
өлшемі200,54 Kb.
#55348
түріЛекция
1   2   3   4   5   6   7   8   9   10
Байланысты:
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

Сонда
&(¬Үiv¬Үj)=(¬Ү1v¬Ү2)&(¬Ү1v¬Ү3)&(¬Ү1v¬Ү4)&(¬Ү2v¬Ү1)&


а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 бграф төбелерінің ізделінген максимал іштен тұрақты жиыны{υ32},{υ24},{υ1} болады және бұл жерде α(D)=2 .

Бағытталған графтарда сыртқы тұрақтылық .


Айталық D=(V,X) бграф берілген болсын.




Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   10




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет