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

О П И С А Н И Е ц 424152ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистицеских Республик(22) Заявлено 28.02.72 с присоелинецием заяв. 1) Л 1. 1 л. 6 06 1520 И ,о -Гссударственныи кемнтеСввета Мииистрав СССРпо делам изабретеиийи открытий(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ АМИЛЪТОНОВЫХ ЛИНИЙ НА СВЯЗНОМ ГРАФ- с 1)2( Произведем 30 паралитическое зепец Изобретепие отцосится к цифровой вычислительной технике и может быть применено при расчете трапспортцой сети, сетевых графиков, тестов контроля электрических сетейит, п.Известы устройства для определения гамильтоцовых линий ца связном графе, имеющие л узлов и гг ребер, содержащие кольцевой счетчик, К линий задержки, К логических схем суммирования и (люч управления, выходы которого полклочепы к регистрирующему блоку. Однако этц устройства це позволяют определять па связном графе всех возможных гамильтоцовых линий мицимальцой длины, одинаковых по расстоянию и разных по (опфцгурации, Устройства также не позволяют определять всего множества гамильтоновых линий, охватывающих все узлы связного графа.Целью изобретения является упрощение и повышение быстродействия устройства. Для этого устройство содержит схему запрета с одиим мпцимальцым ц гг максимальными пороговыми элементами, а кольцевой счетчик содержит и регистров с числом ячеек в каждом регистре, равным числу ребер графе, сходящихся в данном узле, причем одноимепцые выходы кольцевого счетчика соединены со входами соответствующих логических схем суммировация, выходы которых подключены и 1(лочу упзявлспця через лцпип задержки и ко входам пороговых элементов, выходы которых соедццепы с управляющим входом ключа управления.Иа фпг.прслставлец связной граф; ца фпг. 2 - олок-схема устройства лля определения полцого множества гямпльтоцовых ливий на связном графе.Узлы графа нумеруются в процзвольпом порядке; ребра графя обозцачаются псрсмепными (буквамц), а цх противоположные концы теми жс перемсццымц (буквямп) с ццдексами, например противоположные концы репер а, Ь, с ц тяк лалсс соответстзсццо ооозпачаются (а ао), (Ь (22), (сь с 2) и т, д, Для каждого узла графа записывается его модель в вцле с 1 ммы перемсццых, выражающих коццы ребер графя, сходящихся в лянцом узле.Так, для 1-го узла - (а, + (222-го узла - (а 2+ , + 4) о; для 3(с 2 + г 2с 2)1По моделям узлов записывается производящая функцияР = (а, - ;- Ь, + с А+2 -с 1;Хизволящей функции (1) с целью получения множества гамильтоцовых лиций. Для этого перемцожим переменные функции (1) (раскроем сд(обки) и в результате получим мцожество комоццаций (соедццеций) перемен цых в виде суммы из произведений этих перемеццых,1,+Ь+е,),Х 1 Оа,4 е,с, + Р = (а, -, - Ь, + с,), (а: -; Г, + д,)Х (с + 1 - : е 2)- Ь,АС +Ьае 1,(2) Г = Ьйс -; айес + Ьае 1, (3) каждая комбинация из и переменных (в пашем случае и = 4) выражает гамильтоцову 35линию, а все множество комбинаций (3)полное множество гампльтоцовых линий цасвязном графе. Для определения длины отдельной га мильтоцовой линии в соответствующую комбицацию вместо перемецпых, выражающих ребра графа, подставляются значения их длин и зтем все длины суммируются.45 Устройство содержит кольцевой счетчик 1, например, ца дицисторах с трансформаторными связями, имеющий и регистров 2, равное числу узлов связного графа. Каждый регистр 2 счетчика 1 содержит столько динисторцых ячеек, сколько ребер графа сходится в данном узле, Потецциальпым выходам в каждом регистре присваиваются определенные перемеццые с индексами, соответствующими концам ребер графа, сходящимся в55 данном узле, Выходы счетчика, которым присвоецы одинаковые перемецпые с разными индексами, называются одноименными. При отработке полного цш(ла счетчик 1 переби. рает Все Возможцые комбинации перемеццых, соответствующие результату (2). Логические схемы 3 сложеция по модулю 2 (т) предназначены для удаления из комбинаций переменных результата (2), одинаковых перемеццых, которые содержатся в этих комбиПри этом в каждую комбинацию перемец пых мцожсства (2) входит по одной переменцой из каждой скобки функции (1). Из результата перемножения (2) вычеркиваются комбинации, пе удовлетворяющие условиям существования гамильтоцовых линий, т. е. 20 комбинации, обладающие признаками: в (ом. бица переменных входит одца и та же персмеццая (с разными индексами) два и более раз (цапример, комбинации в выраже. ции (2), вычеркнутые одной чертой); в ком бицации переменных входит три и более переменных, прицаллежащих одному и тому же узлу (цапример, комбицации в выражеции (2), вычеркнутые двумя чертами).В получеццом результате 30 нациях. Схема запрета 4, в состав которой входят пороговый элемент б и пороговые эле. менты б, предназначается лля формировация едицичцых сигналов запрет цри появлеции ца выходе счетчика 1 сигналов, соответствующих вычеркнутым комбицацпям выражеция (2), Пороговый элемент 5 принимает едицичцос значение па выходе при числе импульсов и входе ид %, (и -1) и слукцт для удалецпя из результата (2) комбинации, в которые входит олца и та же персмсццая лва и более раза. Назовем пороговый эл. мент б минимальным пороговым элемецтом. Пороговые элементы 6 принимают елицичцые зцачеция ца выходе при числе импульсов ца входах ио : 3 и служат лля удаления из результата (2) комбпцаццй, в которые входит три и более перемеццых, прццаллеж- щцх одному и тому же узлу. Назовем пороговые элементы б максимальными пороговыми элемецтами. Линии задержки 7 слуи(аг для задержки сигналов, поступающих ца р- бочие входы 3 ключа 9; ца управляющий вход 10 ключа 9 поступает сцгцал запрет с выхода схемы запрета 4. Регистрирующий блок 11 предназначается для регистрации результата (3) в процессе отработки полного цикла счетчика 1. Выходы регистров 2 счетчика 1 соединены со входами логических схем 3, причем па входы каждой схемы 3 подключаются только соответствующие одноименные выходы регистров 2, например (аь а), (Ьг М и т, д. На входы счетчика 1 подается последовательцость рабочих импульсов частоты 1 и команда Исхолцое. Выходы логических схем 3 параллельно соелицецы через лицци задержки 7 и ключ 9 со входами регистрирующего блока 11, а также со входами порогового элемецта Ь и пороговых элементов 6 схемы запрета 4. Каждый пороговый элемент б содержит число входов, равное числу ребер графа, сходящихся в лаппом узле, поэтому один и тот же сигнал с выхода каждой логической схемы 3 подается олцовремепцо и входы двух соответствующих пороговых элементов б, Выходы пороговых элементов 5 и б соединены и полключецы ца вход 10 ключа 9. При подаче комацды Исходное включаются следующие лицисторцые ячейки регистров 2 счетчика 1, имеющие выходы: аь а Ь с. По команде Пуск ца вход 12 счетчика 1 начинают поступать рабочие импульсы с частотой следования 1 и счетчик вступает в работу, Число рабочих импульсов У, поступающих ца вход 12 счетчика 1 задается и равпо общему числу комбинаций выражеция (2). Число Л определяется по выражецию (1) (в даии,ом,примере У = 3 3ЗХ Х 3 =81, 3 - число переменных в скобке). Сигналы с выхода счетчика в виде параллельцых кодов, содержащих и едициц из К (К - общее число выходов счетчика) после 424152довательно поступают на логические схемы 3. Если на какую-либо логическую схему 3 сигнал поступает по двум входам, то на выходе таких схем будет нулевой сигнал. Это соответствует случаю, когда комбинация из гг переменных содержит одноименные переменные, например (а а), (Ьь Ь) и т. д. Сигналы с выходов логических схем 3 через линии задержки 7 и ключ 9 поступают на вход регистрирующего блока 11. Каждая переменная, если открыт ключ 9, поступает на свой разряд в регистрирующем блоке 11 и фиксируется в виде нулевого или единичного значения. Одновременно сигналы с выходов логических схем 3 поступают на входы схемы запрета 4, которая формирует единичный сигнал в том случае, когда параллельный код с выходов логических схем 3 не удовлетворяет условиям существования гамильтоновых линий, При единичном сигнале на выходе схемы заврета ключ 9 закрывается и соответствующий сигнал с выхода логических схем 3 не проходит на регистрирующий блок 11,Предмет изобретения Устройство для определения гампльтоновых линий на связном графе, имеющем и уз лов н й ребер, содержащее кольцевой счетчик, К линий задержки, К логических схем суммирования и ключ управления, выходы которого подключены к регистрирующему блоку, отличагогцееся тем, что, с целью упро щения и повышения быстродействия устройства, оно содержит схему запрета, выполненную на гг пороговых элементах с максимальными порогами, с одним минимальным порогом, а кольцевой счетчик содержит гг регист ров с числом ячеек в каждом регистре, равным числу ребер графа, сходящихся в данном узле, причем одноименные выходы кольцевого счетчика соединены со входами логических схем суммирования в соответствии с топологией графа, выходы которых подключены к ключу управления через линии задержки и ко входам пороговых элементов, выходы которых соединены с управляющим входом ключа управления.424152 Фиг. гг Составитель В. ОзерТехред Е, Борисов Тюрина Редакт ип. Харьк. фил. пред. Патент аказ 766/79 Изд,Ц 1-1 ИИПИ Государственн по делам Москва, 7 К95ого комитета Соизобретений и о5, Раушская на раж 624ета Миюскрытийд, 4/5 рректор И. Симкина Подписное ов СССР