Лосев А.К. Теория линейных электрических цепей (1987) (1095414), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Соответственно графы с изъятыми и неизъятыми устранимыми вершинами могут быть названы сжатыми и несжатыми графами. В необходимых случаях далее будем оговаривать, какие графы имеются в виду. Сжатие графов на рис. 2.2?, г, е, э приводит к графам, показанным соответственно на рис. 2.27, д,, ж, и. Сжатый граф, полученный на рис. 2.27, и, персчерчен в более удобном виде на рис. 2.27, к, где для упрощения нумерации ветвь 6 — 7 обозначена одной цифрой 6. При сжатии двух разных графов, изображенных на рис. 2.27, а, б, получается одинаковый граф в виде контура, не содержащего вершин (рис.

2.27, в). Два контура на рис. 2.27, д, полученные при сжатии графа, изображенного на рис. 2.27, г, сохранили общий узел а, поскольку он является неустранимой вершиной в исходном графе (рис. 2.27, г). При этом в графе на рис. 2.27, д образовалось два замкнутых пути, не имеющих других верпшн, кроме узла а, в котором слились концевые вершины каждого из путей. Такие замкнутые пути, содержаи!ие только один узел, называют петлями.

Таким (2.58) Если исходный граф является несвязным, то деревья образуются для каждой несвязной части графа. Совокупность деревьев несвязного графа называют лесок этого графа. формула (2.88) справедлива и для несвязного графа с общим количеством ветвей и„если и, и п„— общее число ветвей и хорд деревьев в лесу. Для каждого графа можно образовать различные деревья (леса).

Например, на рис. 2.28 показаны некоторые деревья графа, изображенного на рис. 2.27, к. При построении дерева графа можно ие удалять хорды, а наращивать ветви дерева. Для е этого надо наметить все узлы графа, расположив их произвольно. Затем, начав с некоторого узла, который называется а а а корнем дерева, следует вставлять ветви графа, идущие к Ряс. 2.2З.

Деревья графа остальным узлам или соединяющие другие узлы графа, не допуская при этом образования контуров. Именно так построены деревья графа иа рнс. 2.28, корнем которых явля- й) ется узел а. Этот процесс построения дерева можно алго- а) Ряс. 2.29. ггеплосаие графи з- ~ззз образом, сжатые графы состоят из узлов, ветвей, контуров и петель, 8. Подграфы. При исследовании структуры цепи может рассматриваться не весь ее граф, а некоторая его часть.

Часть графа, полученную ири изъятии хотя бы одной ветви, называют подграфом этого графа. При удалении некоторых ветвей могут получиться несвязные подграфы. Например, в графе на рис. 2.27, ж изъятие ветвей 7 и 4 — 5 — 5 приводит к двум несвязным подграфам. Поскольку любая ветвь графа входит в состав нескольких контуров, ее изъятие приводит к подграфу с меньшим числом контуров.

Например, при устранении ветви 5 в шестиконтурном графе на рис. 2.27, з — к получается трехконтурный подграф. При удалении же ветви 7 в шестиконтурном графе на рис. 2.27, ж получается двухкантурный подграф. Дальнейшим устранением ветвей в подграфе можно избавиться в нем от всех контуров. Связный подграф, содержащий все узлы графа, но не содержащий ни одного контура, называют деревом этого графа. Оставшиеся при этом ветви, низывают ветвями дерева, а изъятые ветви — связялси (ветвями связи) графа или кордами этого дерева. Хорды дополняют дерево до полного графа. Поэтому число п„ветвей графа связано с числом и, ветвей дерева и количеством его хорд и, простой формулой п„=п,+и„.

ритмизировать. Тогда построение дерева осуществимо с помощью ЭВМ по матрице инциденций графа. Дерево графа с двумя узлами имеет всего одну ветвь. Добавление одного узла позволяет нарастить в дереве также одну ветвь. Поэтому с ростом числа узлов количество ветвей дерева будет оставаться иа единицу меньше этого числа. Таким образом, если граф и его дерево имеют и, узлов, то количество ветвей дерева (2.59) п,=п„т — 1. Если граф является несвязным, то эта формула относится к каждому дереву его леса. Граф с п„несвязными частями имеет и п„деревьев в лесу. Поэтому для такого графа с и, узлами общее количество ветвей деревьев в лесу п,=п„— и„. (2.60) Из формул (2.58) и (2.59) определяют количество хорд для связного графа: п„=п,— и,+1. (2.6!) Из формул (2.58) и (2.60) находят число хорд для несвязного графа: п„=п,— и„+и„. (2.62) 6.

