Логический алгоритм формирования дерева графа

Алгоритм формирования дерева графаявляется неотъемлемой частью некоторых методов формирования математической модели цепи, например, метода переменных состояния. Если выделено дерево графа, то сразу могут быть сформированы матрицы главных сечений и контуров. Выбор дерева графа - в общем случае задача неоднозначная, т.к. общее количество деревьев (без учета направления ветвей) для цепи с узлами выражается формулой . Обычно выделяют правильное дерево. Правильное дерево строится с учетом приоритета ветвей.

Приоритет ветвей при нумерации обусловлен методом формирования математической модели цепи и зависимостью переменных. В частности, для метода переменных состояния принят следующий приоритет ветвей:

1) управляемые источники напряжения;

2) независимые источники напряжения;

3) емкостные элементы;

4) резистивные элементы;

5) индуктивные элементы;

6) независимые источники тока;

7) управляемые источники тока.

Нумерацию начинаем с ветвей высшего приоритета, исчерпав очередную группу ветвей, переходим к следующей группе.

Информация о ветвях обычно содержит следующие данные: номер ветви, признак типа ветви, начальный и конечный узлы подключения ветви, в соответствии с выбранным направлением, и значения параметра или параметров.

Основное условие выделения дерева - это отсутствие контуров из ветвей, принадлежащих дереву. В связи с этим алгоритм выделения дерева графа может быть построен следующим образом.

1. Нумеруем ветви в соответствии с приоритетом.

2. Перебираем ветви, начиная с высшего приоритета, и фиксируем в списках начальный и конечный узлы подключения.

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

4. Если текущий элемент образует контур, то он перемещается в конец списка группы, после чего переходят к рассмотрению следующего элемента.

5. Если текущий элемент не образует контура, то переходят к анализу информации следующего элемента. Алгоритм завершается, если выделено ветвей, принадлежащих дереву.

Ветви, не вошедшие в дерево (хорды), образуют дополнение дерева графа. На основе упорядоченного и переупорядоченного таким образом списка ветвей можно построить матрицу инциденций

,

где - блок, соответствующий дереву графа; - блок, соответствующий дополнению дерева графа. Для перехода к МГС, учитывая, что блок ­- невырожденная квадратная подматрица, помножим оба блока на

.

Проиллюстрируем данный алгоритм на примере (рис. 2.5).

Рисунок 2.5 – Электрическая схема и ее граф с выделенным деревом

Информацию о ветвях схемы приведем в виде табл. 2.1.

Таблица 2.1 - Входная информационная таблица ветвей схемы

Номер ветви
Обозначение	E1	C1	L1	C2	C3	R1
Начальный узел
Конечный узел

 

Информацию о перенумерации ветвей схемы с учетом приоритета, результатах выделения дерева и повторной перенумерации представим в виде табл. 2.2.

Таблица 2.2 - Выходная информационная таблица ветвей схемы

Номер ветви
Обозначение	E1	C1	C3	C2	R1	L1
Начальный узел
Конечный узел

Из таблицы видно, что ветвь C2 не вошла в дерево графа, так как образовала бы контур с первыми ветвями E1, C1. Первые три ветви E1, C1, C3 таблицы представляют дерево графа (см. рис. 2.5). Матрица инциденций переупорядоченных таким образом ветвей схемы запишется как

После умножения этого соотношения справа на

получаем МГС