1
Изобретение относится к области вычислительной техвики и может быть использовано для исследования характеристик вероятностных графов, в частности для определения деления числа пар вершин, связанных между собой.
Известны устройства для исследования вероятностных графов, содержащие кольцевой распределитель, ключи перезаписи, запоминающие триггеры вершин с ключевыми схемами, ключи ребер с управляемыми ключевыми схемами, логические схемы «И, счетчик, распределитель, линию задержки.
Однако с помощью этих устройств невозможно определить число пар вершин, связанных между собой по результатам розыгрыша состояний вершин и ребер графа.
С целью расширения области применения устройства, т. е. пар вершин, связанных между собой по результатам розыграша состояний вершин и ребер графа, в предлагаемом устройстве последний (п-1)-й поразрядный выход кольцевого распределителя подключен к первым входам ключей перезаписи, ко входу ключевой схемы, последней я-й верщппы, ко входу линии задержки и к первому входу схемы «И, остальные разрядные кольцевого распределителя подключены к первым входам соответствующих управляемых ключей и к соответствующим входам ключевых схем
верщин, выходы ключей перезаписи подключены к разрядным входам кольцевого распределителя, а выходы управляющих ключей подключены ко входу счетчика; п-п выход
распределителя подключен ко второму входу п-го ключа и ко второму входу схемы «И, остальные выходы распреде.чителя подключены ко вторым входам распределителя соответствующих управляющих ключей и ко вторым
входам соответствующих ключей перезаписи, вход ключевой схемы первой вершины подключен ко входу первого ключа, а выход линии задержки подключен ко входу распределителя.
На чертеже дана схе.ма предлагаемого устройства.
Устройство содержит кольцевой распределитель / с поразрядными входами 2 и я выходами 3, ключи 4 перезаписи, запоминающие
триггеры 5 я-верщин, управляемые ключевые схемы 6 с одним входом 7 и несколькими выходами 8, управляющие ключи 9, счетчик 10, распределитель 11, линию задержки 12, запоминающие триггеры 13 ребер, управляемые
ключевые схемы 14 с двумя выходами 15, схему «И 16, шины 17 выдачи результатов розыгрыша состояний верщин, шины 18 выдачи результатов розыгрыша состояний ребер, шину 19 установки, шину 20 импульсов продвижения и 21 окончания испытания.
Выходы 8 управляемых ключевых схем 6 соединены с выходами 15 управляемых ключевых схем }4 в схему, отображающую граф.
Работа устройства происходит по тактам ti, tz и /3В такте /i по шине 19 происходит установка устройства в исходное состояние, при котором запоминающие триггеры верщнн 5 и запоминающие триггеры ребер 13 устанавливают в нулевое положение, а кольцевой распределитель 1 и распределитель // устанавливаются в первое положение. Кольцевой распределитель / имеет (л-1) разряд (п-число вершин графа) и каждый разряд нмеет вход 2 и выход о. На (-ом выходе .) кольцевого распрсделителя / появляется импульс нри переходе кольневого раснределнтеля / нз г-го положения в ()0е ноложе 1ие. Перезанись единицы в кольцевом распределнтеле / нроисходнт в зависимости от того, какой ключ 4 нерезаПиси открыт в момент перезаписи. В распределителе // иа его -ом выходе имеется потенциал при нахождении распределителя //в t-OM ноложении.
Таким образом в первом положепин распределителя // на его первом выходе имеется потенциал.
В такте /2 по шинам 17 ноступают результаты розыгрыша состояний вершин графа. Если данная вершина присутствует в розыгрыше, то по соответствующей и.1ине 17 постуиает импульс на вход триггера 5 вершины и перебрасывает его в единичное положение. Открывается соответствующая ключевая управляемая схема 6 и между ее входом 7 и выходом 8 образуется электрический контакт. Одновременно в такте 4 по шииам 18 поступают результаты розыгрыша состояний ребер графа. Если данное ребро нрисутствует в розыгрыше, то но соответствующей щиие 18 импульс поступает на вход триггера 13 ребра и перебрасывает этот триггер в единичное иоложение. Открывается соответствующая управляемая ключевая схема 14 и между ее выходами 15 образуется электрический контакт.
Таким образом управляемые ключевые схемы 6 присутствующих вершин и управляемые ключевые схемы 14 присутствующих ребер находятся в открытом положенин. Если две вершины графа связаны в данном розыгрыше, то между входами 7 управляемых ключевых схем 6, соот; етстБуюи их этим вершинам, имеется электрический контакт.
В такте /з по щние 20 поступает серия имнульсов на продвижение кольцевого распределителя /. При поступлении первого импульса по шине 20 кольцевой распределитель 1 переходит из первого положения во второе и на его первом поразрядном выходе 3 появляется имиульс, который ноступает па вход 7 управляемой ключевой схемы 6, соответствующей второй верщине. Если в данный момент распределитель 11 находится в первом цоложеиии и открыт первый ключ 9, то импульс иа счетчик 9 поступает только в том
случае, если между входом 7 управляемой ключевой схемы 6, соответствующей второй верщине, и входом 7 управляемой ключевой схемы 6, соответствующей первой вершине, имеется электрический контакт. При поступлении второго имнульса по шине 20 кольцевой расиределитель 1 переходит из второго иоложеиия В третье и на его втором иоразрядном выходе 3 ноявляется импульс, поступающий на вход счетчика 10 (через вход 7 управляемой ключевой схемы 6 третьей вершины, вход 7 управляемой ключевой схемы 6 первой вершины и первый ключ 9) только в том случае, если между входом 7 управляеMoii ключевой cxcjMbi 6 третьей вершины и между входом 7 управляемой ключевой схемы 6 первой вершины имеется электрический контакт.
Далее аналогичным образом импульсы с остальных выходов 5 кольцевого раснределителя / ноступают на вход счетчика 10, если вершина связана с нервой. При поступлении (п-1)-го импульса по шине 20 кольцевой распределитель / переходит из (п-1)-го положения в следующее, в зависимости от того, какой ключ 4 открыт в данный момент. Так как расиределитель // иаходится в первом ноложении, то открыт ключ 4, подключенный ко второму входу 2 кольцевого распределителя /. Перезапись едипицы происходит во второй разряд кольцевого распределителя /. Одновременно имнульс с (п-1)-го выхода 3 кольцевого распределителя / -поступает через липию задержки 12 на перевод распределителя //в следующее положение.
Раснределитель // через время, определяемое линией задерж ки 12 (достаточное для иерезаннси в кольцевом распределителе /), переводится во второе положение и открывается ключ 9, управляемый вторым выходом распределителя //. После (я-1) импульсов, поступивших по шиие 20, кольцевой распределитель / и распределитель // находятся во втором положении. Счетчик 10 показывает число вершин, связанных с первой вершиной по результатал данного розыгрыша.
Далее нри поступлении следующих (л-2) нмпульсОВ по шине 20 на счетчик 10 импульсы поступают по числу вершин (исключая первую), связаипых со второй вершиной, так как при постуиленни очередных (п-2) имнульсов по шние 20 на каждом (начиная coi второго) выходе 3 коль 1евого распределителя / появляются импульсы, поступающие иа вход счетчика 10 (через вход 7 управляемой ключевой схемы 6, соответствующей t-й вер-, шиие, подключенной к выходу 3, вход 7 управляемой ключевой схемы 6, соответствую-, ш,ей второй вершине, и второй ключ 9), если между входом 7 управляемой ключевой схемы 6 г-й вершины, на который поступает импульс с Выхода 5 и входом 7 управляемой ключевой схемы 6, соответствующей второй вершине, имеется электрическая проводимость. Когда кольцевой распределитель /
(после (п-l) + (rt-2) импульсов, поступпвших по шине 20) пройдет все свои состояния, то появится импульс на его (п-1)-ом выходе 3 и произойдет перезапись единицы в третий разряд «ольцевого распределителя /, так как в данный момент открыт второй ключ 4 перезаписи. Одновременно импульс с (п-1)-го выхода 3 кольцевого распределителя / поступает через линию задержки 12 на продвижение распределителя 11, последний переводится в третье положение.
При поступлении следующих (п-3) импульсов по шиие 20 на счетчик 10 поступит число импульсов, равное числу вершин, связанных с третьей вершиной, произойдет перезапись едипицы в четвертый разряд кольцевого распределителя 1, и распределитель // переводится в четвертое положение. Этот процесс происходит до иереведения распределителя 11 в (л-1)-ое положение. Поступаюший по шине 20 очередной иМПульс считывает (п-1) разряд кольцевого распределителя / (так как предыдущим импульсом в кольцево.1 распределителе 1 перезаписана единица в (я-1) разряд, поскольку распределитель П находится в момент перезаписи в (га-2) положении.
Импульс с выхода 3 (п-1)-го разряда кольцевого распределителя / поступает па вход 7 управляемой ключевой схемы 6 последней вершины, па вход всех ключей 4 перезаписи и на вход схемы «И 16. Если между входами 7 управляемых ключевых схем 6, соответствующих последней и предпоследней вершинам, имеется электрический контакт, то на вход счетчика 10 поступает импульс. В противном случае на вход счетчика 10 импульс не поступает. Так как все ключи 4 перезаписи закрыты, то перезапись единицы в кольцевом распределителе / не происходит, но появляется импульс на выходе схемы «И 16, который сигнализирует об окончании испытания. Обшее количество импульсов, поступающих
п-1
по шине 20, определяется величиной 2 ( 1
Счетчик 10 показывает результат, равный
п-1
2 (п-г), если граф по результатам розыгрыша имеет п вершин и не разбит па несколько частей. В противном случае показание счетчика 10 равно величине
я-1
Q Q
2(«-0
« i lJ
где Q - число пар вершин, связанных между собой по результатам розыгрыша состояний вершин и ребер графа.
Предмет изобретения
Устройство для исследования вероятностных графов, содержащее кольцевой распределитель с (п-1) выходами, ключи перезаписи, запоминающие триггеры га-вершин, выходы которых подключены к соответствующим ключевым схемам вершин, га управляющих ключей, счетчик, распределитель с /г-выходами, линию задержки, схему «И, запоминающие триггеры ребер, выходы которых подключены к соответствующим клк:)чевым схемам ребер, выходы которых соединены с выходами ключевых схем вершин в схему, отображающую граф, отличающееся тем, что, с целью расщирення области иримепения устройства, в нем («-1)-й разрядный выход кольцевого распределителя подключен к первым входам ключей перезаписи, ко входу ключевой схемы п-й вершины, ко входу линии задержки и к первому входу схемы «И, остальные разрядные выходы кольцевого распределителя подключены к первым входам соответствующих управляемых ключей и к соответствующим входам ключевых схем верщин, выходы ключей перезаписи подключены к разрядным входам кольцевого распределителя, а выходы уиравляющих ключей подключены ко входу счетчика; га-й выход распределптеля подключен ко второму входу п-го ключа и ко второму входу схемы «И, остальные выходы распределителя подключены ко вторым входам распределителя соответствующих управляющих ключей и ко вторым входам соответствующих ключей перезаписи, вход ключевой схемы первой вершины подключен ко входу первого ключа, а выход линии задержки подключен ко входу распределителя.
- I Г i
.JJ.J PJH ...
ТТ
6 /5
