Устройство для разбиения графа на подграфы

Устройство для разбиения графа на подграфы

Иллюстрации

Показать все

Реферат

 

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

СООЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А1. (g1) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4043800/24-24 (22) 26. 03. 86 (46) 23.08. 87. Бюл. и 31 (72) Г.Н.Лаврик, 1().И,Скорин и А.В.111ернин (53) 681. 333 (088. 8) (56) Авторское свидетельство СССР

В 913389, кл. G 06 Е 15/20, 1982.

Авторское свидетельство СССР

Р 1075268, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ ГРАФА

НА ПОДГРАФН (57) Изобретение относится к вычислительной технике, может быть использовано при автоматизированном решении задач компоновки элементов радиоэлектронной аппаратуры в блоки. Целью изобретения является расширение функциональных возможностей устройства за счет обеспечения возможности разбиения графа на минимально связанные подграфы. Устройство обеспечивает возможность задавать объемы подграфов и определять вершины, обладающие максимальным числом связей с вершинами, включенными в формируемый подграф.

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

1 13323

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

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

В состав устроиства входит матрич- 15 ная модель 1 графа, содержащая Т строк и М столбцов триггеров

2-1 1,..., 2-М,T и элементов И 31,1,..., 3-M,Т группу сумматоров

4-1, ..., 4-Т, группу элементов ИЛИ 2р

5-1,..., 5-M группу коммутаторов

6-1,..., 6-М, группу триггеров l-l„..., 7-М, группу элементов

HE 8-1,..., 8-М, дешифратор 9, первый счетчик 10, элемент 11 задержки, 25 элемент И )2, генератор 13 тактовых импульсов, вход 14 задания количества вершин в подграфе устройства, шифратор 15, второй счетчик 16, выход

)7 признака выделения дерева с за- зО данным количеством вершин устройства, два коммутатора 18 и 19, шесть ключей 20 ... 25, элементы ИЛИ 26, схема 27 сравнения, блок 28 памяти, два регистра 29 и 30, входы 31-1,..., З6

31-М задания начальной вершины первого подграфа устройства.

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

Первоначально в нулевое состояние приводятся все триггеры 7-1,..., 7-M группы, счетчики 10 и 16, регистры

29 и 30, блок 28 памяти, ключи 20—

23 закрыты, ключ 24 открыт, коммутаторы 6-1,..., 6-М устанавливаются в 4 состояние, при котором их выходы подключе ы к выходам соответствующих триггеров 7-1,..., 7-М. Информация о топологии моделируемого графа заносится путем установки соответствую- 60 щих триггеров 2-1,..., 2-M в единичное состояние. Соответствующий триггер 2-кр (к,р=l,...,М) формирователя дуги определяется пересечением К-й строки (К-номер начальной вершины модулируемой ветви графа) с р-м столбцом (р-номер конечной вершины моделируемой ветки графа). Задание начальной вершины первого подграфа

29 2 осуществляется подачей на соответствующий вход 31 единичного сигнала, который, проходя через элемент

ИЛИ 5, поступает на вход шифратора

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

ИЛИ 5 устанавливает в единичное состояние триггера 7-К, обеспечивая тем самым возможность для прохождения с выхода триггеров 2-К1,..., 2-К,М сигнала матричной модели графа, соответствующей начальной вершине на сумматоре 4-К, а также запрещает выбор строки, соответствующей начальной вершине в качестве кандидата на включение в первый подграф. Последнее достигается за счет инвертирования в элементе НЕ 8-К сигнала с выхода триггера 7-К, соответствующего включенной в первый подграф начальной вершине. Следствием этих действий является формирование на выходе К-го сумматора 4-К (К-не равно номеру начальной вершины) двоичных кодов количества связей К-й вершины с включенной в первый подграф начальной вершиной. Тактовые импульсы от генератора 13 через открытый ключ 24 обеспечивают последовательное подключение к выходам схемы 27 сравнения и ключа 25 выходов сумматоров

4-К, а также синхронное подключение к одному из входов элемента 12-M c помощью коммутатора 18 выходов элементов НЕ 8-К. Кроме того, тактовые импульсы поступают на счетчик 16, на вьгходе которого образуется двоичный код номера импульса в интервале от до М (код номера аннулируемой вершины), схема 27 производит равнение содержимого регистра 30 с содержимым подключенного через коммутатор 19 сумматора 4-К . Если первое оказывается меньше второго и вершина, соответствующая подключенному сумматору 4-К еще не включена в формируемый подграф (на выходе соответствующего элемента HE 8-К отсутстз 133 вует единичный сигнал), то сигнал с выхода блока 27 после прохождения через элемент И 12 разрешает запись в регистр 30 содержимого подключенного к блоку 27 сумматора 4-К. Одновременно сигнал с выхода блока 27 разрешает запись в регистр 29 через ключ 23 двоичного кода номера соответствующей вершины графа. После завершения цикла просмотра всех М вершин в регистре 30 присутствует максимальное значение количества связей одной из вершин, не включавшихся ранее в первый подграф, а в регистре 29 зафиксирован двоичный код номера этой вершины. Факт окончания этого цикла фиксируется счетчиком 16, который формирует на выходе признака переполнения сигнал. разрешающий передачу из регистра 29 в дешифратор 9 кода номера вершины, максимально связанной с вершинами, включенными в формируемый подграф.

