Устройство для определения изоморфизма графов

 

Союз Советских

Социалистических

Республик

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (1 596951 (61) Дополнительное к авт. свид-ву— (22) Заявлено 16.02.76 (21) 2323377/18-2 с присоединением заявки №(23) Приоритет— (43) Опубликовано 05.03.78. Бюллетень №9 (45) Дата опубликования описания 25.02. 78 (51) М. Кл.

G- 06 F 15/20

Государственный комитет

Совета Министров СССР по делам иэооретений и открытий (53) УДК681.3 (088.8) (72) Авторы изобретения

В. М. Курейчик, В. А. Калашников и А. Г. Королев (71) Заявитель

Таганрогский радиотехнический институт им. В, Д. Калмыкова (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ИЗОМОРФИЗМА ГРАФОВ

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

Известно устройство для исследования связности графов, содержащее матрицу памяти, входные и выходные элементы (11.

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

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

Однако это известное устройство имеет недостаточное быстродействие при определении изоформизма двух графов.

Целью изобр«т««ия является повышение быстродействия устройства.

Для этого в устрой«тво.введе«ы два блока определсния равных локальн!.!х степе«си, гр«тий и четвертый коммутаторы, два узла выделения крайней единицы, причем ьь!ход ««рвого регистра соединен « в.;одом первого узла выделения крайней еди«ицы. выход которого соед«нен с первыг««входами второго, третьего и четвертого коммутаторов. первого блока onpet0 деления равных локальных степ««ей, вторым входом третьего регистра «ч«тв«ртым входом первого регистра, пятый вход которо!ч! «о«ди«е«с выходом третье!.о рег;!стра и вторым входом третьего коммутатора, выход которого соединен с третьим входом блока памяти, ч«твертый вход которого соединен «выходом второго узла выделен«я крайней еди«ицы, с вторыми входами второго регистра и первого коммутатора и с первым входом второго блока определения рав«ых локальных степенен, второй вход которого соеди«ен «выходом первого коммутатора и вторым входом первого блока определения равных локаль«ых степеней, третьи h четвертые входы бг!оков опредег!ен!!я г!окальных степеней соединены соответственно с HLlxoдами четвертого и второго коммутаторов, пер25 вый и второй выходы первого блока определе59695!

15 ения графов и матрицы смежности первого и второго графов.

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

По сигналам с регистра 4 опрашивается блок 1 и образующаяся дизъюнкцпя разрядов

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

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

На чертеже приведена структурная электрическая схема устройства.

Устройство для определения изоморфизма графов содержит блок памяти 1, регистры 2 — 4, буферный регистр 5, коммутаторы 6 — 9, блоки

10 и 11, предназначенные для определения равных локальных степеней, узлы 2 и 13, предназначенные для выделения крайней единицы, узел

14 для выделения минимального подмножества, выходы 15 и 16 устройства, вход 17 устройства.

Узел !4 для выделения минимального подмножества содержит счетчик 18, регистр 19 и элемент знака разности 20. Каждый из блоков

10 и 11 для определения равных локальных степеней содержит узел памяти 21, узел 22 счетчиков и элемент сравнения 23.

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

Перед работой устройства производится занесение исходной информации в блок 1 и узлы

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

В результате в блоке 1 и узлах 21 блоков

10 и 11 запишутся матрица исходного разби20

40 бранных ранее подмножеств. Г1ри этом проводится последовательный опрос строк узлов

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

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

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

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

Постановка изоморфизма содержится в блоке

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

Для каждого из подмножеств определяется

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

Далее в выбранных подмножествах каждого графа выделяется по одной вершине, которые предполагаются изоморфными, что осуществляется с помощью узлов 12 и !3 и коммутаторов

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

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

Лучшие известные алгоритмы имеют оценку временных затрат Q =Вп4, где  — константа.

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

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

15 ства будет окупаться в течение года за счет экономии машинного времени 3ВМ типа ЕС-1020.

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

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

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

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

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

596951

Ш-!ИИ!!!! Государственного комитета Совета Министров CCCP по делам изобретений и открытий

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

Филиал ППГ1 «Патент», г. Ужгород, ул. Г1роектная, 4

Редактор A. Зиньковский

Заказ 1141/47

Составитель T. Арешев

Техред О. Луговая Корректор А. Грииенк

Тираж 826 Подписное