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

5 10 15 20 25 30 40 4550 ИЛИ 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, ко второму входу опроса блока дешифрации 20 ко второму входу элемента И 13 и к третьему входу элемента ИЛИ 23, выход элемента И 18 подключен ко второму входу элемента ИЛИ 21, выход которого подключен к суммирующему входу счетчика 10, выход элемента ИЛИ 20 подключен ко входу синхронизации счетчика 9, выход признака перехода через ноль которого подключен к суммирующему входу счетчика 8 и, через элемент задержки 19, к третьему входу элемента ИЛИ 20 и ко второму входу элемента ИЛИ 14, выход признака равенства блока сравнения эквивалентных ребер 4 подключен ко второму входу элемента И 30, выход которого подключен к входу элемента ИЛИ 17, выход признака неравенства блока сравнения эквивалентных ребер 4 подключен ко второму входу элемента И 31, выход которого подключен к вычитающему входу счетчика 9.В основу работы устройства положен следующий алгоритм, Задача нахождения гамельтонова цикла (ГЦ) заключается в нахождении такового маршрута, который проходил бы по всем вершинам графа один раз и начинался и заканчивался бы в одной и той же вершине. В основу работы устройства положен алгоритм нахождения ГЦ, основанный на понятии "ЭКВИВАЛЕНТНОГО" ребра ЗР). Вершина с локальной степенью два имеет только "ВХОД" и "ВЫХОД" - т,е.является транзитной и выполняет функции ребра "Обычное ребро в графе соединяет две вершины 1 и 1 и имеет вид 0=(1,3). Еслирассматривать как ребро вершину с локальной степенью два, то данное ребро соединит уже три вершины 11, К, (где, 1-вершина с локальной степенью два).ГЦ проходит по всем вершинам графа один раз (т,е. один раз в каждую вершинувходит и од и н раз в ы ходит). Сл едо вател ь но, если в графе существует ГЦ, то у всех вершин графа, независимо от их локальных степеней, в ГЦ входит по два ребра, Каждой вершине графа инцидентно гп ребер (а=2,3И - 1, где М - колицество вершин вграфе). Можно составить различные комбинации прохождения вершин графа (т.е, различные комбинации "вход" - "выход"),которые называются ЗР, Следовательно, ЭР соединяет три вершины 1, 1, К и имеет вид 1.1=(1К). Данная последовательность вершин в О показывает связность вершин 1 и 1,.1 и К соответственно. Для каждой вершины графа можно составить определенное количество ЗР, определяемое для неориентированных графов как Р=С тьИдея алгоритма заклюцается в нахождении последовательности ЗР, в состав которых входили бы все вершины графа один раз, причем номера начальной и конечной вершин графа, входящих в данную последовательность, должны совпадать. Номер последней вершины данного ЭР определяет номер следующей вершины, для которойищется ЗР, в состав которого не входили бы уже рассмотренные вершины, Если такогонет, то производится возврат к предыдущему рассмотренному ЭР, вместо которого находится новое "Процесс продолжается, пока все вершины графа не будут входить в последовательность найденных ЭР (в слу-цае существования ГЦ), либо пока не будетустановлено, что ГЦ в данном графе нет (вэтом случае будут рассмотрены все ЭР дляначальной вершины, а ГЦ не будет найден).оличество ЭР для построения ГЦ;М/2 - когда в графе четное 5Ч = число вершин, (1)1М/2+ -- когда в графе нечетное2число вершин,Если рассмотрено (Ч) ЭР, то меняется условие выбора последнего ЭР (это условиеразлично для случаев четного и нечетногоколичества вершин в графе). Если на предыдущих шагах работы алгоритма определялось первенство номеров второй и третьей 15вершин рассматриваемого ЭР с номерамиранее рассмотренных вершин, то на последнем шаге условие меняется.В случае чегкого количества вершин вграфе номер третьей вершины последнего 20(т.е. Ч-го) ЭР должен соответствовать номеру начальной вершины, с которой начинается поиск ГЦ(чтобы замкнуть цикл). В случаенечетного количества вершины номертретьей вершины последнего Э Р должен соответствовать номеру начальной вершины,Если предусмотреть возможность определения ГЦ для обоих случаев, то необходимы дополнительные аппаратные затраты,Чтобы избежать этого, предлагается ограничить работу устройства определением ГЦв гоафах с нечетным количеством вершин. Вслучае четного количества вершин передначалом работы необходимо в исходныйграф ввести дополнительную "фиктивную" 35вершину, которая была бы смежна с начальной и со всеми вершинами смежными с начальной вершиной. В этом случае ввод"фиктивной" вершины не повлияет на существование ГЦ в рафе и на последовательность вершин в найденном ГЦ в случае егосуществования, Поиск ГЦ необходимо начинать с "фиктивной" вершины,Работу алгоритма рассмотрим на примере графа С=: (Х,О),Х 1= 6,(01 8, матрица 45смежности которого имеет вид:123456 1001101 001011 110100 101000 01 0001 50 110010 За начальную вершину примем Х 1, Для нее составим первые Э Р: 0-: (1,3,2). Послед няя цифра данного ЭР определяет номер следующей вершины, для которой ищется ЭР,-в состав которого не входили бы уже рассмотренные вершины: О = (2,5,6). Для шестой вершины не существует ЭР, в состав которого не входили бы уже рассмотренныевершины 1,2,3,4,5, Поэтому производимвозврат и формируем новое ЭР для второйвершины; О(2,6,5). Для пятой вершины также не существует ЭР, в состав которого невходили бы уже рассмотренные вершины1,3.2,6, Производим возврат. Для второйвершины больше не существует ЭР, поэтому производим возврат еще на один шаг исоставляем новое ЭР для первой вершины;0=(1,3,4), Для четвертой вершины не существует ЭР, в состав которого не входили быуже рассмотренные вершины 1,3, поэтомусоставляем новое ЭР для первой вершины:О=(1,3,4). Для третьей вершины находим ЭР,в состав которого не входят рассмотренныевершины 1,4; О=(3,2,5),Количество вершин в рассматриваемомграфе - 6, Поэтому число ЭР для построенияГЦ: Ч=М 2=3, Рассмотрено (Ч) ЭР. Меняется условие выбора Ч-го ЭР, Такое ЭР существует;О = (1,4,3), О =(3,2,5), О = (5,6,1)Данная последовательность вершин образует ГЦ 1-4-3 - 2 - 5 - 6-1,Подготовка устройства к работе заключается в следующем;1. Запись в регистр 11 номера начальной вершины;2. Задание топологии графа в блоке проверки связности графа;3. Запись в счетчик 10 количества ЭР,необходимых для построения ГЦ (согласноформуле 1);4. Подача сигнала через элемент ИЛИ 17на вход триггера 7 и установка на его прямом выходе уровня логической единицы;5. Запись в блок перебора комбинаций1 через информационный вход комбинациичисел, соответствующей первому ЭР для начальной вершины (последняя цифра ЭР, соответствующая номеру третьей вершинывходящей в ЭР вершины, уменьшена на единицу - с приходом первого тактового импульса в блоке перебора комбинации 1установится первое ЭР для начальной вершины).,ЭР формируются в блоке 1 переборакомбинаций (БПК 1), Тактовые импульсы поступают на тактовый вход БПК 1. Т.к, в тройке вершин, образующих ЭР, не должно бытьвершин с одинаковыми номерами, то на выходе признака несовпадения БПК 1 сигналпоявится только в том случае, когда средисравниваемых чисел нет одинаковых,Если ЭР записывается в блок памяти 5(БП 5) - т.е. предполагается, что через это ЭРпроходит ГЦ - на вход сброса БПК 1 поступает сигнал, по которому формирование нового Э Р будет производиться для последнейрассмотренной вершины, Если для вершины, номер которой определяется последней цифрой последнего записанного в ЭР, не существует ЭР, в состав которого не входили бы уже рассмотренные вершины, необходимо вместо записанного ЭР сформировать новое. В этом случае по сигналу с выхода признака завершения перебора БПК 1 формируется код последнего записанного в БП 5 ЭР и данное ЭР запишется в БПК 1, Т.е,. формирование нового ЭР будет производиться, начиная с записанной комбинации вершин,Сформированное в БПК 1 ЭР необходимо проверить на связность (т.е, связны ли первая и вторая, вторая и третья входящие в ЭР вершины), Проверка связности входящих в ЭР вершин осуществляется в блоке 3 проверки связности графа(БПСГЗ), который может бьть выполнен по схеме, предложенной в а,с. 1086434, Перед началом работы необходимо в БПСГЗ задать топологию графа (согласно описанию, представленному в данном а.с,), Работа БПСГЗ заключается в следующем. На два входа БПСГЗ, соответствующих номерам проверяемых на связность вершин, подаются сигналы, Если данные вершины связны, то навыходе признака связности БПСГЗ появится единичный сигнал. Информация о номерах вершин, проверяемых нэ связность, должны подаваться в унитарном коде. Для преобразования двоичного кода, поступающего с БПК 1, в унитарный код служит блок 2 дешифрации (БДш 2). Т.к, необходимо проверить связность двух пар вершин (первой и второй, второй и третьей соответственно), то с БДш 2 на бПСГЗ должен последовательно поступать код номеров первой и второй, а затем второй и третьей вершин,Когда в бПК 1 сформируется ЭР, в составе которого нет одинаковых цифр, на выходе признака несовпадения появится сигнал, который:- поступит через схему ИЛИ 17 на вход триггера 7 и перебросит его (т.е. на выходе триггера установится уровень логического О). Схема И 16 закроется и тактовые импульсы не будут поступать нэ БПК 1:- через элемент ИЛИ 23 и элемент задержки 24(величина которой равна времени срабатывания БДш 2 и БПСГЗ) поступит на вторые входы схем И 25 и И 26, Если вершины связны, сигнал появится на выходе элемента И 25, если же не связны - на вьходе элемента И 26;- через элемент задержки 22 поступит на второй вход элемента ИЛИ 23. 5 10 15 20 25 30 35 40 45 50 На БПСГЗ поступят последовательно коды номеров первой и второй, второй и третьей вершин ЭР соответственно. Т.к. необходимо проверить связность двух пар вершин, то если сформированное ЭР существует в иссследуемом графе, то с выхода признака связности БПСГЗ должно поступить два сигнала.Сигнал с БПСГЗ поступает через открытый элемент И 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 и откроет его, Импульсы с периодом 72 (величина ко50 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 поступгт номера второй и третьей вершин сформированного ЭР, Если. одинаковых номеров нет, то на выходе признака несовпадения БСЭР 4 появится сигнал, который; 1) поступит через схему ИЛИ 20 на синхровход счетчика 8, где уже записан адрес предпоследнего рассмотренного ЭР, и аналогичным образом произойдет сравнение второй и третьей цифр сформированного ЭР с предпоследним ЭР, 2) снова уменьшит сос 1 ояние счетчика 9 на 1. Процесс будет продолжаться до тех пор, пока:- не появится сигнал признака равенства с БСЭР 4 (означающий, что есть в сформированном ЭР номера уже рассмотренных вершин). Этот сигнал поступит через схему ИЛИ 17 на триггер 7, перебросит его и откроет элемент И 16;- не появится сигнал с выхода признака перехода через 0 счетчика 9 (означающий,что все записанное в БП 5 ЭР сравнены с сформированным ЭР, а одинаковых номеров вершин не найдено), По этому сигналу данное ЭР запишется в БП 5, а сигнал поступит на суммирующий вход счетчика 8, где хранится адрес последнего записанного ЭР, и увеличит этот адрес на единицу (т.е. сформируется адрес следующей ячейки), через элемент задержки 19 (величина которой определяется временем срабатывания счет 5 10 15 20 25 30 35 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) открывается и происходит дальнейшее формирование ЭР. Если же оба условия выполняются (т.е, первая и вторая, вторая и третья вершины, входящие в ЭР, связны, и они ранее не рассматривались), то пбявляется сигнал с выхода элемента задержки 15, по которому элемент И 16 откроется и ТИ начнут поступать на БПК, который уже находится в исходном состоянии,Блок памяти БП 5 состоит из трех идентичных ОЗУ, В каждом ОЗУ хранится код номера одной вершины ЭР. Счетчик 8 служит для остановки работы устройства. Перед началом работы в счетчик 8 записывается информация о количестве ЭР, необходимых для построения ГЦ(вычислен 17787 б 4 12ное по формуле), Как только ЭР записывается в БГ 15, с выхода элемента задержки 15 сигналпоступаег 1 на,вычитающий вход счетчика 10 и умейьшает его состояние на 1, Если не производится возврат, то по сигна лу признака завершения перебора с БПК 1 содержимое счетчика 10 увеличивается на 1 (сигнал с БГ 1 К 1 поступает через элемент ИЛИ 21 на его суммирующий вход).Сигнал с выхода перехода через О счет чика 10 означает. что ГЦ найден.Если сформировано (Ч - 1)ЭР, необходимо проверить на связность последнюю рассмотренную и начальную вершины, Номер начальной вершины перед началом работы 15 записывается в регистр 11.Сигнал с выхода признака равенства единице счетчика 8 поступит:- на второй вход схемы И 18, Если последняя рассмотренная и начальная верши ны не связны. то на первьй вход схемы И 18 поступит сигнал, который откроет схему И 18 и через схему ИЛИ 21 увеличит состояние счетчика 8 на единицу;- через схему ИЛИ 17 на счетный вход 25 триггера 7, перевернет его и закроет схему И 16;- на второй вход опроса БДш 2, По этому сигналу на БДш 2 поступят коды начальной и (п - 1)-й вершин; 30- на первый вход схемы И 13, Если(п)- ая и начальная вершины связны, на второй вход схемы И 13 поступит сигнал и откроет схему И 13:- на инверсный вход элемента И 12 и 35 закроет его (чтобы предпоследнее ЭР осталось записанным в БПК, и если начальная и (и - 1) вершины не связны, то формирование новой ЗР происходило с данной комбинации чисел). 40Если данные вершины связны, то сигнал через открытую схему И 13, схему ИЛИ 14, и элемент задержки 15 поступит на вычитающий вход счетчика 10. Счетчик 10 прийдет в нулевое состояние, и на выходе 45 признака перехода через 0 счетчика 8 появится сигнал, означающий, что ГЦ найден,Если вершины не связны, то сигнал через открытую схему И 18 и схему ИЛИ 21 поступит на суммирующий вход и увеличит 50 состояние счетчика на единицу.Формула изобретенияУстройство для определения гамильтоновых циклов на графе, содержащее блок перебора комбинаций, блок проверки свяэ ности графа, блок памяти и пять элементов задержки, отличающееся тем,что,с целью повышения быстродействия устройства, в него введены формирователь импульсов, блок дешифрации, блок сравнения эквивалентных ребер,.триггер, три счетчика, регистр, счетчик по модулю три, девять элементов И и пять элементов ИЛИ, причем информационный выход блока перебора комбинаций подключен к первым информационным входам блока дешифрации и блока сравнения эквивалентных ребер и к информационному входу блока памяти, информационный выход регистра, подключен к второму информационному входу блока дешифрации, информационный выход блока памяти подключен к второму информационному входу блока сравнения эквивалентных ребер и к информационному входу блока перебора комбинаций, информационный выход первого счетчика подключен к информационному входу второго счетчика, информационный выход которого подключен к адресному входу блока памяти, выход признака несовпадения комбинаций блока перебора комбинаций подключен к первому входу опроса блока дешифрации и к первым входам первого и второго элементов ИЛИ, выход признака завершения перебора блока перебора комбинаций подключен к первому входу третьего элемента ИЛИ, к вычитающему входу второго счетчика и к первому входу четвертого элемента ИЛИ, выход признака выдачи информации блока дешифрацйи подключен к второму входу второго элемента ИЛИ, выход которого через первый элемент задержки подключен к первым входам первого и второго элементов И, информационный выход блока дешифрации подключен к информационному входу блока проверки связности, выход признака связности которого подключен к второму входу первого элемента И, выход признака отсутствия связности блока проверки связности подключен к второму входу второго элемента И, выход первого элемента И подключен к первому входу третьего элемента И и к счетному входу счетчика по модулю три, выход второго элемента И подключен к первому входу четвертого элемента И и через второй элемент задержки к второму входу первого элемента ИЛИ, выход третьего элемента И подключен к первому входу пятого элемента ИЛИ, выход которого подключен к прямому входу пятого элемента И и через третий элемент задержки к входу синхронизации блока памяти, к вычитающему входу третьего счетчика и к третьему входу первого элемента ИЛИ, выход счетчика по модулю три подключен к второму входу четвертого элемента ИЛИ и к первому входу шестого элемента И, выход первого элемента ИЛИ подключен к счетному входу триггера. выход которого подключен к первому входу седьмого элемента И и13 1778764 14 Составитель А,Миши Техред М.Моргентал Корректор В,Пет едактор Н.Коляд аказ 4194 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 роизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 к инверсному входу шестого элемента И, первый выход формирователя импульсов подключен к второму входу седьмого элемента И, выход которого подключен к тактовому входу блока перебора комбинаций и к 5 входу сброса счетчика по модулю три, выход пятого элемента И подключен к входу сброса блока перебора комбинаций. второй выход формирователя импульсов подключен к второму входу шестого элемента И, выход 10 которого подключен к входу опроса блока сравнения эквивалентных ребер и через четвертый элемент задержки к первым входам восьмого и девятого элементов И, выход признака равенства единицы третьего 15 счетчика подключен к второму входу четвертого элемента И, к четвертому входу первого элемента ИЛИ, к инверсному входу пятого элемента И, к второму входу опроса блока дешифрации, к второму входу третьего эле мента и к третьему входу второго элемента ИЛИ, выход четвертого элемента И подключен к второму входу третьего элемента ИЛИ, выход которого подключен к суммирующему входу третьего счетчика, выход четвертого элемента ИЛИ подключен к входу синхронизации второго счетчика, выход признака перехода через ноль которого подключен к суммирующему входу первОго счетчика и через пятый элемент задержки к третьему входу четвертого элемента ИЛИ и к второму входу пятого элемента ИЛИ, выход признака равенства блока сравнения эквивалентных ребер подключен к второму входу восьмого элемента И, выход которого подключен к пятому входу первого элемента ИЛИ, выход признака неравенства блока сравнения эквивалентных ребер подключен к второму входу девятого элемента И, выход которого подключен к вычитающему входу второго счетчика.