Устройство для исследования графов Советский патент 1986 года по МПК G06F15/173 

1

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - схема коммутации для графа, содержащего 4 ребра и 4 вершины, из которых две - центральные.

Устройство содержит генератор 1 импульсов, распределитель 2 импульсов, блок 3 перебора сочетаний, первую группу из m (т - число ребер графа) ключей 4, наборное поле 5 топологии графа, блок 6 ключей, первый элемент И 7, триггер 8, злемент ИЛИ 9, второй 10 и третий 11 элементы И, первый 12 и второй I3 счетчики.

Блок 6 содержит п-1 ключей 14 (п - число центральных рершин).

Первоначально информационные входы и выходы ключей 4 коммутируются в наборном поле 5 согласн9 топологии графа. Информационные входы и выходы ключей 14 блока 6 коммутируются с информационными входами ключей 4, соответствующих ребрам, исходящим из центральных вершин телемеханической системы. Затем обнуляют и записывают 1 в соответствующий разряд распределителя 2, обнуляют триггер 8 и счетчики 12, 13, подготавливают к работе блок 3, выполненный согласно авт. ев. 2.

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

После поступления сигнала запуска генератор 1 выдает импульсы на вход распределителя 2, который поочередно вьщает импульсы на каждый из своих четырех выходов. Импульс с первого выхода распределителя 2 вызывает появление на выходах блока 3 комбинации .сигналов, соответствующих моделируемому состоянию телемеханической системы и обуславливающих замыкание соответствуюш 1Х ключей 4.

Импульс, поступающий с второго выхода распределителя 2, устанавли3i

вает в О триггер-8, в результате чего с его инверсного выхода на второй вход элемента И 10 подается разрешающий, а с прямого выхода на второй вход элемента И 11 - запрещающий потенциал. Кроме того, этот же импульс распределителя 2 проходит через- элемент ИЛИ 9 и в качестве опросного сигнала поступает на информационный вход одного из ключей 4. Если моделируемое состояние телемеханической системы относится к множеству состояний безотказности (каждая вершина связана с цеитральной вершиной), то единичные сигналы появляются на всех входах элемента И 7, и появление единичного сигнала на его выходе приводит к увеличению на 1 показания счетчика 12 состояНИИ безотказности централизованной телемеханической системы, а также к остановке блока 3 на данном сочетании. Если моделируемое состояние относится к состоянию отказа, то хотя

бы на одном входе, а следовательно, и на выходе элемента И 7 присутствует нулевой сигнал.

Проверка состояния децентрализованной телемеханической системы осуществляется при появлении единичного сигнала на третьем выходе распределителя 2, который перебрасывает в единичное состояние триггер 8, открывая элемент И 11. Кроме того,

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

на всех входах и выходе элемента И 7 появляется единичный сигнал, что приводит к увеличению на 1 показаний счетчика 13 состояний безотказности децентрализованной телемеханической системы.

Сигнал на четвертом выходе распределителя 2 разрешает дальнейшую работу блока 3. Далее устройство работает аналогично, и после окончания перебора всех сочетаний, индицируемого ,в блоке 3, снимаются показания счетчиков 12 и 13.

31

Формула изобретения

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

пределителя импульсов соединен с нулевым входом триггера и первым входом элемента Ш1И, третий выход распределителя импульсов подключен

5 к единичному входу триггера и второму входу элемента ИЛИ, четвертый выход распределителя импульсов соединен с вторым тактовым входом блока перебора сочетаний, выходы кото10 рого соединены с управляющими входами соответствующих ключей группы, выход первого элемента И подключен к входу останова блока перебора сочетаний и первым входам второго и

t5 третьего элементов И, выходы которых соединены с входами соответственно первого и второго счетчиков, второй вход второго элемента И подключен к инверсиому выходу триггера, 20 прямой выход которого соедииен с

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

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

Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач определения характеристик структурной надежности централизованных и децентрализован|шх .телемеханических систем. Устройство решает поставленную задачу.путем последовательного перебора и анализа состояния графа. Цель изобретения состоит в расширении функциональных возможностей за счет определения числа состояний связности вершин, графа хотя бы с одной из его центральных вершин. Устройство содержит генератор импульсов, распределитель импульсов, блок перебора сочетаний, группу ключей, наборное поле, блок ключей, первый элемент И, триггер, элемент ИЛИ, второй и третий Зле- менты И, первый и второй счетчики с соответствующими функциональными связями между ними. 2 ил. 9 IND (X со со

Составитель A. Шеренков Редактор М. Бандура ТехредС.Мигунова Корректор В. Синицкая

Заказ 1133/57 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР .

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

Филиал ШШ Патент, г. Ужгород, ул. Проектная, 4

(fuff.Z