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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 711187 6 06 Р 15/41 САНИЕ ИЗОБРЕТЕНИЯ ехническ йчик, Н,Н нс ябец ЗАД лительзовано графа. ирение ойствд ов. УстГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРМ 732879, кл. 6 06 Р 15/20, 1977.Авторское свидетельство СССРМ 1645970 кл. 6 06 Р 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 ил,Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа.Цель изобретения - расширение функциональных возможностей устройства за счет проверки изоморфизма графов,На фиг.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синхронизации снимает потенциал уровня 5 10 15 20 25 30 35 40 45 50 55 логической единицы со своего выхода 9 и формирует потенциал уровня логической единицы на выходе 10. При этом блок 4 сравнения сравнивает поступившую на его входы информацию и формирует на своем выходе значение признака неравенства. При единичном значении признака неравенства блок 2 перечисления подмножества пар вершин устанавливается в исходное состояние, а блок 7 перечисления перестановок формирует на своих выходах значение очередной перестановки (тем самым изменяется нумерация вершин второго графа). Через время, достаточное для выполнения указанныхопераций, блок 1 синхронизации снимает потенциал уровня логической единицы с выхода 10 и формирует потенциал уровня логической единицы на выходе 11. Далее работа устройства повторяется. В том случае, если два исследуемых графа изоморфны, то сигнал уровня логической единицы на выходе блока 4 сравнения появляться не будет (что означает, что при выбранной нумерации вершин второго графа все дуги, соединяющие вершины, с одинаковыми номерами в первом и втором графах либо одновременно отсутствуют, либо имеются), При этом коды на выходах 11 устройства определяют подстановку изоморфизма (т,е. соответствие номеров вершин), В том случае, если графы не изоморфны, то после перебора всех возможных перестановок блок 7 может сформировать признак отсутствия свободных перестановок, который будет являться признаком отсутствия решения.Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, блок перечисления подмножества пар вершин, первый блок задания матрицы смежности и блок сравнения, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу блока пере-, числения подмножества пар вершин, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения проверки изоморфизма графов, в него введены второй блок задания матрицы смежности, двухканальный блок коммутации и блок перечисления перестановок, причем К-й выход позиции первого элемента подмножества (К" 1В, где В - количество вершин в графе) блока перечисления подмножества пар вершин подключен к входу опроса К-го столбца первого блока задания матрицы смежности и к К-му информационному входу первого канала двухканального блока коммутации, К-й ин.Пата аказ 342 Тираж Подписное В НИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 л. Гагарина, 101 водственно-издательский комбинат "Патент", г, Уж формационный выход первого канала которого подключен к входу опроса К-го столбца второго блока задания матрицы смежности, М-й выход позиции второго элемента подмножества (М=1, В) блока перечисления подмножества пар вершин подключен к М- му информационному входу второго канала двухканального блока коммутации и к входу опроса М-й строки первого блока задания матрицы смежности, выход значения (К, М)- го элемента которого подключен к первому информационному входу блока сравнения, второй выход блока синхронизации подключен к входу опроса блока сравнения, выход признака неравенства которого подключен к входу начальной установки блока перечисления подмножества пар вершин и к тактовому входу блока перечисления перестановок, выход кода позиции К-го элемен та которого является К-м выходом значенияподстановки изоморфизма устройства и подключен к входу задания направления переадресации К-х информационных входов каналов двухканального блока коммута ции, М-й информационный выход второгоканала которого подключен к входу опроса М-й строки второго блока задания матрицы смежности, выход значения (М,К)-го элемента которого подключен к второму информа ционному входу блока сравнения.