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

Устройство относится к вычислительной технике и может быть применено в электронике. Известно устройство соцержащев блок триггеров, элементы И и ИЛИ Щ . Недостаток известного устройства невозможность решения задачи определения изомс фности графов. Наиболее близким по технической сущ ности к предлагаемому является устройство, содержащее блсжи памяти, коммутаторы, .блоки счетчиков, блсжи сравне ния, регистры, блоки выделения крайней единицы и блсж определения знака разности f2 ., Недостаток этого устройства - невозможность определения изоморфизма ориентированных графов. Цель изобретения - расширение функциональных возможностей за счет обеспечения учета направленности ребер граФа. Поставленная цель достигается благодаря введению в устройство, содержащее первый блок памяти, первый выход которого соединен с первым входом первого буферного регистра, выход которого подключен соответственно ко входам первого perHCTpaj первого бясжа выделения крайней единицы, первого бпсжа выделения крайней единицы соединен соответственно со вторым входом первого буферного регистра, с первым входом первого, второго и третьего коммутаторов, с первым входом второго буферного регистра и с первым входом второго блока памяти, первый выход которого соединен с первым входом первого блока счетчиков, выход которого подключен к первому входу первого, блока сравнения и ко второму входу второго коммутатора, выход которого соединен со вторым входом первого блока сравнения и с первым входом второго блока сравнения, второй вход которого подключен квыходу второго блока счетчиков, вход которого соединен с первым выходом третьего блока памяти, первый вход которого подклю7чен С(Х)Тветственно к выходу третьего ко мутатора и ко второму входу второго бло ка памяти, выход первого блока сравнения соединен со вторым входом третьего коммутатора, выход которого подключен к третьему входу первого буферного регист ра и к первому входу первого блока памяти, второй выход которого соединен с первым входом третьего буферного регистра, выход которого соединен со входом второго блока выделения крайней еди ницы, первый ВЫХОД которого подключен ко второму входу третьего буферного регистра, ко второму входу первого блока памяти, к первому входу четвертого коммутатора и ко второму входу третьего блока памяти, выход четвертого коммутатора соединен соответственно с третьими входами первого, второго и третьего блоков памяти, второй вход четвертого коммутатора подключен к выходу второго бл.ока сравнения, второй вход четвертого коммутатора соединен со вторым входом второго буферного регистра и является входом устройства, выход второго буферного регистра подключен к четвертому входу первого буферного регистра и ко второму входу первого коммутатора, выход которого соединен с четвертым входом первого блока памяти, выход первого регистра подключен к пятому входу первого буферного регистра, второй №1ход второго блока выделещ1я крайней единицы соединен со входом третьего бл ка счетчиков, выход которого подключен соответственно к первому входу блока определения знака разности и ко входу второго регистра, выход которого соединен со вторым входом блска определения .знака разности, выходы первого и третье го буферных регистров и второго блока счетчиков являются соответственно выходами устройства, введен третий регист причем вход третьего регистра соединен с выходом третьего буферного регистра, выход третьего регистра подключен к третьему входу третьего буферного регистра, выход первого блока выделения крайней единицы соединен с четвертым -входом второго блока памяти , выход второго блока выделения крайней единицы подключен к четвертому входу третьего блока памяти. На чертеже представлена схема пред лагаемого устройства. Устройство содержит блок 1 памяти, буферные регистры 2, .3 и 4, регистр 5, коммутаторы 67, 8 и 9, блоки 10 и 9( 11 выделения крайней единицы, регистр 12, блок 13 сравнения , блок 14 счетчиков, выходы 15 и 1©, вход 17, блок 18 счетчиков, регистр 19, блок 20 определения знака разности, блок 21 памяти, блок 22 счетчиков, блок 23 сравнения, блок 24 наличия. Устройство работает следующим образом. Перед работой устройства производится занесение исходной информации в блоки 1, 21 и 24 с помощью буферного регистра 2 (в котором в начальный моно выделяет крайнюю единицу, определяя Номер строки в блоках памяти). Информация поступает со входа 17 устройства через коммутатор 6. В результате в блоках 1, 21 и 24, записываются матрицы исходного разбиения paфoв и матрицы смежности первого и второго графов. Далее производится формирование неотмеченного подмножества предполагаемо изоморфных вершин исследуемых графов. По сигналам от буферного регистра 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. При этом получается новое разбиение предполагаемого изоморфизма. Затем возвращается в буферные регистры 2 И 3 содержимое регистров 5 и 12 и вы полняется формирование частных локальных степеней по входящим дугам. При этом аналогично проводится последовательный опрос столбцов блоков 21 и 24. После получения нового разбиения, в буферные регистры 2 и 3 возвращаетс содержимое буферных регистров и вьтолняется формирование частных лекальных степеней по антипараллельным дугам. Пр Этом, в отличие от предыдущего, в блоки. 14 и 22 поступает поразряднаяконъю ция строк и столбцов. После изменений разбиения, производится формирование нового неотмеченного подмножества. Если числа вершин в выделенных подмножествах не равны, то проводится выбор нового варианта ветвления. Если новый вариант ветвления выбрать -невозмож но, то графы не изоморфны. Если неотмеченных подмножеств нет, то выполняем ветвление. Среди подмножеств выбираем минимальное по мощности, содержащее более одной вершины. Если все подмножества содержат по одн вершине, .то графы изоморфны. Подстановка изоморфизма определяется единица ми блока 1. При выборе минимального подмножества, содержимое регистра 4 пе реписывается в регистр 2 и проводится последовательное формирование каждоГ-о отмеченного подмножества в буферном регистре 3 через блок 1 с помощью бло ка 1О и коммутатора 8. Для каждого из подмножества определяется его число вершин и выделяется минимальное подмножество с помощью блоков 18,19 и 20. Далее в выбранных подмножествах. каждого графа выделяется по одной верш не, которые предполагаются изоморфными (При выборе другого варианта ветвления вь7бирается ранее не выбранная вершина второго графа Это осуществляется с помощью блсжов Ю и 11 и коммутаторов 6 и 7, изменяющих содержимое блсжа 1 Информация из блсжа 1 и буферных регистров 2, 3 и 4 передается на выходы 15 и 16 устройства. (Выбор, другого варианта ветвления вьшолняется после возврата со входа 17 содержимого буферных регистров 2,3 и 4 и блока 1). Далее производится формирование нового неотмеченного подмножества. Предлагаемое устройство, благодаря наличию нового элемента и новых св51зей позволяет решать задачу определения изo fopфизмa ориентированных графов. Формула изо:бретения Устройство для определения изоморфизма ориентированных графов, содержащее первый блок памяти, первый вь1ход которого соединен с первым входом первого буферного регистра, выход которого подключен соответственно ко входам первого регистра, первого блока выделения крайней единиць, выход первого блока выделения крайней единицы соединен соответственно со вторым входом первого б$гферного регистра, с первыми входами первого, второго и третьего коммутаторов, с первым входом второго буферного регистра и с первым входом второго блсжа памяти, первый выход которого соединен с первым входом первого блсжа счетчиков, вьтход которого подключен к первому входу первого блока сравнения и ко второму входу второго коммутатора, выход которого соединен со вторым входом первого блоса сравнения и с первым входом второго блсжа сравнения, второй вход которого подключен к выходу второго блока счетчиков, вход которого соединен с первым выходом третьего блока памяти, первый вход которого лодключен соответственно к выходу третьего коммутатора и ко второму входу второго блска памяти, выход первого блока сравнения соединен со вторым входом третьего коммутатора, выход которого подключен к третьему входу первого буферного регистра и к первому входу первого блока памяти, второй выход которого соединен с первым входом третьего буферного регистра, выход которого соединен со входом второго блсжа выделения крайней единипы, первый выход которого подключен ко второму входу третьего буферного регистра, ко второму входу первого блока памяти, к первому входу четвертого коммутатсра и ко второму входу третьего блока памяти,, выход четвертого коммутатора соединен с третьими входами первого, второго и трет го блоков памяти, второй вход четвертого коммутатора подключен к выходу второго блсжа сравнения, второй вход четвертого коммутатора соединен со вторым входом второго буферного регистра и является входом устройства . выход второго бу рного регистра подключен к четвертому входу первого буферного регистра и ко второму входу первого коммутатора, выход которого соединен с четвертым входом первого блока памяти, выход первого регистра подключен к пятому входу первого буферного регастра, второй выход, второго бп еж а выделения крайней единицы соецикен со входом третьего блока счетчиков, выход которого подключен к первому входу блсжа определения знака разноста и ко входу второго регистра, выход которого соединен со вторым входом блока определения знака разности, вьтходы первого и третьего буферных регистров и второго блсжа счетчиков являются соответственно выходами устройства, о т личаюшеес.я тем, что, с целью расширения функциональных возможностей за счет обеспечения учета направленности ребер графа, в устройство допопнительно введен тремй регистр, причем вход

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

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

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

2.Авторское свидетельство СССР

по заявке № 2323377/18-24, 26.11.76