I всесоюзная

Союз Советских Социалистических РеспубликЗависимое от авт. свидетельстваЗаявлено 18.И,1971 ( 1669542/1 М. 1 л. 6 06 д 7 присоединезгиехриоритетпубликовано 22. аявкиГосударственный комит Совета Министров ССС по делам изобретенийи открытий УД 1 х 681 чЗЗ 0(088.8) 11,1973. Бюллетень3 Дата опубликования описания 17.Х 11.1973 Авторизобре генг. В. Епих и УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНГРАФОВ Изобретение относится к области вычислительной техники и может быть использовано для исследования характеристик вероятностных графов, в частности для определения деления числа пар вершин, связанных между собой.Известны устройства для исследования вероятностных графов, содержащие кольцевой распределитель, ключи перезаписи, запоминающие триггеры вершин с ключевыми схемами, ключи ребер с управляемыми ключевыми схемами, логические схемы И, счетчик, распределитель, линию задержки.Однако с помощью этих устройств невозможно определить число пар вершин, связанных между собой по результатам розыгрыша состояний вершин и ребер графа.С целью расширения области применения устройства, т. е. пар вершин, связанных между собой по результатам розыграша состояний вершин и ребер графа, в предлагаемом устройстве последний (п - 1) -й поразрядный выход кольцевого распределителя подключен к первым входам ключей перезаписи, ко входу ключевой схемы, последней п-й вершины, ко входу линии задержки и к первому входу схемы И, остальные разрядные кольцевого распределителя подключены к первым входам соответствующих управляемых ключей и к соответствующим входам ключевых схем вершин, выходы ключсн перезаписи подклгочены к разрядным входам кольцевого распределителя, а выходы управляющих ключей подключены ко гходу счетчика; и-й выход 5 распределителя подключен ко второму входуи-го ключа н ко второму входу схемы И, остальные выходь 1 распределителя подключены ко вторым входам распределителя соответствующих управляющих ключен и ко вторым О входам соответствующих ключей перезаписи,вход ключевой схемы первой вершины подключен ко входу первого ключа, а выход линии задержки подкгпочен ко входу распределителя.Б На чертеже дана схема предлагаемого устройства.Устройство содержит кольцевой распределитель 1 с поразрядными входами 2 н и выходами 3, ключи 4 перезаписи, запоминающие О триггеры 5 п-вершин, угравляемые ключевыесхемы 6 с одним входом 7 и несколькими выходами В, управляющие ключи 9, счетчик 10, распределитель 11, линию задержки 12, запоминающие триггеры 13 ребер, управляемые 5 ключевые схемы 14 с двумя выходами 15, схем И 16, шины 17 выдачи результатов розыгрыша состояний вершин, шины 18 выдачи результатов розыгрыша состояний ребер, шину 19 установки, шину 20 импульсов продви- О жения и шину 21 окончания испытания.10 15 3Выходы 8 управляемых ключевых схем 6 соединены с выходами 5 управляемых ключевых схем 14 в схему, отображающую граф.Работа устройства происходит по тактам ь 2 И 13.В такте 1 по шине 19 происходит установка устройства в исходное состояние, прп котором запоминающие триггеры вершин 5 и запомипающпс триггеры реоср 13 устанавливают в нулевое положение, а кольцевой распределитель 1 и распределитель 11 устанавливаются в первое положение. 1 ольцевой распределитель 1 имеет (л. - 1) разряд (п - число вершин графя) и каждый разряд имеет вход 2 и выход 3. 1.1 1-ом выходе 3 кольцевого распределителяпоявляется импульс прн переходе кольцевого распределителя 1 из 1-го положения в (К+1)-ос положсние, Перезапись единицы в кольцевом распределителе 1 происходит в зависимости от того, какой ключ 4 перезаписи открыт в момент перезаписи. В распределителе 11 на его -ом выходе имеется потенциал при нахождении распределителя 11 в 1-ом положении.Таким образом в первом положении распределителя 11 на его первом выходе имеется потенциал.В такте 1, по шинам 17 поступают результаты розыгрыша состояний всршпп графа.Если данная вершина присутствуег в розыгрыше, то по соответствующей шпнс 17 поступает импульс на вход триггера 5 вершины и перебрасывает его в едпнишое положение. Открывается соответствующая ключевая управляемая схема 6 и между ес входом 7 и выходом 8 образуется электрический контакт. Одновременно в такте 1 по шинам 18 поступают результаты розыгрыша состояний рсбер графа. Если данное ребро присутствует в розыгрыше, то по соответствующей шипе 8 импульс поступает на вход триггера 13 рсбра и перебрасывает этот триггер в единичное положение. Открывается соответствующая управляемая ключевая схема 14 и между сс выходами 15 образуется электрический контакт.Таким образом управляемые ключевыс схемы 6 присутствующих вершин и управляемые ключевые схемы 14 присутствующих ребер находятся в открытом положении. Если две вершины графа связаны и данном розыгрыше, то между входами 7 управляемых ключевых схем 6, соответствующих этим вершинам, и м естся эл ектр и ескпй конта кт.В такте 1 з по шинеО поступает серия импульсов на продвижение кольцевого распределителя 1. При поступлении первого импульса по шине 20 кольцевой распределитель 1 переходит из первого положения во второе и на его первом поразрядном выходе 3 появляется импульс, который поступает па вход 7 управляемой ключевой схемы б, соответствующей второй вершине. Если в данный момент распределитель 11 находится в первом положении и открыт первый ключ 9, то импульс на счетчик 9 поступает только в том 20 25 30 35 40 45 50 55 60 65 4случае, если между входом 7 управляемой ключевой схемы б, соответствующей второй вершине, и входом 7 управляемой ключевой схемы б, соответствующей первой вершине, имеется электрический контакт. При поступлении второго импульса по шине 20 кольцевой распределитель 1 переходит пз второго положения в третье и па его втором поразрядном выходе 3 появляется импульс, поступающий на вход счетчика 10 (через вход 7 управляемой ключевой схемы б третьей вершины, вход 7 управляемой ключевой схемы 6 первой вершины и первый ключ 9) только в том случае, если между входом 7 управляемой ключевой схемы б третьей вершины и мсжд входом 7 управляемой ключевой схемы 6 первой вершины имеется электрический контакт,Далее аналогичным образом импульсы с остальных выходов 3 кольцевого распределителя 1 поступают на вход счетчика 10, если вершина связана с первой. При поступлении (п - 1)-го импульса по шине 20 кольцевой распределитель 1 переходит из (и - 1)-го положения в следующее, в зависимости от того, какой ключ 4 открыт в данный момент. Так как распределитель 11 находится в первом положении, то открыт ключ 4, подключенный ко второму входу 2 кольцевого распределителя 1. Перезапись единицы происходит во второй разряд кольцевого распределителя 1. Одновременно импульс с г - 1)-го выхода 3 кольцевого распределителя 1 поступает через линию задержки 12 на перевод распределителя 1 в следующес положение,Распределитель 11 через время, определяемос линией задержки 12 (достаточное для перезаписи в кольцсвом распределителе 1), переводится во второе положение и открывается ключ 9, управляемый вторым выходом распределителя 11. После (и - 1) импульсов, поступивших по шине 20, кольцевой распределитель 1 и распределитель 11 находятся во втором положении. Счетчик 10 показывает число вершин, связанных с первой вершиной по результатам данного розыгрыша.Далее при поступлении следующих (л - 2) импульсов по шине 20 на счетчик 10 импульсы поступают по числу вершин (исключая первую), связанных со второй вершиной, так как при поступлении очередных (и - 2) импульсов но шине 20 ня каждом (начиная со 1 второго) выходе 3 кольцевого распределигеля 1 появляются импульсы, поступающие на вход счетчика 10 (через вход 7 управляемой ключевой схемы б, соответствующей К-й вер- шине, подключенной к выходу 3, вход 7 уп- равляемой ключевой схемы б, соответствую-, щей второй вершине, и второй ключ 9), если мскду входом 7 управляемой ключевой схемы 6 К-й ьершины, на который поступает импульс с выхода 3 и входом 7 управляемой ключевой схемы б, соответствующей второй вершине, имеется электрическая проводимость. Когда кольцевой распределитель 1(после (сг - 1) + (сг - 2) импульсов, поступивших по шине 20) пройдет все свои состояния, то появится импульс на его (сг - 1)-ом выходе 3 и произойдет перезапись единицы в третий разряд кольцевого распределителя 1, так как в данный момент открыт второй ключ 4 перезаписи. Одновременно импульс с (и - 1) -го выхода 3 кольцевого распределителя 1 поступает через линию задержки 12 ца продвижение распределителя 11, последний переводится в третье положение,При поступлении следующих (сг - 3) импульсов по шине 20 ца счетчик 10 поступит число импульсов, равное числу вершин, связанных с третьей вершиной, произойдет перезапись единицы в четвертый разряд кольцевого распределителя 1, и распределитель 11 переводится в четвертое положение. Этот процесс происходит до переведения распределителя 11 в (сг - 1)-ое положение. Поступающий по шине 20 очередной импульс считывает (и - 1) разряд кольцевого распределителя 1 (так как предыдущим импульсом в кольцевом распределителе 1 перезаписана единица в (сг - 1) разряд, поскольку распределитсль 11 находится в момент перезаписи,в (а - 2) положении.Импульс с выхода 3 (сг - 1)-го разряда кольцевого распределителя 1 поступает на вход 7 управляемой ключевой схемы б последней вершины, на вход всех ключей 4 перезаписи и на вход схемы И 1 б. Если между входами 7 управляемых ключевых схем б, соответствующих последней и предпоследней вершинам, имеется электрический контакт, то на вход счетчика 10 поступает импульс. В противном случае на вход счетчика 10 импульс не поступает. Так как все ключи 4 перезаписи закрыты, то перезапись единицы в кольцевом распределителе 1 не происходит, но появляется импульс на выходе схемы И 1 б, который сигнализирует об окончании испытания. Общее количество импульсов, поступающихи впо шине 20, определяется величиной;, (и - г),с:г Счетчик 10 показывает результат, равный и - г(п - с), если граф по результатам розыгс=-г рыша пмсст ц вершин и це разбит ца несколько частей. В противном случае показание счетчика 10 равно величине д - 15 Я Я , (и - с)с:г где Я - число пар вершин, связанных между собой по результатам розыгрыша состояний 10 вершин и ребер графа,Предмет изобретения 15 Устройство для исследования вероятностных графов, содсржащес кольцевой распределитель с (сг - 1) выходами, ключи перезаписи, запоминающие триггеры сг-вершин, выходы которых подключены к соответствующим 20 ключевым схемам всршпц, сг управляющихключей, счетчик, распределитель с и-выходами, линию задержки, схему И, запоминающие триггеры ребер, выходы которых подключены к соответствующим ключевым схемам 25 ребер, выходы которых соединены с выходами ключевых схем вершин в схему, отображающую граф, отличающееся тем, что, с целью расширения области применения устройства, в нем (п - 1)-й разрядный выход кольцевого 30 распределителя подключен к первым входамключей перезаписи, ко входу ключевой схемы сг-й вершины, ко входу линии задержки и к первому входу схемы И, остальные разрядные выходы кольцевого распределителя подЗ 5 ключены к первым входам соогветствующпхуправляемых кспочей и к соответствующим вхздахг ключевых схем вершин, выходы ключей перезаписи подключены к разрядным входам кольцевого распределителя, а выходьг 40 управляющих ключей подключены ко входусчетчика; и-й выход распределителя подключен ко второ.гх входм и-го клгоча и ко второму входу схемы И, остальные выходы распределителя подключены ко вторым входам 45 распределителя соответствующих управляющих ключей и ко вторым входам соответствующих ключей перезаписи, вход ключсвой схемы первой вершины подключен ко входу первого ключа, а выход линии задержки под ключен ко входу распределителя,1 тзд Ъ 163)сударствснного компгета по делам изобретений и Москва, )К, Раушская Тпразк 647Совета Министровоткрытийнаб д. 4/5