Устройство для определения гамильтоновых циклов на графе Советский патент 1992 года по МПК G06F15/419 

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

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

Структурь&я схема устройства приведена на чертеже. Устройство содержит блок перебора комоинаций 1, блок дешифрации 2, блок проверки связности графа 3, блок сравнения эквивалентных ребер 4, блок памяти 5, счетчш 6 по модулю 3, триггер 7, три счетчика управления 8.9,10, информационный регистр 1 |, элементы И 12,13, элемент ИЛИ 14, элемент задержки 15, элемент И 16, элемент ИЛИ 17, элемент И 18, элемент задержки 19, элементы ИЛИ 20, 21, 23, элементы задержки 22, 24, элементы И 25, 28, формироватепь импульсов л7, элементы И 28, 30, 31, эле мент задержки 29.

При этом информационный выход блока перебора комбинаций 1 подключен к первым информационным входам блока дешифрации 2 и блока сравнения эквивалентных ребер 4 и к информационному входу блока памяти 5, информационный выход регистра 11 подключен ко второму информационному входу блока дешифрации 2, информационный выход блока памяти 5 подключен ко второму информационному входу блока сравнения эквивалентных ребер 4 и информационному входу блока перебора комбинаций 1, информационный выход счетчика 8 подключен к информационному входу счетчика 9, информационный выход которого подключен к адресному входу блока памяти 5, выход признака несовпадения комбинаций блока перебора комбинаций 1 подключен к первому входу опроса блока дешифрации 2 и к первым входам элементов ИЛИ 17, 23, выход признака завершения перебора блока перебора комбинаций 1 подключен к перпому входу элемента ИЛИ 21, к вычитающему входу счетчика 8 и к первому входу элемента

СП

с

XJ

vl 00 VI

о

4

ИЛИ 20, выход признака выдачи информации блока дешифрации 2 подключен ко второму входу элемента ИЛИ 23, выход которого через элемент задержки 24 подключен к первым входам элементов И 25,26, информационный выход блока дешифрации

2подключен к информационному входу блока проверки связности 3, выход признака связности которого подключен ко второму входу элемента И 25, выход признака отсут- ствия связности блока проверки связности

3подключен ко второму входу элемента И 26, выход элемента И 25 подключен к первому входу элемента И 13 и к счетному входу счетчика 6 по модулю 3, выход элемента И 26 подключен к первому входу элемента И

18 и, через элемент задержки 22, ко второму входу элемента ИЛИ 17, выход элемента И 13 подключен к первому входу элемента ИЛИ 14, выход которого подключен к пря- мому входу элемента И 12 и, через элемент задержки 15, к входу синхронизации блока памяти 5, к вычитающему входу счетчика 10 и к третьему входу элемента ИЛИ 17, выход счетчика 6 по модулю три подключен ко вто- рому входу элемента ИЛИ 20 и к первому входу элемента И 28, выход элемента ИЛИ 17 подключен к счетному входу триггера 7, выход которого подключен к первому входу элемента И 16 и к инверсному входу элемен- та И 28, первый выход формирователя импульсов 27 подключен ко второму входу элемента И 16, выход которого подключен к тактовому входу блока перебора комбинации 1 и к входу сброса счетчика 6 по модулю три, выход элемента И 12 подключен к входу сброса блока перебора комбинации 1, второй выход формирователя импульсов 27 подключен ко второму входу элемента И 28, выход которого подключен ко входу опроса блока сравнения эквивалентных ребер 4 и, через элемент задержки 29 к первым входам элементов И 30, 31, выход признака равенства единице счетчика 10 подключен ко второму входу элемента И 18, к четверто- му входу элемента ИЛИ 17, к инверсному входу элемента И 12, ко второму входу опроса блока дешифрации 20 ко второму входу элемента И 13 и к третьему входу эпемента ИЛИ 23, выход элемента И 18 подключен ко второму входу элемента ИЛИ 21, выход которого подключен к суммирующему входу счетчика 10, выход элемента ИЛИ 20 подключен ко входу синхронизации счетчика 9, выход признака перехода через ноль кото- рого подключен к суммирующему входу счетчика 8 и, через элемент задержки 19, к третьему входу элемента ИЛИ 20 и ко второму входу элемента ИЛ И 14, выход признака равенства блока сравнения

