Устройство для разбиения графа на подграфы Советский патент 1987 года по МПК G06F15/173 

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

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

0

5

0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Корректор И.

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