Элементы теории графов

Элементы теории графов

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

Топологические уравнения подсистем записываются для узлов и контуров эквивалентной схемы, поэтому получение эквивалентной схемы - необходимый этап подготовки технического объекта к моделированию. Существующие методы получения топологических уравнений основаны на применении графов.

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

Выбор фундаментального дерева графа не однозначен, для одного и того же графа их может быть несколько. Так, на рис. 1, в представлено еще одно фундаментальное дерево графа (рис. 1, а). При этом ребра а, б, в, д, и - ветви дерева. г, е, ж, к - хорды.

Рис. 1. Граф (а) и его фундаментальные деревья (б, в).

Граф несет информацию о связях в объекте, удобную для восприятия человеком, но для обработки на ЭВМ нужна информация числового характера. Представить граф в таком виде можно с помощью матрицы инциденций А, которая кодирует ориентированный граф так: каждому узлу графа (кроме одного, называемого базовым) соответствует одна строка, каждому ребру - один столбец, в столбце записывается +1 на пересечении со строкой узла, из которого, ребро направлено, и -1 на пересечении со строкой узла, к которому оно направлено, остальные элементы этого столбца равны 0. Базовому узлу в матрице инциденций никакая строка не соответствует. В качестве базового может быть выбран произвольный узел.

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

Рекомендуемые материалы

Таблица 1.

Рис. 2. Матрица контуров и сечений графа.