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

О П ИСА-Н-И Е ИЗОБРЕТЕНИЯ Союз Севетсиык Социалистическими Республик(61) дополнительное к авт. саид-ву(22) Заявлено 221177 (2) 2423373/18-24с присоединением заявки ЭЬ(23) Приоритет 606 Г 15/36 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 050479( 54 ) УСТРОЙСТВО ДЛЯ ОП РЕДЕЛЕНИЯ ХАРАКТЕРИСТИК ГРАФАИзобретение относится к областивычислительной техники и может бытьиспользовано для исследования надежности при проектировании и эксплуатации структур систем автоматического управления.Известно у тройство для исследования вероятностных графов 1, содержащее генератор импульсов, управляемые ключи, элементы И, элементыИЛИ.Возможности этого устройстваограничены, поскольку характеристики связности графа могут быть получены только для фиксированного числа вершин.Наиболее близким техническимрешением к изобретению является устройство для определения характерис"тик графа 21, содержащее блок отображения графа, триггеры вершин,единичные выходы которых подключенык первым входам ключей вершин, нулевые выходы триггеров вершин соединены с первыми входами элементовИЛИ, выходы которых подключены ксоответствующим входам элемента И,выход которого соединен с однимвходом ключа съема результата,другой вход которого подключен к шине опроса результата, триггерыребер выходы которых соединенысо входаМи ключей ребер, выходыключей ребер и вершин подключенык соответствующим входам блокаотображения графа, группу ключейи группу последовательно соединенных ключей, при этом первые входысоответствующих ключей обеих групп О объединены, вторые входы группыпоследовательно соединенных ключейподключены к нулевым выходам триггеров вершин, вторые входы группыключей соединены с единичными вы 1 е ходами триггеров вершин, выходыгруппы ключей подключены ко вторымвходам ключей вершин, вторым входамэлементов ИЛИ и выходам блока отображения графа.Ю Недостатком указанного устройства является то, что характеристики ,связности графа определяются без учета числа элементов в замыкающих И множествах и без учета распределениязамыкающих множеств.Целью изобретения является расширение области применения устройства за счет определения распределения З замыкающих множеств в графе.С помощью блока 17 ключи вершин 131 - 13 П и ребер 15- 15 щ соединяются между собой в соответствии с топологией графа. Далее устройство работает по тактам 1В такте С по шине 24 постуйают4сигналы, которые записывают в матрич ный запоминающий блок 22 вероятности возможных исходов розыгрыша вершин и ребер.В такте С 2 поступают сигналы по нам 2 , 2, которые устанавливают в4 Рнулевое положение триггеры 12 -12 я 14 - 14, и очищают счетчики 18, 194В такте 1 З по шинам 3 поступают результаты розыгрыша состояний вершин, а по шинам 4 - результаты розыгрыша состояний ребер. Соответствующие триггеры 12, - 12, 14 - 14 1 55 ши 60 65Укаэанная цель достигается тем, что в устройство введены счетчик вершин, счетчик ребер, дешифратор строки, счетчики чисел, дешифратор столбца и матричный запоминающий блок, первый вход которого через дешифратор строки подключен к выходу счетчика вершин, второй вход матриччого запоминающего блока через дешифратор столбца соединен с выходом счетчика ребер, третий вход матричного запоминающего блока сое" 10 динен с выходом ключа съема результата, выходы матричного запоминающего блока подключены ко входам счетчиков чисел, входы счетчиков вершин соединены с единичными выходами 15 соответствующих триггеров вершин, входы счетчиков ребер подключены к выходам соответствующих триггеров ребер.Функциональная схема предлагае мого устройства изображена на чертеже.Устройство содержит шину 1 проверки проводимости, шины 2, 2 установки триггеров в нулевое йоложение, шины 3 результатов розыгрыша вершин, шины 4 результатов розыгрыша ребер, шину 5 сигнала отсутствия вершин в данном розыгрыше, элементы ИЛИ б -бя,шину 7 съема результата, элемент И 8, шину 9 опро" са результата, группу последовательно соединенных ключей 10 - 10 п группу ключей 11 - 11 п, триггеры 12 - 12 пвершин, ключи 13 - 13 я вершин, трйггеры 14 - 14ребер, ключи35 1 5 - 15 и, ребер, ключ съема результ ат а 16, блок отображения графа 17, счетчики вершин 18, счетчик ребер 19, дешифратор строки 20, дешифратор столбца 21, матричный запоминающий 40 блок 22, счетчики чисел 23 -23,п, шину записи 24 записи чисел.Юнна 24 записи чисел подсоединена к соответствующему входу матричного запоминающего блока 22, 45Устройство работает следующим образом. устанавливаются в состояние 1и подают сигналы на входы соответствующих ключей 13- 13, и 15 - 15которые, срабатывая подготавливаютцепи прохождения сигнала проверкипроводимости через все связные вершины, Единичные сигналы с триггероввершин и ребер подсчитываются счетчиками 18 и 19, с выходов которыхсигналы поступают соответственнона входы дешифраторов 20 и 21. Дешифраторы 20 и 21 выбирают в матричном запоминающем блоке 22 число,соответствующее вероятности появленияданного исхода розыгрыша вершин иребер,В такте 1 по шине 1 подается сиг 4нал проверки проводимости, которыйпоступает на ключи 101 в 10, и 111 -11. Если первая вершина присутствует в розыгрыше, то триггер 12 находится в состоянии 1 и открывает ключ 11, через который сигналпроверки проводимости поступает навторой управляющий вход ключа 13,В противном случае нулевым входомтриггера 12 открывается ключ 10и сигнал проверки проводимости поступает на ключи 10и 11 и такдо тех пор, пока не будет обнаружена присутствующая вершина. Еслисигнал проверки проводимости пройдет все ключи и не обнаружит ни одной присутствующей вершины, то сигнал об. этом поступает по шине 5, иустройство переходит к следующемуиспытанию. Сигнал проверки проводимости поступает на второй вход того ключа 134 в 13 П, который обнару-.жен с помощью ключей 10 - 10 П и11 - 11, далее этот сигнал поступает через блок 17 на вторые входывсе связанных ключей 13 - 13 и ичерез элементы ИЛИ б - б на входыэлемента И 8, Если из прйсутствующих вершин хотя бы одна не связанас остальными, то на входе схемы И,.соответствующем этой вершине сигнала не будет, В случае связностивсех присутствующих вершин сработает элемент И 8, так как на остальные его входы поступает сигналс нулевых выходов триггеров вершин,отсутствующих в розыгрыше. ЭлементИ 8, сработав, открывает ключ съемарезультата 16.В такте 1 по шине 9 поступает сигнал опроса результата испытания на ключ съема результата 16. Если все присутствующие вершины связаны, сигнал опроса результата проходит через ключ 16 на вход считывания матричного запоминающего блока и по шине 7. По этому сигналу в матричном запоминающем блоке происходит считывание числа, соответствующего вероятности появления данного исхода розыгрыша вершин и ребер, и запись его в соответствующий6072 Формула изобретения 4 4 4,ИПИ Заказ 1528/40 Тираж 779 Подписно П Патент, г. Ужгород, ул, Проектная,4 Фили 5 .65 счетчик чисел 23- 23. При поступлении сигнала на шину 7 устройство переходит к работе на такте 1После завершения программы испытаний в счетчиках 234 - 23 п иПЦ 1 накапливается информацйя о распределении замыкающих множеств в графе. Каждому счетчику присвоен двойной индекс ( 1 ), где 1= 1, 2 и ,=1, 2,щ ,и - число вершин в исходном графе, щ - число ребер в исходном графе. Таким образом, содержимое счетчика с индексами ( 1, 3 ) - есть вероятность появления замыкающего множества, состоящего из1- вершин и- ребер. Устройство, выполняя функции известных устройств, реализует дополнительную Функцию . определения распределения замыкающих множеств в графе, что повышает точность и полноту исследования вероятностного графа. Устройство для определения характеристик графа, содержащее блок отображения графа, триггеры вершин, единичные выходы которых подключены к первым входам ключей вершин, нулевые выходы триггеров вершин соединены с первыми входами элементов ИЛИ, выходы которых подключены к соответствующим входам элемента И, выход которого соединен с одним входом ключа съема результата, другой вход которого подключен к шине опроса результата, триггеры ребер, выходы которых соединены со входами ключей ребер, выходы ключей ребер и вершин подключены к соответствующим входам блока отображения графа, группу ключей и группу последовательно соединенных ключей, приэтом первые входы соответстнующихключей обеих групп объединены, вторые входы группы последовательносоединенных ключей подключены к 5 нулевым выходам триггеров вершин,вторые входы группы ключей соединеныс единичными выходами триггеров вершин, выходы группы ключей подключеныко вторым входам ключей вершин, вто рым входам элементов ИЛИ и ныходамблока отображения графа, о т л ич а ю щ е е с я тем, что, с цельюрасширения области применения устройства за счет определения распределения замыкающих множеств в граФе, внего введены счетчик вершин,счетчик ребер, дешифратор строки,счетчики чисел, дешифратор столбцаи матричный запоминающий блок, первый вход которого через дешифраторстроки подключен к выходу счетчикавершин, второй вход матричного запоминающего блока через дешифраторстолбца соединен с выходом счетчикаребер, третий вход матричного запоминающего блока соединен с выходомключа съема результата, выходы матричного запоминающего блока подключены ко входам счетчиков чисел,входы счетчиков вершин соединены 30 с единичными выходами соответствующих триггеров вершин, входы счетчиков ребер подключены к выходам соответствующих триггеров ребер.Источники информации, принятые 38 но внимание при экспертизе1Авторское свидетельство СССР9 433504, кл. 606 б 7/48, 1972.2. Анторское свидетельство СССРМ 304604, кл. б 06 б 7/48, 1969,