эквивалентных ребер 4 подключен ко второму входу элемента И 30, выход которого подключен к входу элемента ИЛИ 17. выход признака неравенства блока сравнения эквивалентных ребер 4 подключен ко второму входу элемента И 31, выход которого подключен к вычитающему входу счетчика 9.

В основу работы устройства положен следующий алгоритм. Задача нахождения гамельтонова цикла (ГЦ) заключается в нахождении такового маршрута, который проходил бы по всем вершинам графа один раз и начинался и заканчивался бы в одной и той же вершине. В основу работы устройства положен алгоритм нахождения ГЦ, основанный на понятии ЭКВИВАЛЕНТНОГО ребра (ЭР). Вершина с локальной степенью два имеет только ВХОД и ВЫХОД - т.е. является транзитной и выполняет функции ребра Обычное ребро в графе соединяет две вершины I и J и имеет вид U(I,J). Если рассматривать как ребро вершину с локальной степенью два, то данное ребро соединит уже три вершины I, J, К, (где, J-вершина с локальной степенью два)

ГЦ проходит по всем вершинам графа один раз (т.е. один раз в каждую вершину входит и один раз выходит). Следовательно, если в графе существует ГЦ, то у всех вершин графа, независимо от их локальных степеней, в ГЦ входит по два ребра. Каждой вершине графа инцидентно m ребер

(,3N-1, где N - количество вершин в

графе). Можно составить различные комбинации прохождения вершин графа (т.е. различные комбинации вход - выход), которые называются ЭР. Следовательно, ЭР соединяет три вершины I, J, К и имеет вид U(I,J,K). Данная последовательность вершин в U показывает связность вершин I и J, J и К соответственно. Для каждой вершины графа можно составить определенное количество ЭР, определяемое для неориентированных графов как ,.

Идея алгоритма заключается в нахождении последовательности ЭР, в состав которых входили бы все вершины графа один раз, причем номера начальной и конечной вершин графа, входящих в данную последовательность, должны совпадать. Номер последней вершины данного ЭР определяет номер следующей аершины, для которой ищется ЭР, в состав которого не входили бы уже рассмотренные вершины. Если такого нет, то производится возврат к предыдущему рассмотренному ЭР, вместо которого находится новое Процесс продолжается, пока все вершины графа не будут входить в последовательность найденных ЭР (в слу- чае существования ГЦ), либо пока не будет

установлено, что ГЦ в данном графе нет (в этом случае будут рассмотрены все ЭР для начальной вершины, а ГЦ не будет найден). Количество ЭР для построения ГЦ:

N/2 - когда в графе четное V- число вершин,(1)

N/2+ - - когда в графе нечетное

число вершин. Если рассмотрено (V--1) ЭР, то меняется условие выбора последнего ЭР (это условие различно для случаев четного и нечетного количества вершин в графе). Если на предыдущих шагах работы алгоритма определялось первенство номеров второй и третьей вершин рассматриваемого ЭР с номерами ранее рассмотренных вершин, то на последнем шаге условие меняется.

В случае четкого количества вершин в графе номер третьей вершины последнего (т.е. V-ro) ЭР должен соответствовать номеру начальной вершины, с которой начинается поиск ГЦ (чтобы замкнуть цикл). В случае нечетного количества вершины номер третьей вершины последнего ЭР должен соответствовать номеру начальной вершины.

Если предусмотреть возможность определения ГЦ для обоих случаев, то необходимы дополнительные аппаратные затраты. Чтобы избежать этого, предлагается ограничить работу устройства определением ГЦ в гоафах с нечетным количеством вершин. В случае четного количества вершин перед началом работы необходимо в исходный граф ввести дополнительную фиктивную вершину, которая была бы смежна с начальной и со всеми вершинами смежными с начальной вершиной. В этом случае ввод фиктивной вершины не повлияет на существование ГЦ в графе и на последовательность вершин в найденном ГЦ в случае его существования. Поиск ГЦ необходимо начинать с фиктивной вершины.

