SU1332329A1 - Устройство дл разбиени графа на подграфы - Google Patents

Abstract

Изобретение относитс  к вычислительной технике, может быть использовано при автоматизированном решении задач компоновки элементов радиоэлектронной аппаратуры в блоки. Целью изобретени   вл etc  15 асширение функциональных возможностей устройства за счет обеспечени  возможности разбиени  графа на минимально св занные подграфы . Устройство обеспечивает возможность задавать объемы подграфов и определ ть вершины,обладающие максимальным числом св зей с вершинами, включенными в формируемый подграф. С этой целью информаци  о топологии исследуемого графа заноситс  в матрицу , после чего инициируетс  один из входов задани  начальной вершины первого подграфа устройства. Аппаратные средства устройства обеспечивают последовательный опрос триггеров мат-, рицы и анализ св зности выбираемых подграфов . Коды номеров вершин подграфа, обладающего минимальной св зностью, занос тс  в блок пам ти. 1 ил. (Л

Description

1 1

Изобретение относитс  к вычислительной технике и может быть использовано при автоматизированном решении задач компоновки элементов радио электронной аппаратуры в блоки.

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

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

В-состав устройства входит матрич на  модель 1 графа, содержаща  Т строк и М столбцов триггеров 2-1,1,..., 2-м,Т и элементов И 3- 1,1,..., 3-М,Т группу сумматоров 4-1 , -. . , 4-Т, группу элементов ИЛИ 5-1,,,. , 5-М, группу коммутаторов 6-1,..., 6-м, группу Tptirre- ров 7-1 , . . . , 7-М, группу элементов НЕ 8-1,,.., 8-м, дешифратор 9, первый- счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых

импульсов, вход 14 задани  количества вершин в подграфе устройства, шифратор 15, второй счетчик IS,выход 17 признака выделени  дерева с заданным количеством вершин устройства , два коммутатора 18 и 19, шесть ключей 20 ... 25, элементы ИЛИ 26, схема 27 сравнени , блок 28 пам ти, два регистра 29 и 30, входа: 31-1,... 31-М задани  начальной вершины первого подграфа устройства.

Устройство работает следующим образом .

Первоначально в нулевое состо ние привод тс  все триггеры 7-1 ,. . ., 7-М группы, счетчики 10 и 16, регистры 29 и 30, блок 28 пам ти, ключи 20 - 23 закрыты, ключ 24 открыт, коммутаторы 6-1 , ..., 6-м устанавливаютс  в состо ние, при котором их выходы одключены к вькодам соответствующих триггеров 7-1,..., 7-м. Информаци  о топологии моделируемого графа заноситс  путем установки соответствуюих триггеров 2-1,. . ., 2-м в единичое состо ние. Соответствующий триггер 2-кр (,...,М) формировател  уги определ етс  пересечением К-й строки (К-номер начальной вершины одулируемой ветви графа) с р-м столбцом (р-номер конечной вершины оделируемой ветки графа). Задание ачальной вершины первого подграфа

323292

осуществл етс  подачей на соответствующий вход 31 единичного сигнала, который, проход  через элемент ИЛИ 5 , поступает на вход шифратора 15, который формирует на своих выходах двоичный код номера заданной начальной вершины. Сигнал задани  начальной вершины после прохождени 

1Q через соответствуюш е элементы ИЛИ 5 . и 26 открывает ключ 20,обеспечива  тем самьм запись двоичного кода номе- . ра начальной вершины в блок 28 ти,осуществл ет запуск генератора 13 15 увеличивает содержимое счетчика 10 на единицу. Одновременно сигнал с выхода соответствующего элемента ИЛИ 5 устанавливает в единичное со- сто ние триггера 7-К, обеспечива  тем

2Q самым возможность дл  прохо;кдени  с выхода триггеров 2-К1,..., 2-К,М сигнала матричной модели графа, соответствующей начальной вершине на сумматоре 4-К, а также запрещает вы25 бор строки, соответствующей начальной вершине в качестве кандидата на включение в первый подграф. Последнее достигаетс  за счет инвертировани  в элементе НЕ 8-К сигнала с выхода

30 триггера 7-К, соответствующего включенной в первый подграф начальной вершине. Следствием этих действий  вл етс  формирование на выходе К-го сумматора 4-К (К-не разно номеру начальной вершины) двоичньгк кодов количества св зей К-й вершины с включенной в первый подграф начальной вершиной. Тактовые импульсы от генератора 13 через открытый ключ 24

40 обеспечивают последовательное подключение к выходам схемы 27 сравнени  и ключа 25 выходов сумматоров 4-К, а также синхронное подключение к одному из входов элемента 1 2-М с

45 помощью коммутатора 18 выходов элементов НЕ 8-К. Кроме того, тактовые импульсы поступают на счетчик 16, на выходе которого образуетс  двоичный код номера импульса в интервале

50 от 1 до М (код номера аннулируемой вершины), схема 27 производит равнение содержимого регистра 30 с содержимым подключенного через коммутатор 19 сумматора 4-К, Если первое

55 оказываетс  меньше второго и вершина , соответствующа  подключенному сумматору еще не включена в формируемый подграф (на выходе соответствующего элемента НЕ 8-К отсутст- .

35

3

вует единичный сигнал), то сигнал с выхода блока 27 после прохождени  через элемент И 12 разрепшет запись в регистр 30 содержимого подключенного к блоку 27 сумматора 4-К. Одновременно сигнал с выхода блока 27 разрешает запись в регистр 29 через ключ 23 двоичного кода номера соответствующей вершины графа. После завершени  цикла просмотра всех М вершин в регистре 30 присутствует максимальное значение количества св зей одной из вершин, не включавшихс  ранее в первый подграф, а в регистре 29 зафиксирован двоичный код номера этой вершины. Факт окончани  этого цикла фиксируетс  счетчиком 16, который формирует на выходе признака переполнени  сигнал, разрешающий передачу из регистра 29 в дешифратор 9 кода номера вершины, максимально св занной с вершинами, включенными в формируемый подграф. Этот же сигнал после задержки в элементе 11 на врем , необходимое дл  передачи информации из регистра 29 в дешифратор 9 осуществл ет обнуление содержимого регистров 29 и 30, а также счетчика 16. Поступивший в дешифратор 9 код вершины преобразуетс  в сигнал на одном из его выходов , который после прохождени  через элемент ИЛИ 5 устанавливает один из триггеров 7-,..., 7-М в единичное состо ние, обеспечива  тем самым возможность дл  прохождени  сигналов с выхода триггеров 2-1,..., 2м одного из столбцов матричной модели, соответствующего включенной в подграф вершине, на сумматор 4, а также запрещает выбор строки, соответствующей включенной вершине, в качестве кандидата на включение в подграф. По аналогии со случаем начальной вершины производис  запись в блок 28 кода номера очередной включаемой в первый подграф вершины, а содержимое счетчика 10 увеличиваетс  на единицу. Цикл работы устройства дл  выбора и включени в подграф последующих вершин аналогичен . Аналогично осуществл етс  задание начальной вершины подачей сигнала на один из входов 31 устройства . Если в первый подграф включено заданное количество вершин, то на выходе счетчика 10 формируетс  сигнал , поступающий на выход 17 устрой

0

5

ства и запрещающий прохождение тактовых импульсов от генератора 13, и разрешает прохождение через ключ 21 сигналов с выходов триггеров 7-1, ,.., 7-м на управл ющие входы соответствующих коммутаторов 6-1,..., 6-М. В этом случае коммутаторы 6-1, , . ., 6-м, на управл ющие входы которых поступили единичные сигналы (коммутаторы, соответствующие включенным в первый подграф вершинам), устанавливаютс  в состо ние, при котором к их выходам подключены выходы соответствующих элементов 8-1,..., 8-м НЕ, исключа  тем самым из рассмотрени  при последующем анализе св зи вершин 6, уже включенных в сформированный подграф. Дл  формировани  второго подграфа в счетчике 10 устанавливаетс  граничное значение , равное суммарному объему первого и второго подграфов. В этом случае сигнал на выходе счетчика 10 5 аннулируетс  открыва  путь дл  прохождени  по схеме устройства тактовых импульсов от генератора 13 и устройство функционирует аналогично случаю формировани  первого подграфа . Результатом работы устройства  вл етс  накопление в блоке 28 кедов номеров вершин в пор дке их включени  в подграфы.

0

35

Claims (1)

1. Формула изобретени 

   0

   5

   0

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

   причем первые входы элементов ИЛИ группы  вл ютс  входами задани  начальной вершины первого подграфа устройства, выход К-го элемента ИЛИ группы (К-1,..., М, где М - количество вершин в моделируемом графе) подключен к К-му информационному входу шифратора, информационный выход котоционному входу второго ключа, к п вому информационному входу К-го к мутатора группы и к входу К-го эл мента НЕ группы, выход которого п ключен к второму информационному ду К-го коммутатора группы, к К-м информационному входу первого ком татора и к вторым входам элементо

   рого подключен к информацинному входу ю Р всех узлов К-й строки матричной

   модели графа, выход К-го коммутат ра группы подключен к третьим вхо элементов И всех узлов К-го столб матричной модели графа, выход эле та И К-го узла Р-й строки матричн модели графа(,..., м) подключе входу К-го слагаемого Р-го суммат ра группы, выход которого подключ к Р-му информационному входу втор коммутатора, выход которого подкл чен к первому информационному вхо схемы сравнени  и к управл ющему ду шестого ключа, выход которого подключен к информационному входу второго регистра, выход которого подключен к второму информационно входу схемы сравнени , выход приз неотрицательного результата котор подключен к первому входу элемент выход первого коммутатора подключ к второму входу элемента И, выход которого подключен к информационн входу шестого ключа и к управл ющ входу четвертого ключа, выход при ка переполнени  второго счетчика подключен к управл ющему входу п  го ключа и к входу элемента задер ки, выход которого подключен к вх дам установки в О второго счетчик и первого и второго регистров.

   первого ключа, выход которого подключен к информацинному выходу блока пам ти, информационный вход первого счетчика  вл етс  входом задани  количества вершин в подграфе устройст- ва, выход признака переполнени  первого счетчика подключен к управл ющим входам второго и третьего ключей и  вл етс  выходом признака выделени  дерева с заданным количеством вершин устройства, выход элемента ИЛИ подключен к управл ющему входу первого ключа к счетному входу первого счетчика и к входу пуска генератора тактовых импульсов, выход которого подключен к информационному входу третьего ключа, выход которого подключен к управл ющим входам первого и второго коммутаторов и к счетному входу второго счетчика, икформацион- ный выход которого подключен к информационному входу четвертого ключа, выход которого подключен к информационному входу первого регистра, выход которого подключен к информацион- ному входу п того ключа, выход кото- рого подключен к информационному входу дешифратора, К-й выход которого подключен к второму входу К-го элемента ИЛИ группы, выход К-го тригге- ра группы подключен к К-му информа329

   ционному входу второго ключа, к первому информационному входу К-го коммутатора группы и к входу К-го элемента НЕ группы, выход которого подключен к второму информационному входу К-го коммутатора группы, к К-му информационному входу первого коммутатора и к вторым входам элементов

   Р всех узлов К-й строки матричной

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

   Редактор Н.Лазаренко

   Составитель А.Мишин Техред Л.Сердюкова

   Заказ 3834/45Тираж 672Подписное

   ВНИИПИ Государственного комитета СССР

   по делам изобретений и открытий 113035, Москва, Ж-35, Раушска  наб., д. 4/5

   Производственно-полиграфическое предпри тие, г.Ужгород, ул.Проектна , 4

   Корректор И.