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

 

! >424152

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Со!оэ Советских

Социалистических

Республик (0l ) 33BIIC!i IOC OТ 3ВТ. CB!17OTC7BCТва (22) Заявлено 28.02.72 (21) 17531101 18-24 с присоединением заявки №вЂ” (32) Приоритет—

Опубликовано 15.04.74. Бюллетень ¹ 14 (51) 4l. 1 .7. 6 06(15/20

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.33.157..001 (088.8) Дата опубликования описания 27.02.75 (72) Автор изобретения

П. E. Чистяков (71) Заявнтсль (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ГАМИЛЪТОНОВЫХ ЛИНИЙ HA СВЯЗНОМ ГРАФЕ

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

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

Целью изобретения является упрощение и повышение быстродействия устройства. Для этого устройство содержит схему запрета с оде!им мн!Иимальным н и максимальными пороговыми элементами, а кольцевой счетчик содержит п регистров с числом ячеек в каждом регистре, равным числу ребер графе, сходящихся в данном узле, причем одноименные выходы кольцевого счетчика соединены со входами соответствующих логических .схем суммирования, выходы которых подключены к кл10ч2 уграBлсllия через ли!!ии 33держки и ко входам пороговых элементов, выходы которы.; соединены с управляющим входом ключа управления.

5 1-13 фнг. 1 представлен связной граф; на фнг. 2 — Олок-схема устройства для определения пî7! ого множссTBà г3мнльтоliовых лиI!HI! на связном графе.

3 злы ГP !ф3 н 1 1 !ОР ются в 17P0113B07ьнОъ!

10 порядке; ребра графя обозначаются псрсменными (буквамн), а их противоположные кон ы теми жс перемсннымн (буквамн) с нндекc371è, например противоположные концы реОср a, b, с ii T3i да 7ее соответст 7 "Bнo ООО15 значаются (а,, ае), (b!, !22), (с,, с2) н т. д.

Для каждого узла графа записывается его модель В Виде с1 о!мь! Перемс:lных. Bhlp3æ3þщнх ко! цы ребер графа, сходящихся в дан ном узле.

T3I, для 1-го узла — (а; + Ь - - с,),; для

2-го узла — (a — / + d!); g.7si 3-го узла

id2 + b2 + е,).; для 4-;о узла (с2 + f2 с2) °

По моделям узлов 33ïèc!>IB3åòcÿ произво25 дягцая ф нкция

F =(a, —; — b, + c,), (a. + j, -, — d,).2,(d2+b2+e )-.Х

X (с + !. - - с.) .:. (1) зо Пронзве-,ем i!;II!;IIITIIческое решение про

424152 изводящей функции (1) с целью получения множества гамильтоновых линий. Для этого перемножим переменные функции (1) (раскроем скобки) и в результате получим множество комоннаций (соединений) перемен- 5 ных в виде суммы из произведений этих переменных, F = (a, -,— 6, + с,}, (а. - ; f., + d,)

Х (с) + / > —: — e9) .> — Ь / Ас > +

- - baef. (d))+Ь >+e)),Х 10

-- a!dye!cg + (2) При этом в каждую комбинацию перемен- 15 ных мно?ксства (2) входит по одной переменной из каждой скобки функции (1). Из результата пере, ножения (2) вычеркиваются комбинации, не удовлетворяющие условиям существования гамильтоновых линий, т. е. р0 комбинации, обладающие признаками: в ком бинацию переменных входит одна и та же переменная (с разными индексами) два и более разя (например, комбинации в выражении (2), вычеркнутые одной чертой); в ком- 25 бинации переменных входит три и более переменных, принадлежащих одному и тому же узлу (например, комбинации в выражении (2), вычеркнутые двумя чертами).

В полученном результате 30

F = bfdc - ; adec + baef. (3) каждая комбинация из и переменных (в нашем случае и = 4) выражает гамильтонову 55 линию, а все множество комбинаций (3) полное множество гамнльтоновых линий на связном графе.

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

Устройство содержит кольцевой счетчик

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

