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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИ КРЕСПУБЛИК ЯО(54) УС ГРАФОВ (57) Из вычислииспользтур свяваннымидить р ТРОЙСТВ тносится к области ники, может быть оделирования струкаемых неориентиропозволяет нахоние которых в графобретени тельной овано дл зи, отоб графами бра, вкл ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ ПИСАНИЕ ИЗО(56) Авторское свидетельствР 552617, кл. С 06 С 7/ 122,Авторское свидетельствоВ 1193685, кл. С 06 Р 15/12 дерево приводит к появлению максимальных циклов. С этой целью устройство для моделирования графов содержит матрицу элементов, моделирующихподключаемые ребра, и блок сравнения. Аппаратные средства устройстваобеспечивают последовательное подключение моделирующих элементов матрицы к узлам модели графа, а блокипамяти, входящие в состав моделирующих элементов, запоминают значениявеса цикла, образованного подключением данного моделирующего элемента.После подключения последнего моделирующего элемента устройство останав"ливается при этом на информационномвыходе блока сравнения выделяется на- Жиаалввиц иа весов циклов графа. 1 ил. рИзобретение относится к Вычислительной технике и может быть использовано для исследования параметровструктур связи и управления, отображаемьгл графами,Целью изобретения является расширение класса решаемых задач за счетнахождения максимального цикла В граФе.На чертеже изображен пример Функциональной схемы устройства для графа имеющего четыре узла (М = 4)Устройство для моделирования графов содержит модель 1 графа составленную из моделей 2 ребер и М ключей 3, где М - количество узлов В модели 1 графа, соединенных согласнотопологии графа, модель 4 ребра, дваключа 5 и 6, коммутатор 7, два распределителя 8 и 9 импульсов, два элемента ИЛИ 10 и 11, триггер 12, генератор 13 напряжения, блок 14 сравненичи наддиагональную матрицу 15 из М;столбцов моделирующих элементов 16,.содержащих два ключа 17 и 18, причем выход первого ключа 17 подклк 1 чен к информационному входу второгоключа 18, модель 4 ребра, информационный вход которой подключен к инФормационному входу блока 19 памяти,и развязывающий элемент 20., инйорма -ционный вход которого подключен кинформационному выходу модели 4,вход пуска генератора 21 импульсовявляется входом пуска устройствавыход генератора 21 импульсов нодключен к информационному Входу коммутатора 7, первый и второй информационные выходы которого подключены кинформационным входам первого 8 ивторого 9 распределителя импульсовсоответственно, К-й информационныйвыход первого распределителя 8 импульсов (К = 1 М) подключенк управляющим входам первых ключейвсех моделирующих элементов К-й строки наддиагональной матрицы 15 моделирующих элементов и к К-му входупервого элемента ИЛИ 10, выход которого подключен к ичформационномувходу триггера 12, информационный выход которого подключен к управляющему вхОду коммутатора 7 Кй инйот ма=ционный Выход второго распредепт-тег 1 я9 импульсов подключен к управляющимвходам вторых ключей всех моделирующих элементов К-го столбца надциагональной матрицы 15 моделируюпжх эле 0807 2ментов, к управляющему входу К + 1) -го ключа 3 модели 1 графа и к К-мувходу Второго элемента ИЛИ 11, выход,которого подключен к входу опросагенератора 13 напряжения, информационный выход которого подключен кинформационным вхоцам первых ключей17 всех моделирующих элементов 16,информационные выходы развязывающихЮ элементов 20 всех моделирующих элементов 16 К-й строки наддиагональнойматрицы 15 моделирующих элементов 16подключены к информационному входуК-го ключа 3 модели 1 графа, инйорма 15 ционные выходы всех ключей 3 модели1 графа подключень. к управляющемувходу первого ключа, информационныйВыход которого подключен к входу установки в "0" генератора 13 линейно 20 изменяющегося напряжения, инйормационные Выходы блоков 19 памяти моделирующих элементов 16 наддиагональной матрицы 15 моделирующих элементов 16 подключены к соответствующимвходам блока 14 сравнения. выход которого является выходом устройства,М)-й Выход первого распределителя8 импульсов подключен к управляющемувходу Второго ключа 6, информацион 30 1 ный Выход которого подключен к входуостанова генератора 2 1 импульсов ияьляется выходом признака окончанияработы устройства, (М)-й инйормационный Выход второго распуеделителя35 9 импульсов подключен к установочному входу триггера 12 и к йнформацлонному входу второго ключа б, инфсрмационный вход первого ключа 5в .ляется входом признака установки: =.нератора 13, Модель 2 ребра содер-жит тиристор 22 источник 23 напряжения переменный резистор 24 и разВязывающие диоды 25-28,Устройство работает следующим обД 5разом.Б исходном состоянии распределители 8 и 9 и триггер 22 обнулены,ключи 3, 17, 18 и 6 закрыты. С помощью переменных резисторов 24 устакавливяют токи В управляющих цепях тиристаров 22 соответственно заданнымнапряжениям переключения, пропорциональным весам ребер графа,арабоу чстройс ВЯ по нахождениютоГО ребрЯ, Включение котОроГО В топологию грЯФЯ типа дереВО ОбрЯзуетмаксима,1 ьный цикл, рассмотрим на примере дерева образованного узлами07 1 Формула 3 13108 А, В, С, В и ребрами АВ, ВС и ВР. В этот граф могут быть включены ребра АС, АП и СП, соответственно которым в матрице 15 участвуют моделирующие элементы 16(АС), 16(АП) и 16(СЭ).После пуска устройства импульс генератора 21 поступает через коммутатор 7 на вход распределителя 8, который выдает единичный потенциал со своего первого информационного вы хода на управляющие входы ключей 17 моделей 16 первой строки матрицы 15, соответствующих узлу А графа, т.е. опрашиваются ребра, инцидентные узлу А. 15Единичный сигнал с первого выхода распределителя 8 проходит через элемент ИЛИ 10 на информационный вход триггера 12, который выдает единичный потенциал на управляющий вход 20 коммутатора 7, переключающего свой информационный вход на второй выход. Поэтому следующий импульс генератора 21 поступает на вход распределителя 9, который вьдает на свой первый выход прямоугольный импульс, а затем по поступлении следующего импульса генератора 21 - прямоугольный импульс на свой второй выход. Этот импульс поступает на управляющие входы ключей 30 18 моделей 16 второго столбца матрицы 16 и открывает их. Аналогично после поступления единичного потенциала на управляющий вход открывается ключ 3 модели 2 С. 35Кроме того, передний фронт импульса с выхода распределителя 9, пройдя через элемент ИЛИ 11 на вход опроса генератора 13, обусловливает вьдачу на выходе генератора 13 линейно в в- ф растающего напряжения. При некоторой величине Е с этого напряжения происходит подключение тиристоров 22 моделей 2 некоторой совокупности ребер графа. Ток протекает по цепи: выход генератора 13, информационные входы- выходы ключей 17 и 18, модель 16 (АС), модель 2(А, С), разделительный диод 20 модели 16 (аС), ключ 3(А), модель 2(А,В), ключ 3(В), модель 2(В,С), ключ 3(С), информационный выход ключа 3(С), управляющий вход ключа 5, в качестве которого может выступать например, обмотка реле, выход которой подключен к нулевому потенциалу устройства.Единичный потенциал, соответствующий признаку сброса генератора 13,проходит через исполнительную цепь ключа (например через контакт реле) и сбрасывает в "0" напряжение на выходе генератора 13. Длительность импульсов распределителя 9 выбирается такой, чтобы до их окончания успевал произойти сброс генератора 13. По окончании импульса распределителя 9 ключ 5 закрывается (через обмотку реле не протекает ток, так как напряжение на выходе генератора равно нулю).При поступлении очередного импульса генератора 21 распределитель 9 выдает прямоугольный импульс третьему выходу и устройство работает аналогично, однако подключаются тиристоры 22 моделей 2(А,0), 2(А,В) и 2 (В, Р), а напряжение Ео запоминается в блоке 19 модели 16(А,Р).Поскольку в рассматриваемом примере третий выход является последним выходом распределителя 9, его задним фронтом триггер 12 переключается в нулевое состояние, и при поступлении нулевого потенциала с выхода триггера 12 на управляющий вход коммутатор 13 вновь подключает свой информационный вход к первому выходу. Очередной импульс генератора 21 проходит на вход распределителя 8, который вьдает единичный потенциал по второму выходу. Работа устройства повторяется.В момент, когда распределитель 14 выдает единичный потенциал на свой последний выход, открывается ключ 6 и задний фронт импульса с распределителя 9 проходит через ключ 6 на вход останова генератора 21. В это время блок 14 вьдсляет максимальное ,из входных напряжений, поступивших с выходов блоков 19 и соответствующих весам циклов, образованных при подключении в граф-дерево различных ребер, и вьдает его на информационный выход устройства. изобретения Устройство для моделирования графов, содержащее модель графа, генератор импульсов, два ключа, распределитель импульсов, элемент ИЛИ, триггер и блок сравнения, о т л и ч а ю - щ е е с я тем, что, с целью расширения класса решаемых задач за счет нахождения максимального цикла гра 1310807Фа, модель графа составлена из моделей ребер, и И ключейгде М - коли:чествс узлов Б МОдели графа соединенных согласно топологии графа., ивведены генератор линейно изменяющегося напряжения, второй распределитель импульсов, второй элемент ИЛИ,коммутатор и наддиагональная матрицаиз (М - 1) строк и (М - 1) столбцовмоделирующих элементов 1 каждый изкоторых содержит два ключа, блок памяти, причем информационный выходПЕРБО 1 О КЛЮЧЯ ПОДКЛтОЧЕН К И 1 ФОРМЯ 1 ПОН 1 трт ВХОДт ВТтрсо КЛ 1 атт 1 тсдЕт 1ребра,. информационный вход которойподключен к информационному входублока памяти, и развивающий элемент,информационный вход которого,подкл 1 а-чен к информационному входу моделиграфа причем вход пуска генератораимпульсов подключен к информационно му входу коммутатора, первый и второйинформационные выходы которого подключены к информационным входам первого и второго распределителей импульсов соответственно, К-й информационный выход первого распределителяимпульсов (К = 1 М - ) псдкпо-.чен к управляющим входам первых клю"чей всех моделирующих элементов К.-йстроки наддиагональной матрицы мс-"делиртющих элементов и к К-му входупервого элемента ЮП 4, выход которогоподключен к инфсрмяциОннсму Входутриггера информационный вьГсд кс. Орого подключен к управляющему входукомму Ратсра 9 К и информЯциснтыи зыхОДвторого распределителя импулЬссв подключен к управляющим входам вторыхключей всех мсделируопах 91 ементоК-го столбца наддиагональной матри"хОД котороГО подключен к ВхОду соро.тт Са ГЕНЕРатОРа ЛИЦЕйно ИЗМЕНЯЮЩЕГОСЯнапряжения, информационные выходы блоков памяти моделирующих элементов ЦаДДИаГ ЗНЯЛЬНОй МатРИ 1 тЫ ЬтОДЕПИРУЮПЯХ элементов псдклтачетЬ 1 к соответса жующим входам блока сравцеция: выхоп к -тОРСГО ЯВЛЯЕШЬСЯ ВЫХОДОМ УттРойСТБЯ:,(М)-й выход первого распрепзл;Геля НИНУЛЕ ЬС Б ПОД 1 Л 10 ЧЕЕ К УПРЯВЛЯЮ та: БХОДУ Б. ОР ОГО КЛЮЧЯ. БЫХО,Ц КО 1. О 1 то СПОДКЛЮЧЕН К ВХОДУ ССТЯНОВЯ ГЕ 1 т гатов Б Я И 1 тт 1 уЛЬС ОВ и явля Етя БЫ т тПО, 1 тИ -.кака окончания работы устройства,(. - )-1 выход второго ряспредел 1 те -ЛЯ ИМПУЛЬСОВ ПОДКЛЮЧЕН К УСТЯ 101;От. у НОМУ Бхсарт Тр;тг.ЕОЯ. И К цатстт:1 Я 1 т 1 сц .НОМУ ВХОДУ БТОРОГО КЛЮЧЯ:,. ЧНФОР 11 ЯБ 1.снцый вход герьсго ключа ягпяется 13 ХОЦОМ 1 РЬт 91 атк Я О " Генератора С т НОБК т1 ц е йитЬ 1 ЕНЯ 1 тЩЕГОСЯ ЦапРЯжЕНИЯства. УСТтсй 1 ЦЫ МОДЕ тт:О "тктР,",Х ЗЛ .1, - ПТЛьтЮщЕЬттт;.О-,1 (К):.т-О К. .ли ГрафЯ и к К-му БхОДу Бто:."ГО эл- МЕНТя 1 ЛИ ВЬ 1 ХОД Ксторс 1 О Псттк 1 атЕН к входу пуска генератора линейно из- МЕНЯЮЩЕГОСЯ НЯПРЯЖЕЦИЯ т ИНФОР 11 атт 11 О 1- цььй ВыхОд котсрсгс подктпочец к ицфОр-" мапионным входам первых кл 1 ачей всех мопел 1 рующих элементов 1911.иягсналь - 1 О ной матрицы, информационные выходырязвязывяющих элементов всех мсделиПуЮщих ЗЛЕМЕН аов К-й СТртс 1 И цадпиагоЦа 1 ЬЦсй ЬаТРИ 1 Ы;.,Г ЕтттИР ттюьтих ЗЛЕМтЕН" тов Годктпоче 1 п 1 к ицформапиоцному Бхотт 15 ду К - ГО ключа модели Гр фя, иьтфсрмя -ционные выходы всех ключей модели графа подключены к управляющему БхоДтт ПтЕБВОГО КЛ 1 атаиьтфорттаттИОННЬ 1 т ВЫ-.рректор М. Демчи 5 Зака Производственно-полиграФическое предприятие, г.ужгород, ул.Проектная НИИПИ Го по дела 3035, М Тираж 672 дарственного изобретений и ква, Ж, Ра омитета СССР открытийушская наб., д. 4/