Устройство для моделирования графов

Устройство для моделирования графов

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИН

<1р) В0 ш> (5-1)4 С 06 F 7 48

А1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ 17

/р(/ .

ОПИСАНИЕ ИЗОБРЕТЕНИЯ (" (21) 4022373/24-24 (22) 17.02.86 (46) 15.05.87. Бюл. И 18 (72) Д.ПеМальцев и С.K.Ìèõàéëîâñêèé (53) 681.333(088.8) (56) Авторское свидетельство СССР

Р 552617, кл. G 06 G 7/ 122, 1975.

Авторское свидетельство СССР

Р 1193685, кл. G 06 F 15/122, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники, может быть использовано для моделирования структур связи, отображаемых неориентированными графами, и позволяет находить ребра, включение которых в графдерево приводит к появлению максимальных циклов. С этой целью устройство для моделирования графов содержит матрицу элементов, моделирующих подключаемые ребра, и блок сравнения. Аппаратные средства устройства обеспечивают последовательное подключение моделирующих элементов матрицы к узлам модели графа, а блоки памяти, входящие в состав моделирующих элементов, запоминают значения веса цикла, образованного подключением данного моделирующего элемента.

После подключения последнего моделирующего элемента устройство останав" ливается„ при этом на информационном выходе блока сравнения выделяется на- 9 ицалввиц ив весов циклов графа. 1 ил. д

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

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

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

;столбцов моделирующих элементов 16,.

1 содержащих два ключа 17 и 18, причем выход первого ключа 17 подклк1чен к информационному входу второгс:. ключа 18, модель 4 ребра, информационный вход которой подключен к информационному входу блока 19 памяти, и развязывающий элемент 20., информа— ционный вход которого подключен к информационному выходу модели 4, вход пуска генератора 21 импульсов является входом пуска устройства,, выход генератора 21 импульсов нодключен к инфОрмациОннОму БХОду ком мутатора 7, первый и второй информа-. ционные выходы которого подключены к информационным входам первого 8 и второго 9 распределителя импульсов соответственно, К-й информационный выход первого распределителя 8 импульсов (К = 1,..., N-1) подключен к управляющим входам первых ключей всех моделирующих элементсв Х-й строки наддиагональной матрицы 15 моделирующих элементов и к К-му входу первого элемента ИЛИ 10, выход которого подключен к ичформационному входу триггера 12 информационный выход которого подключен к управляющему входу коммутатора 7 K--й инфопма= цианный выход втОрОгО распредепитег1я

9 импульсОв подключен к управляющим входам вторых ключей всех моделирующих элементов К-го столбца наддиагональной матрицы 15 моделируюпщлх эле080/ 2 ментов, к управляющему входу (К + il)— га ключа 3 мэдели 1 графа и к К-му входу второго элемента ИЛИ 11, выход .которого подключен к входу опроса генератора 13 напряжения, информационный выход которого подключен к информационным вхоцам первых ключей

17 всех моделирующих элементов 16, информационные выходы развязывающих

Ю элеменч ов 20 всех моделирующих элементов 16 К-й строки наддиагональной матрицы 15 моделирующих элементов 16 подключены к информационному входу

К вЂ” го ключа 3 модели 1 графа, информационные выходы всех ключей 3 модели

1 графа подключень. к управляющему входу первого ключа, информационный выход которого подключен к входу установки в "0" генератора 13 линейно20 изменяющегося напряжения, информационные выходы блсков 19 памяти моделирующих элементов 16 наддиагональной матрицы 15 моделирующих элементов 16 подключены к соответствующим входам блока 14 сравнения. выход которого является выходом устройства, (М-1)-й выход первого распределителя

8 импульсов подключен к управляющему входу второго клю !а 6, информацион-30 1ныйл выход которого подключен к входу

I останова генератора 2 1 импульсов и яьляет"я выходом признака окончания работы устройства, (М-1)-й информационный выход второго распуеделителя

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

Устройства работает следующим обД5 разом.

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

Panicóó у, тройс «aa a нахождению того ребра, включение котОраго в То пологию графа тип I "дерево" образует максимальный цикл„, рассмотрим на примере дерева Об|2азОваннОгО узлами

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

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

При поступлении очередного импульса генератора 21 распределитель 9 выдает прямоугольный импульс третьему выходу и устройство работает аналогично, однако подключаются тиристоры 22 моделей 2(А,0), 2(А,В) и

2 (В, D), а напряжение Е A д запоминается в блоке 19 модели 16(A,D) .

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

Очередной импульс генератора 21 про.ходит на вход распределителя 8, который вьдает единичный потенциал по второму выходу. Работа устройства повторяется.

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

Формула

3 13108

А, В, С, D и ребрами АВ, ВС и BD. В этот граф могут быть включены ребра

АС, AD и CD, соответственно которым в матрице 15 участвуют моделирующие элементы 16(AC), 16(AD) и 16(CD).

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

А. 15

Единичный сигнал с первого выхода распределителя 8 проходит через элемент ИЛИ 10 на информационный вход триггера 12, который выдает единичный потенциал на управляющий вход 20 коммутатора 7, переключающего свой информационный вход на второй выход.

Поэтому следующий импульс генератора

21 поступает на вход распределителя

9, который вьдает на свой первый выход прямоугольный импульс, а затем по поступлении следующего импульса генератора 21 — прямоугольный импульс на свой второй выход. Этот импульс поступает на управляющие входы ключей30

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

3 модели 2С. 35

Кроме того, передний фронт импульса с выхода распределителя 9, пройдя через элемент ИЛИ 11 на вход опроса генератора 13, обусловливает вьдачу на выходе генератора 13 линейно — воз- 0 растающего напряжения. При некоторой величине F1iс этого напряжения происI ходит подключение тиристоров 22 моделей 2 некоторой совокупности ребер графа. Ток протекает по цепи: выход генератора 13, информационные входывыходы ключей 17 и 18, модель 16 (АС), модель 2 (А, С), разделительный диод 20 модели 16 (аС), ключ 3(А), модель 2 (А, В), ключ 3 (В), модель

2(В,С), ключ 3(C), информационный выход ключа 3(С), управляющий вход ключа 5, в качестве которого может выступать например, обмотка реле, выход которой подключен к нулевому потенциалу устройства.

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

Устройство для моделирования графов, содержащее модель графа, генератор импульсов, два ключа, распределитель импульсов, элемент ИЛИ, триггер и блок сравнения, о т л и ч а ю— щ е е с я тем, что, с целью расширения класса решаемых задач за счет нахождения максимального цикла гра131 О807 фа, модель графа составлена из»o, .-,B-лей ребер, и И ключей„где М вЂ” коли"-чество узлов в модели графя, соединенных согласна топологии графа., и введены генератор линейно изменяющегося напряжения, второй распределитель импульсов, второй элемент ИЛИ, коммутатор и наддиагакальная матрица из (М вЂ” 1) строк и (М вЂ” 1) столбцов моделирующих элементов каждый из которых содержит два ключа, блок па . мяти,,- причем информационный выход первог ключа подключен к информяциОННОМ»" ВХОДУ BTOPO) O KJIIOH!B,„»OÄeÏÜ ребра,. информационный вход которой подключен к информационному входу блока памяти, и развивающий элемент информяционный ВхОЦ K0TopoI Î, ПОдклю-. чен к информационному входу модели графа„ причем вход пуска генератора импульсов подключен к информационно-му входу коммутатора, первый и второй информационные выходы которого подключены к информационным входам I!ервогo и второго распределителей импульсов соответственно, K-й информа-.

ЬтиОННЬй ВЫХОД ПЕРВОГО РЯСПРЕДЕЛИТЕЛЯ импульсов (К = 1,..., М вЂ” 1) подклю-чен к управляющим входам первых клю.чей всех моделирующих элементов К--й строки наддиагональкой матрицы »а-ДЕЛИРт1ОЩИХ ЭЛЕМЕНТОВ И К К--МУ ВХОДУ первого элемента ViJIM выход катарога пОдключен к информационна»1 ВхОду триггepB информяционнь1й Вь) Од KO а =рого подключен к упрявляюще»у Входу

Комму ГЯТара p (И Икфармат»И()Н )Ыи БЬ1ХОБ второго распределителя импулвсов нод— ключен к управляющим входам Бторьгх ключей всех моделируюпц1Х элемента

К-га столбца наддиагональнай матри-ХОД KÎTOPOI" 0 ПОДКЛЮЧЕН К ВХОДУ СОР О

;.О са генератора линейно изменяющегося напряжения информационные Выходы блоков памяти моделирующих элементов

НаДДИаГ 0НЯЛЬНОй МЯТРИЦтЬ! Ь!ОДЕПИРУЮПт1Х

ЭЛЕМЕНТОВ ПОДКЛЮЧЕ :Ь! СОО HBTC 1 9„)1 )щим Входам блакя cpa H)»IIHë ° Выход тарого является Вььходо» устра - -:ствя:, (11-1)-й Выход первого ряспредел! тел."=:

ИМПУЛЬСОБ ПОДКЛЮЧЕН К УПРЯВЛЯЮ":та. .:;:

ВХОД»у ВТОРОГО КЛЮЧЯ ВЫХОД КО i.аРОГС подключен к входу с:станавя 1-е1-: ратс— т! ) QB ИМПУЛЬС >Н т! ЯВЛЯЕТ II BIlXOПО Пт -".: =. някя акОьlчяния pB60T!)I устройства, (! . — 1)-й Выход второго распредел т:-:— ля импу - сав подключен к усTBllorlo-=35 НОМУ БХО!т;т ТГ)Ьт)-ГЕОЯ И К ИкаоттмаlтнснH0Mó" ВХОДУ БТОРОГО КЛЮЧЯ:,. IHIPOP ЯБ1-

