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

 

О ПИСА-Н вЂ” И Е

ИЗОБРЕТЕНИЯ

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

Союз Севетсиык

Сецыалыстыческык

Республик

<ц656072 (6lj Дополнительное к авт. свид-ву(22} Заявлено221177 (2l } 2423373/18-24 с присоединением заявки ЭЙ (23j Приоритет

506 F 15/36

Государствеииий комитет

СССР по делам изобретений и открытий

Опубликовано 050479. Бюллетень % 13 (53) УДК681.333 (088.8 7

Дата опубликования описания 050479 (72) Автор. изобретения

В.И.Червяцов (54 ) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ХАРАКТЕРИСТИК ГРАФА

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

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

ИЛИ.

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

Наиболее близким техническим решением к изобретению является устройство для определения характерис" тик графа (2), содержащее блок отображения графа, триггеры вершин, единичные выходы которых подключены к первым входам ключей вершин, нулевые выходы триггеров вершин соединены с первыми входами элементов

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

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

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

656072 4

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

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

Устройство содержит шину 1 проверки проводимости, шины 2, 2 установки триггеров в нулевое положение, шины 3 результатов розыгрыша вершин, шины 4 результатов розыгрыша ребер, шину 5 сигнала отсутствия вершин в данном розыгрыше, элементы ИЛИ 6 -бя,шину 7 съема результата, элемент И 8, шину 9 опроса результата, группу последовательно соединенных ключей 10 — 10п группу ключей 11„ - 11, триггеры

12 — 12 вершин, ключи 13 — 13д вершин, трйггеры 14„ — 14 „ ребер, ключи

15< — 15 ребер, ключ съема результата

l6, блок отображения графа 17, счетчики вершин 18, счетчик ребер 19, дешифратор строки 20, дешифратор столбца 21, матричный запоминающий 40 блок 22, счетчики чисел 23„ -23,п„, шину записи 24 записи чисел.Мина 24 записи чисел подсоединена к соответствующему входу матричного запоминающего блока 22. 45

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

С помощью блока 17 ключи вершин

13 — 13 и ребер 15 - 15щ соединяИ ются между собой в соответствии 50 с топологией графа. Далее устройство работает по тактам t it2ltÝ t4iъ

В такте по шине 24 постуйают

4 сигналы, которые записывают в матричный запоминающий блок 22 вероятности возможных исходов розыгрыша вершин и ребер.

В такте t 2 поступают сигналы по шинам 2, 2, которые устанавливают в

4 1 нулевое положение триггеры 12 -12 я

14 — 14,„ и очищают счетчики 18, 19 °

В такте < Э по шинам 3 поступают результаты розыгрыша состояний вершин, а по шинам 4 - результаты розыгрыша состояний ребер. Соответствующие триггеры 12. - 12>,> 14„ — 14 д

65 устанавливаются в состояние 1 и подают сигналы на входы соответствующих ключей 13„- 13, и 15„— 15 которые, срабатывая подготавливают цепи прохождения сигнала проверки проводимости через все связные вершины. Единичные сигналы с триггеров вершин и ребер подсчитываются счетчиками 18 и 19, с выходов которых сигналы поступают соответственно на входы дешифраторов 20 и 21. Дешифраторы 20 и 21 выбирают в матричном запоминающем блоке 22 число, соответствующее вероятности появления данного исхода розыгрыша вершин и ребер.

В такте 1 по шине 1 подается сиг4 нал проверки проводимости, который поступает на ключи 101 в 10, и 111—

ll Если первая вершина присутствует в розыгрыше, то триггер 12 находится в состоянии 1 и открывает ключ 11, через который сигнал проверки проводимости поступает на второй управляющий вход ключа 13А .

В противном случае нулевым входом триггера 12 открывается ключ 10„ и сигнал проверки проводимости поступает на ключи 10 и 11 и так до тех пор, пока не будет обнаружена присутствующая вершина. Если сигнал проверки проводимости пройдет все ключи и не обнаружит ни одной присутствующей вершины, то сигнал об. этом поступает по шине 5, и устройство переходит к следующему испытанию. Сигнал проверки проводимости поступает на второй вход того ключа 134 в 13, который обнаружен с помощью ключей 10 — 10> и

ll — 11, далее этот сигнал поступает через блок 17 на вторые входы все связанных ключей 13 — 13 и и через элементы ИЛИ б — б „ на входы элемента И 8. Если из прйсутствующих вершин хотя бы одна не связана с остальными, то на входе схемы И,. соответствующем этой вершине сигнала не будет. В случае связности всех присутствующих вершин сработает элемент И 8, так как на остальные его входы поступает сигнал с нулевых выходов триггеров вершин, отсутствующих в розыгрыше. Элемент

И 8, сработав, открывает ключ съема результата 16.

В такте э по шине 9 поступает сигнал опроса результата испытания на ключ съема результата 16. Если все присутствующие вершины связаны, сигнал опроса результата проходит через ключ 16 на вход считывания матричного запоминающего блока и по шине 7. По этому сигналу в матричном запоминающем блоке происходит считывание числа, соответствующего вероятности появления данного исхода розыгрыша вершин и ребер, и запись его в соответствующий

6072

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

4 4 4

ЦНИИПИ Заказ 1528/40 Тираж 779 Подписное

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

5 .65 счетчик чисел 23 - 23 „. При поступлении сигнала на шину 7 устройство переходит к работе на такте 1

После завершения программы испытаний в счетчиках 234 — 23> < я1п накапливается информацйя о распределении замыкающих множеств в графе. Каждому счетчику присвоен двойной индекс (() ), где (= 1, 2

n, j =1, 2, ... m, п — число вершин в исходном графе, m - -число ребер в исходном графе. Таким образом, содержимое счетчика с индексами (1 ) — есть вероятность появления замыкающего множества, состоящего из

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

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

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

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

30 с единичньги выходами соответствующих триггеров вершин, входы счетчиков ребер подключены к выходам соответствующих триггеров ребер.

Источники информации, принятые

38 вс внимание при экспертизе

1. авторское свидетельство СССР

Р 433504, кл. 606 6 7/48, 1972.

2. Авторское свидетельство СССР

9 304604, кл. Ci 06 G 7/48, 1969