Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

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

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

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

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

Блок 2 перечисления подмножеств вершин содержит группу из Я кольцевых регистров 9 сдвига, где Я - количество ярусов в графе, причем тактовый вход 10 блока 2 перечисления подмножеств вершин под- ключей к входу признака сдвига первого кольцевого регистра 9 сдвига, выход Т(Р)-го разряда Р-го кольцевого регистра 9 сдвига

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

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

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

ярусов в графе; Т(Р)1ВЯ(Р), где ВЯ(Р) количество вершин в Р-м ярусе графа).

На вход 6 пуска устройства подают импульс уровня логической единицы. Блок 1

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

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

матрицы смежности ( ,...В, где

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

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

0

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

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

52J-

j

-JT9ft 12

Фиг.2