I всесоюзная
3948I3
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
Зависимое от авт. свидетельства №
Заявлено 18.VI.1971 (¹ 1669542118-24) с присоединением заявки №
Приоритет
Опубликовано 22.М11.1973. Бюллетень ¹ 34
Дата опубликования описания 17.XI I.1973
М. 1 л. 6 06g 7/48
Государственный комитет
Совета Министров СССР по делам изобретений и открытий
УДК 681.333.001.57 (088.8) Автор изобре гения
В. В. Е х н
Заявитель
УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ
ГРАФОВ
Изобретение относится к области вычислительной техники и может быть использовано для исследования характеристик вероятностных графов, в частности для определения деления числа пар вершин, связанных между собой.
Известны устройства для исследования вероятностных графов, содержащие кольцевой распределитель, ключи перезаписи, запоминающие триггеры вершин с ключевыми схемами, ключи ребер с управляемыми ключевыми схемами, логические схемы «И», счетчик, распределитель, линию задержки.
Однако с помощью этих устройств невозможно определить число пар вершин, связанных между собой по результатам розыгрыша состояний вершин и ребер графа.
С целью расширения области применения устройства, т. е. пар вершин, связанных между собой по результатам розыграша состояний вершин и ребер графа, в предлагаемом устройстве последний (n — 1)-й поразрядный выход кольцевого распределителя подключен к первым входам ключей перезаписи, ко входу ключевой схемы, последней и-й вершины, ко входу линии задержки и к первому входу схемы «И», остальные разрядные кольцевого распределителя подключены к первым входам соответствующих управляемых ключей и к соответствующим входам ключевых схем вершин, выходы ключей перезаписи подключены к разрядным входам кольцевого распределителя, а выходы управляющих ключей подключены ко гходу счетчика; л-й выход распределителя подключен ко второму входу л-го ключа н ко второму входу схемы «И», остальные выходь1 распределителя подключены ко вторым входам распределителя соответствующих управляющих ключей и ко вторым
10 входам соответствующих ключей перезаписи, вход ключев;é"с,хемы первой вершины подключен ко входу первого ключа, а выход линии задержки подключен ко входу распределителя.
15 На чертеже дана схема предлагаемого устройства.
Устройство содержит кольцевой распределитель 1 с поразрядными входами 2 и п.выходами 8, ключи 4 перезаписи, запоминающие
20 триггеры 5 п-вершин, угравляемые ключевые схемы 6 с одним входом 7 и несколькими выходами В, управляющие ключи 9, счетчик 10, распределитель 11, линию задержки 12, запоминающие триггеры 18 ребер, управляемые
25 ключевые схемы 14 с двумя выходами 15, схему «И» 16, шины 17 выдачи результатов розыгрыша состояний вершин, шины 1В выдачи результатов розыгрыша состояний ребер, шину 19 установки, шину 20 импульсов продви30 жения и шину 21 окончания испытания.
394813
3
Выходы 8 управляемых ключевых схем 6 соединены с выходами !5 управляемых ключевых схем 14 в схему, отображающую граф.
Работа устройства происходит по тактам
II I2 И 13.
В такте l по шине 19 происходит установка устройства в исходное состояние, прп котором запоминающие триггеры вершин 5 и запомицающпс триггеры реоср 13 устанавливают в нулевое положение, а кольцевой распределитель 1 и распределитель 11 устанавливаются в первое поло>кение. Еольцевой распределитель 1 имеет (n. 1) разряд (n — число вершин графа) и ка»<алый разряд имеет вход 2 и вы."<од 3. 1-1а 1-ом выходе 3 кольцевого распределителя I появляется импульс прн переходе кольцевого распрсдслнпгсля 1 из t-го поло>кения в (i+1)-ос поло>кение. Перезапись единицы в кольцевом распределителе 1 происходит в зависимости от того, какой ключ 4 перезаписи открыт в момент перезаписи. В распределителе 11 на его t-ом выходе имеется потенциал при нахо>кдспии распределителя
11 в t-ом поло>кении.
Таким образом в первом поло>кении распределителя 11 на его первом выходе имеется потенциал.
В такте 13 по шинам 17 поступают результаты розыгрыша состояний всршпп графа.
Если данная вершина присутствуег в розыгрыше, то по соответствующей шпнс 17 поступает импульс на вход триггера 5 вершины и перебрасывает его в единичное положение.
Открывается соответствующая ключевая уllравляемая схема 6 и между ес входом 7 и выходом 8 образуется электрический контакт.
Одновременно в такте 12 по шинам 18 поступают результаты розыгрыша состояний рсбер графа. Если данное ребро присутствует в розыгрыше, то по соответствующей шипе 18 импульс поступает па вход триггера 13 рсбра и перебрасывает этот триггер в единичное положение. Открывается соответствующая управляемая ключевая схема 14 II между сс выходами 15 образуется электрический контакт.
Таким образом управляемые ключевыс схемы 6 присутствующих вершин и управляемь|е ключевые схемы 14 присутствующих ребер находятся в открытом ffo;iý>KBBèè. Если две вершины графа связаны и да,гпо:,I розыгрыше, то мс>кду входами 7 управляемых ключевых схем 6, coorвстствующих этим вершинам, имеется электрн ес1<пй контакт.
В такте 13 по шине ?О поступает серия импульсов на продви>кение KoaBBBBof o распрсделителя 1. При поступлении первого импульса по шине 20 кольцевой распределитель
1 переходит из первого поло>кения во второе и на его первом поразрядном выходе 3 появляется импульс, который поступает па вход 7 управляемой ключевой схемы б, соответствующей второй вершине. Если в данный момент распределитель 11 находится в первом положении и открыт первый кл оч 9, то импульс на счетчик 9 поступает только в том
4 случае, если между входом 7 управляемой
1<лючевой схемы б, соответствующей второй вершине, и входом 7 управляемой ключевой схемы б, соответствующей первой вершине, имеется электрический контакт. При поступлении второго импульса по шине 20 кольцевой распределитель 1 переходит пз второго положения в третье и Ifa его втором поразрядном выходе 3 появляется импульс, поступающий на вход счетчика 10 (через вход 7 управляемой ключевой схемы б третьей вершины, вход 7 управляемой ключевой схемы 6 первой вершины и первый ключ 9) только в том случае, если между входом 7 управляемой ключевой схемы б третьей вершины и iIC>KtI> BXOQOM 7 уtlpBB.BBC IOII Kлючевой мы 6 первой вершины имеется электрический контакт.
Далее аналогичным образом импульсы с остальных выходов 3 кольцевого распределителя I поступают на вход счетчика 10, если вершина связана с первой. При поступлении (n — 1) -го импульса по шине 20 кольцевой распределитель 1 переходит из (и — 1) -го поло>кения в следующее, в зависимости от того, какой ключ 4 открыт в данный момент. Так как распределитель 11 находится в первом положении, то открыт ключ 4, подключенный ко второму входу 2 кольцевого распределителя 1. Перезапись сд|шицы происходит во второй разряд кольцевого распределителя 1.
Одновременно импульс с (n — 1)-го выхода 3 кольцевого распределителя 1 поступает через линию задержки 12 на перевод распределителя 11 в следующес положение.
Распределитель 11 через время, определяемос лпнпей задер>кки 12 (достаточное для перезаписи в кольцевом распределителе 1), перево.ц тся во второе положение и открывается ключ 9, управляемый вторым выходом распределителя 11. После (n — 1) импульсов, поступивших по шине 20, кольцевой распределитель 1 и распределитель 11 находятся во втором поло>кении. Счетчик 10 показывает число вершин, связанных с первой вершиной по результатам данного розыгрыша.
Далее при поступ Iåнии следующих (и — 2) импульсов по шине 20 на счетчик 10 импульсы поступают по числу вершин (исключая первую), связан со второй вершиной, так как при поступлении очередных (и — 2) импульсов по шине 20 на каждом (начиная col
BIopolo) выходе 3 кольцевого распределигеля
1 появляются импульсы, поступающие на вход счетчика 10 (через вход 7 управляемой ключевой схемы б, соответствующей i-й вершине, подключенной к выходу 3, вход 7 уп-. равляемой ключевой схемы б, соответствую-, щей второй вершине, и второй ключ 9), если между входом 7 управляемой ключевой схемы 6 1-й ьершицы, на который поступает импульс с выхода 3 и входом 7 управляемой ключевой схемы б, соответствующей второй вершине, имеется электрическая проводимость. Когда кольцевой распределитель 1
394813 (после (n — 1) + (n — 2) импульсов, поступивших по шине 20) пройдет все свои состояния, то появится импульс на его (n — 1)-ом выходе
8 и произойдет перезапись единицы в третий разряд кольцевого распределителя 1, так как в данный момент открыт второй ключ 4 перезаписи. Одновременно импульс с (и — 1) -го выхода 8 кольцевого распределителя 1 поступает через линию задержки 12»а продвижение распределителя 11, последний переводится в третье положение.
При поступлении следующих (n — 3) импульсов по шине 20 на счетчик 10 поступит число импульсов, равное числу вершин, связанных с третьей вершиной, произойдет перезапись единицы в четвертый разряд кольцевого распределителя 1, и распределитель 11 переводится в четвертое положение. Этот процесс происходит до переведения распределителя 11 в (и — 1)-ое положение. Поступающий по шине 20 очередной импульс считывает (и — 1) разряд кольцевого распределителя 1 (так как предыдущим импульсом в кольцевом распределителе 1 перезаписана единица в (и — 1) разряд, поскольку распределитсль 11 находится в момент перезаписи,в (n — 2) положении.
Импульс с выхода 8 (и — 1)-го разряда кольцевого распределителя 1 поступает на вход 7 управляемой ключевой схемы б последней вершины, на вход всех ключей 4 перезаписи и HB вход схемы «И» lб. Если между входами
7 управляемых ключевых схем б, соответствующих последней и предпоследней вершинам, имеется электрический контакт, то на вход счетчика 10 поступает импульс. В противном случае на вход счетчика 10 импульс не поступает. Так как все ключи 4 перезаписи закрыты, то перезапись единицы в кольцевом распределителе 1 не происходит, но появляется импульс на выходе схемы «И» lб, который сигнализирует об окончании испытания.
Общее количество импульсов, поступающих и — 1 по шине 20, определяется величиной;», (n — i).
C=1
Счетчик 10 показывает результат, равный и — 1 (n — i), если граф по результатам розыг1=-1 рыша пмсст и вершин и не разбит па несколько частей. B противном случае показание счетчика 10 равно величине
n — 1
5 Q Q (», (и — i)
1=1 где Q — шсло пар вершин, связанных между собой по результатам розыгрыша состояний
10 вершин и ребер графа.
Предмет изобретения
Устройство для исследования вероятностных графов, содсржащес кольцевой распределитель с (n — 1) выходами, ключи перезаписи, запоминающие триггеры и-вершин, выходы которых подключены к соответствующим ключевым схемам вершин, и управляющп i ключей, счетчик, распределитель с и-выходами, линию задержки, схему «И», запоминающие триггеры ребер, выходы которых подключены к соответствующим кл!очевым схемам ребер, выходы которых соединены с выходами ключевых схем вершин в схему, отображающую граф, отличающееся тем, что, с целью расширения области применения устройства, в нем (и — 1)-й разрядный выход кольцевого
30 распределителя подключен к первым входам ключей перезаписи, ко входу ключевой схсмы п-Й Вершины, 1 .о входу лпппп задержки и K первому входу схемы «И», остальные разрядные выходы кольцевого распределителя подз5 ключены к первым входам соогветствующпх управляемых кл!оче!! и к соответствующим входам ключевых схем вершин, выходы ключей перезаписи подключены к разрядным входам кольцевого распределителя, а выходы
40 управляющих ключей подключены ко входу
c÷åT÷èê3; и-й выход распределителя водки!очен ко второму входу и-го ключа и ко второму входу схемы «И», остальные выходы распределителя подключены ко вторым входам
45 распределителя соответствующих управляющих ключей и ко вторым входам соотвстствующих ключей перезаписи, вход ключсвой схемы первой вершины подключен ко входу первого ключа, а выход линии задержки под50 ключен ко входу распределителя.
Состав ель В. Озеров
Текрсд А. Каиышникова
Редактор Т. Морозова
Корректор Л. Орлова
Типография, пр. Сапунова, 2
Заказ 3316/15 г1.. г, 1939
Е1НИ11ПИ Государственного комигета по делага изобретений и
Москва, )К-35, Раушская
Тир",æ 647 Подписное
Совета Министров СССР открытий иаб., д. 4/5
