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

ПИСАНИЕ ИЭОБРЕТ АВТОР ТВ(57) Изобретение овычислительной техиспользовано призадач определениякратчайших путей,сетевых структур.является расширен ДЕЛИРОВАНИЯ ен тносится к областиники и может бытьешении на графахнаиболее длинныхцентров и радиусовЦелью изобретенияе функциональных 6, перементов 19, тригкаждая2, триггерство поз ЬР Об ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ возможностей устройства за счетделения одного или нескольких узкратчайшие пути до которых из лузла графа имеют наибольшие значния. Поставленная цель достигаеттем, что в устройство для моделвания графов, содержащее моделивей 7 и модели узлов 1, соединесогласно топологии исследуемогофа, каждая модель ветви состоитэлемента задержки 8, формироватимпульсов 9, разделительного дио10 и полюсов 11 и 12, введены гратор импульсов 14, первый элемеИЛИ 15, элемент задержкивый счетчик 17, группа элИ 18, второй элемент ИЛИгер 20, второй счетчик 21,модель узла содержит ключ3 и полюса 4, 5, 6. Устрой1280382 воляет определять узлы, кратчайшие пути до которых иэ любого назначенного узла имеют максимальную величину, при этом определяется и вес это. го наибольшего кратчайшего пути. Ре. шение данной задачи необходимо, например, при оценке времени доставки 1Изобретение относится к вычислительной технике и может быть использовано при решении на графах задачопределения наиболее длинных кратчайших путей, центров и радиусов сетевых структур.Цель изобретения - расширениефункциональных возможностей устройства путем определения наибольшегоиз кратчайших путей,На чертеже изображена структурная схемаустройства для моделирования графов.Устройство содержит модели узлов1, каждая из которых состоит изключа 2, ВЯ-триггера 3 и полюсов4-6, модели 7 ветвей, каждая из которых состоит из элемента 8 задержки,формирователя 9 импульсов, разде.лительного диода 10 и полюсов 11 и12, переключатель 13, генератор 14импульсов, первый элемент ИЛИ 15,элемент 16 задержки, первый счетчик17, группу элементов И 18, второйэлемент ИЛИ 19, триггер 20 и второйсчетчик 21. Первоначально модели узлов и ветвей соединяют согласно топологии графа, триггеры 3 и счетчик 17 устанавливают н нулевое положение (цепи установки на чертеже не показаны), при этом все ключи 2 открыты единичными потенциалами с инверсных выходов триггеров 3. Переключатель 13 устанавливают в положение, соответствующее узлу графа, из которого должны определяться наиболее длинные кратчайшие пути. В элементах 8 устанавливаются величины задержек, пропорциональные весу ветвей графа.Устройство работает в два этапа следующим образом. сообщении из пунктов управления донаиболее удаленных исполнительныхпунктов, а также при нахождении центров и радиусов сетевых структур сцелью выбора оптимальных мест размещения ремонтно-восстановительныхи аварийных бригад и служб. 1 ил. 2При поступлении сигнала на пусковой вход генератор 14 выдает импульсы, первый из которых через переключатель 13 поступает на второй Б-вход 5 триггера 3 модели 1 .начального узлаграфа. Триггер 3 переходит в единичное состояние, вследствие чего нулевой потенциал с его инверсного выхода закрывает ключ 2, а импульс спрямого выхода триггера 3 поступаетна Входы элементов 8 всех моделейветвсй 7, исходящих из начальногоузла графа. Последующие импульсы генератора 14 на состояние триггера 3влияния не оказывают, а работа блоков Ина первом этапе значенияне имеет.Импульс, поступивший на вход элемента 8 модели 7, задерживается элементом 8 на время, пропорциональноевесу ветви, и далее через формирователь 9 и разделительный диод 1 О поступает на вход ключа 2 модели 1 уз.ла. Пройдя через ключ 2 на первый. Я-вход триггера 3, он перебрасываеттриггер 3 в единичное состояние,вследствие чего нулевой сигнал с инверсного выхода закрывает ключ 2 дляпрохождения всех других импульсовс выходов 12 моделей ветвей, входящих в данный узел. Импульс с прямого выхода триггера 3 поступает навходы 11 моделей ветвей, исходящих 35из данного узла, и,т.д.Кроме того, импульс с выходатриггера 3 каждой модели 1 поступает, во-первых, на первый вход соответствующего элемента И 18 работа 4 О этих элементов на первом этапе неимеет значения, во -в-орых, на соответствующий вход элемента ИЛИ 15.С выхода этого элемента импульс про 1280382 415 ходит через элемент задержки 1 Ь на счетный вход счетчика 17, который увеличивает свои показания на 1. По истечении времени, не превышающего величины И,Ч, (где И - число вершин графа; Чм - максимальыый вес ветви графа), в счетчике 17 .фиксируется число импульсов М .( Б, причем М = Б, если никакая п,ара триггеров 3 не перебросилась;в единичное состояние практически одновременно, т.е. на интервале времени, меньшем разрешающей способности счетчика 17, и М( Б - , в противном случае.Через время, не меньшее величины И Ч на вход останова генератора 14 подают сигнал останова, устройство приводят в исходное состояние, а именно обнуляют триггеры 3 и 20 и счетчик 21. В счетчик же 17 заносят количество импульсов, дополняющее до его полной емкости М -1 (где показания счетчика 17 после первого этапа работы устройства).Устройство на втором этапе работает следующим образом.При подаче сигнала на пусковой вход генератор 14 вновь выдает импульсы на выход и блоки 1-13 работают аналогично. При этом импульсы, поступающие с прямых выходов триггеров 3 на первые входы соответствующих элементов И 18, на их выходы не проходят, поскольку элементы И 18 закрыты нулевым потенциалом с выхода счетчика 17. И лишь после отсчета счетчиком 17 (М) импульсов потенциал переполнения с выхода счетчика 17 открывает элементы И 18, вследствие чего только импульс с выхода триггера 3, перебросившегося в единичное состояние, последним проходит через соответствующий элемент И 18, во-первых, на соответствующий выход устройства, идентифицируя номер искомого -го (,)еБ) узла графа, кратчайший путь до которого из начального узла имеет наибольшее значение. Во-вторых, этот импульс с выхода элемента И 18 проходит через элемент ИЛИ 19 на вход триггера 20 и перебрасывает его в единичное состояние, что обусловливает снятие с управляющего входа, счетчика 21 разрешения на дальнейший отсчет импульсов, Счетчик 21, ведущий счет импульсов, поступающих на 1его счетщый вход с выхода генерато 20 25 30 35 40 45 50 55 ра 14, благодаря наличию сигнала разрешения с инверсного выхода триггера20 при снятии разрешения прекращаетсчет импульсов, фиксируя вес максимального кратчайшего пути от начального до 1-го узла графа. Если вграфе имеется два или более такихравноудаленных ( в пределах разрешающей способности счетчика 17) узлов,то импульсы поступят на два или более выходов устройства с выходовдвух или более элементов И 18. Формула изобретени,Устройство для моделирования графов, содержащее модели ветвей и . модели узлов, соедйненные согласно топологии моделируемого графа, каждая модель ветви содержит последовательно соединенные элемент задержки, формирователь импульсов и разделительный диод, вход элемента задержки является входом модели ветви, а свободный вывод разделительного диода является выходом модели ветви, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения наибольшего из кратчайших путей, в него введены два счетчика, два элемента ИЛИ, группа элементов И, элемент задержки, триггер, генератор импульсов, переключатель, каждая модель узла содержит ключ и ВБ-триггер, управляющий вход ключа подключен к инверсному выходу триггера, прямой выход которого является выходом модели узла, информационный вход ключа является информационным входом модели узла, выход ключа подключен к первому Б-входу ВБ- триггера, второй Б-вход ББ-триггера каждой -й модели узла (где =1,й) подключен к одноименному неподвижному контакту переключателя, подвижный контакт которого подключен к выходу генератора импульсов, вход запуска и вход останова которого являются соответственно входом запуска и входом останова устройства, прямой выход ВБ-триггера каждой 1,-й модели узла подключен к первому входу а-го элемента И группы и к -му входу первого элемента ИЛИ, выход которого через элемент задержки подключен к счетному входу первого счетчика, выход которого подключен ко вторым входам элементов И группы, выход1280382 Составитель Т. СапуноваТехред Л.Олейник Редактор Л. Пчелинская Корректор М. Пожо Заказ 7051/42 Тираж 671 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 каждого -го элемента И группы подключен к 1 -му входу второго элемей-та ИЛИ и является ъ-тым выходомгруппы информационных выходов устройства, выход второго элемента ИЛИ подключен к входу установки в "1 триггера, инверсный выход которого подключен к входу разрешения счета импульов второго счетчика, счетный вход кото 5 рого подключен к выходу генератора импульсов