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

 

OllHCAHHЕ

ИЗОБРЕТЕНИЯ

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

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

Респу6лии

,732879

К АВТОЯСКОМУ СВИДЕТЕЛЬСТВУ (6l ) Дополнительное к авт. свид-ву (22) Заявлено 04. 11.77 (2I ) 2540026/18-2 с присоединением заявки М (23) Приоритег (54)М. Кл.

9 06 F 15/20

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

СССР

Опубликовано05.05.80 Бюллетень ¹ 17 ао делам иэооретеиий и открытий (53) УДК 681.3 (088.8) Дата опубликования описания 06.05.80

А, Г. Королев, В, А. Калашников и В. М. Курейчик (72) Авторы изобретения

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

ОРИЕНТИРОВАННЫХ ГРАФОВ

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

Известно устройство содержашеэ блок триггеров, элементы И и ИЛИ $1)

Недостаток известного устройства1 невозможность решения задачи определения изоморфности графов.

Наиболее близким по технической сущности к предлагаемому является устрой1о ство, содержащее блоки памяти, коммутаторы, .блоки счетчиков, блоки сравнения, регистры, блоки. выделения крайней единицы и блок определения знака разности 21 ., 15

Недостаток этого устройства — невозможность определения изоморфизма ориентированных графов.

liens изобретения —. расширение функциональных возможностей за счет обеспечения учета направленности ребер графа.

Поставленная цель достигается благодаря введению в устройство, содержа2 шее первый блок памяти, первый выход которого соединен с первым входом первого буферного регистра, выход которого подключен соответственно ко входам пер вого регистра, первого блока выделения крайней единицы, выход первого блока выделения крайней единицы соединен соответственно со вторым входом первого буферного регистра, с первым входом первого, второго и третьего коммутаторов, с первым входом второго буферного регистра и с первым входом второго блока памяти, первый выход которого соединен с первым входом первого блока счетчиков, выход которого подключен к первому входу первого блока сравнения и ко второму входу второго коммутатора, выход которого соединен со вторьгм входом первого блока сравнения и с первым входом второго блока сравнения, второй вход которого подключен к выходу второго блока счетчиков, вход которого соединен с первым выходом третьего блока памяти, первый вход которого подклю7328 чеи соответственно к выходу третьего коммутатора и ко второму входу второго блока памяти, выход первого блока сравнения соединен со вторым входом третьего коммутатора, выход которого подключен к третьему входу первого буферного регистра и к первому входу первого блока памяти,. второй выход которого соединен с первым входом третьего буферного регистра, выход которого соединен со входом второго блока выделения крайней единицы, первый выход которого подключен ко второму входу третьего буферного регистра, ко второму входу первого блока памяти, к первому входу четвертого ком- 15 мутатора и ко второму входу третьего блока памяти, выход четвертого коммутатора соединен соответственно с третьими входами первого, второго и третьего блоков памяти, второй вход четвертого коммутатора подключен к выходу второго блока сравнения, второй вход четвертого коммутатора соединен со вторым входом второго буферного регистра и является входом устройства, выход второго буферного регистра подключен к чет- вертому входу первого буферного регистра и ко второму входу первого коммутатора, выход которого соединен с четвертым входом первого блока памяти, выход первого регистра подключен к пятому входу первого буферного регистра, второй выход второго блока выделения крайней единицы соединен со входом третьего блока счетчиков, выход которого подключен соответственно к первому входу блока определения знака разности и ко входу второго регистра, выход которого соединен со вторым входом блока определения . знака разности, выходы первого и третьего буферных регистров и второго блока счетчиков являются соответственно выходами устройства, введен. третий регистр, причем вход третьего регистра соединен с выходом третьего буферного регистра, выход третьего регистра подключен к третьему входу третьего буферного регистра, выход первого блока выделения крайней единицы соединен с четвертым входом второго блока памяти, выход второго блока выделения крайней единицы подключен к четвертому входу третьего блока памяти, па чертеже представлена схема предлагаемого устройства.

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

79

1 1 выделения крайней единицы, регистр

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. При этом получается новое разбиение предполагаемого изоморфизма. Затем возвращается в буферные регистры 2

7328

35 и 3 содержимое регистров 5 и 12 и выполняется формирование частных локальных степеней по входяшим дугам. При атом аналогично проводится последовательный опрос столбцов блоков 21 и

24, После получения нового разбиения, в буферные регистры 2 и 3 возврашается содержимое буферных регистров и выполняется формирование частных локальных степеней по антипараллельным дугам. При 10 атом, в отличие от предыдущего, в блоки 14 и 22 поступает пораэряднаяконъюкция строк и столбцов. После изменений разбиения, производится формирование нового неотмеченного подмножества:

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

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

Если все подмножества содержат по одной

25 вершине, то графы изоморфны, Подстаножа изоморфизма определяется единицами блока 1. При выборе минимального подмножества, содержимое регистра 4 пезо реписывается в регистр 2 и проводится последовательное формирование каждого отмеченного подмножества в буферном регистре 3 через блок 1 с помощью блока 10 и коммутатора 8.

Для каждого из подмножества определяется его число вершин и выделяется минимальное подмножество с помощью . блоков 18, 1 9 и 20, Далее в выбранных подмножествах каждого графа выделяется по одной вершине, которые предполагаются изоморфными. (При выборе другого варианта ветвления, выбирается ранее не выбранная вершина второго графа, Это осушествляется с помощью блоков 10 и 11 и коммутаторов

6 и 7, иэменяюших содержимое блока 1.

Информация иэ блока 1 и буферных регистров 2, 3 и 4 передается на выходы

15 и 16 устройства. (Выбор. другого варианта ветвления выполняется после возврата со входа 17 содержимого буфернь1х регистров 2,3 и 4 и блока 1).

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

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

79 6

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

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

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

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

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

2. Авторское свидетельство СССР по заявке № 2323377/18-24-, 26,11.76, UHHHFIH Заказ 1555711 Тираж 751 Подписное

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