Модель схемы в виде ориентированного мультиграфа

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

где X₁ — множество вершин источников сигнала ;

X₂ — множество вершин приемников сигнала ;

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

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

Рис. 3.5 – Граф схемы

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

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

Идентификацию с точностью до выводов элементов схем можно получить при сопоставлении выводов с вершинами графа (рис. 3.6).

Рис. 3.6 – Компоненты связности

Граф схемы распадается на l компонент связности, где l — число электрических цепей схемы.