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

 

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

COI03 СОВЕТСКИХ

СОЦИАЛИСГИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 15/419

ГОСУДАРСТВЕННОЕ ПАТЕНТНОГ

ВЕДОМСТВО СССP (ГОСПАТЕНТ СССР1

Ф(Ёцщр

Оп ИСАН И Е ИЗОБРЕТЕНИЯ,",. ."",".; "" нвв

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4757104/24 (22) 09,11.89 (46) 30.11,92, Бюл. М 44 (71) Таганрогский радиотех; ический институт им.В.Д,KBflMblKOBB (72) В.M.Ãëóè,àíü, B.M.Курейчик, С,И.Макеев и Н.Н.Рябс L:, (56) Авторское свидетельсте о СССР

N 1134944, кл, G 06 F 15/2G 1983.

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

N 424152, кл, 6 06 F 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ГАМИЛЬТОНОВЫХ ЦИКЛОВ НА ГРАФЕ

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

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

Структур» ая схема устройства приведена на чертеже. Устройство содержит блок перебора комбинаций 1, блок дешифрации

2, блок проверки связности графа 3, блок сравнения эквивалентных ребер 4, блок памяти 5, счетчик 6 по модулю 3, триггер 7, три счетчика управления 8.9.10, информационный регистр 1, элементы И 12,13, элемент

ИЛИ 14, элеме11т задержки 15, элемент И 16, элемент ИЛИ 17, элемент И 18, элемент задержки 19, элементы ИЛИ 20, 21, 23, элементы задержки 22, 24, элементы И 25, 28, формирователь импульсов ",:7, элементы И

28, 30, 31, эле мент задержки 29, При этом информационный выход блока . перебора комбинаций 1 подключен к пер„, SLJ,, 1778764 Al (57) Изобретение относится к области вычислительной техники и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной аппаратуры. Целью изобретения является повышение быстродействия устройства. Устройство использует алгоритм определения гамильтоновых циклов, основанный на переборе эквивалентных ребер, под которыми понимают ветви графа. соединяющие три вершины (из которых центральная имеет локальную степень два), 1 ил, 1

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

1778764

20

30

ИЛИ 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, выход счетчика б по модулю три подключен ко второму входу элемента ИЛИ 20 и к первому входу элемента И 28, выход элемента ИЛИ

17 подключен к счетному входу триггера 7, выход которого подключен к первому входу элемента И 16 и к инверсному входу элемента И 28, первый выход формирователя импульсов 27 подключен ко второму входу элемента И 16; выход которого подключен к тактовому входу блока перебора комбинации 1 и к входу сброса счетчика 6 по модулю три, выход элемента И 12 подключен к входу сброса блока перебора комбинации 1, второй выход формирователя импульсов 27 подключен ко второму входу элемента И 28, выход которого подключен ко входу опроса блока сравнения эквивалентных ребер 4 и, через элемент задержки 29 к первым входам элементов И 30, 31, выход признака равенства единице счетчика 10 подключен ко второму входу элемента И 18, к четвертому входу элемента ИЛИ 17, к инверсному входу элемента И 12, ко второму входу onроса блока дешифрации 20 ко второму входу элемента И 13 и к третьему входу элемента

ИЛИ 23, выход элемента И 18 подключен ко второму входу элемента ИЛИ 21, выход которого подключен к суммирующему входу счетчика 10, выход элемента ИЛИ 20 подключен ко входу синхронизации счетчика 9, выход признака перехода через нбль которого подключен к суммирующему входу счетчика 8 и, через элемент задержки 19, к третьему входу элемента ИЛИ 20 и ко второму входуэлемента ИЛИ 14, выход признака равенства блока сравнения эквивалентных ребер 4 подключен ко второму входу элемента И 30, выход которого подключен к входу элемента ИЛИ 17, выход признака неравенства блока сравнения эквивалентных ребер 4 подключен ко второму входу элемента И 31, выход которого подключен к вычитающему входу счетчика 9.

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

ГЦ проходит по всем вершинам графа один раз (т.е. один раз в каждую вершину входит и од и н раз в ы ходит). Сл едо вател ь но, если в графе существует ГЦ, то у всех вершин графа, независимо от их локальных степеней, в ГЦ входит по два ребра. Каждой вершине графа инцидентно m ребер (m-2,3,...,N — 1, где N — количество вершин в графе). Можно составить различные комбинации прохождения вершин графа (т.е. различные комбинации "вход" — "выход"), которые называются ЭР, Следовательно, ЭР соединяет три вершины I, J, К и имеет вид U=(I,J,К). Данная последовательность вершин в U показывает связность вершин I и J, J и К соответственно. Для каждой вершины графа можно составить определенное количество ЭР, определяемое для неориентированных графов как Р =С m .

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

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

N/2 — когда в графе четное 5

V = число вершин, (1i

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

2 число вершин.

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

В случае чегкого количества вершин в графе номер третьей вершины последнего 20 (т.е. V-го) ЭР должен соответствовать номеру начальной вершины, с которой начинается поиск ГЦ(чтобы замкнуть цикл). В случае нечетного количества вершины номер третьей вершины последнего Э P должен со- 25 ответствовать номеру начальной вершины, Если предусмотреть возможность определения ГЦ для обоих случаев, то необходимы дополнительные аппаратные затраты, Чтобы избежать этого, предлагается огра- 30 ничить работу устройства определением ГЦ в гоафах с нечетным количеством вершин. В случае четного количества вершин перед началом работы необходимо в исходный граф ввести дополнительную "фиктивную" 35 вершину, которая была бы смежна с начальной и со всеми вершинами смежными с начальной вершиной. В этом случае ввод

"фиктивной" вершины не повлияет на существование ГЦ в рафе и на последователь- 40 ность вершин в найденном ГЦ в случае его существования, Поиск ГЦ необходимо начинать с "фиктивной" вершины, Работу алгоритма рассмотрим на примере графа С=- .(X,U),jXL= б,lUl=- 8, матрица 45 смежности которого имеет вид:

123456

001101

001011 10100

010001

2

110010

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

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

1,3.2,6, Производим возврат. Для второй вершины больше не существует ЭР, поэтому производим возврат еще на один шаг и составляем новое ЭР для первой вершины;

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

U=(1,3,4). Для третьей вершины находим ЭР, в состав которого не входят рассмотренные вершины 1,4; U=(3,2,5), Количество вершин в рассматриваемом графе — 6. Поэтому число ЭР для построения

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

U = (1,4,3), U =(3,2,5), U = (5,6,1)

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

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

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

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

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

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

5. Запись в блок перебора комбинаций

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

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

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

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

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

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

О). Схема И 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-х видов: с периодом г1, с периодомг .

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

Когда на выходе триггера 7 стоит нулевой потенциал (это означает, что необходимо произвести проверку сформированного

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

55 торого определяется временем сравнения двух ЭР в БСЭР 4) начинают поступать на вход НО опроса БСЭР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 поступ"r номера второй и третьей вершин сформированного ЭР, Если, одинаковых номеров нет, то на выходе признака несовпадения БСЭР4 появится сигнал, который; 1) поступит через схему ИЛИ

20 на синхровход счетчика 8, где уже записан адрес предпоследнего рассмотренного

ЭР, и аналогичным образом произойдет сравнение второй и третьей цифр сформированного ЭР с предпоследним 3Р, 2) снова уменьшит состояние счетчика 9 на 1. Процесс будет продолжаться до тех пор, пока: — не появится сигнал признака равенства с БСЭР 4 (означающий, что есть в сформированном ЭР номера уже рассмотренных вершин). Этот сигнал поступит через схему

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

ЭР, и увеличит этот адрес на единицу (т.е. сформируется адрес следующей ячейки), через элемент задержки 19 (величина которой определяется временем срабатывания счет5

40 чика 9) и элемент ИЛИ 20 поступит на синхровход счетчика 9 поэтому информация запишется в счетчик 9 и поступит на адресные входы БП5; через элемент ИЛИ 14 и элемент задержки 15 (величина которой определяется временем срабатывания счетчиков 8 и 9) поступит на вход синхронизации БП5, и сформированное ЭР запишется в БП5; поступит на вычитающий вход счетчика 10 и уменьшит состояние данного счетчика на 1; поступит на второй вход элемента И 12 и на вход сброса БПК1, Триггер 7 работает в следующих режимах: — перед работой на прямом выходе устанавливается уровень логической 1; — по сигналу признака несовпадения с

БПК на выходе устанавливается уровень логического 0; — по сигналу с выхода элемента И26 на выходе устанавливается уровень логической 1; — по сигналу с выхода элемента задержки 15 на выходе устанавливается уровень логической 1; — по сигналу с выхода признака равенства БСЭР на выходе устанавливается уровень логической 1.

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

Блок памяти БП5 состоит из трех идентичных ОЗУ, В каждом ОЗУ хранится код номера одной вершины ЭР. Счетчик 8 служит для остановки работы устройства. Перед началом работы в счетчик 8 записывается информация о количестве ЭР, необходимых для построения ГЦ(вычислен1778764

12 ное по формуле), Как только ЭР записывается в БП5, с выхода элемента задержки 15 сигналпоступаег на,вычитающий вход счетчика 1U и умейьшает его состояние на 1, Если не производится возврат, то по сигна- 5 лу признака завершения перебора с БПК1 содержимое счетчика 10 увеличивается на 1 (сигнал с БГ1К1 поступает через элемент

ИЛИ 21 на его суммирующий вход).

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

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

Сигнал с выхода признака равенства единице счетчика 8 поступит: — на второй вход схемы И 18, Если последняя рассмотренная и начальная верши- 20 ны не связны. то на первь|й вход схемы И18 пбступит сигнал, который откроет схему

И18 и через схему ИЛИ 21 увеличит состояние счетчика 8 на единицу; — через схему ИЛИ 17 на счетный вход 25 триггера 7, перевернет его и закроет схему

И 16; — на второй вход опроса БДш2, По этому сигналу на БДш2 поступят коды начальной и (п — 1)-й вершин; 30 — на первый вход схемы И 13, Если (n-1)ая и начальная вершины связны, на второй вход схемы И 13 поступит сигнал и откроет схему И 13: — на инверсный вход элемента И 12 и 35 закроет его (чтобы предпоследнее ЭР осталось записанным в БПК. и если начальная и (и — 1) вершины не связны, то формирование новой ЗР происходило с данной комбинации чисел). 40

Если данные вершины связны, то сигнал через открытую схему И 13, схему ИЛИ

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

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

Устройство для определения гамильтоновых циклов на графе, содержащее блок перебора комбинаций, блок проверки свяэ- 55 ности графа, блок памяти и пять элементов задержки, отличающееся тем,что,с целью повышения быстродействия устройсгеа, в него введены формирователь импульсов, блок дешифрации, блок сравнения эквивалентных ребер,.триггер, три счетчика, регистр, счетчик по модулю три, девять элементов И и пять элементов ИЛИ, причем информационный выход блока перебора комбинаций подключен к первым информационным входам блока дешифрации и блока сравнения эквивалентных ребер и к информационному входу блока памяти, информационный выход регистра, подключен к второму информационному входу блока дешифрации, информационный выход блока памяти подключен к второму информационному входу блока сравнения эквивалентных ребер и к информационному входу блока перебора комбинаций, информационный выход первого счетчика подключен к информационному входу второго счетчика. информационный выход которого подключен к адресному входу блока памяти, выход признака несовпадения комбинаций блока перебора комбинаций подключен к r-„åðeîìó входу опроса блока дешифрации и к первым входам первого и второго элементов ИЛИ, выход признака завершения перебора блока перебора комбинаций подключен к первому входу третьего элемента ИЛИ, к вычитающему входу второго счетчика и к первому входу четвертого элемента ИЛИ, выход признака выдачи информации блока дешифрацйи подключен к второму входу второго элемента ИЛИ, выход которого через первый элемент задержки подключен к первым входам первого и второго элементов И, информационный выход блока дешифрации подключен к информационному. входу блока проверки связности, выход признака связности которого подключен к второму входу первого элемента И, выход признака отсутствия связности блока проверки связности подключен к второму входу второго элемента И, выход первого элемента И подключен к первому входу третьего элемента И и к счетному входу счетчика по модулю три, выход второго элемента И подключен к первому входу четвертого элемента И и через второй элемент задержки к второму входу первого элемента ИЛИ, выход третьего элемента И подключен к первому входу пятого элемента ИЛИ, выход которого подключен к прямому входу пятого элемента И и через третий элемент задержки к входу синхронизации блока памяти, к вычитающему входу третьего счетчика и к третьему входу первого элемента ИЛИ, выход счетчика по модулю три подключен к второму входу четвертого элемента ИЛИ и к первому входу шестого элемента И, выход первого элемента ИЛИ подключен к счетному входу триггера. выход которого подключен к первому входу седьмого элемента И и

1778764

Составитель А.Мишин

Техред М.Моргентал Корректор В,Петраш

Редактор Н.Коляда

Заказ 4194 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 к инверсному входу шестого элемента И, первый выход формирователя импульсов подключен к второму входу седьмого элемента И, выход которого подключен к тактовому входу блока перебора комбинаций и к 5 входу сброса счетчика по модулю три, выход пятого элемента И подключен к входу сброса блока перебора комбинаций. второй выход формирователя импульсов подключен к второму входу шестого элемента И, выход 10 которого подключен к входу опроса блока сравнения эквивалентных ребер и через четвертый элемент задержки к первым входам восьмого и девятого элементов И, выход признака равенства единицы третьего 15 счетчика подключен к второму входу четвертого элемента И, к четвертому входу первого элемента ИЛИ, к инверсному входу пятого элемента И, к второму входу опроса блока дешифрации, к второму входу третьего эле- 20 мента и к третьему входу второго элемента

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

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