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

 

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

СО1ОЭ СОВЕТСНИХ

NUIWMC

РЕСПУБЛИК

ÄÄSUÄÄ 121839 (Я)4 G 06 F 15 20

L

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ГО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3786806/24-24 (22) 30.08.84 (46) 15,03.86. Бюл. ¹ 10 (72) П,К. Павнитьев (53) 681.33,(088.8 ) (56) Авторское свидетельство СССР № 656073, кл. G 06 F 15/36, 1976.

Авторское свидетельство СССР № 238238, кл. G 06 F 15/32, 1977.

Авторское свидетельство СССР № 329538, кл. G 06 G 7/48, 1970. (54)УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

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

1 12

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

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

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

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

ИЛИ 9, второй 1О и третий 11 элементы И, первый 12 и второй 13 счетчики.

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

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

1 в соответствующий разряд распределителя 2, обнуляют триггер 8 и счетчики 12, 13, подготавливают к работе блок 3, выполненный согласно авт. св. L2).

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

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

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

8393

5

50 вает в О триггер 8, в результате чего с его инверсного выхода на второй вход элемента И 10 подается разрешающий, а с прямого выхода на второй вход элемента И 11 — запрещающий потенциал. Кроме того, этот же импульс распределителя 2 проходит через элемент ИЛИ 9 и в качестве опросного сигнала поступает на информационный вход одного из ключей

4. Если моделируемое состояние телемеханической системы относится к множеству состояний безотказности (каждая вершина связана с центральной вершиной), то единичные сигналы появляются на всех входах элемента

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

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

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

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

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

Устройство для исследования графов, содержащее блок перебора сочетаний, группу из m ключей .(m — чис- 5 ло ребер графа), первый элемент

И, блок ключей иэ и-1 ключей (n— число центральных вершин графа), триггер, два счетчика и наборное поле, выходы которого соединены с

10 информационными входами и выходами соответствующих ключей группы, выходы i-х клвяей (i = I, т — Т) группы подключены к входам первого элемента И, о т л и ч а ю щ е е с я 15 тем, что, с целью расширения функциональных возможностей за счет определения числа состояний связности вершин графа хотя бы с одной из его центральных вершин, в устройство вве- 20 дены элемент ИЛИ, второй и третий элементы И и генератор импульсов, вход которого является пусковым входом устройства, а выход соединен с входом распределителя импульсов, первый выход которого подключен к первому тактовому входу блока перебора сочетаний, второй выход распределителя импульсов соединен с нулевым входом триггера и первым входом элемента ИЛИ, третий выход распределителя импульсов подключен к единичному входу триггера и второму входу элемента ИЛИ, четвертый выход распределителя импульсов соединен с вторым тактовым входом блока перебора сочетаний, выходы которого соединены с управляющими входами соответствующих ключей группы, выход первого элемента И подключен к входу останова блока перебора сочетаний и первым входам второго и третьего элементов И, выходы которых соединены с входами соответст" венно первого и второго счетчиков, второй вход второго элемента И подключен к инверсному выходу триггера, прямой выход которого соединен с вторым входом третьего элемента И и управляющим входом блока ключей, выход элемента ИЛИ подключен к выходу

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

1218393

Составитель А. Шеренков

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

Заказ 1133/57 Тираж 673 Подписное

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

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

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

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

 

Похожие патенты:

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

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

Изобретение относится к области цифровой вычислительной техники, в (Частности к устройствам обработки информации специального назначения ,с точки зрения вычислительного устройства

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

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

Изобретение относится к вычислительной технике и может быть использовано при моделировании посредством сетей Петри

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

Изобретение относится к области электротехники, в частности к матричным коммутаторам, и может быть использовано в системах управления и наблюдения

Изобретение относится к области вычислительной техники и может быть использовано для построения коммутационных средств мультипроцессорных вычислительных и управляющих систем

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

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта
Наверх