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

ИАТ" "-"Ф ттсСШР л-Л ОП ИСАЙИ Е ИЗОБРЕТЕН ИЯ Союз СоветскихСоциалистическихРеспублик и,732879 К АВТОЯСКОМУ СВИДЕТЕЛЬСТВУОпубликовано 05.05.80. Бюллетень % 17 ао делам иэобретеиий и открытийДата опубликования описания 06.05,80 А, Г, Королев, В, А, Калашников и В, М, Курейчик(72) Авторы изобретения Таганрогский радиотехнический институт им, В, Д, Калмыкова(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ИЗОМОРФИЗМА ОРИЕНТИРОВАННЫХ ГРАФОВУстройство относится к вычислительной технике и может быть применено вэлектронике.Известно устройство содержашеэ блоктриггеров, элементы И и ИЛИ 13Недостаток известного устройства 1невозможность решения задачи определения изоморфности графов,Наиболее близким по технической сущности к предлагаемому является устрой 1 оство, содержащее блоки памяти, коммутаторы, .блоки счетчиков, блоки сравнения, регистры, блоки. выделения крайнейединицы и.блок определения знака разности 2115Недостаток этого устройства - невозможность определения изоморфизмаориентированных графов,11 ель изобретения в . расширение функциональных возмсиностей за счет обеспечения учета направленности ребер графа,Поставленная цель достигается благодаря введению в устройство, содержа 2шее первый блок памяти, первый выход которого соединен с первым входом первого буферного регистра, выход которого подключен соответственно ко входам пер вого регистра, первого блока выделения крайней единицы, выход первого блока выделения крайней единицы соединен соответственно со вторым входом первого буферного регистра, с первым входом первого, второго и третьего коммутаторов, с первым входом второго буферного регистра и с первым входом второго блока памяти, первый выход которого соединен с первым входом первого блока счетчиков, выход которого подключен к первому входу первого блока сравнения и ко второму входу второго коммутатора, выход которого соединен со вторьгм входом первого блока сравнения и с первым входом второго блока сравнения, второй вход которого подключен квыходу второго блока счетчиков, вход которого соединен с первым выходом третьего блока памяти, первыйвход которого подклю7328чен соответственно к выходу третьего коммутатора и ко второму входу второго блока памяти, выход первого блока сравнения соединен со вторым входом третьегокоммутатора, выход которого подключен ктретьему входу первого буферного регистра и к первому входу первого блока памяти, второй выход которого соединен спервым входом третьего буферного регистра, выход которого соединен со входом второго блока выделения крайней единицы, первый выход которого подключенко второму входу третьего буферного регистра, ко второму входу первого блокапамяти, к первому входу четвертого коммутатора и ко второму входу третьегоблока памяти, выход четвертого коммутатора соединен соответственно с третьими входами первого, второго и третьего блоков памяти второй вход четвертого коммутатора подключен к выходу второго блока сравнения, второй вход четвертого коммутатора соединен со вторымвходом второго буферного регистра и является входом устройства, выход второго буФерного регистра подключен к чет-вертому входу первого буферного регистра и ко второму входу первого коммутатора, выход которого соединен с четвертым входом первого блока памяти, выходпервого регистра подключен к пятомувходу первого буферного регистра, второйвыход второго блока выделения крайнейединицы соединен со входом третьего блока счетчиков, выход которого подключенсоответственно к первому входу блокаопределения знака разности и ко входувторого регистра, выход которого соепинен со вторым входом блока определениязнака разности, выходы первого и третьего буферных регистров и второго блокасчетчиков являются соответственно выходами устройства, введен. третий регистр,причем вход третьего регистра соепиненс выходом третьего буферного регистра,выход третьего регистра подключен ктретьему входу третьего буферного регистра, выход первого блока выделения крайней единицы соединен с четвертым входом второго блока памяти, выход второго блока выделения крайнейединицы подключен к четвертому входутретьего блока памяти,На чертеже представлена схема предлагаемого устройства,Устройство содержит блок 1 памяти,буферные регистры 2, .3 и 4, регистр 5,коммутаторы 6 7, 8 и 9, блоки 10 и 7911 выделения крайней единицы, регистр 12, блок 13 сравнения, блок 14 счетчиков, выходы 15 и 16, вхоп 17, блок 18 счетчиков, регистр 19, блок 20 определения знака разности, блок 21 памяти, блок 22 счетчиков, блок 23 срав- . нения, блок 24 наличия. Устройство работает следующим образом,Перед работой устройства производится занесение исходной информации в блоки 1, 21 и 24 с помощью буферного регистра 2 (в котором в начальный моно выделяет крайнюю единицу, определяяномер строки в блоках памяти), Информация поступает со входа 17 устройствачерез коммутатор 6,В результате в блоках 1, 21 и 24,записываются матриды исходного разбиения графов и матрицы смежности первогои второго графов,далее производится формирование неотмеченного подмножества предполагаемоизоморфных вершин исследуемых графов,По сигналам от буферного регистра 4опрашивается блок 1 и образующаясядизъюжция разрядоВ строк инвертируетсяи записывается в буферный регистр 3,Если в регистре не оказывается ни однойединицы, то производится ветвление какого-либо из подмоножеств, По сигналу от блока 11 выбирается соответствующий столбец в 1 и запоминается в буферный регистр 2, Сигнал. от блока 10 через коммутатор 8 выделяет строку в блоке 1,которая запоминается в регистре 3, Первая вершина отмеченная единицей в буферный регистр 2, отмечается также в регистре 4, Содержимое буферных регистров 2 и 3 запоминается в регистрах 5 и 12,Далее производится формирование частных локальных степеней вершин относи - тельно выбранных ранее подмножеств по исходящим дугам, При этом проводится последовательный опрос строк блоков в 21 и 24, входящих в выделенное подмножество, Результаты опроса фиксируются в блоках 22 и 14, Затем формируются группы вершин с равными локальными степенями. При этом в блоках 13 и 23 формируется коп, в котором единицами отмечены вершины, образующие группу с данной локальной степенью. Эти коды через коммутаторы 6 и 7 поступают в блок 1, При этом получается новое разбиение предполагаемого изоморфизма, Затем возвращается в буферные регистры 27328и 3 содержимое регистров 5 и 12 и вы- .полняется формирование частных локальных степеней по входящим дугам. Приэтом аналогично проводится последовательный опрос столбцов блоков 21 и24, После получения нового разбиения,в буферные регистры 2 и 3 возврашаетсясодержимое буферных регистров и выполняется формирование частных локальныхстепеней по антипараллельным дугам. При 10этом, в отличие от предыдущего, в блоки 14 и 22 поступает пораэряднаяхоньюкция строк и столбцов, После измененийразбиения, производится формированиенового неотмеченного подмножества;15Если числавершин в выделенных подмножествах не равны, то проводится выбор нового варианта ветвления, Если новый вариант ветвления выбрать -невозможно, то графы не изоморфны,Если неотмеченных подмножеств нет,то выполняем ветвление, Среди подмножеств выбираем минимальное по мощности, содержащее более одной вершины,Если все подмножества содержат по одной25вершине, то графы изоморфны, Подстаножа изоморфизма определяется единицами блока 1, При выборе минимальногоподмножества, содержимое регистра 4 пе 30реписывается в регистр 2 и проводитсяпоследовательное формирование каждогоотмеченного подмножества в буферномрегистре 3 через блок 1 с помощью блока 10 и коммутатора 8,Для каждого из подмножества опре 35деляется его число вершин и выделяетсяминимальное подмножество с помощьюблоков 18,19 и 20,Далее в выбранных подмножествах.каждого графа выделяется по одной вершине, которые предполагаются изоморфными,(При выборе другого варианта ветвления,выбирается ранее не выбранная вершинавторого графа, Это осушествляется с помощью блоков 10 и 11 и коммутаторов6 и 7, изменяющих содержимое блока 1,Информация иэ блока 1 и буферных регистров 2, 3 и 4 передается на выходы15 и 16 устройства, (Выбор. другоговарианта ветвления выполняется послевозврата со входа 17 содержимого буферных регистров 2,3 и 4 и блока 1),Далее производится формированиенового неотмеченного подмножества, 55Предлагаемое устройство, благодаряналичию нового элемента и новых связей,позволяет решать задачу определенияизоморфизма ориентированных графов,79 6 Формула изобретения Устройство для определения изоморфизма ориентированных графов, содержащее первый блок памяти, первый выход Которого соединен с первым входом первого буферного регистра, выход которого подключен соответственно ко входам первого регистра, первого блока выделения крайней единицы, выход первого блока выделения крайней единицы соединен соответственно со вторым входом первого буферного регистра, с первыми входами первого, второго и третьего коммутаторов, с первым входом второго буферного регистра и с первым входом второго блока памяти, первый выход которого соединен с первым входом первого блока счетчиков, выход которого подключен к первому входу первого блока сравнения и ко второму входу второго коммутатора, выход которого соединен со вторым входом первого блока сравнения и с первым входом второго блока сравнения, второй вход которого подключен к выходу второго блока счетчиков, вход которого соединен с первым выходом третьего блока памяти, первый вход которого подключен соответственно к выходу третьего коммутатора и ко второму входу второго блока памяти, выход первого блока сравнения соединен со вторым входом третьего коммутатора, выход которого подключен к третьему входу первого буферного регистра и к первому входу первого блока памяти, второй выход которого соединен с первымвходомтретьего буферного регистра, выход которого соединен со входом второго блока выделения крайней единицы, первый выход которого подключей ко второму входу третьего буферного регистра, ко второму входу первого блока памяж, к первому входучетвертого коммутатора и ко второму входу третьего блока памяти выход четвертого коммутатора соединен с третьими входами первого, второго и третьб го блоков памяти, второй вход четвертого коммутатора подключен к выходу второго блока сравнения, второй вход четвертого коммутатора соединен со вторым входом второго буферного регистра и является входом устройства выход второго буферного регистра подключен к четвертому входу первого буферного регистра и ко второму входу первого коммутатора, выход которого соедини с четвертым входом первого блока памяти, выход первого регистра подключен к пятому входу пер7 73 вого буферного регистра, второй выход, второго блока выделения крайней единицы соединен со входом третьего блока счетчиков, выход которого подключен к первому входу блока определения знака разности и ко входу второго регистра, выход которого соединен со вторым входом блока определения знака разности, выходы первого и третьего буферных регистров и второго блока счетчиков являются соответственно выходами устройства, о тл и ч а ю ш е е с,я тем, что, с целью расширения функциональных возможностей эа счет обеспечения учета направленнос. ти ребер графа,. в устройство допопнительно введен третий регистр, причем вход 287 9третьего регистра соединен с выходомтретьего буферного регистра, выходтретьего регистра подключен к третьему входу третьего буферного регистра,5 выход первого блока выделения крайнейединицы соединен с четвертым входомвторого блока памяти, выход второго блока выделения крайней единицы подключенк четвертому входу третьего блока пао мя,цИсточники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР468244, кл. б 06 Г 15/20, 1975,2, Авторское свидетельство СССРпо заявке2323377/18-24, 26,11,76