Устройство для исследования вероятностных графов с ограничениями1изо'бретение относится к области вычислительной техники и может быть использовано для исследования вероятностных графов с ограничениями, в частности для определения характеристик связности графа при условии, что вершины считаются связанным'и между собой, если расстояние между ними не превышает зада'нную величину.известно устройство для моделирования вероятностных графов, содержаш,ее запоминающие триггеры вершин, управляемые ключевые схемы вершин, схему «и» запоминаюш,ие триггеры ребер, управляемые ключевые схемы ребер, клю'ч, распределитель, линию задержки, счетчик, ключ тактовых сигналов, шины выдачи результатов розыгрыша состояний вершин и ребер, ши'ну проверки проводимости и шину установки в исходное состояние.однако с .помош,ью этого устройства невозможно определить характер'истики связности вероятностного графа при наложенном ограничении по связности.цель изо'бретёния — возможность определения характеристик связности вероятностных графов при наложении ограничений по связности.с этой целью в предложенное устройство введены дополнительные запоминающие триггеры вершин, управляемые ключевые схемы вершин, управляемые ключевые схемы ребер.схема «и», а также схемы «или» и шина сброса. единичные входы дополнительных запоминающ'их триггеров вершин соединены с соответствующими выходами распределителя 5 и с выходами соответствующих схем «или». входы сброса в нулевое положение дополнительных запоминающих тригеров вершин соединены с шиной сброса, а их единичные выходы—с соответствующими входами допол-10 нительной схемы «и» и с управляющими входами соответствующих дополнительных управляемых ключевых схем вершин, входы которых соединены с выходом ключа тактовых сигналов, а выходы — со'входами соответствующих15 схем «или» и соединены в схему, отображающую граф, с выходами дополнительных управляемых ключевых схем ребер, управляющие входы которых соединены с единичными выходами соответствующих запоминающих тригге-20 ров ребер. выход дополнительной схемы «и» соединен с управляющим входом ключа тактовых сигна'лов и со входом линии задержки. схема устройства изображена на чертеже. устройство содержит запоминающие тригге-25 ры вершин 1, которые подключены к управляемым ключевым схемам вершин 2с одним входом 3 и несколькими выходами 4; запоминающие триггеры ребер 5, подключенные к управляемым ключевым схемам ребер 6 с двумя вы-30 ходами 7 и к дополнительным управляемым

О Il И С А Н И Е (ii) 435536

ИЗОБРЕТЕНИЯ

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

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

Социвлисти4ескнх

Республик (61) Зависимое от авт. свидетельства (22) Заявлено 09.07.71 (21) 1680875/18-24 с присоединением заявки №вЂ” (32) Приоритет

Опубликовано 05.07.74. Бюллетень ¹ 25

Дата опубликования описания 19.11.74 (51) М. Кл. 6 06g 7/48

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

Совета Министров СССР оо делам изобретений и открытий (53) УД1 681.33.157.001 (088.8) (72) Автор изобретения

В, В. Епихин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ

ГРАФОВ С ОГРАНИЧЕНИЯМИ

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

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

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

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

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

5 и с выходами соответствующих схем «ИЛИ».

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

15 схем «ИЛИ» и соединены в схему, отображающую граф, с выходами дополнительных управляемых ключевых схем ребер, управляющие входы которых соединены с единичными выходами соответствующих запоминающих тригге20 ров ребер. Выход дополнительной схемы «И» соединен с управляющим входом ключа тактовых сигналов и со входом линии задержки.

Схема устройства изображена на чертеже.

Устройство содержит запоминающие тригге25 ры вершин 1, которые подключены к управляемым ключевым схемам вершин 2с одним входом 3 и несколькими выходами 4; запоминающие триггеры ребер 5, подключенные к управляемым ключевым схемам ребер 6 с двумя вы30 ходами 7 и к дополнительным управляемым

435536 ключевым схемам ребер 8 с двумя выходами

9; схему «И» 10; дополнительные запоми нающие триггеры вершин ll с единичными выходами 12 и единичными входами 13; дополнительные управляемые ключевые схемы вершин

14 с одним .входом 15 и несколькими выходами

1b; схемы «ИЛИ» 17; ключ 18; распределитель

19; дополнительную схему «И» 20; ключ тактовых сигналов 21; счетчик 22 и линию задержки 23. Устройство содержит также шины

