Устройство для решения задач на графах

Устройство для решения задач на графах

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для исследования связности графов. Целью изобретения является расширение функциональных возможностей устройства за счет разбиения множества вершин графа на подможества вершин одного поколения. Устройство содержит накапливающий блок логического сложения, блок 2 задания матрицы смежности, блок 3 определения полустепеней захода, блок 4 регистрации матрицы расслоения, блок 5 синхронизации, вход 6 пуска устройства, первый и второй выходы 7 и 8 блока 5 синхронизации, выходы 9 группы блока 5 синхронизации и выход 10 признака окончания работы устройства. Установив в "0" разряды блока 3, в блок 2 заносят информацию о топологии графа. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок 5 синх0ронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой в блоке 4 фиксируются все слои вершин одного поколения. 2 ил.

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИК

„„SU„, 1587534

А1 (Я)5 С 0

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

Н АВторСКом свиДКткльСтВЬ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯЩ

flPH ГКНТ СССР

1 (21) 4374149/24-24 (22) 01.02.88 (46) 23.08.90. Бюл. ¹ 31 (71) Московский институт радиотехники, электроники и автоматики (72) А.Н.Романов, О.А.Славин и М.В.щеглова (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 1238099, кл. G 06 F 15/20, 1984.

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

¹ 1513470., кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

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

Устройство содержит накапливающий блок логического сложения, блок 2 задания матрицы смежности, блок 3 определения полус тепе ней з ах ода, блок

4 регистрации матрицы расслоения, блок 5 синхронизации, вход 6 пуска устройства, первый и второй выходы

7 и 8 блока 5 синхронизации, выходы

9 группы блока 5 синхронизации и выход 10 признака окончания работы устройства» Установив в "0" разряды блока 3, в блок 2 заносят информацию о топологии графа. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок

5 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы,под управлением которой в блоке 4 фиксируются все слои вершин одного поколения. 2 ил.

1587534

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

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

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

Устройство содержит накапливающий 15 блоК 1 логического сложения, блок 2 задания матрицы смежности, блок 3 определения полустепеней захода, блок

4 регистрации матрицы расслоения, блок

5 синхронизации, вход 6 пуска устройст-20 ва, первый и второй выходы 7 и 8 блока 5 синхронизации, выходы 9 группы блока 5 синхронизации и выход 10 признака окончания работы устройства, Устройство работает следующим образом.

Пусть необходимо разбить все вершины графа (без циклов и петель) на слои таким образом, чтобы вершиныпредки и вершины-потомки оказались 30 в различных слоях (подмножества,множества вершин графа) или, другими словами, чтобы каждый слой содержал вершины одного поколения.

Перед началом работы устанавлива.ЭЭ ют в ноль разряды блока 3, в блок 2 заносят информацию о топологии графа. При этом блок 3 выдает на свои выходы состав вершин, полустепени захода которых равны нулю (т.е. состав 40 вершин не имеющих предков). На вход

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

9 группы блока 5 синхронизации. При этом блок 4 регистрации подготавлива- 50 ется к записи первой строки матрицы расслоения (первого слоя вершин).

Через время, достаточное для окончания операции определения полустепеней захода, блок 5 синхронизации формирует импульс уровня логической единицы на выходе 7. При этом блок

4 фиксирует данные, поступившие на

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

его информационный вход. Через время, достаточное для выполнения укаэанных операций, блок 5 снимает потенциал уровня логической единицы с первого выхода 9 и формирует импульс уровня логической единицы на выходе 8. При этом блок 10 фиксирует на своем выходе накопленное значение. При этом блок 2 задания матрицы смежности устанавливает в ноль (удаляет) столбцы матрицы смежности, а блок 3 определения полустепеней захода блокирует опрос тех вер-. шин, соответствующие которым разряды информационного выхода 1О блока установлены в единицу (тем самым удаляются дуги, исходящие иэ вершин вошедших во все уже выделенные слои, и запрещается определение полустепени захода для этих вершин) . При этом блок 3 выдает на свои выходы состав вершин, полустепени захода которых равным единице. Далее блок 5 синхронизации выдает потенциал уровня логической единицы на второй выход 9, и работа устройства повторяется. После того, как все слои вершин будут найдены, на выходе 10 признака окончания работы устройства появится потенциал уровня логической единицы.

При этом в блоке 4 регистрации будут зафиксированы все: слои вершин одного поколения.

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

Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок синхронизации и блок регистрации матрицы расслоения,. причем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к входу признака записи блока регистрации матрицы расслоения, P-й выход группы блока синхронизации (Р = 1,..., С, где С вЂ” количество слоев в графе) подключен к P-му адресному входу блока регистрации матрицы расслоения, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет разбиения множества вершин графа на подмножества вершин одного поколе1587534

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

Редактор С.Патрушева Техред А. Кравчук. Корректор М, Кучерявая

Заказ 2422 Тираж 568 Подписное НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С

СССР

113035, Ъэсква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г.ужгород, у ю tl л. Гага ина 101

P ф ния, в него введены блок определения полустепеней захода и накапливающий блок логического сложения, причем первый выход блока синхронизации подключен к тактовому входу накапливающего блока логического сложения, К-й разряд информационного выхода которого (К = 1, ...,В, где  — количество вершин в графе) подключен к входу блокировки опроса К-й вершины блока определения полустепеней захода и к входу признака удаления (К-го столбца блока задания матрицы смежности, выход признака наличия (К,М)го элемента которого (M = 1,...,B) подключен к входу признака наличия (К,М)-й дуги блока определения полустепеней захода, выход признака равенства нулю полустепени захода (К-й

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