Описание ГКС матрицами

Т.к. ГКС содержит вершины и рёбра разных типов, его удобно описать двумя матрицами A и B.

Матрица A представляет цепи схемы и определяется следующим образом:

А=¦aij¦mxk,.

где m — число цепей, k — число выводов в схеме. Строки матрицы соответствуют цепям, а столбцы — выводам элементов.

Для графа, приведенного на рис. 2, матрица, А имеет вид:

Табл. 1.

Каждый столбец матрицы A содержит одну единицу, поскольку любой вывод может входить лишь в одну цепь. Число единиц в любой строке матрицы равно размеру соответствующей цепи.

Матрица:

B=¦bij¦nxk,.

выделяет подмножества выводов, принадлежащих отдельным элементам. Строки матрицы соответствуют элементам, а столбцы — выводам.

Для графа, приведенного на рис. 2, матрица B имеет вид:

Табл. 2.

В каждом столбце матрицы В одна единица, т.к. вывод может принадлежать только одному элементу. Число единиц в строке равно числу выводов на соответствующем элементе.

Структуру ГКС можно задать одной матрицей.

T=¦tij¦nxk1,.

строки которой соответствуют элементам, а столбцы выводам элемента, причём к1 = max ki, i=1,n.

Элемент матрицы tij представляет номер цепи, связанной с выводом cj элемента ei. Т. е. t23 — номер цепи, связанной с выводом c3 элемента e2. Для нашей схемы:

Табл. 3.

Матрица T называется матрицей цепей. Для построения матрицы цепей необходимо каждой цепи присвоить номер.

Существуют упрощенные модели схем. Так, при компоновке элементов в конструктивные узлы можно не рассматривать выводы элементов, а рассматривать только сами элементы. Тогда элементные рёбра можно устранить, т. е. вершины — как бы «стянуть» в элементы (убираем выводы элементов, а цепи обозначаем точками). Тогда можно построить граф элементных комплексов (ГЭК) G1= (E, V1, W) Здесь множества вершин соответствуют:

• — Е — элементам;
• — V1 — элементным комплексам;
• — W — сигнальным рёбрам.

Элементный комплекс V’j — подмножество элементов из E=e1,e2,…, en, соединенных цепью j, j=1,M. Элементные комплексы могут содержать общие элементы, то есть V’jV’j0, ij. Число элементов в комплексе V’j назовем размером элементного комплекса p’j.

ГЭК для схемы рис. 2 имеет вид:

Рис. 3.

Описать множества цепей (комплексов) этого графа:

V1=e0,e1; V2=; V3=; V4=; V5=; V6=.

Для описания ГЭК удобно воспользоваться матрицей:

Q=¦qij¦nxm,.

строки которой соответствуют элементам, а столбцы элементным комплексам.

В нашем случае:

Табл. 4.