УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ГАМИЛЬТОНОВЫХ ЛИНИЙ НА СВЯЗНОМ ГРАФЕ Советский патент 1974 года по МПК G06F15/173 

Изобретение относится к цифровой вычислительной технике и .может быть применено при расчете траиснортной сети, сетевых графиков, тестов контроля электрических сетей и т. п. Известны устройства для определения гамильтоновых лииий на евязпом графе, имеющие п узлов и k ребер, содержащие кольцевой счетчик, jX линий задержк, /С логических схем суммирования и ключ управления, выходы которого подключены к регистрирующему блоку. Однако эти устройства не позволяют определять на связном графе всех возможных гамильтоновых линий минимальной длины, одинаковых по расстоянию и разных по конфигурации. Устрорютва также не позволяют определять всего множества гамильтоновых линий, охватывающих все узлы связного графа. Целью изобретения является уирощенне и повышение быстродействия устройства. Для этого устройство содержит схему запрета с одним минимальиым и п максимальными пороговыми элементами, а кольцевой счетчик содержит п регистров с числом ячеек в каждом регистре, равным числу ребер графе, сходящихся в данном узле, приче.м одноименные выходы кольцевого счетчика соединены со входами соответствующих логических схем сум.мироваршя, выходы которых подключены к ключу управления через линии задержки и ко в.хода.м пороговых эле.ментов, выходы которых соединены с управляющим входом ключа управления. На фнг. 1 представлен связной граф; на фиг. 2 - блок-схема устройства для определения ПОЛ1ЮГО множества гамнльтоновых линий на связном графе. Узлы графа нумеруются в ироизвольиом порядке; ребра графа обозначаются иерсменными (буквами), а их противоположные концы темн же переменными (буквамн) с индекса.ми, например противоположные концы ребер о, Ь, с и так далее соответстзе нно обозначаются (GI, fla). (bi, bz, (C|, Co) и т. д. Для каждого узла графа записывается его модель в виде сулпп) переменных, выражающих концы ребер графа, сходящихся в даниом узле. Так, .т,ля 1-го узла - (а-, + Ьо + Ci)i; для 2-го узла --- ( 1 + di}2; для З-го узла - (//2 + 2 + Оз; для 4-го узла - (С2 +/2 -Ь 2).. По моделям узлов записЕявается производящая функция F (а, -;- &, + Cj), (а., /, -- d,,(d2 + b-2+et}sX X (С2 + f2 - 2) .1.(1) Произведем ; налнтическое реигение производящей функции () с целью получения множества гамильтоновых линий. Для этого переыпожид переменные функции (1) (раскроем скобки) и в результате получим множество комбинаций (соединений) переменпых в виде суммы из произведений этих перемен.ных. F. (a, Н- bi + с,), (а, + /., + d,), (d.2 + bz+e,;X X (С2 + /о + 2)4 - .,c., + ...,-- aid2e,C2 + --.- baef.(2) При этом в каждую комбинацию переменпых множества (2) входит по одной переменной из каждой скобки функции (1). Из результата перег.пюжепия (2) вычеркиваются комбинации, не удовлетворяющие условиям существования гамильтоновых линий, т. е. комбииации, обладающие нризнаками: в ком. бииацию переменпых входит одна и та же переменная (с разными индексами) два и более раза (например, комбинации в выражении (2), вычеркнутые одной чертой); в комбииации переменных входит три и более переменных, принадлежащих одному и тому же узлу (иапример, комбинации в вьфажении (2), вычеркнутые двумя чертами). В полученном результате F bfdc + adec + baef. каждая комбинация из п перемепных (в пашем случае п 4) выражает гамильтонову линию, а все миожество комбипаций (G) - полное множество гамильтоновых линий на связном графе. Для оиределения длины отдельной гамильтоновой лннпн в соответствующую комбинацию вместо переменных, выражающих ребра графа, подставляются зпачепия их длип и затем все длины суммируются. Устройство содержит кольцевой счетчик 1, например, на динисторах с трансформаторными связями, имеющий п регистров 2, равное числу узлов связного графа. Каждый регистр 2 счетчика / содержит столько динисторных ячеек, сколько ребер трафа сходится в данном узле. Потенциальным выходам в каждом регистре присваиваются определепные переменные с иидексами, соответствующими концам ребер графа, сходящимся в данном узле. Выходы счетчика, которым присвоены одинаковые переменные с разными индексами, называются одноименными. При отработке полного цикла счетчик 1 переби.. рает все возможные комбииации переменных, соответствующие результату (2). Логические схемы 5 сложения по модулю 2 т- предназначены для удаления из комбипаций переменных результата (2), одииаковых переменных, которые содержатся в этих комбинациях. Схема запрета 4, в состав которой входят пороговый элемент 5 и пороговые элементы 6, предназначается для формирования «единичных сигналов «запрет при появлении на выходе счетчика 1 сигналов, соответствующих вычеркнутым комбинациям выражения (2). Пороговый элемент 5 принимает «единичное значение на выходе при числе имиульсов па входе «а (п-1) и служит для удалення из результата (2) комбинаций, в которые входит одна и та же переменная два и более раза. Назовем пороговый элемент 5 минимальным пороговым элементом. Пороговые элементы 6 принимают «единичные значения на выходе при числе импульсов на входах Пп - 3 и служат для удаления из результата (2) комбинаций, в которые входит три и более неременных, нринадлежащих одному и тому же узлу. Пазовем пороговые элемеиты 6 максимальиыми пороговыми элементами. Линии задержки 7 служат для задержки сигналов, постунающнх на рабочие входы 8 ключа 9 на уиравляющий вход Ю ключа 9 поступает сигнал «запрет с выхода схемы запрета 4. Регистрирующий блок 11 предиазначается для регистрации результата (3) в процессе отработки полного цикла счетчика /. Выходы регистров 2 счетчика / соединены со входами логических схем 3, причем на входы каждой схемы 3 подключаются только соответствующие одноименные выходы регистров 2, например (а, а, () и т. д. На входы счетчика 1 подается последовательность рабочих импульсов частоты / и команда «Исходное. Выходы логических схем 3 параллельно соединены через линии задержки 7 и ключ 9 со входами регистрирующего блока //, а также со входами норогового элеме1 та 5 и нороговых элементов 6 схемы запрета 4. Каждый пороговый элемепт 6 содержит число входов, равное числу ребер графа, сходящихся в данном узле, поэтому одия и тот же сипнал с .выхода :каждой логической схемы 3 подается одновременно на входы двух соответствующих пороговых элементов 6. Выходы пороговых элементов 5 п 6 соединены и подключены на вход 10 ключа 9. При подаче команды «Исходное включаются следующие динисторные ячейки регистров 2 счетчика /, имеющие выходы: а, а-2, bz, €2- По команде «Пуск на вход 12 счетчика / начииают поступать рабочие импульсы с частотой следования / и счетчик .вступает в работу. Число рабочих импульсов N, поступающих на вход 12 счетчика / задается и равно общему числу комбинаций выражения (2). Число N определяется по вырал ению (1) (IB давдном прИ|мере Л 3 3 ЗХ X , 3 - число переменных в скобке). Сигналы с выхода счетчика в виде параллельпых кодов, содержащих п «единиц из Л (К. - общее число выходов счетчика) последовательно поступают на логические схемы 3. Если на какую-либо логическую схему 3 сигнал поступает по двум входам, то па выходе таких схем будет «нулевой сигнал. Это соот.ветствует случаю, когда комбинация из п переменных содержит одноименные переменные, наоример (сь 122), (bi, bz) и т. д. Сигналы с выходов логических схем 3 через линии задержки 7 и ключ 9 поступают на вход регистрирующего блока 11. Каждая переменная, если открыт ключ 9, поступает на свой разряд в регистрирующем блоке 11 и фиксируется в виде «нулевого или «единичного значения. Одновре.менно сигналы с выходов лог.ическ1их схем 3 поступают на входы схемы запрета 4, которая формирует «единичный сигнал в том случае, когда параллельный код с выходов логических схем 3 не удовлетворяет условиям существования гамильтоиовых линий. При «единичном сигнале на выходе схемы запрета ключ 9 закрывается и соответствующий сигнал с выхода логических схем 3 не проходит на регистрирующий блок 11.

Предмет изобретения

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

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

,llcxoSH is

,