Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год, страница 39

ф:,'Ф Рис. 9.6. Перестановка несмежных (а) и смежиых (6) Причем количество соединительных ребер уменьшается на ЛВ1; = — сс (х;) + а (х1), (9.1 1) или ЛВ1 г .— — сс (х1) + а (хх) — 2т1; при перестановке несмежных (а) и смежных (б) вершин соответственно (рис. 9.6). Очевидно, что парная перестановка вершин х1 и хг приведет к изменению показателя а только у вершин, смежных ха и х;, поэтому после выполнения очередного обмена можно подсчитывать значения а только у таких вершин и корректировать приращение ЛВ у тех парных обменов, в которых онн участвуют.

Изложим основные пункты алгоритма, считая, что мультиграф задан множеством вершин Х и многозначным отображением Х в себя. 1. Для всех х1 е Х' и х; Е Х Х' подсчитываем по (9.9) или (9.10) показатели а (ха) и а (хт). 2. Для всех возможных парных обменов по (9.11) или (9.12) определяем приращение ЛЯ,, 3. Находим ЛВр р —— - игах Л5; р Проверяем условие ЛВр ч О. Если условие выполняется, то переходим к п. 4, иначе — к и. 8.

4. Осуществляем перестановку вершин хр и х«. 5. Определяем вершины, смежные хр и х«. Гхр Хр и 1хг Х« 6. Для вершин подмножеств Хр и Хн подсчитываем показатель а. Ч. Для возможных парных обменов с участием х, (- Хр, х, ~ Хе находим новые значения ЛЯ. Переходим к п. 3. 8. Конец работы алгоритма. Итерационный алгоритм компоновки при задании схемы гиперграфом.

Пусть множество вершин Х гиперграфа разбито на два непере- секающнхся подмножества Х' и Х~,х', т. е. имеется начальная компоновка. На основании (9.5) при перестановке вершин х; ~ Х' и хт Е Е Х" Х' изменение числа внешних связей Ь5ь т = 3 ГХ' П Г. (Х' Х')! — ( Г ((Х' () хт)- х;) П Г (~х'~,(Х' () хД) () х») ~. (9.13) Определение приращения А5 по этой формуле неэкономно с точки зрения затрат машинного времени.

Перестановка вершин х; и х; вызызает изменение состояния только тех и) б' , 'с б) з ' й' ребер, которые инцидентны этим вер. х, о ~ ох„, о хз шинам. Для ребер, инцидентных вершине х» и' о хз х; о о возможны следующие состояния: ~»го х 1. Останутся в разрезе между куска'- ь 1 "з хзо» о,' о хг ми6' и 6- 6'те ребра, которые содер-' 3 хй жат вершину хт или хотя бы по одной; рис. э.т. Ребра гипергрзфа, ос. вершине х, Е Х' и хрЕ Х- Х'.

На рис.. тзющиесЯ в РазРезе (а) и из- 9.7, а это РебРа аз =- (хь хь хб) и меняющие свое состояние от- а — (х х. х ). и — (»»Р) носнгеиьно Рз'рези (б) при 2 Вудут удалены из разреза между перестановке вершин х» и кз кусками 6' н 6'~6' те ребра, которые не содержат вершины хт и ни одной из вершин х, Е Х'.

Множество вершин Х„, входящих в такое ребро и, должно удовлетворять условию (Х ~,х») Д (Х' () х,) = 8. (9.14) На рис. 9.7, б таким ребром является и, =- (х» хр, хг). 3. Появятся в разрезе между кусками 6' и 6'~6' те ребра, в которые не входили вершины из куска 6'~6'. Для подмножеств вершин Х„таких ребер и„должно выполняться условие Х П(Х',Х')= я. (9.15) На рис. 9.7, б это ребро из = (хь х» х1). Аналогичные замечания справедливы и для ребер, инцидентиых вершине хт Р Х; Х'. На основании изложенного прирашение Д5» т = — (3,— + 31 ) — (3,+.

+ 3! ), (9.18) где з» и з — количество ребер, которые будут удалены из разрез т при перестановке вершин х» и хт соответственно; з» и з; — количество ребер, которые появятся в разрезе при перестановке вершин х» и хт соответственно. После обмена вершин х, и хт можно пересчитать значение А5 только у тех парных перестановок, в которых участвуют вершины, имеющие общие ребра с х; и хь Основные пункты алгоритма. 1.