Онный вход герього ключа является

БХСЦОМ 1!РЬТЗКЯК Я

О " генератора

УСТЯНОБКИ чин: йн - ттт ус трой ь!еняющегося напряжения ства.

ЦЫ МОДЕ П:.:; Б-,:,. 1).! Х тл;-..1,—:)1Т ляющему: —;хсду (К, - 1)-:- -.; к ли ГРЯФЯ и K К-мУ БКОДУ BTG;: ":0 = .!Bмента ИЛИ, вь1ход катарага -падкл10 1ен к входу пуска генера-ора линейно из-меняющеГОся няпряжеHHR т инфармяциан нььй ВыхОд котарОГO подключен к инфор " ь!Япианным входам первых ключей всех

ЫОДЕЛ1тРУЮЩИХ ЭЛЕЬ!ЕНТОБ 11ЯДД)ИЯГОНЯЛт-18 най матрицы, информационные выходы развязывающих элементов ВсВК МОдели

Буюших элементов К-й страхи нядпиягаНЯ-!ЬНСй МЯТРИIТЫ МОДPl!HP 1тюших ЗЛЕ..,!ЕНТОВ ПОДКЬ1ЮЧЕ11!т! K и г!IOP»BHHOНБ01!»У БхаД»т K 1 0 КПЮЧЯ МОДЕЛИ ГРЯфЯ:, ИнфаРМЯ цианные выходы всех ключей мацели графа подключены к управляющему БхаД»т ПтЕБВОГО КЛЮт!Я» Ит!фат»МЯ1)ИОНН Цт Вьт "

1310807

Составитель А.Мишин

Редактор Е. Копча Техред Н. Глущенко

Корректор! M. Демчик

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

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

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

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