Работу алгоритма рассмотрим на примере графа О (X,U),|Xl 6.IUI- 8, матрица смежности которого имеет вид: 123456

1001101

2001011

3110100

4101000

50 1 000 1 б| 110010

За начальную вершину примем Х1. Для нее составим первые ЭР: U(1,3,2). Последняя цифра данного ЭР определяет номер следующей вершины, для которой ищется ЭР,-в состав которого не входили бы уже рассмотренные вершины: U (2,5,6). Для шестой вершины не существует ЭР, в состав

которого не входили бы уже рассмотренные вершины 1,2,3,4,5. Поэтому производим возврат и формируем новое ЭР для второй вершины: U(2,6,5). Для пятой вершины также не существует ЭР, в состав которого не входили бы уже рассмотренные вершины 1,3,2,6, Производим возврат. Для второй вершины больше не существует ЭР, поэтому производим возврат еще на один шаг и

0 составляем новое ЭР для первой вершины: U(1,3,4). Для четвертой вершины не существует ЭР, в состав которого не входили бы уже рассмотренные вершины 1,3, поэтому составляем новое ЭР для первой вершины:

5 U(1,3,4). Для третьей вершины находим ЭР, в состав которого не входят рассмотренные вершины 1,4: U(3,2,5),

Количество вершин в рассматриваемом графе - б. Поэтому число ЭР для построения

0 ГЦ. . Рассмотрено (V-1) ЭР. Меняется условие выбора V-ro ЭР. Такое ЭР существует:

U (1,4,3), U-(3,2,5), U (5,6,1) Данная последовательность вершин об5 разует ГЦ 1-4-3-2-5-6-1.

Подготовка устройства к работе заключается в следующем:

1. Запись в регистр 11 номера начальной вершины;

02. Задание топологии графа в блоке проверки связности графа;

3. Запись в счетчик 10 количества ЭР, необходимых для построения ГЦ (согласно формуле 1);

5 4. Подача сигнала через элемент ИЛИ 17 на вход триггера 7 и установка на его прямом выходе уровня логической единицы;

5. Запись в блок перебора комбинаций 1 через информационный вход комбинации

0 чисел, соответствующей первому ЭР Для начальной вершины (последняя цифра ЭР, соответствующая номеру третьей вершины входящей в ЭР вершины, уменьшена на единицу - с приходом первого тактового им5 пульса в блоке перебора комбинации 1 установится первое ЭР для начальной вершины). .

ЭР формируются в блоке 1 перебора комбинаций (БПК1). Тактовые импульсы по0 ступают на тактовый вход БПК1. Т.к. в тройке вершин, образующих ЭР, не должно быть вершин с одинаковыми номерами, то на выходе признака несовпадения БПК1 сигнал появится только в том случае, когда среди

5 сравниваемых чисел нет одинаковых.

Если ЭР записывается в блок памяти 5 (БП5) - т.е. предполагается, что через это ЭР проходит ГЦ - на вход сброса БПК1 поступает сигнал, по которому формирование нового Э Р будет производит ься для последней

рассмотренной вершины. Если для вершины, номер которой определяется последней цифрой последнего записанного в ЭР, не существует ЭР, в состав которого не входили бы уже рассмотренные вершины, необходимо вместо записанного ЭР сформировать новое. В этом случае по сигналу с выхода признака завершения перебора БПК1 формируется код последнего записанного в БП5 ЭР и данное ЭР запишется в БПК1. Т.е. формирование нового ЭР будет производиться, начиная с записанной комбинации вершин.

Сформированное в БПК1 ЭР необходимо проверить на связность (т.е. связны ли первая и вторая, вторая и третья входящие в ЭР вершины). Проверка связности входящих в ЭР вершин осуществляется в блоке 3 проверки связности графа (БПСГЗ), который может быть выполнен по схеме, предложенной в а.с. 1086434. Перед началом работы необходимо в БПСГЗ задать топологию графа (согласно описанию, представленному в данном а.с.). Работа БПСГЗ заключается в следующем. На два входа БПСГЗ, соответствующих номерам проверяемых на связность вершин, подаются сигналы. Если данные вершины связны, то на выходе признака связности БПСГЗ появится единичный сигнал. Информация о номерах вершин, проверяемых на связность, должны подаваться в унитарном коде. Для преобразования двоичного кода, поступающего с БПК1, в унитарный код служит блок 2 дешифрации (БДш2). Т.к. необходимо проверить связность двух пар вершин (первой и второй, второй и третьей соответственно), то с БДш2 на БПСГЗ должен последовательно поступать код номеров первой и второй, а затем второй и третьей вершин.

