2.1 Использование графов для описания принципиальных схем.

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

Граф – это математический объект, который состоит из множества вершин и множества ребер или дуг, находящихся с собой в некотором отношении.

Обозначение графа: G=(X,U), где Х – множество вершин; U – множество ребер.

Большинство задач удобно решать при помощи матричного задания графов.

2.1.1 Описание графа матрицей смежности.

В этом случае элементы матрицы образуются по правилу:

Пример:

      

 

 

 

 

2.1.2 Описание графа матрицей инцидентности.

В этом случае элементы матрицы образуются по правилу:

Пример для рассмотренного выше графа:

 

 

 

 

 

 

Пример описания схемы с помощью графа:

 

 

 

 

 

 

 

 

 

 

Кроме рассмотренных гримеров существуют и другие варианты описания схем с помощью графов (например, с помощью т.н. графа Кёнига).