Представление схемы гиперграфом и ультраграфом
Рассмотрим модель в виде гиперграфа, когда множество элементов схемы Э соответствует множеству X, а множество электрических цепей С — множеству ребер U (|X| = n — число элементов в схеме; |U| = m — число электрических цепей схемы). Каждое ребро гиперграфа представляется подмножеством тех вершин которым соответствуют элементы, соединенные k-й электрической цепью.
При задании схемы гиперграфом учитывается фактор неизвестности соединения, т. е. для определения связи между i-м и j-м элементами схемы
k-электрической цепью, достаточно проверить условие . Так как один элемент схемы может принадлежать разным цепям, то в общем случае
.
Количество связей между некоторым подмножеством вершин гиперграфа и его дополнением подсчитывают как число ребер для которых выполняется условие
;
. (3.2)
Отсюда видно, что по гиперграфу можно точно оценить число электрических соединений между частями или элементами схемы. Например, схема (рис. 3.1) интерпретируется гиперграфом (рис. 3.7).
Рис. 3.7 – Гиперграф схемы
Множество вершин этого гиперграфа составляет , множество ребер определяется, как ; ; .
Число электрических цепей, соединяющих элементы 1 и 3 с остальными, будет равно единице. Подсчет числа ребер гиперграфа, для которых выполняется условие (3.2), при , дает такое же значение. При матричном представлении модели схемы в виде гиперграфа принадлежность i-го элемента схемы j-й электрической цепи с точностью до вывода элемента можно задать, если элементы матрицы определять но правилу:
где — номер вывода i-го элемента схемы. Матрица схемы:
Идентификацию элементов с точностью до вывода при аналитическом представлении гиперграфа можно обеспечить присваиванием весов, характеризующих эти выводы, вершинам, входящим в ребра. Рассматриваемый гиперграф будет представлен массивами
; ;
; ; ;
.
причем поставлено во взаимно однозначное соответствие . Из гиперграфа с помощью соответствующих преобразований можно получить модель схемы в виде неориентированного мультиграфа [20,37].
При представлении схемы ультраграфом множеству элементов схемы ставится во взаимно однозначное соответствие множество вершин X, а множеству электрических цепей — множество ребер U. Направление передачи сигналов в такой модели схемы задается таким образом: пусть i-й элемент схемы принадлежит j-й цепи, тогда бинарное отношение инцидентности задано на паре , если сопоставлено с элементом как источником сигнала, и — если интерпретирует элемент как приемник сигнала (рис. 3.8).
Рис. 3.8 – Кенигово представление ультраграфа схемы
Отображение схемы с точностью до выводов элементов обеспечивается введением весов, характеризующих эти выводы. При задании ультраграфа в виде множеств X, U и отображения U в X весами вершин, входящих в и , — установлены номера контактов элементов, сопоставленных с этими вершинами. Данная схема описана следующими массивами:
При матричном представлении элементы матрицы определяются по правилу
Такая матрица для схемы имеет вид
Ультраграф, как и гиперграф, учитывает фактор неизвестности соединений и позволяет точно оценить число электрических соединений [26, 49]. Для всех рассмотренных моделей не выполняется требование информационной полноты. В наибольшей степени оно удовлетворяется, когда схема представляется ультраграфом, при наличии дополнительных сведений о конструктивно-технологических характеристиках элементов и их логических функциях. При интерпретации элементов схемы вершинами графа эти сведения для всех моделей могут быть заданы в виде весовых характеристик вершин. Топологические свойства элементов схемы не отображены ни в одной из рассмотренных моделей.
При представлении схемы в виде неориентированного мультиграфа и гиперграфа не удовлетворяется требование однозначности перехода от модели к схеме. Теория неориентированных и ориентированных графов развита достаточно хорошо. Разработано большое количество алгоритмов решения задач схемно-топологического конструирования методами теории графов. Математический аппарат теории гиперграфов и ультраграфов в настоящее время только развивается.
Дата добавления: 2015-10-29; просмотров: 1688;