Когда в БПК1 сформируется ЭР, в составе которого нет одинаковых цифр, на выходе признака несовпадения появится сигнал. который:

-поступит через схему ИЛИ 17 на вход триггера 7 и перебросит его (т.е. на выходе триггера установится уровень логического 0). Схема И 16 закроется и тактовые импульсы не будут поступать на БПК1;

-через элемент ИЛИ 23 и элемент задержки 24 (величина которой равна времени срабатывания БДш2 и БПСГЗ) поступит на вторые входы схем И 25 и И 26. Если вершины связны, сигнал появится на выходе элемента И 25, если же не связны - на выходе элемента И 26;

-через элемент задержки 22 поступит на второй вход элемента ИЛИ 23.

На БПСГЗ поступят последовательно коды номеров первой и второй, второй и третьей вершин ЭР соответственно. Т.к. необходимо проверить связность двух пэр

вершин, то если сформированное ЭР существует в иссследуемом графе, то с выхода признака связности БПСГЗ должно поступить два сигнала.

Сигнал с БПСГЗ поступает через открытый элемент И 25 на счетчик 6 по модулю 3. Если на вход счетчика поступит последовательно два сигнала, то на выходе появится сигнал. Если проверяемые на связность вершины не связны, то сигнал появится на

выходе признака отсутствия связности БПСГЗ, который через открытую схему И26 и схему ИЛИ 17 поступит на триггер 7, перебросит его и откроет схему И 16. Если на счетчик 6 не поступит двух сигналов, необходим принудительный сброс счетчика в исходное состояние. Это осуществляется каждым новым ТИ (независимо от состояния счетчика 6), который с выхода элемента И 16 поступает на вход сброса счетчика 6.

Если сформированное ЭР в исследуемом графе существует, необходимо проверить, не входят ли в него уже рассмотренные вершины. Для сравнения сформированного ЭР с ранее записанными в БП5 ЭР служит блок

4 сравнения ЭР (БСЭР4, представляющий собой шесть схем сравнения, выходы которых объединены схемой ИЛИ).

Формирователь импульсов 27 формирует импульсы 2-х видов: с периодом т, с периодом Т2.

Первые импульсы поступают на первый вход элемента И 16.

Вторые импульсы поступают на второй вход элемента И 28,

Если на выходе триггера 7 стоит единичный потенциал, то элемент И 16 открыт, а элемент И 28 закрыт. Следовательно, вторые импульсы не проходят через схему И 48 и не поступают на вход V 0 опроса БСЭР4.

Когда на выходе триггера 7 стоит нулевой потенциал (это означает, что необходимо произвести проверку сформированного ЭР), схема И 16 закрыта, импульсы не поступают на тактовый вход БПК1,

Если на счетчик 6 поступит последовательно два сигнала (означающие, что сформированное ЭР существует в графе) на выходе счетчика появится единичный потенциал, означающий, что необходимо сравнить сформированное ЭР с ранее записанными в БП5 ЭР. Этот потенциал поступит на третий вход элемента И 28 и откроет его. Импульсы с периодом Г2 (величина которого определяется временем сравнения двух ЭР в БСЭР 4) начинают поступать на вход VO опроса БСЭР4. Одновременно импульсы через элемент задержки 29 поступают на вторые входы элементов И 31, И 30.

Если потенциал появится на выходе признака неравенства БСЭР 4 (это означает, что одинаковых номеров вершин в сравниваемых ЭР нет), то импульсы продолжают поступать. Если потенциал появится на выходе признака равенства БСЭР (это означает, что есть одинаковые номера вершин в сравниваемых ЭР), то импульс с выхода элемента И 30 поступит через элемент ИЛИ 17 на счетный вход триггера 7 и перевернет его, На выходе триггера 7 появится единичный потенциал: схема И 28 закроется, а схема И 16 откроется и начнут поступать тактовые импульсы,

