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

(5) 4 я 15 2 ПИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРГО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСВ(56) Авторское свидетельство СССРВ 656073, кл, 0 06 Р 15/36, 1976,Авторское свидетельство СССРУ 238238, кл. 0 0615/32 ф 977Авторское свидетельство СССРУ 329538, кл. О 06 С 7/48, 1970.(57)Изобретение относится к областивычислительной техники и может бытьиспользовано при решении на графахзадач определения характеристик.структурной надежности централиэоЯ 0121839 ванных н децентрализованных телемеханическнх систем, Устройство решае поставленную задачу,путем последовательного перебора и анализа состояния графа. Цель изобретения состоит в расширении функциональных возмоляостей эа счет определения числа состояний связности вершин. графа хотя бы с одной иэ его центральных вершин. Устройство содерзит генератор импульсов, распределитель импульсов, блок перебора сочетаний, группу ключей, наборное поле, блок ключей, первый элемент И, триггер, элемент ИЛИ, второй и третий элементы И, первый и второй счетчикис соответствующими функциональными связями мелду ними. 2 ил,8393 55 1 12Изобретение относится к вычислительной технике и может быть использовано при решении на графах задачопределения характеристик структурной надежности централизованных идецентрализованных телемеханических систем.Цель изобретения - расширениефункциональных возможностей за счетопределения числа состояний связности вершин графа хотя бы с одной "из его центральных вершин.На фиг. 1 представлена функциональная схема устройства; нафиг, 2 - схема коммутации для графа, содержащего 4 ребра и 4 вершины,из которых две - центральные,Устройство содержит генератор 1импульсов, распределитель 2 импульсов, блок 3 перебора сочетаний, первую группу из ш (ш - число реберграфа) ключей 4, наборное поле 5топологии графа, блок 6 ключей, первый элемент И 7, триггер 8, элементИЛИ 9, второй 10 и третий 11 элементы И, первый 12 и второй 3 счетчики.Блок 6 содержит пключей 14(и - число центральных вершин).Первоначально информационные входы и выходы ключей 4 коммутируютсяв наборном поле 5 согласно топологииграфа. Информационные входы и выходыключей 14 блока 6 коммутируются синформационными входами ключей 4,соответствующих ребрам, исходящим изцентральных вершин телемеханическойсистемы. Затем обнуляют и записывают1 в соответствующий разряд распределителя 2, обнуляют триггер 8 и счетчики 12, 13, подготавливают к работе блок 3, выполненный согласноавт. св, 123Устройство работает следующим образом.После поступления сигнала запуска генератор 1 выдает импульсы навход распределителя 2, который поочередно выдает импульсы на каждыйиэ своих четырех выходов. Импульс спервого выхода распределителя 2 вызывает появление на выходах блока 3комбинации .сигналов, соответствующихмоделируемому состоянию телемеханической системы и обуславливающих замыкание соответствующих ключей 4.Импульс, поступающий с второговыхода распределителя 2, устанавли 5 О 15 20 25 30 35 40 45 50 вает в О триггер 8, в результате чего с его инверсного выхода на второй вход элемента И 1 О подается разрешающий, а с прямого выхода на второй вход элемента И 11 - запрещающий потенциал. Кроме того, этот же импульс распределителя 2 проходит через. элемент ИЛИ 9 и в качестве опросного сигнала поступает на информационный вход одного из ключей 4, Если моделируемое состояние теле- механической системы относится к множеству состояний безотказности (каждая вершина связана с центральной вершиной), то единичные сигналы появляются на всех входах элемента И 7, и появление единичного сигнала на его выходе приводит к увеличению на 1 показания счетчика 12 состояний безотказности централизованной телемеханической системы, а также к остановке блока 3 на данном сочетании. Если моделируемое состояние относится к состоянию отказа, то хотя бы на одном входе, а следовательно, и на выходе элемента И 7 присутствует нулевой сигнал.Проверка состояния децентрализованной телемеханической системы осуществляется при появлении единичного сигнала на третьем выходе распределителя 2, который перебрасывает в единичное состояние триггер 8, открывая элемент И 11. Кроме того, единичный сигнал поступает на управляющий вход блока 6 и открывает ключи 14, Одновременно на выходе элемента ИЛИ 9 формируется сигнал опроса, и если моделируемое состояние децентрализованной телемеханической системы принадлежит к множеству состояний безотказной работы (каждая вершина связана хотя бы с одной из центральных вершин), то на всех входах и выходе элемента И 7 появляется единичный сигнал, что приводит к увеличению на 1 показаний счетчика 13 состояний безотказности децентрализованной теле- механической системы. Сигнал на четвертом выходе распределителя 2 разрешает дальнейшую работу блока 3. Далее устройство работает аналогично, и после окончания перебора всех сочетаний, индицируемого,.в блоке 3, снимаютсяпоказания счетчиков 12 и 13,Формула изобретения Устройство для исследования графов, содержащее блок перебора сочетаний, группу из щ ключей .(щ - чис ло ребер графа), первый элемент И, блок ключей из иключей (ив число центральных вершин графа), триггер, два счетчика и наборное поле, выходы которого соединены с1 О информационными входами и выходами соответствующих ключей группы, выходы г-х хпычед (г = 1, й - Т) группы подключены к входам первого элемента И, о т л и ч а ю щ е е с я 15 тем, что, с целью расширения функциональных возможностей за счет определения числа состояний связности вершин графа хотя бы с одной из его центральных вершин, в устройство вве дены элемент ИЛИ, второй и третий элементы И и генератор импульсов, вход которого является пусковым входом устройства, а выход соединен с входом распределителя импульсов, 25 первый выход которого подключен к первому тактовому входу блока перебора сочетаний, второй выход распределителя импульсов соединен снулевым входом триггера и первымвходом элемента ИЛИ, третий выходраспределителя импульсов подключенк единичному входу триггера и второму входу элемента ИЛИ, четвертыйвыход распределителя импульсов соединен с вторым тактовым входом блока перебора сочетаний, выходы которого соединены с управляющими входами соответствующих ключей группы,выход первого элемента И подключенк входу останова блока перебора сочетаний и первым входам второго итретьего элементов И, выходы которых соединены с входами соответст"венно первого и второго счетчиков,второй вход второго элемента И подключен к инверсному выходу триггера,прямой выход которого соединен свторым входом третьего элемента И иуправляющим входом блока ключей, выход элемента ИЛИ подключен к выходущ-го ключа группы, а информационныевходы и выходы блока ключей соединены с информационными входами ключейгруппы, соответствующих ребрам, исходящим иэ центральных вершин.1218393 Риг 2 Шеренкоова Корр ставитель хред С.Ми едактор М, Б иннцкая"Патент", г ал в 1133/57 ВНИИПИ Государс по делам изо 113035, Москва, Тираж 673 Подписноеенного комитета СССРетений и открытий