24 выдачи результатов розыгрыша состояний вершин; шины 25 выдачи результатов розыгрыша состояний ребер; шину 26 проверки проводимости; шину 27 выдачи сигнала о связности графа при отсутствии ограничении по связности; шину 28 импульсов продвижения; шину

29 выдачи сигнала о связанности графа.с наложенным ограничением по связности; шину 30 выдачи серии. сигналов; шину 31 выдачи сигнала отсутствия связности графа с наложенным ограничением IIQ связности; ши ну 32 выдачи сигнала на продолжение испытания; шину 33 сброса и шину 34 установки в исходное состояние.

Выходы 4 схем вершин 2 и выходы 7 схем ребер 6 соединены между собой в схему, отображающую граф, и образуют модель графа первого уровня. Выходы 16 дополнительных схем вершин 14 и выходы 9 дополнительных схем ребер 8 соединены между собой в схему, отображающую граф, и образуют модель графа второго уровня. Шина 26 подключена ко входу 3 схемы 2 одной из вершин исследуемой группы.

Устройство работает по основным тактам

Ть Т и Т и вспомогательным тактам 4, 4 и 4.

Работа устройства рассматривается на примере определения характеристик связности всех вершин графа. Если необходимо определить характеристики связанности группы вершин, то ко входам схемы «И» 10 подключаются входы 3 схем 2, соответствующих только вершинам заданной группы, выходы распределителя 19 подключаются только к единичным входам 13 триггеров .вершин 11, соответствующих вершинам заданной группы, и ко входам дополнительной схемы «И» подключаются единичные выходы 12 триггеров вершин 11, соответствующих вершинам заданной группы. Соответственно уменьшается число входов схемы

«И» 10, разрядность распреедлителя 19 и число входов дополнительной схемы «И» 20.

В такте Т по шине 34 устанавливаются в исходное состояние распределитель 19 и в нулевое положение триггеры вершин 1, триггеры ребер 5 и счетчик 22. Одновременно в такте T »Ilo шине 33 сбрасываются в нулевое положение все триггеры вершин 11. В исходном положении в распределителе 19 записана единица в первом разряде. При переходе распределителя 19 из -го состояния в (i+1)-å на его -м выходе появляется импульс. Разрядность распределителя 19 превышает на единицу число вершин исследуемой группы.

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. С помощью модели графа второго уровня определяется расстояние между вершинами заданной группы по

435536

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

Таким образом, при появлении сигнала на шине 27 происходит задержка очередного такта Ть и начинается работа устройства по вспомогательным тактам tI, 4 и б. В такте tI no шине 28 поступает импульс, который через открытый ключ 18 поступает на вход распределителя 19 и переводит его во второе положение. При этом на первом выходе распределителя 19 появляется импульс, который перебрасывает триггер вершины 11, соответствующий первой вершине заданной группы, в единичное положение. Этот триггер вершины 11 открывает соответствующую ему схему вершины 14 и между входом 15 и выходами 6 этой схемы вершины 14 образуется электрический контакт.

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

В такте 4 по шине 30 через открытый ключ тактовых сигналов 21 (ключ тактовых сигналов 21 закрыт при наличии сигнала на выходе схемы «И» 20) поступает серия из (К+1) импульсов на вход счетчика 22 и на все входы 15 схем вершин 14 (К вЂ” ограничение по связности). Первый импульс с шины 30 поступает через вход 15 схемы вершины 14, соответствующей первой вершине из зада иной группы, на выходы 16 только тех схем вершин 14 (через выходы 16 схемы вершины 14. соответствующей первой вершине, и через схемы ребер 8), которые соответствуют вершинам заданной группы, расстояние ло которых от первой веошины равно единипе. Через схемы «ИЛИ» 17 этих вептпи н импульс поступает на единичные входы 13 триггеров веотпин 11, которые перебрасываются в единичное положение иоткоывяют соответствуюнтие их схемы вершин 14. Дли тельность импчльсов, поступающих по шине

30, должна быть меньше времени срабатывания схем вершин 14 (исключая перебрасывание лрчгих тпиггеров вершин 11, соответствующих веошинам, расстояние до которых от первой больше елинипы). Втопой импульс, поступивтпий по тпине 30, перебрасывает в единичное положение тоиггеры вершин 11, сооТветствчтощие IlppIIIHHBM, расстояние до котопых от пеовой вершины равно двум. Если максимальное расстояние чо всех вептпин заданной гпчппы от пепвой меньттте или павно К, то ппи постчплении К или менее К импульсов по шине 30, все триггепы вершин 11 заданной гочппы вершин перебрасываются в единичное положение. собирается дополнительная схема

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

