ВУЗ:
Составители:
Рубрика:
11
сигнала от причины к следствию. Отсюда общее правило исключения произволь-
ного узла : исключать узел следует так, чтобы после этой операции все состав-
ляющие преобразованного графа во всех оставшихся узлах были такими же, как в
исходном графе . Практически это означает, что переменная исключаемого узла -
выражается через переменные остальных узлов и подставляется в выражения для
тех узлов, которые от нее зависят.
Примеры упрощения графов с использованием правил табл. 1.2, а также
исключения произвольного узла приведены на рис. 1.2. Задачи для самостоятель-
ных упражнений на решение графов методом их упрощения вместе с ответами
приведены в табл. 1.3. Для простоты в рассматриваемых примерах вместо пере-
менных узлов
x
1
, x
2
, x
3
… .
записываются их порядковые номера 1,2,3,… .
1.3. Решение графов. Формула Мэзона
Под решением графа понимают решение системы уравнений , соответст-
вующих графу. Методы решения систем линейных уравнений хорошо известны ,
например, правило Крамера, когда неизвестные выражаются через коэффициенты
и свободные члены , что в переводе на «язык графов» означает, что переменные в
зависимых узлах записываются через передачи ветвей и переменные источников.
Важной особенностью теории графов является возможность нахождения таких
решений непосредственно , без оставления уравнений , причем двумя способами –
упрощением исходного графа до тривиальной формы (рис. 1.1а ) или по формуле
Мэзона, связанной со структурными особенностями графа . Первый способ слабо
формализован, страдает излишней громоздкостью вычислений и может играть
лишь вспомогательную роль.
Формула Мэзона для случая одного источника записывается как
∆
∆
•
==
∑
l
ll,ik
i
k
ki
P
x
x
G , (1.7)
где x
k
– переменная в зависимом узле ;
x
i
–
переменная источника ;
P
ik,l
– передача l-го прямого пути от истока x
i
к выбранному узлу x
k
;
∑
∑
∑
+
−
+
−
=
∆
n,m,j
nmj
m,j
mj
j
j
...*)TTT(*)TT(T1 - определитель графа , в кото -
ром символ (*) означает, что суммируются произведения передач только не -
соприкасающихся контуров («касание» - наличие хотя бы одного общего
узла );
T
j
–
передачи всех контуров графа ;
∆
l
–
алгебраическое дополнение – величина ∆
для части графа , касающейся
l-го прямого пути .
Пример определения передачи графа по формуле (1.7) приведен на рис. 1.3.
11 си г на ла о тпр и чи ны к сле дстви ю . О тсю да о б ще е пр а ви ло и склю че ни я пр о и зво ль- но г о узла : и склю ча ть узе л сле дуе т та к, что б ы по сле это й о пе р а ци и все со ста в- ляю щи е пр е о б р а зо ва нно г о г р а фа во все х о ста вш и х ся узла х б ы ли та ки ми ж е , ка к в и сх о дно м г р а фе . П р а кти че ски это о зна ча е т, что пе р е ме нна я и склю ча е мо г о узла - вы р а ж а е тся че р е з пе р е ме нны е о ста льны х узло в и по дста вляе тся в вы р а ж е ни я для те х узло в, ко то р ы е о тне е за ви сят. П р и ме р ы упр о ще ни я г р а фо в с и спо льзо ва ни е м пр а ви л та б л. 1.2, а та кж е и склю че ни я пр о и зво льно г о узла пр и ве де ны на р и с. 1.2. За да чи для са мо сто яте ль- ны х упр а ж не ни й на р е ш е ни е г р а фо в ме то до м и х упр о ще ни я вме сте с о тве та ми пр и ве де ны в та б л. 1.3. Для пр о сто ты в р а ссма тр и ва е мы х пр и ме р а х вме сто пе р е - ме нны х узло в x1, x2, x3… . за пи сы ва ю тся и х по р ядко вы е но ме р а 1,2,3,… . 1.3. Ре ш е ни е г р а фо в. Ф о р мула М эзо на П о д р е ш е ни е м г р а фа по ни ма ю т р е ш е ни е си сте мы ур а вне ни й , со о тве тст- вую щи х г р а фу. М е то ды р е ш е ни я си сте м ли не й ны х ур а вне ни й х о р о ш о и зве стны , на пр и ме р , пр а ви ло Кр а ме р а , ко г да не и зве стны е вы р а ж а ю тся че р е з ко эффи ци е нты и сво б о дны е чле ны , что в пе р е во де на «язы к г р а фо в» о зна ча е т, что пе р е ме нны е в за ви си мы х узла х за пи сы ва ю тся че р е з пе р е да чи ве тве й и пе р е ме нны е и сто чни ко в. В а ж но й о со б е нно стью те о р и и г р а фо в являе тся во змо ж но сть на х о ж де ни я та ки х р е ш е ни й не по ср е дстве нно , б е з о ста вле ни я ур а вне ни й , пр и че м двумя спо со б а ми – упр о ще ни е м и сх о дно г о г р а фа до тр и ви а льно й фо р мы (р и с. 1.1а ) и ли по фо р муле М эзо на , связа нно й со стр уктур ны ми о со б е нно стями г р а фа . П е р вы й спо со б сла б о фо р ма ли зо ва н, стр а да е т и зли ш не й г р о мо здко стью вы чи сле ни й и мо ж е т и г р а ть ли ш ь вспо мо г а те льную р о ль. Ф о р мула М эзо на для случа я о дно г о и сто чни ка за пи сы ва е тся ка к ∑ Pik , l • ∆ l x G ki = k = l , (1.7) xi ∆ г де xk – пе р е ме нна я в за ви си мо м узле ; xi – пе р е ме нна я и сто чни ка ; Pik,l –пе р е да ча l-г о пр ямо г о пути о ти сто ка xi к вы б р а нно му узлу xk; ∆ = 1 − ∑ T j + ∑ (T jTm ) * − ∑ (T jTm Tn ) * +... - о пр е де ли те ль г р а фа , в ко то - j j, m j, m , n р о м си мво л (*) о зна ча е т, что сумми р ую тся пр о и зве де ни я пе р е да что лько не - со пр и ка са ю щи х ся ко нтур о в («ка са ни е » - на ли чи е х о тя б ы о дно г о о б ще г о узла ); Tj – пе р е да чи все х ко нтур о в г р а фа ; ∆l – а лг е б р а и че ско е до по лне ни е – ве ли чи на ∆ для ча сти г р а фа , ка са ю ще й ся l-г о пр ямо г о пути . П р и ме р о пр е де ле ни я пе р е да чи г р а фа по фо р муле (1.7) пр и ве де н на р и с. 1.3.
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »