Устройство для моделирования графов Советский патент 1987 года по МПК G06F7/48 

1

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

Целью изобретения является расширение класса решаемых задач за счет нахождцения максимального цикла в графе.

На чертеже изображен пример функциональной схемы устройства для фа имеющего четыре узла (М 4) г.

Устройство для моделирозания графов содержит модель 1 графа,, составленную из моделей 2 ребер и М ключей 3, где М - количество узлов в модели 1 графа, соединенных согласно топологии графа, модель 4 ребра, два ключа 5 и 6, коммутатор 7, два рас пределителя 8 и 9 импульсов, два элемента ИЛИ 10 и 11, триггер 12, генератор 13 напряжения,блок 14 сравнени и наддиагональную матрицу 15 из М-1 (столбцов моделирунлцих элементов 16,.. содержащих два ключа 17 и ISf при3

чем выход первого ключа 17 подключен к информационному входу второго ключа 18, модель 4 ребра; информационный вход которой подключен к кк- формационному входу блока 19 памй:тиэ и развязьюающий элемент 20, информационный вход которого подключен к информационному выходу модели 4 вход пуска генератора 21 шульсов является входом пуска устройства; выход генератора 21 импульсов подключен к информационному входу коммутатора 75 первый и второй информа- тдионные. выходы которого подключены к информационным входам первого 8 и второго 9 распределителя импульсов соответственно, К--й информационный выход первого распределителя 8 им-- пульсов (К Ij,. М-1) подключен к управляющим входам первых ключей всех моделирующих элементов К-й строки наддиагональной натрицы 15 моделирующих элементов и к К-му входу первого элемента ИЛИ 10 Е .ЫХОД которого подключен к инфорнапионнощ входу триггера 12 информационный выход которого подклк чен к управляющему входу коммутатора 7g К-й информа- ционньй выход второго распредепителя 9 импульсов подключен к угфав-ляюгфгг- входам вторых, ключей всех моделйрз 0 щих элементов К-го столбца наддиаго- нальной матрицы 15 моделирующих эле--

108072

ментов, к управляющему входу (К + 1) го ключа 3 модели 1 графа и к K-i-ry входу второго элемента ИЛИ 11, выход которого подключен к входу опроса

5 генератора 13 напряжения, информационный выход которого подключен к информационньш входам первых ключей 17 всех моделирующих элементов 16, информационные выходы развязывающих

С элементов 20 всех моделирующих элементов 16 К-й строки наддиагональной матрицы 15 моделирующих элементов 16/ подключены к информационному входу К-го ключа 3 модегш 1 графа, информа55 ционные выходы всех ключей 3 модели 1 графа подключены к управляющему входу первого ключа, информационный выход которого подключен к входу установки в О генератора 13 линейно20 изменяющегося напряжения, информационные выходы блоков 19 памяти моделирующих элементов 16 наддиагональной матрицы 15 моделирующих элементов 16 подключены к соответствующим

входам блока 14 сравнения, выход которого- является выходом устройства, (М-1)-и выход первого распределителя 8 импульсов подключен к управляющему входу второго ключа 6, информацион30 |нь:й выход которого подключен к входу останова геке;ратора 21 импульсов и является вьшодом признака окончания работы устройства, (М-1)-и информа- ционньБЙ выход второго распределителя

35 9 импульсов подключен к установочному входу триггера 12 и к информа- ци:онно.гу входу второго ключа 6 йн- формационньй вход первого ключа 5 являет:iH входом признака установки 40 генератора 13. Модель 2 ребра содер- жит тиристор 22.. источник 23 напря- . жения,) переменный резистор 24 и раз- зязывающие диоды 25-28,

7/стройство работает следующим об- разом,

В исходном состоянии распредел - - тели 8 и 9 и триггер 22 обнулены .ключи 3j 17, 18 и 6 закрыты С помощью переменных резисторов 24 устанавливают токи в управляющих цепях тиристоров 22 соответственно заданным напряжениям переключения, пропорцио- 1альньм весам ребер графа

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

0

S

А, В, С, D и ребрами АВ, ВС и BD. В этот граф могут быть включены ребра АС, AD и CD, соответственно которым в матрице 15 участвуют моделирующие элементы 16(АС), 16(AD) и 16(CD). После пуска устройства импульс генератора 2 поступает через коммутатор 7 на вход распределителя 8, который вьщает единичный потенциал

со своего первого информационного реле не протекает ток, так как на

хода на управляющие входы ключей 17 моделей 16 первой строки матрицы 15, соответствующих узлу А графа, т.е. опрашиваются ребра, инцидентные узлу А.

Единичный сигнал с первого выхода распределителя 8 проходит через элемент ИЛИ 10 на информационньш вход триггера 12, который выдает единичный потенциал на управляющий вход коммутатора 7, переключающего свой информационный вход на второй выход. Поэтому следующий импульс генератора 21 поступает на вход распределителя 9, который вьщает на свой первьш выход прямоугольный импульс, а затем по поступлении следующего импульса генератора 21 - прямоугольный импуль на свой второй выход. Этот импульс поступает на управляющие входы ключе 18 моделей 16 второго столбца матрицы 16 и открывает их. Аналогично после поступления единичного потенциала на упрарляющий вход открывается ключ 3 модели 2С.

Кроме того, передний фронт импульса с выхода распределителя 9, пройдя через элемент ИЛИ 11 на вход опроса генератора 13, обусловливает вьщачу на выходе генератора 13 линейно-возрастающеговеличине Е