14, через линию задержки 23 сбрасывает счетчик 22 в нулевое положение и выдает сигнал на шину 32, сигнализирующий о том, что расстояние от первой вершины ло остальных вершин заданной группы в данном позыгрыше не превышает величины К, В этом случае в такте (з триггеры вершин 11 сбрасывается в ,нулевое положение по IImHe ЗЗ.

В такте fI по шине 28 вновь поступает импульс, который (через ключ 18) пеоеволит распределитель 19 в третье положение. и на его втором выходе появляется импчльс, который перебрасывает дополнительный запомина ющий триггер, соответствчющий втопой вершине, в елиничное положение. Начинается

15 аналогичный поопесс провеоки лля втооотт вершины: превышает ли расстояние 0Т нее ло остальных вершин заданной гочппы величину

К или нет?. Этот пооцесс проверки ппоисходит лля всех вершин заданной lovllllII. Если расстояние между всеми веотпинями заданной группы равно или меньше К, то ояспоелелитель 19 прохолит все свои (N !-1) положений (У вЂ” число веошин исслел емой гпчппы) и пои поступлении (У-т-1)-го импчлься по птине

28 и на шине 29 появляется сигнал, по которому испытание считается члачным, т. p.. в данном розыгрыше исслелчемяя гочппя веошин связана с учетом наложенного ограничения по связности. Если хотя бы между лвчмя вершинами i и т (i(j) расстояние поевьтптает величину К, то при постчплении c-го импульса ня ахоп распрелелителя 19 ня его (-м вы холе появляется HvlllvJIhc, котопьттт пепебпясывяет в единичное положение триггеп 11 т -II вершины. Далее по шине 30 в тякте t> постчпяет сепия из (К-1-1) импульса. После IIoc Ti пления К импчльсов по шине 30 в е тиничное положение перебрасываются все тпиггеоы 11 вершин, расстояние до которых от t-й вепптины меньше или равно К. Так как оясстояние ло вершины т превышает величитт К, то тоиггеп

11 т-й вершины находится в и левом положении, и на выходе лополнительпой схемы «И»

20 отсчтствчет сигнал. Далее пост пает (К+1) импчльс по шине 30, котооый пепеводит счетчик 22 в (К+1)-e пo тoжениe. (К-1-1)-й выход счетчика 22 подключен к шине 31. и пои пепехоле счетчика 22 в (К4-1)-е положение ня шине 31 появляется сигнал, Появление сигнала на шине 31 говопит о том, что в данном оозыгпытпе расстояние межл какими-либо вепшинями заланной гпчппы llneelllllaeT величиттi К. Испытание считается ттсчлячттьтм. xoTB без ччетя няложснттого ограничения заданная грчппя вершин связана, После члачного или неудачного испытания (сигнал на шине 29 или сигнал ня птине 31) ппекращается работа по вспомогательным тактам, и устройство пепехолит к работе по ос6О новным тактам Т,, Т, и Т;. Так кяк работа устройства была преована после такта Т>, то пНа ППОЛОЛжаЕтСЯ С тЯКта Тт.

В такте Т, устройство чстянавливается в исходное положение. В такте Т по шинам 24 и

65 25 поступают результаты розыгрыша состоя

435536 ний вершин и ребер графа. Определяется связность заданной группы вершин в такте Тз по результатам нового розыгрыша и т. д.

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

Пусть было, проведено М испытаний, в результате которых сигнал на шине 27 появлялся М раз, а на шине 29 М раз P4)M>).

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

Предмет изобретения

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

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

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

30 «ИЛИ» и шина сброса; причем единичные входы дополнительных запоминающих триггеров вершин соединены с соответствующими выходами распределителя и с выходами соответствующих схем «ИЛИ»; входы сброса в ч5 нулевое положение дополнительных запоминающих триггеров вершин соединены с шиной сброса, а их единичные выходы — с соответствующими входами дополнительной схемы «И» и с управляющими входами соответствующих

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

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

Г5 25

Составитель В. Озерова

Техред О. Вешкина

Корректор А. Васильева

Редактор Л. Утехина

Типография, пр. Сапунова, 2

Заказ 3162/12 Изд. № 985 Тираж 624 Подписное

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

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