55 данном узле. Выходы счетчика, которым присвоены одинаковые переменные с разными индексами, называются одноименными. При отработке полного цикла счетчик 1 переби рает все возможные комбинации переменных, 50 соответствующие результату (2). Логические схемы 8 сложения по модулю 2 (т)) предназначены для удаления из комбинаций переменных результата (2), одинаковых переменных, которые содержатся в этих комбинациях. Схема запрета 4, в состав которой входят пороговый элемент 5 и пороговые элементы 6, предназначается для формирования

«единичных» сигналов «запрет» при появлении на выходе счетчика 1 сигналов, соотве:ствующих вычеркнутым комбинациям выражения (2) . Пороговый элемент 5 принимает

«единичное» значение па выходе при числе импульсов н» входе n =. (и -! ) и слу?кнт для удаления из результата (2) комбинации, в которые входит одна и та же переменная два и более раза. Назовем пороговый эл >мент 5 минимальным пороговым элементом.

Пороговые элементы 6 принимают «единичные» значения lla выходе при числе импульсов на входах и>,:- 3 и служат для удаления из результата (2) комбинаций, в которы > входит три и более переменных, прннадлеж»щнх одному и тому же узлу. Назовем пороговые элементы 6 максимальными пороговыми элементами. Линии задержки 7 служа г для задержки сигналов> пост?>пающнх на р»бочие входы 8 ключа 9; на управляющий вход

10 ключа 9 поступает спгнал «запрет» с выхода схемы запрета 4. Регистрирующий блок

11 предназначается для регистрации результата (3) в процессе отработки полного цикла счетчика 1. Выходы регистров 2 счетчика 1 соединены со входами логических схем Л, причем па входы ка?кдой схемы 8 подключаются только соответствующие одноименные выходы регистров 2, например (а„а,), (b!,4) и т. д. На входы счетчика 1 подается последовательность рабочих импульсов частоты

f и команда «Исходное». Выходы логических схем 3 параллельно соединены через линни задержки 7 и ключ 9 со входами регистрирующего блока 11, а также со входами порогового элемента 5 и пороговых элементов 6 схемы запрета 4. Каждый пороговый элемент

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

6 соединены и подключены на вход 10 ключа 9.

При подаче команды «Исходное» включаются следующие динисторные ячейки регистров 2 счетчика 1, имеющие выходы: al, а,, b>, c . По команде «Пуск» на вход 12 счетчика 1 начинают поступать рабочие импульсы с частотой следования f и счетчик вступает в работу. Число рабочих импульсов N, поступающих на вход 12 счетчика 1 задается и равно общему числу комбинаций выражения (2). Число N определяется по выражению (1) (в дa!HIHoì,ïðèìåðå N = 3 . 3 ЗХ

X 3 = 81, 3 — число переменных в скобке).

Сигналы с выхода счетчика в виде параллельных кодов, содержащих и «единиц» из К (К вЂ” общее число выходов счетчика) после424152 довательно поступают на логические схемы 8.

Если на какую-либо логическую схему 8 сигнал поступает по двум входам, то на выходе таких схем будет «нулевой» сигнал. Это соответствует случаю, когда комбинация из и переменных содержит одноименные переменные, например (аь а ), (Ьь b>) и т. д. Сигналы с выходов логических схем 8 через линии задержки 7 и ключ 9 поступают на вход регистрирующего блока 11. Каждая переменная, если открыт ключ 9, поступает на свой разряд в регистрирующем блоке 11 и фиксируется в виде «нулевого» или «единичного» значения. Одновременно сигналы с выходов логических схем 8 поступают на входы схемы запрета 4, которая формирует «единичный» сигнал в том случае, когда параллельный код с выходов логических схем 8 не удовлетворяет условиям существования гамильтоновых линий. При «единично»» сигнале на выходе схемы запрета ключ 9 закрывается и соответствующий сигнал с выхода логических схем 8 не проходит на регистрирующий блок 11.

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

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

424152

Фиг.!

> -z

Редактор Л. Тюрина

Корректор И. Симкина

Заказ 766/79 Изд. № 1595 Тираж 624 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 7К-35, Раушская наб., д, 4/5

Тип. Харьк. фил. пред, «Патент»

Составитель В. Озеров

Техред Е, Борисова

I