Этот же сигнал после задержки в элементе 11 на время, необходимое для передачи информации из регистра 29 в дешифратор 9 осуществляет обнуление содержимого регистров 29 и 30, а также счетчика 16. Поступивший в дешифратор 9 код вершины преобразуется в сигнал на одном из его выходов, который после прохождения через элемент ИЛИ 5 устанавливает один из триггеров 7-1,..., 7-M в единичное состояние, обеспечивая тем самым возможность для прохождения сигналов с выхода триггеров

2-1,..., 2M одного из столбцов матричной модели, соответствующего включенной в подграф вершине, на сумматор 4, а также запрещает выбор строки, соответствующей включенной вершине, в качестве кандидата на включение в подграф. По аналогии со случаем начальной вершины производится запись в блок 28 кода номера очередной включаемой в первый подграф вершины, а содержимое счетчика 10 увеличивается на единицу. Цикл работы устройства для выбора и включения в подграф последующих вершин аналогичен. Аналогично осуществляется задание начальной вершины подачей сигнала на один из входов 31 устройства. Если в первый подграф включено заданное количество вершин, то на выходе счетчика 10 формируется сигнал, поступающий на выход 17 устрой2329

55

30 ства и запрещающий прохождение тактовых импульсов от генератора 13, и разрешает прохождение через ключ

21 сигналов с выходов триггеров

7-1,..., 7-М на управляющие входы соответствующих коммутаторов 6-1,...

6-M. В этом случае коммутаторы

6-1,..., 6-М, на управляющие входы которых поступили единичные сигналы (коммутаторы, соответствующие включенным в первый подграф вершинам), устанавливаются в состояние, при котором к их выходам подключены выходы соответствующих элементов

8-1,..., 8-M НЕ, исключая тем самым . из рассмотрения при последующем анализе связи вершин 6, уже включенных в сформированный подграф. Для формирования второго подграфа в счетчике

10 устанавливается граничное значение, равное суммарному объему первого и второго подграфов. В этом случае сигнал на выходе счетчика 10 аннулируется открывая путь для прохождения по схеме устройства тактовых импульсов от генератора 13 и устройство функционирует аналогично случаю формирования первого подграфа. Результатом работы устройства является накопление в блоке 28 кедов номеров вершин в порядке-их включения в подграфы.

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

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

И и триггер, выход которого подключен к первому входу элемента И того же узла матричной модели графа, выходы всех элементов ИЛИ группы подключены к информационным входам соответствующих триггеров группы, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет возможности разбиения графа на минимально связанные подграфы, в него введены два коммутатора, группа коммутаторов, группа элементов НЕ, группа сумматоров, два регистра, элемент ИЛИ, второй счетчик, схема сравнения, шифратор, блок памяти и шесть ключей, 1332329 причем первые входы элементов ИЛИ группы являются входами задания начальной вершины первого подграфа устройства, выход К-ro элемента ИЛИ группы (К-1,..., M, где М вЂ” количест5 во вершин в моделируемом графе) подключен к К-му информационному входу шифратора, информационный выход которого подключен к информацинному входу 10 первого ключа, выход которого подключен к информацинному выходу блока памяти, информационный вход первого счетчика является входом задания количества вершин в подграфе устройст- 15 ва, выход признака переполнения первого счетчика подключен к управляющим входам второго и третьего ключей и является выходом признака выделения дерева с заданным количеством вершин устройства, выход элемента ИЛИ подключен к управляющему входу первого ключа к счетному входу первого счетчика и к входу пуска генератора тактовых импульсов, выход которого 25 подключен к информационному входу третьего ключа, выход которого подключен к управляющим входам первого и второго коммутаторов и к счетному входу второго счетчика, информацион- дд ный выход которого подключен к информационному входу четвертого ключа, выход которого подключен к информационному входу первого регистра, выход которого подключен к информационному входу пятого ключа, выход которого подключен к информационному вхоо ду дешифратора, К-й выход которого подключен к второму входу К-ro элемента ИЛИ группы, выход К-го тригге- 4п ра группы подключен к К-му информационному входу второго ключа, к первому информационному входу К-ro коммутатора группы и к входу К-го элемента НЕ группы, выход которого подключен к второму информационному входу К-го коммутатора группы, к К-му информационному входу первого коммутатора и к вторым входам элементов 1 всех узлов К-й строки матричной модели графа, выход К-го коммутатора группы подключен к третьим входам элементов И всех узлов К-го столбца матричной модели графа, выход элемента И К-ro узла P-й строки матричной модели графа(Р=1,..., М) подключен к входу К-го слагаемого P-го сумматора группы, выход которого подключен

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

1332329

Составитель А.Мишин

Техред Л.Сердюкова

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

Корректор И.Иуска

Заказ 3834/45

Тираж 672

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1!3035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

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