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

 

Изобретение относится к вычислительной технике и может быть использовано для исследования связности графов. Целью изобретения является расширение функциональных возможностей устройства за счет перечисления маршрутов в ярусно-параллельном графе. Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств вершин, блок 3 проверки связности вершин, блок 4 задания матрицы смежности, блок 5 определения соединяющих дуг , вход 6 пуска устройства, выход 7 признака окончания списка маршрутов и выходы 8 признаков принадлежности дуг множеству дуг маршрута устройства. Перед началом работы в блок 4 заносят информацию о топологии графа. Приводят в исходное состояние блок 2. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок 1 формирует на своих выходах последовательность сигналов , предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устройства формируется состав дуг маршрута. 2 ил. w ё 00 00 АИ г Риг.1 8П 812 8№

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

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

РЕСПУБЛИК (51)5 G 06 F 15/419

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ется состав дуг маршрута. 2 ил. (21) 4663712/24 (22) 15.03.89 (46) 07.02.92. Бюл. М 5 (72) А.Ю,Лапин (53) 681.333(088.8) (56) Авторское свидетельство СССР

hb 1327126, кл, G 06 G 7/122, 1987.

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

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

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

„„ Ы„„1711188 Al синхронизации, блок 2 перечисления подмножеств вершин, блок 3 проверки связности вершин, блок 4 задания матрицы смежности, блок 5 определения соединяющих дуг, вход 6 пуска устройства, выход 7 признака окончания списка маршрутов и выходы 8 признаков принадлежности дуг множеству дуг маршрута устройства, Перед началом работы в блок 4 заносят информацию о топологии графа. Приводят в исходное состояние блок 2. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок 1 формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устройства формиру1711188

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

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

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

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

6 пуска устройства, выход 7 признака окончания списка маршрутов устройства и выходы 8 признаков принадлежности дуг множеству дуг маршрута устройства.

Блок 2 перечисления подмножеств вершин содержит группу из Я кольцевых регистров 9 сдвига, где Я вЂ” количество ярусов в графе, причем тактовый вход 10 блока 2 перечисления подмножеств вершин подключен к входу признака сдвига первого кольцевого регистра 9 сдвига, выход Т(Р)-го разряда Р-го кольцевого регистра 9 сдвига (Р=1,...,Я; Т(Р)=1,...,ВЯ(Р), где ВЯ(Р) — количество вершин в P-м ярусе графа) является выходом 11 признака принадлежности Т(Р)-й вершины текущему подмножеству блока 2 перечисления подмножеств вершин, выход признака переноса из ВЯ(Р)-го разряда Р-го кольцевого регистра 9 сдвига (Р=Я) подключен к входу признака сдвига (Р+1)-ro кольцевого регистра 9 сдвига, выход признака переноса из ВЯ(Я)-го разряда Я-го кольцевого регистра 9 сдвига является выходом 12 признака окончания списка подмножеств блока 2 перечисления подмножеств вершин, Устройс. ьо работает следующим образом.

Перед на-:ачом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа. На вход первого разряда первого регистра 9 группы подают сигнал уровня логической единицы, младшие (первые) разряды всех остальных регистров 9 устанавливают в единицу(при этом предполагается, что вершины графа перенумерованы таким образом, что существует соответствие между (К)-й (К=1,...,В, где В— количество вершин в графе) и T(P)-й вершинами графа (Р=1,.„,Я, где Я вЂ” количество ярусов в графе; Т(Р)=1, .„ВЯ(Р), где ВЯ(Р)— количество вершин в P-м ярусе графа), На вход 6 пуска устройства подают импульс уровня логической единицы. Блок 1 синхронизации формирует на своем первом выходе импульс уровня. логической единицы. Блок 2 перечисления подмножеств вершин формирует на своем выходе очередное (в первом такте — первое) подмножество множества вершин графа (после первого тактового импульса сигнал уровня логической единицы с входа первого разряда первого кольцевого регистра 9 группы необходимо снять). Через время, достаточное для окончания указанной операции, блок 1 синхронизации формирует импульс уровня логической единицы на своем втором выходе. Если все вершины, выбранные по входам опроса блока 3, связаны, то последний формирует сигнал уровня логической единицы на своем выходе признака связности. При этом блок 5 выдает на свои выходы состав дуг, соединяющих заданные концевые точки (т.е. вершины текущего подмножества). На этом работа устройства заканчивается. Если вершины, выбранные по входам опроса блока 3, не связаны, то последний формирует импульс уровня логической единицы на своем выходе признака отсутствия связности, При этом блок 1 синхронизации повторяет цикл из двух импульсов. Далее работа устройства повторяется либо до тех пор, пока не будет сформировано подмножество связных вершин, либо до окончания (исчерпывания) списка подмножеств.

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

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

 — количество вершин в рафе) подключен к входу признака наличия (К,М)-й дуги блока проверки связности вершин, о т л и ч а ющ o с я тем, что, с целью расширения фн кциональных возможностей устройства путем перечисления маршрутов в яруснопараллельном графе, в него введен блок определения соединяющих дуг, причем выход признака принадлежности К-й вершины текущему подмножеству блока перечисления подмножеств вершин подключен к входу задания К-й концевой точки блока определения соединяющих дуг и к входу опроса К вЂ” и вершины блока проверки связности вершин, выход признака отсутствия связности

1711188

Я N(1

2) r ВЯ(Я)

° Э °

° а ° 9 Q

luz.2

35

45

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

Редактор С.Патрушева Техред М.Моргентал Корректор Л.Патай

Заказ 342 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 которого подключен к входу повторного пуска блока синхронизации, выход значения (К,M-ro элемента блока задания матрицы смежности подключен к входу признака наличия (К,M)-й дуги блока определения соединяющих дуг, выход признака принадлежности(К,М)-й дуги множеству дуг, соединяющих концевые точки, которого является выходом признака принадлежности (К,М)-й дуги множеству дуг маршрута устройства, выход признака окончания списка маршрутов которого является выходом признака окончания списка подмножеств блока перечисления подмножеств вершин и

5 подключен к входу останова блока синхронизации, второй выход которого подключен к входу опроса блока проверки связности вершин, выход признака связности которого подключен к входу опроса блока опреде10 ления соединяющих дуг.