Сигнал со счетчика 6 через схему ИЛИ 20 поступит на синхровход счетчика 9. По этому сигналу: 1) информация со счетчика 8 (где хранится код адреса последнего записанного в БП5 ЭР) запишется в счетчик 9, а с него поступит на адресный вход БП5. На информационном выходе БП5 появится записанное по этому адресу ЭР, которое поступит на БСЭР 4; 2) через элемент задержки 21 поступит на вычитающий вход счетчика 9 и уменьшит состояние на 1. С БПК1 на БСЭР 4 поступит номера второй и третьей вершин сформированного ЭР. Если, одинаковых номеров нет, то на выходе признака несовпадения БСЭР4 появится сигнал, который: 1) поступит через схему ИЛИ 20 на синхровход счетчика 8, где уже записан адрес предпоследнего рассмотренного ЭР, и аналогичным образом произойдет сравнение второй и третьей цкфр сформированного ЭР с предпоследним ЭР, 2) снова уменьшит состояние счетчика 9 на 1. Процесс будет продолжаться до тех пор, пока:

- не появится сигнал признака равенства с БСЭР 4 (означающий, что есть в сформированном ЭР номера уже рассмотренных вершин). Этот сигнал поступит через схему ИЛИ 17 на триггер 7, перебросит его и откроет элемент И 16;

. - не появится сигнал с выхода признака перехода через 0 счетчика 9 (означающий, что все записанное в БП5 ЭР сравнены с сформированным ЭР, а одинаковых номеров вершин не найдено). По этому сигналу данное ЭР запишется в БП5. а сигнал поступит на суммирующий вход счетчика 8, где хранится адрес последнего записанного ЭР, и увеличит этот адрес на единицу (т.е. сформируется адрес следующей ячейки), через элемент задержки 19 (величина которой определяется временем срабатывания счетчика 9) и элемент ИЛИ 20 поступит на синхровход счетчика 9 поэтому информация запишется в счетчик 9 и поступит на адресные входы БП5; через элемент ИЛИ 14 и элемент

задержки 15 (величина которой определяет- ся временем срабатывания счетчиков 8 и 9) поступит на вход синхронизации БП5, и сформированное ЭР запишется в БП5; поступит на вычитающий вход счетчика 10 и

0 уменьшит состояние данного счетчика на 1; поступит на второй вход элемента И 12 и на вход сброса БПК1.

Триггер 7 работает в следующих режимах:

5 - перед работой на прямом выходе устанавливается уровень погической 1;

-по сигналу признака несовпадения с БПК на выходе устанавливается уровень логического 0;

0 - по сигналу с выхода элемента И26 на выходе устанавливается уровень логической 1;

-по сигналу с выхода элемента задержки 15 на выходе устанавливается уровень

5 логической 1;

-по сигналу с выхода признака равенства БСЭР на выходе устанавливается уровень логической 1.

Иными словами перед началом работы

0 элемент И 16 открывается (через триггер 7) и ТИ поступают на БПК1. Как только в БПК1 сформировано ЭР, в состав которого не входят вершины с одинаковыми номерами, на выходе признака несовпадения БПК1 поя5 вится сигнал, который закрывает схему И 16 (через триггер 7). ТИ не поступают на БПК1 и не происходит формирование нового ЭР. Далее происходит последовательно проверка сформированного ЭР на связность, а за0 тем с ранее записанными ЭР, Если хоть одно условие не выполняется, то появляется сигнал (либо с выхода элемента И 26, либо с выхода признака равенства БСЭР), по которому элемент И 16 (через триггер 7) от5 крывается и происходит дальнейшее формирование ЭР. Если же оба условия выполняются (т.е. первая и вторая, вторая и третья вершины, входящие в ЭР, связны, и они ранее не рассматривались), то появля0 ется сигнал с выхода элемента задержки 15, по которому элемент И 16 откроется и ТИ начнут поступать на БПК, который уже находится в исходном состоянии.

