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

Союз СоветскихСоциалистическихРеспублик П ИСАН БРЕТЕН 11 596951 И АВТОРСКОМУ СВИДЕТЕЛЬСТВ Дополнительное к авт. свид-в Заявлен.02.76 (21) 2323377/18-2 51) М, Кл,2 6- 06 Р 15/2 исоединением заявкиГосударственный комитет Совета Министров СССР по делам иэооретений и откРытий(45) Дата опубликования описания 25.02.78 3) УДК 681.3 088.8), М, Курейчик, В. А. Калашников и А олев 71) Заявитель аганрогский радиотехнический инсти, В. Д. мыко Целью изобртия является повышение быстродействия устройства.Для этого в устройтво.введеы два блока определсния равных локальых степеси, гр- тий и четвертый коммутаторы, два узла выделения крайней единицы, причем ьыход рвого регистра соединес входом первого узла выделения крайней едиицы, выход которого соед- нен с первыгвходами второго, третьего и четвертого коммутаторов. первого блока определения равных локальных степей, вторым входом третьего регистра птвртым входом первого регистра, пятый вход которого одиес выходом третьего регистра и вторым входом третьего коммутатора, выход которого соединен с третьим входом блока памяти, птвертый вход которого содине выходом второго узла выделения крайней едиицьк с вторыми входами второго регистра и первого коммутатора и с первым входом второго блока определения равых локальных степенеи, Второи вход которого соедиен с выходом первого коммутатора и вторым входом первого блока определения равных локальых степеней, третьи ь четвертые входы блоков определения локальных степеней соединены соответственно выходами четвертого и второго коммутаторов, первый и второй выходы первого блока определе(54) УСТРОЙСТВО ДЛЯ О Изобретение относится к вычислительной технике и может быть применено в электронике.Известно устройство для исследования связности графов, содержащее матрицу памяти, входные и выходные элементы 11.Однако известное устройство характеризуется йедостатопными функциональными возможностями и невысоким быстродействием.Наиболее близким по сущности техническим решением задачи является устройство дляопределения изоморфизма графов, содержащее блок памяти, три регистра, буферный регистр, два коммутатора, узел для выделения минимального подмножества, причем, выходы блока памяти соединены с первыми входами двух регистров, выход первого регистра соединен перез буферный регистр со своим вторым входом и с первым выходом устройства, выход второго регистра соединен с вторым выходом устройства, первые входы третьего регистра и первого коммутатора соединены с входом устройства, выход первого коммутатора соединен с первым входом блока памяти, выход второго коммутатора соединен с вторым входом блока памяти и третьим входом первого регистра 2.Однако это известное устройство имеет недостаточное быстродействие при определении изоформизма двух графов. НИЯ ИЗОМОРФИЗМА ГРАФОВ59695 1 О 15 ения графов и матрицы смежности первого и второго графов.45Далее производится формирование пеотмеченного подмножества предполагаемого изоморфных вершин исследуемых графов.По сигналам с регистра 4 опрашивается блок 1 и образующаяся дизъюнкцпя разрядов50 строк инвертируется и записывается в регистр 3, Если в регистре 3 не окажется ни одной единицы, то производится ветвление какого-либо из подмножеств. По сигналу с узла 13 выбирается соответствующий столбец блока 1 и запоминается в регистре 2. Сигнал с узла 12 через коммутатор 8 выделяет строку в блоке 1 которая запоминается в регистре 3. Первая вершина, отмеченная единицей в регистре 3 огмечается также в регистре 4.Далее производится формирование частных локальных степенеи вершин относительно вынбО ния равных локальных степеней соединен.ы соответственно с вторыми входами второго и четвертого коммутаторов, выход второго блока определения равных локальных степеней соединен с третьим входом первого коммутатора, второй выход второго узла выделения крайней единицы соединен с входом узла выделения минимального подмножества, причем каждый блок определения равных локальных степеней содержит узел памяти, узел счетчиков и элемент сравнения, первый вход которого соединен с третьим входом блока, а второй входс выходом узла счетчиков, вход которого соединен с выходом узла памяти, первый, второй и третий входы которого соединены соответственно с первым, вторым и четвертым входами олока, причем, в первом блоке выход элемента сравнения и второй выход узла счетчиков соединены соответственно с первым и вторым выходами блока, а во втором блоке выход элемента сравнения соединен с выходом блока,На чертеже приведена структурная электрическая схема устройства.Устройство для определения изоморфизма графов содержит блок памяти 1, регистры 2 - 4, буферный регистр 5, коммутаторы 6 - 9, блоки 10 и 11, предназначенные для определения равных локальных степеней, узлы2 и 13, предназначенн 1 ле для выделения крайней единицы, узел 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 запишутся матрица исходного разби 20 25 30 35 40 бранных ранее подмножеств. Г 1 ри этом проводится последовательный опрос строк узлов 21 блоков 10 и 11, входящих в выделенное подмножество. Результаты опроса фиксируются в узлах 22 блоков 10 и 11. Затем формируются группы вершин с равными локальными сгспенями. Г 1 ри этом в узлах 23 блоков 10 и 11 формируется код, в котором единицами отмечены вершины, образующие группу с данной локальной степенью. Эти коды через коммутаторы 6 и 7 поступают в блок 1. При этом получается новое разбиение предполагаемого чзоморфизма вершин. Далее производится формирование нового неотмеченного подмножества.Если числа вершин в выделенных подмножествах не равны, то проводится выбор ново о варианта ветвления, Если новый вариант ветвления выбрать невозможно, то графы не изоморфны.Среди отмеченных подмножеств выбирают минимальное по мощности, содержащее более одной вершины. Если все подмножества содержат по одной вершине, то графы изоморфны Постановка изоморфизма содержится в блоке 1.-.Йри этом содержимое регистра 4 переписывается в регистр 2 и проводится последовательное формирование каждого отмеченного подмножества в регистре 3 через блок 1 с помощью узл а 12 и ком мутатора 8.Для каждого из подмножеств определяется его число вершин с помощью узлов 13 и 14 и выделяется минимальное подмножество (элемент 20 сравнивает содержимое счетчика 18 и регистра 19 и фиксирует в регистре 19 меньшее значение) . Метка выделенного подмножества запоминается в регистре 5.Далее в выбранных подмножествах каждого графа выделяется по одной вершине, которые предполагаются изоморфными, что осуществляется с помощью узлов 12 и 3 и коммутаторов 6 и 7, изменяющих содержимое блока 1. Информация из блока 1 и регистров 2 - 4 передается на выходы 15 и 16 устройства.Далее производится формирование нового неотмеченного подмножества. Алгоритм, положенный в основу устройства, обладает практически всеми качествами лчших известных алгоритмов, а при реализации на ЭВМ обеспечивает временные затраты Я Ап, где А - константа, а пчисло вершин графа.Лучшие известные алгоритмы имеют оценку временных затрат Я:Вп 4, где В - константа. Реализации алгорю ма в предлагаемом специализированном устройстве позволяет обеспечить временные затраты Я-Си, где С - константа. Таким образом, в основу функционирования устройства положен наиболее совершенный алгоритм распознавания изоморфизма. Само устройство позволяет достичь более высокого быстродействия, чем любое другое. Устройство также обеспечивает существенно лучшие временные характеристики,чем ЭВМ, как за счет распараллеливания процесса, так и за счет специализированного состава оборудования. Ориентировочные расчеты позволяют ожидать, что при потоке задач порядка 1000 и более в год и при размере графов в несколько сотен вершин, применение серийно изготавливаемого устрой 596951ства будет окупаться в течение года за счет эко номии машинного времени ЭВМ типа ЕС. Форлгула изобретенггя1. Устройство для определения изоморфизма графов, содержащее блок памяти, три регистра, буферный регистр, два коммутатора, узел выделения минимального подмножества, причем выходы блока памяти соединены с первыми входами двух регистров, выход первого регистра соединен через буферный регистр со своим вторым входом и с первым выходом устройства, выход второго регистра соединен с вторым выходом устройства, первые входы третьего регистра и первого коммутатора соединены с входом устройства, выход первого коммутатора соединен с первым входом блока памяти, выход второго коммутатора соединен с вторым входом блока памяти и третьим входом первого регистра, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены два блока определения равных локальных степеней, третий и четвертый коммутаторы, два узла выделения крайней единицы, причем выход первого регистра соединен с входом первого узла выделения крайней единицы, выход которого соединен с первыми входами второго, третьего и четвертого коммутаторов, первого блока определения равных локальных степеней, вторым входом третьего регистра и четвертым входом первого регистра, пятый вход которого соединен с выходом третьего регистра и вторым входом третьего коммутатора, выход которого соединен с третьим входом блока памяти, четвертый вход которого соединен с выходом второго узла выделения крайней единицы, с вторыми входами второго регистра и первого коммутатора и с первым входом второго блока определения равных локальных степеней, второй вход которого соединен с выходом первого коммутатора и вторым входом первого блока определения равных локальных степеней, третьи и четвертые входы блоков определения локальных степеней соединены соответственно с выходами четвертого и второго коммутаторов, первый и второй выходы первого блока определения равных локальных степеней соединены соответственно с вторыми входами второго и четвертого коммутаторов, выход второго блока определенг 1 я равных локальных степеней соединен с третьим входом первого коммутатора, второй выход второго узла выделения крайней единицы соединен с входом узла выделения минимального подмножества.2. Устройство по п. 1, отличающееся тем, что каждый блок определения равных локальных степеней содержит узел памяти, узел счетчиков и элемент сравнения, первый вход которого соединен с третьим входом блока, а второй вход - с выходом узла счетчиков, вход которого соединен с выходом узла памяти, первый, второй и третий входы которого соединены соответственно с первым, вторым и четвертым входами блог(а, причем, в первом блоке выход элемента сравнения и второй выход узла счетчиков соединены соответственно с первым и вторым выходами блока, а во втором блоке выход элемента сравнения соединен с выходом блока.Источники информации, принятые во внимание при экспертизе:1. Авторское свидетельство СССР468244, кл. Сг 06 Г 15/20, 1972.2. Шейнаускас Р. И. Алгоритм установления изоморфизма и изоморфного вхождения двух графов, в сб. Вычислительная техника, Каунас, т. 3, с. 347.596951 Составитель Т. АрТехред О. Луговая Тирак 826 митета Совета Министров СССР тоний и открытий Щ-Р 1 ИИ Государственного ко по делам изобр 113035, Москва, Жаушская наб., д. 45 город, ул. Гроектная илиал ППГ 1 Патент, г Редактор А. ЗиньковскийЗаказ 114147 ев Корректор А. Грииеик Подписное