УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ ГРАФОВ С ОГРАНИЧЕНИЯМИ1Изо'бретение относится к области вычислительной техники и может быть использовано для исследования вероятностных графов с ограничениями, в частности для определения характеристик связности графа при условии, что вершины считаются связанным'и между собой, если расстояние между ними не превышает за- да'нную величину.Известно устройство для моделирования вероятностных графов, содержаш,ее запоминающие триггеры вершин, управляемые ключевые схемы вершин, схему «И» запоминаюш,ие триггеры ребер, управляемые ключевые схемы ребер, клЮ'Ч, распределитель, линию задержки, счетчик, ключ тактовых сигналов, шины выдачи результатов розыгрыша состояний вершин и ребер, ши'ну проверки проводимости и шину установки в исходное состояние.Однако с .помош,ью этого устройства невозможно определить характер'истики связности вероятностного графа при наложенном ограничении по связности.Цель изо'бретёния — возможность определения характеристик связности вероятностных графов при наложении ограничений по связности.С этой целью в предложенное устройство введены дополнительные запоминающие триггеры вершин, управляемые ключевые схемы вершин, управляемые ключевые схемы ребер.схема «И», а также схемы «ИЛИ» и шина сброса. Единичные входы дополнительных за- поминаюЩ'Их триггеров вершин соединены с соответствующими выходами распределителя 5 и с выходами соответствующих схем «ИЛИ». Входы сброса в нулевое положение дополнительных запоминающих тригеров вершин соединены с шиной сброса, а их единичные выходы—с соответствующими входами допол-10 нительной схемы «И» и с управляющими входами соответствующих дополнительных управляемых ключевых схем вершин, входы которых соединены с выходом ключа тактовых сигналов, а выходы — со'входами соответствующих15 схем «ИЛИ» и соединены в схему, отображающую граф, с выходами дополнительных управляемых ключевых схем ребер, управляющие входы которых соединены с единичными выходами соответствующих запоминающих тригге-20 ров ребер. Выход дополнительной схемы «И» соединен с управляющим входом ключа тактовых сигна'лов и со входом линии задержки. Схема устройства изображена на чертеже. Устройство содержит запоминающие тригге-25 ры вершин 1, которые подключены к управляемым ключевым схемам вершин 2с одним входом 3 и несколькими выходами 4; запоминающие триггеры ребер 5, подключенные к управляемым ключевым схемам ребер 6 с двумя вы-30 ходами 7 и к дополнительным управляемым Советский патент 1974 года по МПК G06G7/48 

ключевым схемам ребер 8 с двумя выходами 9; -схему «И 10; дополнительные запоминающие триггеры вершин 11 с единичными выходами 12 и единичными входами 13; дополнительные управляемые ключевые схемы вершин 14 с одним .входом 15 и несколькими выходами 1Ь; схемы «ИЛИ 17; ключ 18; распределитель 19; дополнительную схему «И 20; ключ тактовых сигналов 21; счетчик 22 и линию задержки 23. Устройство содержит также шины 24 выдачи результатов розыгрыша состояний вершин; шипы 25 выдачи результатов розыгрыша состояний ребер; шину 26 проверки проводимости; шину 27 выдачи сигнала о связности графа при отсутствии ограничении по связности; шину 28 импульсов продвижения; шину 29 выдачи сигнала о связиости графа .с наложенным ограничением по связности; шину 30 выдачи серии .сигналов; шину 31 выдачи сигнала отсутст1вия связности графа с наложенным ограничением по -связности; шииу 32 выдачи сигнала на продолжение испытания; шину 33 сброса и шину 34 установки в исходное состояние.

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

Устройство работает по основным тактам TI, Га и Гз и вспомогательным тактам /ь tz и ta.

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

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

В такте Га по шинам 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 в такте

Гз), то заданная группа вершин не связана и при учете нналоженного ограничения. Испытание считается неудачным, и работа продолжается по основным тактам Т, Tz и Тз. Определяется связность заданной группы вершин по

результатам нового розыгрыша состояний вершин и ребер графа.

Если заданная группа вершин связана без учета наложенных ограничений (наличие в такте Тз сигнала на шине 27), то происходит

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

Модель графа второго уровня образуют дополнительные триггеры 11, дополнительные схемы вершин 14, схемы «ИЛИ 17 и дополнительные схемы ребер 8. С помощью модели графа второго уровня определяется расстояние между вершинами заданной группы по

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