Блок памяти БП5 состоит из трех иден5 тичных ОЗУ. В каждом ОЗУ хранится код номера одной вершины ЭР. Счетчик 8 служит для остановки работы устройства. Перед началом работы в счетчик 8 записывается информация о количестве ЭР, необходимых для построения ГЦ (вычисленное по формуле), Как только ЭР записывается в БП5, с выхода элемента задержки 15 сигнал поступаег)на,вычитающий вход счетчика 1U и уменьшает его состояние на 1. Если не производится возврат, то по сигналу признака завершения перебора с БПК1 содержимое счетчика 10 увеличивается на 1 (сигнал с БПК1 поступает через элемент ИЛИ 21 на его суммирующий вход).

Сигнал с выхода перехода через 0 счетчика 10 означает, что ГЦ найден.

Если сформировано (V-1)3P. необходимо проверить на связность последнюю рассмотренную и начальную вершины. Номер начальной вершины перед началом работы записывается в регистр 11.

Сигнал с выхода признака равенства единице счетчика 8 поступит:

-на второй вход схемы И 18. Если последняя рассмотренная и начальная вершины не связны, то на первый вход схемы И18 по ступит сигнал, который откроет схему И18 и через схему ИЛИ 21 увеличит состояние счетчика 8 на единицу;

-через схему ИЛИ 17 на счетный вход триггера 7, перевернет его и закроет схему И 16;

-на второй вход опроса БДш2. По этому сигналу на БДш2 поступят коды начальной и (п-1)-й вершин.

-на пе рвый вход схемы И 13. Если ()- ая и начальная вершины связны, на второй вход схемы И 13 поступит сигнал и откроет схему И 13:

-на инверсный вход элемента И 12 и закроет его (чтобы предпоследнее ЭР осталось записанным в ВПК, и если начальная и (п-1) вершины не связны, то формирование новой ЭР происходило с данной комбинации чисел).

Если данные вершины связны, то сигнал через открытую схему И 13, схему ИЛИ 14, и элемент задержки 15 поступит на вычитающий вход счетчика 10. Счетчик 10 прийдет в нулевое состояние, и на выходе признака перехода через 0 счетчика 8 появится сигнал, означающий, что ГЦ найден.

Если вершины не связны, то сигнал через открытую схему И 18 и схему ИЛИ 21 поступит на суммирующий вход и увеличит состояние счетчика на единицу.

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

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

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

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

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

5 перебора комбинаций, информационный выход первого счетчика подключен к информационному входу второго счетчика, информационный выход которого подключен к адресному входу блока памяти, выход при0 знака несовпадения комбинаций блока перебора комбинаций подключен к первому входу опроса блока дешифрации и к первым входам первого и второго элементов ИЛИ, выход признака завершения перебора бло5 ка перебора комбинаций подключен к первому входу третьего элемента ИЛИ, к вычитающему входу второго счетчика и к первому входу четвертого элемента ИЛИ, выход признака выдачи информации блока

0 дешифрации подключен к второму входу второго элемента ИЛИ, выход которого через первый элемент задержки подключен к первым входам первого и второго элементов И, информационный выход блока де5 шифрации подключен к информационному входу блока проверки связности, выход признака связности которого подключен к второму входу первого элемента И, выход признака отсутствия связности блока про0 верки связности подключен к второму входу второго элемента И, выход первого элемента И подключен к первому входу третьего элемента И и к счетному входу счетчика по модулю три, выход второго элемента И под5 ключей к первому входу четвертого элемента И и через второй элемент задержки к второму входу первого элемента ИЛИ, выход третьего элемента И подключен к первому входу пятого элемента ИЛИ, выход

0 которого подключен к прямому входу пятого элемента И и через третий элемент задержки к входу синхронизации блока памяти, к вычитающему входу третьего счетчика и к третьему входу первого элемента ИЛИ, вы5 ход счетчика по модулю три подключен к второму входу четвертого элемента ИЛИ и к первому входу шестого элемента И, выход первого элемента ИЛИ подключен к счетному входу триггера, выход которого подключен к первому входу седьмого элемента И и

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

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

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