ходит подключение тиристоров 22 моделей 2 некоторой совокупности ребер графа. Ток протекает по цепи: выход генератора .13, информационные входы- выходы ключей 17 и 18, модель 16 (АС), модель 2(А, С), разделительный диод 20 модели 16 (аС), ключ 3(А), модель 2(А,В), ключ 3(В), модель 2(В,С), ключ 3(С), информационный выход ключа 3(С), управляющий вход ключа 5, в качестве которого может выступать например, обмотка реле, выход которой подключен к нулевому потенциалу устройства.

Единичный потенциал, соответствующий признаку сброса генератора 13,

напряжения. При некоторой д (, этого напряжения проис

проходит через исполнительную цепь ключа (например через контакт реле) и сбрасывает в О напряжение на выходе генератора 13. Длительность импульсов распределителя 9 выбирается такой, чтобы до их окончания успевал произойти сброс генератора 13. По окончании импульса распределителя 9 ключ 5 закрывается (через обмотку

5

0

5

О 5

0

5

0

5

пряжение на выходе генератора равно нулю).

При поступлении очередного импульса генератора 21 распределитель 9

выдаёт прямоугольный импульс третьему выходу и устройство работает аналогично, однако подключаются тиристоры 22 моделей 2(A,D)5 2(А,В) и 2(B,D), а напряжение запоминается в блоке 19 модели 16(A,D).

Поскольку в рассматриваемом примере третий выход является последним выходом распределителя 9, его зад- ,ним фронтом триггер 12 переключается в нулевое состояние, и при поступлении нулевого потенциала с выхода триггера 12 на управляющий вход коммутатор 13 вновь подключает свой информационный вход к первому выходу. Очередной импульс генератора 21 проходит на вход распределителя 8, который вьщает единичный потенциал по второму выходу. Работа устройства повторяется.

; В момент, когда распределитель 14 выдает единичньй потенциал на свой последний выход, открывается ключ 6 и задний фронт и пyльca с распределителя 9 проходит через ключ 6 на вход останова генератора 21. В это время блок 14 выделяет максимальное ,из входных напряжений, поступивших с (выходов блоков 19 и соответствующих весам циклов, образованных при подключении в граф-дерево различных ребер, и вьщает его на информационный выход устройства. t ;Формула изобретения

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

фЗр модель графа составлена из моделей ребер5 и М ключей, где М - количество узлов в модели графа, соединенных согласно топологии графа и введены генератор линейно изменяющегося напряженияJ второй распределитель импульсов, второй элемент ИЛИ коммутатор и наддиагональная матрица из (М - 1) строк и (М - 1) столбцов

моделирующих элементов« каждый из которых содержит два ключа,, блок памяти j причем информационный выход nepBOi O ключа подключен к кмформата- онномз входу второго ключа,, модель ребра,, информационный вход которой подключен к информационному входу блока памяти и развивающий элемент, информационный вход которого.-подключен к информационному входу модели графа,, причем вход пуска генератора импул7эсов подключен к информационному входу коммутатора, первый и второ информационные выходы которого подключены к информационным входам первого и второго распределителей импульсов соответственно, К-й информа- ционньгй выход первого распределителя

импульсов (к 1,

М - 1 ) ПОДКЛЮ-чен к управляющим, входам первьш клю-- чей всех моделируюнрх элементов К-й строки наддиагональной матрицы мо-- делирующнх элементов и к К-му входу первого элемента ШШ, вькод которого подключен к информационному входу триггера, информационный вьшод .которого подключен к управляюще.гу входу коммутатора, К-й информационный вькод второго распределителя импульсов подключен к управляющим входам вторысг ключей всех моделирующих элементов К-го столбца наддиагональной матри

й

ць модапкруюц1-1х эламеитоп„ .. п ляющему зходу -(К -;- i) -ro ли графа и к К-му входу второго мента ИЛИ, вькод которог о подключен

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

ду К-го ключа модели графа,, информа- щюнные выходы всех ключей модели графа под1ш.юченьг к управляющему/ входу первого ключа,, информапйонный выход которого подключен к входу сброса генератора линейно изменяющегося, напряжения, информз-ционные вг)Г,коды блоков памяти моделирующих элементов наддиагональной матрицы моделкруюпткх элементов подключены к соответствующим входам блока сраЕнениЯ; выход которого является вькодом згстройстзз, (М-1)-й выход первого распре.далител я иг-шульсов подзслючек к управляющее входу второго ключа вьшод которогс

подключвлЧ. к входу останова гекорато - ра импульсов и является выходом признака окончания работы устройства5 (М - 1)й вьпсод второго р ас пред ЗЛИТ е- ля ш-шульсов подключен к установочноку вхо,цу триггера и к ин-формацкоьг ному входу второго тшючЯэ инфсрмаци--- онньш вход первого ключа яг-ляется входом признака установки в О генератора линейно кз меняющегося напр оке ния устрой - ства.

Составитель А.Мишин Редактор Е.Копча Техред Н.Тлущенко

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

Корректор М. Демчик

Изобретение относится к области вычислительной техники, может быть использовано для моделирования струк- i тур связи, отображаемых неориентированными графами, и позволяет находить ребра, включение которых в графдерево приводит к появлению максимальных циклов. С этой целью устройство для моделирования графов содержит матрицу элементов, моделирующих подключаемые ребра, и блок сравнения. Аппаратные средства устройства обеспечивают последовательное подключение моделирующих элементов матрицы к узлам модели графа, а блоки памяти, входящие в состав моделирующих элементов, запоминают значения ., веса цикла, образованного подключением данного моделирующего элемента. После подключения последнего моделирующего элемента устройство останавливается, при этом на инфдрмационном ц, выходе блока сравнения выделяется на- S ибольший из весов циклов графа. 1 ил.