Таким образом, при появлении сигнала на шине 27 происходит задержка очередного такта Гь и начинается работа устройства по вспомогательным тактам ti, fz и ts- В такте fi по шине 28 поступает импульс, который через открытый ключ 18 поступает на вход распределителя 19 и переводит его во второе положение. ПрИ этом на первом выходе распределителя 19 появляется импульс, который перебрасывает триггер вершины М, соответствугоший первой вершине заданной группы, в единичное положение. Этот триггер вершины 11 открывает соответствующую ему схему вершины 14 и между входом 16 и выходами 16 этой схемы вершины 14 образуется электрический контакт. Выходы распределителя 19 подключены к единичным входам 13 триггеров вершин 11, соответствующих всем вершинам заданной группы. В такте fz по шине 30 через открытый ключ тактовых сигналов 21 (ключ тактовых сигналов 21 закрыт при наличии сигнала на выходе схемы «И 20) поступает серия из () импульсов на вход -счетчика 22 и на все входы 15 схем вершин 14 {К - ограничение по связности). Первый импульс с шины 30 поступает через вход 15 схемы вершины 14, соответствующей первой верши1не из заданной группы, на выходы 16 только тех схем вершин 14 (через выходы 16 схемы вершины 14, соответствующей первой вершине, и через схемы ребер 8), которые соответст-вуют вершинам заданной группы, расстояние до которых от первой вершины равно единипе. Через схемы «ИЛИ 17 этих вершин импульс поступает на единичные входы 13 триггеров вершин 11, которые перебрасываются в единичное положение и открывают соответствующие их схемы верщин 14. Длительность ИМПУЛЬСОВ, поступающих по шине 30, лолжна быть меньпте времени срабатывания схем вершин 14 (исключая перебра-сывание других триггеров вершин 11, соответствующих вершинам, расстояние до которых от первой бо.льше единипы). ВТОРОЙ импульс, поступивший по тпине 30, перебрасывает в единичное положение триггеры вершин 11, соответствующие вертпинам, расстояние до которых от первой вершины равно двум. Если максимальное расстояние до всех вершин зала-нной группы от первой меныпе или равно К, то ПРИ поступлении /С или менее К импульсов по шине 30, все триггеры вершин П заданной группы вершин перебрасываются в единичное положение, собирается дополнительная схема «И 20 и на ее выходе появляется сигнал, который запрещает прохождение следующих ИМПУЛЬСОВ с шины 30 на входы 15 схем вершнн 14, через линию задержки 23 сбрасывает счетчик 22 в нулевое положение и выдает сигнал на шину 32, сигнализирукущий о том, что расстояние от первой вершины до остальных вершнн заданной группы в ланнолт розыгрыше не превышает величины /С. В эт.ом случае в такте 3 триггеры вершин 11 сбрасывается в ,нулевое положение по и:и1не 33.

В такте t по шине 28 вновь поступает импульс, который (через ключ 18) переводит распределитель 19 в третье положение, и на его втором выходе появляется ИМПУЛЬС, который перебрасывает пополнительный запоминающий триггер, соответствующий ВТОРОЙ верши-не, в едини-чное положение. Начинается аналогичный процесс прове рки для ВТОРОЙ вершины: превышает ли расстояние от нее до остальных вершин заданной группы величину К или нет. Этот пропесс проверки ПРОИСХОДИТ для всех вершин заданной ГРУППЫ. Если расстояние между всеми вершинами заданной группы равно пли меньше К. то распределитель 19 проходит все свои W-Ll) положений (Я - число вершин исследуемой группы1 и при поступлении ()-го импульса по шине 28 и на шине 29 появляется сигнал, по которому испытание считается удачным, т. е. в данном розыгрыше исследуемая группа вершин связана с учетом наложенного ограничения по связности. Если хотя бы между ДВУМЯ верши-нами i и f () расстояние превышает величину /С, то при поступлении т-го импульса на вход ра-спределителя 19 на РГО f-м выходе появляется импульс, КОТОРЫЙ пепебрясывает в единичное положение триггер 11 t-й вершины. Далее по шине 30 в такте f. поступает серия из (/С-4-1) импульса. После постл пления К ИМПУЛЬСОВ по шине 30 в единичное положение перебрасываются все триггеры 11 вершин, расстояние до которых от г-й веппшны меньше или равно К. Так как расстояние до верпшны превыптает величину К. то триггер 11 /-Й верпшпьт находится в нулевом положении, и на выходе дополнительной схемы «И 20 отсутствует сигнал. Далее поступает ( импульс по шине 30, КОТОРЫЙ переводит счетчик 22 в (/«С-ЬО-еположение, f/С4-1)-и ньтхоп счетчика 22 подключен к шине 31. и при переходе счетчика 22 в СК-1-П-е положение нп шине 31 появляется сигнал. Появление сигнала на пгине 31 ГОВОРИТ о том, что в данном розыгрыше расстояние между какими-либо верптинами заданной группы превышает величину К. Испытание считается неудачным, хотя без учетя наложенного ограничения заданная группа вершин связана.

После удачного или неудачного испытания (сигнал на шине 29 илп сигнал на шине 31) прекращается работа по вспомогательным тактам, и устройство переходит к работе по основным тактам Т, Т, и Г.-. Так как работа устройства была прервана после такта Тд, то она продолжается с такта Гь

В такте TI устройство устанавливается в исходное положение. В такте TZ по шинам 24 и 25 поступают результаты розыгрыша состояНИИ вершин и ребер графа. Определяется связность заданной групны вершин в такте Гз по результатам нового розыгрыша и т. д.

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

Пусть было, проведено М испытаний, в результате которых сигнал на шине 27 появлялся Mi раз, а на шине 29 MZ раз (). Отношение MJM характеризует вероятность связности заданной группы вершин без учета наложенного ограничения по связности, а отношение MzIM характеризует вероятность связности этой групны вершин с учетом наложенного ограничения по связности.

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

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

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

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

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

«ИЛИ и шина сброса; причем единичные входы .дополнительных запоминающих триггеров вершин соединены с соответствующими выходами распределителя и с выходами соответствующих схем входы сброса в

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

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

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

21 гц25

2525

2