Cтраница 3
В направленном графе сечение направлено из одного разделенного им частичного графа в сторону другого. Ветви, относящиеся к отдельным сечениям, могут быть выражены матрицей сечений Qa. Элемент этой матрицы q j, если 1 - е сечение содержит / - ю ветвь и направления сечения и ветви совпадают, а если противоположны, то qij - 1; Vij 0 если г е сечение не содержит у-и ветви. [31]
Процесс образования деревьев сводится к последовательному замещению ветвей базисного дерева t0 всевозможными сочетаниями остальных ветвей схемы, которые инцидентны сочетанию, соответствующему замещаемой ветви. Полезная особенность этого алгоритма, заключающаяся в образовании новых деревьев по предыдущим, позволяет при его реализации на вычислительных машинах [220] загружать оперативную память в меньшей степени, чем при прямом деребо-ре всех миноров матрицы сечений. В то же время необходимость выделения множества хорд относительно ветвей предыдущего дерева и сравнения этих - множеств с соответствующими множествами относительно базисного дерева t0 значительно усложняет логику алгоритма и увеличивает время вычислений. [32]
Чтобы получить третью строку матрицы сечений, достаточно сложить вторую и третью строки матрицы А и изменить знаки у всех элементов на обратные или сложить первую, четвертую и пятую строки без изменения знаков. Таким образом, матрица сечений С определяется из матрицы Ан с помощью простых алгебраических преобразований, что соответствует преобразованиям уравнений, вытекающих из I закона Кирхгофа. [33]
Поскольку каждая ветзь графа образует с ветвями дерева замкнутый контур, то напряжения ветвей можно выразить по второму закону Кирхгофа через узловые напряжения. Совокупность ветвей дерева, образующих с некоторой ветвью графа контур, определяется совокупностью инцидентных данной ветви сечений. Однако последняя, в свою очередь, определяется ненулевыми элементами того столбца матрицы сечений, который соответствует данной ветви графа. [34]
Для расчета электрических цепей часто пользуются понятием матрицы сечений. Сечением называется некоторая замкнутая поверхность, пересекаемая только один раз одной ветвью дерева и по одному разу соответствующими ветвями связи. На рис. 2.9 изображена схема с семью ветвями и показаны следы четырех поверхностей, каждая из которых пересекается одной ветвью дерева ( отмечены жирными линиями) и ветвями связи. Следует составить матрицу сечений для этой схемы, которая устанавливает связь между разностями потенциалов независимых узловых пар и напряжениями на зажимах ветвей схемы. [35]
Все векторы-циклы образуют пространство циклов: сумма mod 2 любых двух циклов есть цикл. Векторы-сечения также образуют пространство. Всякий вектор-сечение ортогонален любому вектору-циклу. Пространство сечений ортогонально пространству циклов. Пространство циклов является ортогональным дополнением пространства сечений. Матрица инциденций ( как матрица сечений) ортогональна матрице циклов. [36]