Устройство для определения изоморфизма графов Советский патент 1978 года по МПК G06F15/173 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ИЗОМОРФИЗМА ГРАФОВ

ния равных локальных степеней соединет 1 соответственно с вторыми входами второго и четвертого коммутаторов, выход второго блока определения равных локальных степеней соединен с третьим входом первого коммутатора, второй выхОлТ, второго узла выделения крайней единицы соединен с входом узла выделения минимального подмножества, причем каждый блок определения равных локальных степеней содержит узел памяти, узел счетчиков и элемент сравнения, первый вход которого соединен с третьим входом блока, а второй вход - с выходом узла счетчиков, вход которого соединен с выходом узла намяти, первый, второй и третий входы которого соединены соответственно с первым, вторым и четвертым входами 6,юка, причем, в первом блоке выхо/а элемента сравнения и второй выход узла счетчиков соеллнены соответственно с первым и вторым выходами блока, а во втором блоке выход элемента сравнения соединен с выходом блока.

На чертеже приведена структурная электрическая схема устройства.Устройство для определения изоморфизма графов содержит блок памяти 1, регистры 2-4, буферный регистр 5, коммутаторы 6-9, блоки 10 и I 1, предназначенные для определения равных локальных степеней, узлы 12 и 13, предназначенные для выделения крайней единицы, узел 14 для выделения минимального подмножества, выходы 15 и 16 устройства, вход 17 устройства.

Узел 14 для выделения минимального подмножества содержит счетчик 18, регистр 19 и элемент знака разности 20. Каждый из блоков 10 и 11 для определения равных локальных степеней содержит узел па.мяти 21, узел 22 счетчиков и элемент сравнения 23.

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

Перед работой устройства производится занесение исходной информации в блок 1 и узлы 21 блоков 10, 11 с помощью регистра 2 (в котором в начальный момент содержатся единицы в каждом разряде) и узла 12 (который носледовательно выделяет крайнюю единицу, что соответствует но.меру строки в блоках памяти). Информация поступает с входа 17 устройства через коммутатор 6.

В результате в блоке 1 и узлах 21 блоков 10 и 11 запишутся матрица исходно о разбиения графов и матрицы смежности первого и второго графов.

Далее производится формирование неот.меченного подмножества предполагаемого изо.морфных верфин исследуемых графов.

По сигналам с регистра 4 опрашивается блок 1 и образующаяся дизъюнкция разрядов строк инвертируется и записывается в регистр 3. Если в регистре 3 не окажется ни одной единицы, то производится ветвление какого-либо из подмножеств. По сигналу с узла 13 выбирается соответствующий столбец блока 1 и запоминается в регистре 2. Сигнал с узла 12 через коммутатор 8 выделяет строку вблоке 1 которая запоминается в регистреЗ. Первая вершина, отмеченная единицей в регистре 3 отмечается также в регистре 4.

Далее производится формирование частных

о

локальных степенен вершин относительно выбранных ранее подмножеств. При этом проводится последовательный опрос строк узлов 21 блоков 10 и 11, входящих в выделенное подмножество. Результаты опроса фиксируются в узлах 22 блоков 10 и 11. Затем формируются гругшы вершин с равными локальными степенями. При этом в узлах 23 блоков 10 и 11 формируется код, в которо.м единицами отмечены вершины, образующие груину с данной локальной степенью. Эти коды через коммутаторы 6 и 7 поступают в блок 1. При это.м получается новое разбиение преднолагае.мого изоморфизма вершин. Далее производится формирование нового неотмеченного подмножества.

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

Среди отмеченных под.множеств выбирают минимальное но .мощности, содержащее более одной вершины. Если все подмножества содержат по одной вершине, то графы изоморфны Постановка изоморфизма содержится в блоке 1.-Лри это.м содержимое регистра 4 переписывается в регистр 2 и проводится последовательное фор.мирование каждого от.меченного под.множества в регистре 3 через блок 1 с помощью узла 12 и коммутатора 8.

Для каждого из подмножеств определяется его число вершин с помощью узлов 13 и 14 и выделяется мини.мальное подмножество (элемент 20 сравнивает содержимое счетчика 18 и регистра 19 и фиксирует в регистре 19 меньшее значение). Метка выделенного подмножества запоминается в регистре 5.

Далее в выбранных подмножествах каждого графа выделяется по одной верщине, которые предполагаются изоморфны.ми, что осуществляется с помощью узлов 12 и 13 и коммутаторов 6 и 7, изменяющих содержимое блока I. Инфор.мация из блока 1 и регистров 2-4 передается на выходы 15 и 16 устройства.

Далее производится формирование нового неотмеченного под.множества. Алгорит.м, положенный в основу устройства, обладает практически всеми качествами лучших известных алгоритмов, а при реализации на ЭВМ обеспечивает вре.менные затраты , где А - константа, а л - - число вершин графа.

Лучшие известные алгоритмы имеют оценку временных затрат , где В -константа. Реализации алгоритма в предлагаемо.м специализированном устройстве позволяет обеспечить временные затраты , где С - константа. Таким образо.м, в основу функционирования устройства положен наиболее совершенный алгорит.м раснознавания изо.морфизма. Само устройство позволяет достичь более высокого быстродействия, чем любое другое. Устройство также обеспечивает существенно лучшие вре.меннь е характеристики,чем ЭВМ, как за счет распараллеливания процесса, так и за счет специализированного состава оборудования. Ориентировочные расчеты позволяют ожидать, что при потоке задач порядка 1000 и более в год и при раз.мере графов в несколько сотен вершин, при.менение серийно изготавливаемого устройства будет окупаться в течение года за счет экономии машинного времени ЭВМ типа ЕС-1020.

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

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

2. Устройство по п. 1, отличающееся тем, что каждый блок определения равных локальных стененей содержит узел памяти, узел счетчиков и элемент сравнения, первый вход которого соединен с третьим входом блока, а второй вход - с выходом узла счетчиков, вход которого соединен с выходом узла памяти, первый, второй и третий входы которого соединены соответственно с первым, вторым и четвертым входа.ми блока, причем, в первом блоке выход 5 элемента сравнения и второй выход узла счетчиков соединены соответственно с первы.м и вторым выходами блока, а во втором блоке выход элемента сравнения соединен с выходом блока.

Источники информации, принятые во внимание при экспертизе:

. .Авторское свидетельство СССР № 468244, кл. G 06 F 15/20, 1972.

2. Шейнаускас Р. И. Алгоритм установления изоморфизма и изоморфного вхождения двух , графов, в сб. «Вычислительная техника, Каунас, т. 3, с. 347.