Для пары вершин х; Е Х' и хт с Х Х' определяем инцидентные им ребра: Гх, = и; и Гхт = ил 2. Находим множество вершин, входящих в каждое ребро: Уиз Е= и~ (Г и„=Х„); »' и, ~= ит(ги~ = Х»). 3. Подсчитываем показатель зг — количество ребер из Р и» для которых выполняется условие (Х„~ х;) П(Х'()хт) = Я, и показатель з+ — количество ребер из Р и» для которых справедливо Хз () П(Х- Х') --= Я. 4. Подсчитываем показатель з~ — количество ребер и~ ~ ип для которых выполняется условие (Х,- х;)() ((Х', Х')() х») = Я, зт — количество ребер и~ ~ и»» для которых справедливо Х~ ПХ' = =Я б.

Определяем приращение А5»; =- (зг + з,.) — (з»+ + з(). б. Повторяем пп. 1 — б для всех возможных парных обменов. 7. Находим Л5р» — — гпах А5» ~. Проверяем условие А5„» ) О. Если оно выполняется, то переходим к и. 8, иначе — к п. 12. 8. Осуществляем перестановку вершин хр Е Х' и х» Р Х', Х'. 9. Для вершин хр н х определяем инцидеитные им ребра: Гх„=- и =и,иГх,=и„. 10. Находим множество вершин, входящих в эти ребра: Гир —— =Х, и Ги,=Х,. 11.

Повторяем пп. 1 — б для всех возможных парных обменов, в которых участвуют вершины х, Е Х„и х„~ Х». Переходим к п. 7. 12. Конец работы алгоритма. Компоновка схем с помощью итерационного алгоритма может выполняться как по способу последовательного выделения узлов, описанному в р 9.2, так и по способу последовательного разделения. При последовательном разделении схема разбивается на две равные части. Итерационным алгоритмом выполняется улучшение компоновки. Далее каждая часть опять разделяется на две и к каждой паре приме,няется итерационный алгоритм. Процесс повторяется до тех пор, пока рте получим разбиение схемы на требуемое число узлов. $ ЭА.

АЛГОРИТМ ОПРЕДЕЛЕНИЯ ИДЕНТИЧНОСТИ ЧАСТЕЛ СХЕМ При решении задачи компоновки часто возникает необходимость установления идентичности отдельных частей схемы ЭВМ. Эта задача сводится к распознаванию изоморфизма графов, если граф является корректной моделью схемы в смысле полноты отображения в нем свойств схемы, определяющих логику ее функционирования. В этом случае изоморфизм графов означает тождественность функционирования отображаемых ими схем. Рассмотрим алгоритм определения изоморфизма взвешенных ориентированных мультиграфов.

Такие графы — корректная модель в указанном выше смысле, например для функциональных схем, построенных на логических (базовых) элементах с равнозначными входами и одним выходом. При распознавании изоморфизма взвешенных ориентированных графов 6 = (Х, Р) и Н = (1', Р) используются следующие характеристики мультиграфа: полустепень исхода а» и захода Ь, каждой вер- шины хь т. е. количество ребер, исходящих из этой вершины и заходящих в нее; тип (вес) 55 вершины х5 (определяется логической функцией элемента схемы, которому поставлена во взаимно однозначное соответствие данная вершина); мощность прямого отображения Р+'х; вершины х; мощность обратного отображения Р ' х; вершины х5.

Например, для вершины х, графа, показанно р НЫ Х5, '. го на ис. 9.8, эти ха- Р"'х 1=1, 1Р-'хД=2 (сравнить рактеристики будут: аз=1, Ь,=З, !Р ха!=, ! с соответствующими характеристиками вершины х,: аа = 1, Ь, =- 3; !Ре' ха! = 1, !Р а х,( =- 3). Хгм ха(8) Для того чтобы графы Н и О были изоморфны, необходимо выполнение условия: хз(7) ()Гх5 ~ Х) (Еут а= у) ((ай=с ) а (Ь,= Рис. 9.8. Ориеити- = с(5) э (55 = 55) а (! Р+' х,! = розанный граф =7+' у5!)а(!Р ' х! = !Р 'И). (9.17) 3 есь с и с( — полустепени исхода и захода вершины граф ы г афа Н. Но это условие не является достаточным, что док азывается, в частности примером, показанным на рис. 9.9, а.

Поско у оскольк полный набор инвариантов в настоящее время неизвестен, н р д е п е ставляется возможным определить, изоморфиы ли графы без построения графа соответствия, т. е. подстановки ): Π— Н. х, х уа Х2 У з уе у5 Рис. 9.9. Неизоморфные (а) и нзоморфные (8) ориенти- розанные графы 6 н п Граф соответствия строится следующим образом: 1. Проверяется условие (9.17) возможности изоморфизма. 2.

)з матривается условие существования д е инственной вершины асс и мощностью прямого и с некоторой полустепенью захода и исхода и обратного отображения: Ь вЂ” Ь. Ь(Р+'х ~= (ЕХ5 5-= Х)(ДХ5 ~а Х)((5,=55) и (а,=а,) д (Ь,=Ь5) Э (~Р+ Х, ~= = )Р+' х5 ~) й(~Р-' х,~=~Р-' х5))); ~ Х ) = я; 5 чь ]; 5, 1 ~ 7 = 1, и. 599 (9.18) Тем вершинам графа О, для которых условие (9.18) выполняется, можно поставить в соответствие вершины графа Н по правилу: (х5 — у5» ((55=55) э,(а5=с5) 8 (Ьа=с(5) ь(~Р+ х5~= =~Р+ у5~) еа(~Р ' х5~=!Р у5~)). (9.19) Таким образом, определяется частичная подстановка п5 = -х5 — У5 (9.20) Найденные вершины исключаются из Х и )'.