Представление схемы неориентированным графом и гиперграфом. Неориентированный граф

Такая модель, как правило, используется для задач коммутации. В ней необходимо отобразить элементы объекта, их характеристики, координаты и, возможно, функциональное назначение, а также связи между элементами и их характе­ристики. На множестве X вершин неориентированного графа G (X, U) определе­ны двуместные отношения смежности, обладающие свойством симметричнос­ти.

Правила перехода от схемы соединения элементов к графу прос­ты: множеству элементов Э ставится во взаимно-однозначное соответст­вие множество вершин графа X, множеству соединений С - множество ребер U (Э «Х, С «U). Если функциональное назначение связей и/или их характеристики различны, необходимо функции и/или ха­рактеристики отразить в графе в виде весов ребер.

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

Например, для фрагмента схемы, изображенной на рис. цепь с₂ может быть представлена деревьями, показанными на рис. а и б.

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

Гиперграф – адекватная математическая модель схемы для задач декомпозиции/композиции.

Гиперграф - это множество , на элементах которого задан набор n -местных отношений связанности, обладающих свойствами коммутативности, транзитивности и рефлексивности. При представлении гиперграфа в форме Н(Х, U) каждое ребро и_j U - это некоторое подмножество X_j X, на котором предикат принимает значение «истина». При переходе от схемы к гиперграфу, аналогично: Э «Х, С «U. Тогда n = | Э | (кол-во элементов схемы) и m = | C | (кол-во цепей схемы).

Модель схемы должна учитывать фактор неизвестности соединения. Если, например, цепь С₁ соединяет выводы элементов Э₁, Э₅, Э₆ (см. рис. 1), то в ребре u₁={x₁, x₅, x₆} гиперграфа порядок перечисления вершин не должен означать порядка соединения элементов, так как этот порядок определяется после размещения элементов при решении задачи трассировки. При представлении схемы гиперграфом учитывается фактор неизвестности соединения, так как подмножество X_j, представляющее ребро u_j, не является упорядоченным.

Для того чтобы определить, соединены ли элементы э _i и э_к цепью с_j, дос­таточно проверить условие x_i, x_k X_j. Так как один элемент схемы может при­надлежать разным цепям, то в общем случае Х_t Х_j .Погиперграфу можно точно оценить количество электрических соединений между частями или элементами схемы.

Схема, показанная на рис. выше, интер­претируется гиперграфом Н(Х, U) (след. рис.)

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

Гиперграф может быть представлен в форме H(Y,E), где , причём , а Е – отношение инцидентности, обладающее свойством симметричности., между множествами X и Y. Гиперграф в виде H(Y,E),

Будет задан, если заданы множества X, U и многозначное отображение множества X в U или U в X/

Задается множество отображений X в U: , где - множество ребер, инцидентных верши­не х_i.

Задается множество отображений U в X: , где - множество вершин, инцидентных ребру u_j.

Типы элементов, а также имена или типы цепей в гиперграфе можно отобразить, задав однозначное соответствие множествами множества типов элементов T: х r t и взаимнооднозначное отображение множества U в множест­во типов цепей V: и_j n_j. По типам элементов и цепей из соответствующих библиотек может быть получена информация об их топологических и мет­рических характеристиках.