Плоские графы. На рис. 2.27, и, к один и тот же граф изображен в двух видах. В первом виде ветви графа не пересекаются, во втором — пересекаются. Если граф можно перечертить в таком видр, чтобы ветви его не пересекались, то граф называют плоским. Соответствующую ему цепь называют планарной цепью. Схему такой цепи, изображенную с непересекающимися ветвями, называют планарной схемой. Плоским является не каждый граф. Например, граф, изображенный на рис. 2.29, а, является иеплоским, поскольку его невозможно перечертить с непересекающими ветвями.

Этот неплоский граф с десятью ветвями отображает цятиугольннк, показанный на рис. 2.20.. Подобные цепи называются непланарными. Прн шести узлах в графе достаточно девяти ветвей, включенных определенным образом, как на рис. 2.29, б, чтобы граф стал неплоским. По теореме Куратовского любой граф является плоским в том случае, если он не содержит подграфы такого вида, как на рнс. 2.29, В любом плоском графе с непересекающимися ветвями имеется наружный контур, разделяющий всю плоскость на две области — внешнюю и внутреннюю. Например, в графе иа рис. 2.27, и такой наружный контур образован ветвями 2, 4, б — 7. При этом часть контуров плоского графа разбивает внутреннюю область на непсрекрывающиеся ячейки.

На рис. 2.27, и такие внутренние ячейки ограннцеиы контурами 1,2,5, 8,4,5 и 1,5,5 — 7. Внешнюю облас~ь будем рассматривать как еще одну внешнюю неперекрывающуюся ячейку, ограниченную с одной стороны наружным бб контуром, а с другой стороны простирающуюся до бесконечности. Можно условно считать, что эта внешняя ячейка ограничена в бесконечности некоей окружностью бесконечно большого радиуса.

7. Дуализацин графов. Графы можно подвергать различным преобразованиям, например сжатию. Более сложным преобразованием является дуализапия плоского несжатого графа. Для дуализации плоский граф изображают с непересекающимися ветвями. Затем в каждой неперекрывающейся ячейке (включая внешнюю) намечают по одному новому узлу для преобразованного графа.

Например, для графа, изображенного на рис. 2.27, е, такие новые узлы а', б', в', г'. показаны на рис. 2.30, а. Далее каждое ребро исходного графа пересекают новым ребром, соединяя им новые узлы в смежных ячейках, как показано цветными линиями на рис. 2.30, а. При этом образуется новый граф, который перечерчен на рис. 2.30, б в более удобном виде. г Ю) Рис. 2 3!. Ориентирован- ный граф Рис. 2.30. Дуальиые графы Преобразованный граф является также плоским. Все узлы и устранимые вершины исходного графа расположены во внешней и внутренних ячейках нового графа, которые ограничены его образовавшимися новыми контурами.

Это наглядно видно из рис. 2.30, а. Таким образом, дуализация плоских графов является взаимным преобразованием их вершин н контуров. Несжатые плоские графы с одинаковым количеством ребер, в которых вершины одного графа соответствуют контурам другого', называются дуальными графами.

В дуальных графах последовательное соединение ребер в одном графе соответствует параллельному соединению ребер в другом графе, как это видно из рис. 2.30. вт Пепи с дуальными графами также называются дуильными, если они составлены из дуальных элементов. Процессы в дуальных цепях описываются уравнениями одинаковой структуры, в которых все параметры заменены их дуальными значениями, а напряжения и заменены токами !'и наоборот. Дуализации могут подвергаться также сжатые плоские графы. При этом происходит взаимное преобразование узлов и контуров дуальных графов.

8. Ориентированные графы. Ветвям графа можно приписывать определенные направления по аналогии с выбором положительного направления отсчета токов и напряжений. Выбранные направления ветвей отмечают на графе стрелкой. Полученные при этом ветви называюГ ориентированными ветвями, а графы с ориентированными ветвями — ориентированными (направленными) графами. В отличие от них рассмотренные графы с неориентированными ветвями называют неориентированными (ненаправленными) графами.

Например, неориентированный граф, изображенный на рис. 2.27, к, можно превратить в ориентированный граф, как это сделано на рис. 2.31. Тогда вместо матрицы иициденций (2.57) для несжатого неориентированного графа (рис. 2.27, з) получается новая матрица инциденций для сжатого ориентированного графа (рис. 2.31*): 2 ! О (А,) = — ! Π— ! О О 3 4 5 б Π— ! О о ΠΠΠΠ— ! ! О е — ! ! О ! г (2.63) Здесь вследствие сжатия графа столбцы ребер заменены столбцами ветвей, а строки вершин — строками узлов. Кроме того, в этой матрице вследствие ориентации ветвей инцидентным коэффициентам приписаны разные знаки: положительный для ветвей, направленных от итщидентиого узла, и отрицательный для ветвей, направленных в сторону инцидентного узла. Такой выбор знаков инцидеитных коэффициентов соответствует правилу знаков для токов ветвей, оттекающих и притекающих к узлу.

Характеристики

Список файлов книги