13 Вопрос

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

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

Рис. 2.15

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

Пути, маршруты, цепи и циклы.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

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

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

Граф отношения делимости

Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16).

Рис. 2.16

Подграфы

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

Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана.  Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

14 Вопрос

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

Для получения топологических уравнений все ветви эквивалентной схемы разделяют на подмножества хорд и ветвей дерева. Имеется в виду фундаментальное дерево(покрывающее дерево), т.е. подмножество из   дуг, не образующее ни одного замкнутого контура, где   — число вершин графа (узлов эквивалентной схемы). На рис. 1,б показан граф эквивалентной схемы рис. 1,a, толстыми линиями выделено одно из возможных покрывающих деревьев.

Рис. 1. Эквивалентная схема и соответствующий ей граф

Выбор дерева однозначно определяет вектора напряжений   и токов   хорд, напряжений   и токов   ветвей дерева и приводит к записи топологических уравнений в виде

 

(1)

 

(2)

где   — матрица контуров и сечений,   — транспонированная  -матрица.

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

Для схемы на рис. 1,б  -матрица представлена в виде табл. 1.

Таблица 1

Обозначение	Ветвь C1	Ветвь C2	Ветвь C3
Хорда R1	1
Хорда R2		1
Хорда R3			1
Хорда R4	1	+1	+1
Хорда J	+1

 

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

Второй шаг – решение системы полученных ОДУ+АУ тем или иным способом.