Графотеоретические модели описания схем

Рассмотрим несколько способов описания схем графами для математической постановки задач конструирования.

4.2.1 Граф коммутационной схемы (ГКС). В отличие от обычного линейного графа, в ГКС три типа вершин и два типа ребер. Обозначение такого графа G=(X, C, V, F, W)

Вершины графа ГКС:

X – элементы схемы;

C – выводы элементов, включая внешние выводы схемы;

V – цепи (комплексы) схемы.

Ребра ГКС: F – элементные ребра ();

W – сигнальные ребра ().

Элементные ребра принадлежат выводам из множества С и элементам из множества Х и задается парами вершин (х_i, c_k).

Сигнальные ребра определяют вхождение выводов из С в отдельные цепи и задается парами вершин (c_k,v_j).

Граф коммутационной схемы (ГКС).

Для задания структуры схемы способ изображения графа (положение вершин и форма ребер не важен).

Иногда (при решении задач конструирования) дополняют схемы информацией об источниках и приемниках сигналов (придается ориентация сигнальным ребрам). Граф схемы становится ориентированным.

В других ситуациях (при трассировке соединений на плоскости) необходимо учитывать порядок расположения конструктивных выводов на элементах. В этих случаях и ГКС устанавливается порядок следования элементных ребер.

Учитывая, что ГКС содержит вершины и ребра разных типов, его структуру можно описать с помощью матриц А и В.

Матрица А представляет цепи схемы и определяется как А=||а _ij || _mxК, где m – число цепей, K – число выводов в схеме.

Элемент а_ij =1, если вывод с_i принадлежит цепи v_j; и а_ij =0 в противном случае.

	c01 c02 c03 c04 c11 c12 c13 c21 c22 c23 c31 c32 c33 c41 c42
v1	1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
v2	0 1 0 0 0 1 0 0 0 0 0 1 0 0 0
A = v3	0 0 0 0 0 0 1 1 0 0 1 0 0 0 0
v4	0 0 0 0 0 0 0 0 1 0 0 0 1 1 0
v5	0 0 1 0 0 0 0 0 0 1 0 0 0 0 0
v6	0 0 0 1 0 0 0 0 0 0 0 0 0 0 1

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

Матрица В =||b _ij || _nxK (n – число элементов) выделяет подмножества выводов, принадлежащие отдельным элементам. Строки матрицы соответствуют элементам, а столбцы – выводам. Элемент матрицы b _ij =1, если вывод с_j принадлежит элементу x_i, и b _ij =0 в противном случае.

	c01 c02 c03 c04 c11 c12 c13 c21 c22 c23 c31 c32 c33 c41 c42
x0	1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
x1	0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
В = x2	0 0 0 0 0 0 0 1 1 1 0 0 0 0 0
x3	0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
x4	0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

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

Информация о схеме в виде матриц А и В занимает большой объем памяти. Широко используется списковое задание схемы (*.ALT-файл). Он представляет собой последовательности перечислений комплексов (список цепей и принадлежащие им элементы и выводы). Достоинства этого способа – наглядность и малые затраты памяти. Сложность – в обработке информации, в воде в программное обеспечение специальных процедур обработки списков.

Структуру ГКС можно задать с помощью матрицы Т (матрицы цепей).

T=||t _ij || _nxk,. строки которой соответствуют элементам схемы, а столбцы – выводам элемента. Элемент матрицы t _ij – номер цепи, связанной с выводом с_j элемента x_i.

	c1 c2 c3 c4
x0	v1 v2 v5 v6
x1	v1 v2 v3 -
Т = x2	v3 v4 v5 -
x3	v3 v2 v4 -
x4	v4 v6 - -

Комплексы схемы (совокупность выводов в цепи) определяются равными элементами матрицы Т. Данный способ описания сохраняет упорядоченность матричной формы, что удобно с вычислительной точки зрения, но требует предварительной нумерации цепей.

Модель в виде ГКС используется при задании полной и точной информации о схеме в процессе конструирования решение задач трассировки соединений. В отдельных случаях удобнее пользоваться упрощенными моделями схем. Например, при компоновке узлов.

4.2.2 Граф элементных комплексов (ГЭК). В ГКС выводы элементов (контакты) стягиваем внутрь вершины, т.е. отождествляем выводы с_i с самими элементами x_i. При этом устраняются элементные ребра F, комплексы v_j переходят в элементные комплексы v′_j. Данная модель схемы G ^x =(X,V ^x,W) называется графом элементных комплексов.

Граф элементных комплексов (ГЭК).

Для описания ГЭК используют матрицу Q (матрицу комплексов) - Q=||q _ij || _nxm,. строки которой соответствуют элементам схемы, а столбцы – элементным комплексам v′_j.

q_ij =1, если элемент x _i входит в элементный комплекс v′_j (связан j –й цепью),

q_ij =0, если элемент x _i не входит в элементный комплекс v′_j.

	v’1 v’2 v’3 v’4 v’5 v’6
x0	1 1 0 0 1 1
x1	1 1 1 0 0 0
Q = x2	0 0 1 1 1 0
x3	0 1 1 1 0 0
x4	0 0 0 1 0 1

Число единиц в любой строке равно числу цепей, связанных с соответствующим элементом. Число единиц в столбце равно размеру данного элементный комплекса. Одноэлементные комплексы (ρ ′_j=1) приводят к образованию петель на вершине x_i ГЭК. Такие комплексы соответствуют цепям, связывающим выводы одного и того же элемента, и не оказывают влияния на решение задач компоновки и размещения. В связи с этим при задании схемы в виде ГЭК они могут быть опущены.

4.2.3 Взвешенный граф схемы (ВГС).

Наиболее простая модель описания схемы G=(X,V), в котором вершины x _i соответствуют элементам, а ребра v_ij с приписанными к ним весами r_ij >0– количеству цепей между элементами x_i и x_j.

Взвешенный граф схемы (ВГС).

Структуру ВГС можно задать с помощью матрицы R (матрицы соединений или смежности) R=||r _ij || _nxn, строки и столбцы которой соответствуют элементам схемы, а r _ij = весу, приписанному соединению элементов x_i и x_j. Матрица R – симметрическая, с нулевой главной диагональю (r_ii =0, i=1, 2,…, n).

	x0 x1 x2 x3 x4
x0	0 2 1 1 1
x1	2 0 1 2 0
R = x2	1 1 0 2 1
x3	1 2 2 0 1
x4	1 0 1 1 0

Между матрицей соединений R и матрицей комплексов Q существует связь:

m

r_ij =∑ q_isq_js,

s =1

т.е. r_ij равно числу цепей, связывающих элементы x_i и x_j.

Описание схем взвешенным графом схемы не учитывает соединения выводов одной цепи в Т-образной форме и т.п. Поэтому в ряде алгоритмов размещения и компоновки используются весовые оценки, учитывающие приоритеты цепей и вероятности реализации отдельных соединений. Элемент матрицы соединений (R) описывается выражением:

m

r_ij =∑ q_isq_js•w _s •f _s,

s =1

где w_s – коэффициент (0< w_s ≤1), отражающий особенности s–й цепи; f_s - коэффициент учета размера цепи. В рассмотренных ранее графах w_s = f_s =1. (Алгебра соединений)