Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год (999411), страница 35
Текст из файла (страница 35)
Модель схемы (рис. 8.14, а) при сопоставлении элементам схемы вершин графа представлена на рис. 8.14,б. Введение избыточных ребер может сделать граф непланарным, хотя интерпретируемая им схема — планарна. По данному графу нельзя получить правильную оценку числа электрических связей между частями схемы. Например, количество ребер, попадающих в разрез между кусками 6, и 6, графа 6 (рис. 8.14,, б, Х, = (х„хз), Хз — — (хг. х4)), равно четырем (для вероятностного графа сумма весов ребер равна 4/3), в то время как в 4 Рас. 8.18. Графы схемы, показанной на рве.
8.14, а, црн сопоставлении вервган графа выводам (а) и пра представленви цепей фнкснрованныын деревьями (б) Рас. 8.14. Фрагмент принципиальной влектрнчеекой схемы (а) и ее граф (б) формация о метрических параметрах элементов может учитываться в весовых характеристиках вершин) и компоновки алгоритмами, в которых определяющим является фактор связности. Модель схемы в виде отдельных компонент связности несет информацию о соединяемых выводах элементов для задачи трассировки. Электрическая цепь может быть представлена фиксированным деревом (рис.
8.15, б). В этом случае исключаются избыточные ребра, однако не учитывается фактор неизвестности соединений и неверно отражается связность элементов схемы, так как любые две несмежные вершины дерева не связаны между собой, в то время как в схеме между соответствующими элементами существует электрическая связь. Такая модель может быть использована для решения топологнческих задач трассировки, если нет ограничений на проведение соединений под элементами и между их контактами. Модель схемы в виде ориентированного мультиграфа. Такое представление схемы используется для задач, в которых необходимо учитывать направления связей между элементами. В этих задачах точная оценка числа линий связи между элементами или частями схемы несущественна.
В данном случае, чтобы определить, что сигнал с выхода одного элемента поступает на вход другого, используется следующий способ представления электрических цепей дугами ориентированного графа: каждая цепь, соединяющая выходы и источников сигналов с схеме в этом случае разрезается одна цепь. Однако при такой модели схемы между этими показателями существует сильная корреляционная связь, так что оптимизация одного приводит, как правило, к оптимизации другого (см. !17)). При сопоставлении выводам элементов вершин графа граф схемы (см. рис. 8.14, а) распадается на отдельные компоненты связности (рис. 8.15, а), количество которых определяется числом электрических цепей схемы. Объединяя эти компоненты связности в соответствии с принадлежностью выводов элементам схемы, получим рассмотренную выше модель.
Модель схемы, полученная объединением полных подграфов, может использоваться для решения задач размещения элементов (ин- ) Ю вход™ ~ приемников интерпретируется двудольным ориенти о ным подграфом, таким, что тирован- (гхгЕ-:ХыЪ'х)Е=-Хз)Ви=(х,х)).Х Х () Х.Х ()Х где Х, множество вершин источников сигналов ((Х ) и) Х множество вершин приемников сигналов (~Хз~ = т), т.
е. каждая вершина, поставленная в соответствие элементу — источнику сигнала для данной цепи, соединена дугой с каждой вершиной, соответствующей элементу †приемни сигнала. При таком способе представления цепей также появляются избы- р ра. одель схемы получается объединением двудольных ориентированных графов.
Логическая функция элемента схемы может быть задана в качестве весовой ХаРаКтЕРИСтИКИ СООтВЕтСтВУЮ- Е) 8) а Н) Р Ге) Гаг(ГГ) Р,(а,) щей вершины графа. Граф схе- к, а мы (см. рис. 8.14, а) показан на рис. 8.16, а. В этом графе ве- к х совая характеристика, напри- з мер, вершины х, равна семи, уазнз) упвмг) вагиз) у,гмг) т. е, определяется типом элемента31.Модель неотображаетсхе- Рае. 8.18. ОРЯеатврованные гРафы схему с точностью до вывода элемен- ыы, взееражеавой ва рае. 8.14, а та, поэтому является корректной для схем, реализованных на элементах с одним выходом н равнозначными входами. Корректность модели для схем, построенных на элементах с неравнозначными входами и выходами, может быть обеспече- ядоченн ю п на введением весов ребер.
Вес каждого ребра предста ля бой в яет со упор ную пару, первый элемент которой характеризует выход элемента-источника, а второй — вход элемента-приемника (в простейшем случае пару составляют номера выводов этих элементов). Данная д редназначена для решения частных задач компоновки (поиск повторяющихся частей схем, установление идентичности схем). пол чена т к Идентификация с точностью до выводов элементов схем мож б ет ыть 8.16,б. Г у а также при сопоставлении выводов вершинам г а а рис. ). раф схема распадается на 1 компонент связности, где 1— число электрических цепей схемы.
Представление схемы гиперграфом и ультраграфом. Рассмотрим модель в виде гиперграфа, когда множество элементов схемы соответствует множеству вершин Х, а множество электрических цепей— множеству ребер 0 ()Х) = п — число элементов в схеме; )У) = т— число электрических цепей схемы). Каждое ребро гиперграфа Уа представляется подмножеством тех ве шин Х с= Х, Х, соответствующие которым элементы соединены й-й электрической цепью. При задании схемы гиперграфом учитывается фактор неизвестности соединения, так как для того чтобы определить, соединены ли г-й и )тй элементы схемы А-й электрической цепью, достаточно проверить условие х;, х; Е Ха.
Так как один элемент схемы может при- надлежать разным цепям, то в общем случае Хд П Х, ~ Я (А, 1 ~-=К = Т, лг). Количество связей между некоторым подмножеством Х' вершин гиперграфа и его дополнением Х Х' подсчитывается как число ребер 04 — Х„, для которых выполняется условие: и хо х? е= Х„(х; е"- Х' д х; е= Х Х'); 1,(Е=.7=1, а; й ~.=- К=1, пг. Отсюда видно, что по гиперграфу можно точно оценить число электрических соединений между частями или элементами схемы. Например, схема, данная на рис. 8.14, а, интерпретируется гнперграфом, показанным на рис. 8.17.
Множество вершин этох,о оз го гиперграфа Х =- (х„, хы х„хз), множество ре- беР 1?', = Х, = (х„х,); 4?'г=Хг — — (х„хг, хз, цг х,); (7,'=Х, = (х,,). 6Ызг З Число электрических цепей, соединяющих элементы 1 и 8 с остальными, будет равно единице. р я 17 1 Подсчет числа ребер гиперграфа, для которых вы"ф ' „'смнрндз~~„полняется условие (8.1О) при Х' = (х„хз) дает ной нз рнс. 8,14,а такое же значение. При матричном представлении модели схемы в виде гиперграфа принадлежность рго элемента схемы /-й электрической цепи с точностью до вывода элемента может быть задана, если элементы матрицы определять по правилу: / йь если х, е= Г и?,' ) О, если хг ф Г и?, где й; — номер вывода 1-го элемента схемы. Такая матрица для схемы, изображенной на рис. 8.14, а будет иметь вид и, и, и, 5 11 О О 8 12 4 5 О О 2 11 х, Т'= "з хз хз Идентификация с точностью до вывода при аналитическом представлении гиперграфа может быть обеспечена присваиванием весов, характеризующих эти выводы, вершинам, входящим в ребра.
Рассматриваемый гиперграф будет представлен следующими массивами: Х = (хг, хг, хз, х ); (7 = (иг, иг из)' ид — — (х„хз); иг =- (хд, хм х„хз); из = (хм хз); йг = (5 4); йг = (11 8 5. 2)' йз = (12 11)* причем и? поставлено во взаимно однозначное соответствие й?, 179 5 11 О О 8 — 12 — 4 — 5 ΠΠ— 2 11 Т, =- Ультраграф, так же как и гиперграф, учитывает фактор неизвестности соединений и позволяет точно оценить число электрических соединений.
Для всех рассмотренных моделей не выполняется требование информационной полноты. В наибольшей степени оно удовлетворяется при представлении схемы ультраграфом при наличии дополнительных 171 Из гиперграфа с помощью соответствующих преобразований (см. [171) может быть получена модель схемы в виде неориентированного мультиграфа. При представлении схемы ультраграфом множеству элементов схемы ставится во взаимно однозначное соответствие множество вершин Х, а множеству электрических цепей — множество ребер (7. Направление передачи сигналов в такой модели схемы задается следующим образом: пусть г'-й элемент схемы принадлежит 7тй цепи, тогда бинарное отношение иицидентности задано на паре (хо и;), если х; сопоставлено элементу — источнику сигнала, и (и,, х;) — если х; интерпретирует элемент — приемник сигнала.
Кенигово представление ультраграфа — модели схемы, показанной на рис. 8.14, а, дано на рис. 8.!8. и и и ? Отображение схемы с точностью до выводов элементов может быть обеспечено введением весов, "нс. ц18. Кеннгохарактеризующих эти выводы Напри ер при за-' во ПРсд"анленне дании ультраграфа в виде множеств Х, (7 и ото- мм рнс. Вдч,а бражения 1?' в Х весами вершин, входящих в Р+'и? и Р-'ип могут быть номера контактов элементов, сопоставленных этим вершинам.
Тогда данная схема будет описана следующими массивами: Х=(хп хг, х,, хз); 1?'=(и„и„из); Р+ иг (хз) Р+ иг (хз Х4) Р+ из (хг) К+ ' и, = (4); К+ ' и, = (5, 2); К+' и, = (12); Р 'иг=(хг); Р-' из=(хм хг) Р— ' и,=(х,); К-' и, = (5); К-' и,=-(11,8); К ' из=(11). При матричном представлении элементы матрицы можно определить по правилу йп если и; е= Р+' х,; 6ь ?= — й,, если и, ~ Р ' хб О, если и? ~ Р+' х, д и? ф Р— ' х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
