Направленные и ненаправленные графы
Аналогично к выходному узлу должна подходить только одна ветвь (отходящих от него ветвей не должно быть). Это можно сделать, введя в граф дополнительные узлы и ветви, передачи которых равны единице. В графе на рис. П1.1, б дополнительными узлами являются узлы 1 и 5. Между входным узлом 0 и дополнительным узлом 1 имеется ветвь с передачей 1. На рис. П1.1, б дополнительный узел 5 соединен… Читать ещё >
Направленные и ненаправленные графы (реферат, курсовая, диплом, контрольная)
Характеристика двух направлений в теории графов
Обобщенно граф — это совокупность узлов и соединяющих их ветвей. Каждый граф характеризуется своей топологией, т. е. информацией о том, какими ветвями и с какой проводимостью (с какой передачей и в каком направлении) связаны друг с другом узлы графа.
Теория графов — это учение об общих топографических свойствах графов и о методах их расчета. Теория графов развивалась в двух направлениях: первое — матрично-топологическое, второе — чисто топологическое. Основные положения матрично-топологического направления были рассмотрены в гл. 2 (см. параграфы 2.31—2.37). Основные положения чисто топологического направления рассмотрены в данном приложении, где сначала рассмотрены основные положения теории направленных графов (см. параграфы П1.2—П1.5), затем ненаправленных (см. параграфы П1.6—П1.9).
Основные определения
Направленным, или линейным, графом (графом сигнала, диаграммой прохождения сигнала) называют совокупность узлов и соединяющих их ветвей, стрелки на которых указывают направление передачи сигнала (воздействия) от одного узла к другому.
Узлами в направленных графах обычно являются токи и (или) потенциалы узлов исследуемых электрических цепей, а не узловые точки этих цепей, как это имеет место в ненаправленных графах (см. параграфы П1.6—П1.9).
Каждая ветвь графа характеризуется своей передачей. Под передачей ветви понимают отношение выходной величины к входной. Так, выходная величина х2 ветви (рис. П1.1, а) равна произведению входной величины (входного сигнала) на передачу а: х2 =х1а.
Передача ветви может иметь размерность проводимости, сопротивления или нулевую размерность.
В том или ином узле графа, кроме входного и выходного, в общем случае может сходиться и от него может уходить по нескольку ветвей. На рис. П1.1, б изображен некоторый граф с узлами 0, 1, 2, 3, 4, 5, 6.
Передачи ветвей этого графа обозначены буквами а, Ъ, с,… Направление передач указано стрелками.
Рис.ПТЛ
Под х1 будем понимать узловой сигнал первого узла, под х2 — узловой сигнал второго узла и т. д.
Узловой сигнал /с-узла равен сумме сигналов, приходящих к этому узлу. При составлении узлового сигнала /с-узла выходящие из этого узла сигналы не учитываются; они учитываются при составлении узловых сигналов тех узлов, к которым эти сигналы подходят. Так, узловой сигнал первого узла графа на рис. П1.1, бхг = lr0 + dx4, второго узла — х2 = = bx3 + g’x5, третьего узла — х3= gx1 и т. д.
Узел графа, выражающий собой величину, принятую в изучаемой системе за входную, обычно изображают на чертеже слева, а узел, соответствующий выходной величине, — справа.
Принято изображать граф так, чтобы от входного узла отходила только одна ветвь, а подходящих ко входному узлу ветвей вообще не было.
Аналогично к выходному узлу должна подходить только одна ветвь (отходящих от него ветвей не должно быть). Это можно сделать, введя в граф дополнительные узлы и ветви, передачи которых равны единице. В графе на рис. П1.1, б дополнительными узлами являются узлы 1 и 5. Между входным узлом 0 и дополнительным узлом 1 имеется ветвь с передачей 1. На рис. П1.1, б дополнительный узел 5 соединен с выходным узлом 6 ветвью с передачей, равной единице. Часто узлы, передача между которыми равна единице, обозначают одинаково; например, для схемы на рис. П1.1, б узел 0 можно назвать узлом 1 (тогда на рисунке будет два узла, обозначенных цифрой 1).