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

 

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

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

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

РЕСПУБЛИК ()9) ((() (я)ю G 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4632444/24 (22) 04.01.89 (46) 07.02,92. Бюл. N- 5 (71) Таган рагс кий радиотехнический и нститут им. В.Д.Калмыкова (72) В.М.Глушань, В,М.Курейчик, Н,Н,Рябец и Л.И.Щербаков (53) 681,333(088,8) (56) Авторское свидетельство СССР

¹ 732879, кл. G 06 F 15/20, 1977.

Авторское свидетельство СССР № 1645970 кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

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

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

3,5 заносят информацию о топологии графов, приводят в исходное состояние блоки

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

11 устройства формируется подставка изоморфизма (соответствие номеров вершин графов). 2 ил.

1711187

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

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

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

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

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

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

7 перечисления перестановок.

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

"0" — дуги в первом графе). Одновременно двухканальный блок 6 коммутации выдает на свои выходы каналов информацию, поступившую на входы каналов с учетом переадресации каждого информационного входа каналов (тем самым осуществляется перенумерация вершин второго графа), При этом второй блок 5 задания матрицы смежности выдает на свой выход значение элемента матрицы, находящегося на пересечении опрошенных строки и столбца (признак отсутствия или наличия дуги во втором графе). Через время, достаточное для окончания указанных процессов, блок 1 синхронизации снимает потенциал уровня

55 логической единицы со своего выхода 9 и формирует потенциал уровня логической единицы на выходе 10. При этом блок 4 сравнения сравнивает поступившую на его входы информацию и формирует на своем выходе значение признака неравенства.

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

Через время, достаточное для выполнения указанныхопераций, блок 1 синхронизации снимает потенциал уровня логической единицы с выхода 10 и формирует потенциал уровня логической единицы на выходе 11.

Далее работа устройства повторяется. В том случае, если два исследуемых графа изоморфны, то сигнал уровня логической единицы на выходе блока 4 сравнения появляться не будет (что означает, что при выбранной нумерации вершин второго графа все дуги, соединяющие вершины, с одинаковыми номерам n B первом и втором графах либо одновременно отсутствуют, либо имеются). При этом коды на выходах 11 устройства определяют подстановку изоморфизма (т,е. соответствие номеров вершин), В том случае, если графы не изоморфны, то после перебора всех возможных перестановок блок 7 может сформировать признак отсутствия свободных перестановок, который будет являться признаком отсутствия решения.

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

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

Фиг, 2

40 45

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

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

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

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

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

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

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