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

пц 435536 О Й И С А Н И Е ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Сезцквлкстмческнх Республик(32) ПриоритетОпубликовано 05,07.74, Бюллетень25Дата опубликования описания 19.11,4 51) М, 1(л. 6 06 д 7/48 осударственный комите Совета Министров ССС оо делам изобретенийи открытий 53) УД 1 681,33.157.001) Заявитель 54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ ГРАФОВ С ОГРАНИЧЕНИЯМИсти.С этойвведеныгеры вервершин,Изобретение относится к области вычислительной техники и может быть использовано для исследования вероятностных графов с ограничениями, в частности для определения характеристик связности графа при условии, что вершины считаются связанными между собой, если расстояние между ними не превышает задаиную величину.Известно устройство для моделирования вероятностных графов, содержащее запоминающие триггеры вершин, управляемые ключевые схемы вершин, схему И запоминающие триггеры ребер, управляемые ключевые схемы ребер, ключ, распределитель, линию задержки, счетчик, ключ тактовых сигналов, шины выдачи результатов розыгрыша состояний вершин и ребер, шину проверки проводимости и шину установки в исходное состояние.Однако с,помощью этого устройства невозможно определить характеристики связности вероятностного графа при наложенном ограничении по связности.Цель изобретения - возможность определения характеристик связности вероятностных графов при наложении ограничений по связноцелью в предложенное устройство дополнительные запоминающие тригшин, управляемые ключевые схемы правляемые ключевые схемы ребер,схема И, а также схемы ИЛИ и шина сброса. Единичные, входы дополнительных запоминающих триггеров вершин соединены с соответствующими выходами распределителя 5 и с выходами соответствующих схем ИЛИ.Входы сброса в нулевое положение дополнительных запоминающих тригеров вершин соединены с шиной сброса, а их единичные выходы - с соответствующими входами допол нительной схемы И и с управляющими входами соответствующих дополнительных управляемых ключевых схем вершин, входы которых соединены с выходом ключа тактовых сигналов, а выходы - со входами соответствующих 15 схем ИЛИ и соединены в схему, отображающую граф, с выходами дополнительных управляемых ключевых схем ребер, управляющие входы которых соединены с единичными выходами соответствующих запоминающих тригге ров ребер. Выход дополнительной схемы Исоединен с управляющим входом ключа тактовых сигналов и со входом линии задержки.Схема устройства изображена на чертеже, Устройство содержит запоминающие тригге ры вершин 1, которые подключены к управляемым ключевым схемам вершин 2 с одним входом 3 и несколькими выходами 4; запоминающие триггеры ребер 5, подключенные к управляемым ключевым схемам ребер 6 с двумя вы ходами 7 и к дополнительным управляемымключевым схемам ребер 8 с двумя выходами 9; схему И 10; дополнительные запоминающие триггеры вершин 11 с единичными выходами 12 и единичными входами 13; дополнительные управляемые ключевые схемы вершин 14 с одним входом 15 и несколькими выходами 16; схемы ИЛИ 17; ключ 18; распределитель 19; дополнительную схему И 20; ключ тактовых сигналов 21; счетчик 22 и линию задержки 23. Устройство содержит также шины 24 выдачи результатов розыгрыша состояний вершин; шины 25 выдачи результатов розыгрыша состояний ребер; шину 26 проверки проводимости; шину 27 выдачи сигнала о связности графа при отсутствии ограничении по связности; шину 28 импульсов продвижения; шину 29 выдачи сигнала о связанности графа.с наложенным ограничением по связности; шину 30 выдачи серии. сигналов; шину 31 выдачи сигнала отсутствия связности графа с наложенным ограничением по связности; шину 32 вы дачи сигнала на продолжение испытания; шину 33 сброса и шину 34 установки в исходное состояние.Выходы 4 схем вершин 2 и выходы 7 схем ребер 6 соединены между собой в схему, отображающую граф, и образуют модель графа первого уровня, Выходы 16 дополнительных схем вершин 14 и выходы 9 дополнительных схем ребер 8 соединены между собой в схему, отображающую граф, и образуют модель графа второго уровня. Шина 26 подключена ко входу 3 схемы 2 одной из вершин исследуемой группы.Устройство работает по основным тактам Ть Т и Тз и вспомогательным тактам 1 ь 1 и 1 з. Работа устройства рассматривается на примере определения характеристик связанности всех вершин графа, Если необходимо определить характеристики связанности группы вершин, то ко входам схемы И 10 подключаются входы 3 схем 2, соответствующих только вершинам заданной группы, выходы распределителя 19 подключаются только к единичным входам 13 триггеров .вершин 11, соответствующих вершинам заданной группы, и ко входам дополнительной схемы И подключаются единичные выходы 12 триггеров вершин 11, соответствующих вершинам заданной группы. Соответственно уменьшается число входов схемы И 10, разрядность распреедлителя 19 и число входов дополнительной схемы И 20.В такте Т по шине 34 устанавливаются в исходное состояние распределитель 19 и в нулевое положение триггеры вершин 1, триггеры ребер 5 и счетчик 22. Одновременно в такте Т по шине 33 сбрасываются в нулевое положение все триггеры вершин 11, В исходном положении в распределителе 19 записана единица в первом разряде. При переходе распределителя 19 из -го состояния в (+1) -е на его -м выходе появляется импульс. Разрядность распределителя 19 превышает на единицу число вершин исследуемой группы,5 10 15 20 25 30 35 40 45 50 55 60 65 4В такте Т по шинам 24 поступают результаты розыгрыша состояний вершии графа, а по шинам 25 - результаты розыгрыша состояний ребер графа. Если вершина (ребро) присутствует в данном розыгрыше, то по соответствующей шине 24 (25) на единичный вход триггера вершины 1 (триггера ребра 5) поступает импульс и перебрасывает его в единичное положение. Схемы вершин 2 триггеров вершин 1, находящихся в единичном полжении, открываются, и между входами 3 и выходами 4 этих схем вершин 2 образуется электрический контакт. Триггеры ребер 5, которые находятся в единичном положении, открывают соответствующие им управляемые схемы ребер 6 и дополнительные схемы ребер 8, Между выходами 7 схем ребер 6 образуется электрический контакт. Одновременно между, выходами 9 схем ребер 8 образуется электрический контакт.В такте Тз по шине 26 поступает сигнал проверки проводимости, который поступает на вход 3 схемы 2, соответствующей одной из вершин исследуемой группы. Если заданная группа вершин связана по результатам розыгрыша состояний вершин и ребер без учета ограничения по связности, то между выходами 3 всех схем 2 этих вершин образован электрический контакт и при подаче сигнала проверки проводимости по шине 26 на всех входах схемы И 10 появляется сигнал. При этом на выходе схемы И 10 появляется сигнал, который открывает ключ 18 и одновременно подается на шину 27, сигнализируя о том, что в данном розыгрыше заданная группа вершин связана без учета наложенного ограничения, по связности. Таким образом, триггеры вершин 1, триггеры ребер 5, схемы вершин 2 и схемы ребер 6 образуют модель графа первого уровня, на которой определяется наличие связности заданной группы вершин без учета наложенного ограничения по связности,Если заданная группа, вершин не связана без учета наложенного ограничения по связности (отсутствует сигнал на шине 27 в такте Тз), то заданная группа вершин не связана и при учете нналоженного ограничения, Испытание считается неудачным,и:работа продолжается по основным тактам Ть Т и Тз Определяется связность заданной группы вершин по результатам нового розыгрыша состояний вершин и ребер графа.Если заданная группа вершин связана без учета наложенных ограничений (наличие в такте Тз сигнала на шине 27), то происходит задержка очередного такта Т, для проведения исследования связности заданной труппы вершин по результатам этого розыгрыша моделью графа второго уровня с учетом наложенного ограничения по связности.Модель графа второго уровня образуют дополнительные триггеры 11, дополнительные схемы вершин 14, схемы ИЛИ 17 и дополнительные схемы ребер 8. С помощью модели графа второго уровня определяется расстояние между вершинами заданной группы по5результатам данного розыгрыша состояний вершин и ребер графа, Если расстояние между вершинами не превышает величины заданного ограничения по связности К, то исход всего испьттания считается удачным. В противном случае испытание считается неудачным, и заданная группа вершин не связана с учетом наложенного ограничения по связности.Таким образом, при появлении сигнала на шине 27 происходит задержка очередного такта Ть и начинается работа устройства по вспомогательным тактам 1 ь 1 и 1 з. В такте 1 т по шине 28 поступает импульс, который через открытый ключ 18 поступает на вход распределителя 19 и переводит его во второе положение. При этом на первом выходе распределителя 19 появляется импульс, который перебрасывает триггер вершины 11, соответствующий первой вершине заданной группы, в единичное положение, Этот триггер вершины 11 открывает соответствующую ему схему вершины 14 и между входом 15 и выходами6 этой схемы вершины 14 образуется электрический контакт. Выходы распоеделителя 19 подключены к еди ничным входам 13 триггеров вершин 11, соответствующих всем вершинам заданной группы. В такте 1 з по шине 30 через открытый ключ тактовых сигналов 21 (ключ тактовых сигналов 21 закрьтт при наличии сигнала на выходе схемы И 20) поступает серия из (К+1) импульсов на вход счетчика 22 и на все входы 15 схем вершин 14 (К - ограничение по связности). Первый импульс с шины ЗО поступает через вход 15 схемы вершины 14, соответствующей первой вершине из задаиной группы, на выходы 16 только тех схем вершин 14 (через выходы 16 схемы вершины 14, соответствующей первой вершине, и через схемы ребер 8), которые соответствуют вершинам заданной группы, расстояние до которых от первой вепшины равно единице. Через схемы ИЛИ 17 этих веотцин импульс поступает на единичные входы 13 триггеров веотпин 11, которые перебрасываются в единичное положение иоткоывяют соответствующие их схемы вершин 14, Длительность импчльсов, поступающих по шине 30, должна быть меньше времени срабатывания схем вершин 14 (исклточая перебрасывание лрчгих триггеров вершин 11, соответствующих веошинам, расстояние до которых от первой больше елиниттт.т). Втопой импульс, поступивтпий по тпине 30, перебрасывает в единичное положение тоиггеры вершин 11, соответствчтощие верптинам, расстояние до котопых от пеовой вершины равно двум. Если максимальное расстояние чо всех вептпин заданной гпчппы от пепвой меньттте или оавно К, то ппи постчплении К или менее К импульсов по шине 30, все триггеоы вершин 11 заданной гоуппы вершин перебрасываются в единичное положение. собирается дополнительная схема И 20 и на ее выхоле появляется сигнал, который запрещает прохождение следующих импчльсов с птины 30 на вхолы 15 схем вершин 14, через линию задержки 23 сбрасывает счетчик 22 в нулевое положение и вылает сигнал на шину 32, сигнализирующий о том, что расстояние от первой вершины ло остальных вершин заданной группы в ланном позыгрыше не превышает величины К, В этом случае в такте 1 з триггеры вершин 11 сбрасывается в,нулевое положение по птине ЗЗ.В такте 1 т по шине 28 вновь поступает импульс, который (через ключ 18) пепеволит распределитель 19 в третье положение, и на его втором выходе появляется импчльс, который перебрасывает дополнительный запомина.ющий триггер, соответствчющий втооой вершине, в елиничное положение. Начинается 15 аналогичный пооцесс провеоки лля втооойвершины: превышает ли расстояние от нее ло остальных вершин заданной гпчппы величину К или нет. Этот пооцесс проверки ппоисхолит лля всех вершин заданной гпчппы, Если расстояние между всеми вептпинями заданной группы равно или меныпе К, то ояспоелелитель 19 прохолит все свои (У-т) положений (У - число веошин исслел емой гпчппьт 1 и пои поступлении (У-т)-го импульса по шине 28 и на шине 29 появляется сигнал, по которому испытание считается члачным, т. е. в данном розыгрыше исслелчемая гочппа веошин связана с учетом наложенного ограничения по связности. Если хотя бы между лвчмя 3 О вершинами т и т (т(т) расстояние поевьтптаетвеличину К, то при постчплении т-го импчлься на вхоч распрелелителя 19 ня его т-м вы.холе появляется импульс, котопьттт пепебпясывяет в ечиничное положение триггеп 11 т-тт вершины. Далее по шине 30 в такте 1 з постчпяет сепия из (К1) импульса. После поетчпления К импчльсов по шине ЗО в е 1 тиничное положение перебоасываютсл все тпиггеоы 11 вершин, расстояние до которых от г-й ветттттиньт меньше или равно К. Так как пясстояние ло вептттиньт т превышает величину К, то тоиггеп 11 т-й вершины находится в нулевом положении, и на выходе лополнительпой схемы И 20 отсутствует сигнал. Далее поступает (К+1) импульс по тцине 30, котооый пеоевочит счетчик 22 в (К+1) -е почожение. (К-1) -й выхоч счетчика 22 подключен к шине 31. и пои пепехоле счетчика 22 в (К 4-11-е положение ня шине 31 полнляетея сигнал, Появление сигнала на шине 31 говооит о том, что в данном оозыгпьцпе расстояние межлч какими-либо веотпииями заланной гоуппьт ппевышает величию К. Иепьттяттие считяетсл ттечлячттьтм, хотя без ччетя няложенттого ограничения заданная гчппя вертттттн свлзяття,После улатного или неучачного испытания(сигнал на шине 29 или сигнал на птине 31) ппекращаетсл работа по вспомогательным тактам, и устройство пеоехолит к работе по основным тактам Т, Т. и Тз. Так как работа устройства была преована после такта Тз, то оня поололжается с такта ТьВ такте Т, устройство устанавливается в исходное положение. В такте Т по шинам 24 и 65 25 поступают результаты розыгрыша состоя.ний вершин и ребер графа. Определяется связность заданной группы вершин в такте Тз по результатам нового розыгрыша и т. д.Таким образом, между двумя тактами Т происходит йсследованине одного из состояний вероятностного графа по результатам розыгрыша состояний его вершин и ребер. Если в процессе испытания в такте Тз отсутствует сигнал на шине 27, то заданная группа вершин по результатам данного розыгрыша разбита на несколько частей. Если в такте Т, на шине 27 имеется сигнал, то заданная группа вершин связана без учета наложенного ограничения по связности и начинается проверка связности заданной группы вершин с учетом наложенного ограничения по связности. Если в процессе этой проверки появляется сигнал на шине 29, то заданная группа вершин связана с учетом наложенного ограничения по связности. Если сигнал появляется на шине 38, то с учетом наложенного ограничения по связности заданная группа вершин считается как-бы разбитой на несколько частей.Пусть было, проведено М испытаний, в результате которых сигнал на шине 27 появлялся М раз, а на шине 29 М раз (М)М), Отношение М/М характеризует вероятность связности заданной группы вершин без учета наложенного ограничения по связности, а отношение М/М характеризует вероятность связности этой группы вершин с учетом наложенного ограничения по связности,Предмет изобретенияУстройство для исследования вероятностных графов с ограничениями, содержащее запоминающие триггеры вершин, управляемые ключевые схемы вершин, схему И, запоминающие триггеры ребер, управляемые ключевые схемы ребер, ключраспределитель, линию задержки, счетчик, ключ тактовых сигналов, причем единичные выходы запоминающих триггеров вершин соединены с шинами выдачи результатов розыгрыша состояний вершин, единичные входы запоминающих триггеров ребер соединены с шинами выдачи результатов,розыгрыша состояний ребер, единичные выходы запоминающих триггеров вершин соединены с управляющими входами соответствующих управляемых ключевых схем вершин,единичные выходы запоминающих триггеров ребер соединены с управляющими входами соответствующих управляемых ключевых схем ребер, выходы управляемых ключевых схем вершин и выходы управляемых ключевых схем ребер соединены между собой в схему, отображающую граф, входы управляемых ключевых схем вершин соединены с соответствующими входами схемы И, а один из них сое динен, кроме того, с шиной проверки проводимости, выход схемы И соединен с управляющим входом ключа, вход которого соединен с шиной импульсов продвижения, а выход - со входом распределителя, вход ключа такто Б вых сигналов соединен с шиной выдачи серииимпульсов, а его выход - со входом счетчика, вход сброса которого соединен с выходом линии задержки, а входы установки в исходное состояние счетчика, запоминающих триггеров 20 вершин, запоминающих триггеров ребер и распределителя соединены с шиной установки в исходное состояние, о т л и ч а ю щ е е с я тем, что, с целью получения возможности определения характеристик связности вероятностных 25 графов с наложенным ограничением по связности, в него введены дополнительные запоминающие триггеры вершин, управляемые ключевые схемы вершин, управляемые ключевые схемы ребер, схема И, а также схемы ЗО ИЛИ и шина сброса; причем единичныевходы дополнительных запоминающих триггеров вершин соединены с соответствующими выходами распределителя и с выходами соответствующих схем ИЛИ; входы сброса в З 5 нулевое положение дополнительных запоминающих триггеров вершин соединены с шиной сброса, а их единичные выходы - с соответствующими входами дополнительной схемы И и с управляющими входами соответствующих 40 дополнительных управляемых ключевых схемвершин, входы которых соединены с выходом ключа тактовых сигналов, а выходы соединены со входами соответствующих схем ИЛИ, а также соединены в схему, отображающую 45 граф, с выходами дополнительных управляемых ключевых схем ребер, управляющие входы которых соединены с единичными выходами соответствующих запоминающих триггеров ребер; выход дополнительной схемы И соединен с управляющим входом ключа тактовых сигналов и со входом линии задержки.Изд.985 Тираж 624 сударственного комитета Совета Минн по делам изобретений и открытий Москва, Ж, Раушская наб., д, 4/5