Патент ссср 314214

0ПИСАНИЕ 314214

ИЗОБРЕТЕ Н ИЯ

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

Социалистических

Республик

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

",Ф»

Зависимое от авт. свидетельства №вЂ”

Заявлено 17.04.1970 (№ 1432004/18-24) с присоединейием заявки №

Приоритет—

Опубликовано 07.IX.1971. Бюллетень ¹ 27

Дата опубликования описания 20.ХП.1971.ЧПЬ; G 06 7/48

Комитет по делам изобретений н открытий при Совете Министров

СССР

4 Д 1х 681.333.001.57 (088.81

Авторы изобретения

В. В. Епихин, A. Н. Чаплин и В. И. Ян

Заявитель

УСТРОИСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ

ГРАФОВ

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

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

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

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

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

Это достигается путем поиска присутствующей вершины в данно м розыгрыше, выявле ня связанных с ней вершин, переброса запоминающих триггеров, соответствующих этим вершинам, В IIE"левое положсн1!е и многок1татного повторения этого процесса до тех пор, пока все запоминающие триггеры вершин будут находиться в нулевом положении.

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

Оно содержит шину 1 запуска генератор» импульсов, генератор импульсов 2, шину 8 окончания испытания, шину 1 установки устройства в нсходнос состоя11ис, схему «И» 5, схемы «ИЛИ» 6, счетчик 7, ключи 8 передачи

IO сигнала проверки проводимости. ключи 9 выделения сигнала проверки проводимости, входы вершин 10, шины 11 результатов розыгрыша верштш, шины 12 результатов розыгрыша ребер, шину 18 сигнала отсутствия вершин и

1к данном розыгрыше, запоминающие триггеры

14 вершин, управляемые ключевые схемы вершин, выполненные в виде герконов 15, запоминающие триггеры 16 ребер, управляемые кгночевые схемы ребер 17. Гсрконги управляются запоминающими триггерами И вершин. Управляемыс ключевые схемы 17 входами управления .подключены к выходам триггеров 16, а входамн 18 подсоединены !I

19 контактов I cplxol103 ыгцйдентных

I:м вершин в схему, отображающую граф.

Работа устройсгва происходит по тактам

1„ lg, /з. В такте 1, по шине 4 трнггсры 14 н

16 устанавливаются в нулевос положение, В такте 12 по шннс 11 поступают результаты зо розыгрыша состояний вершин ila входы трнг314214

13

re)IoB 1::1, à по шинам 12 поступают результаты розыгрыша состояний ребер сна входы триггеров 1б. 1 езуль(аты розыгрыша фиксируются запоминающими триггерами 14 и 16, г(ричсм единичное состояние этих триггеров соответствует наличию вершины или ребра в дашкам розыгрыше. Между выходами 19 контактов герконов приоутствующих вершин ооразуется электрический контакт. Соответственно между входами 18 управляемых ключеBbIx схем присутствующих ребер та кже образуется элсктричeсlсий lсоптакт. Eсли в данном розыгрыше нет IIII одной вершины, то на все входы схемы «И» через схемы «ИЛИ» будут ,поданы сигналы с (lóëåBûõ выходов триггеров 14. Схема «И» срабатывает, и на шине 8 будет сигнал оо отсутствии вершин в данном розыгрыше.

При наличии па шине 8 сигнала после такта l дальнейшее испытание прекращается.

Если в данном розыгрыше присутствует хотя бы одна вершина, на выходе шины 8 пет curvала, и в такте !; vо ши>не 1 поступает сигнал запуска генератора импульсов 2. Сигналы проверки проводимости с генератора импульсов поступают;(а вход счетчика 7 и на входы ключей 8 и 9, управляемых соответственно нулевым и единичным вы.содами запоминающего триггера 14, соответствующего первой вершине. Если первая вершина присутствует в данном розыгрыше, то единичным выходом она открывает ключ 9, через который первый импульс с генератора поступает на вход первон вершины, а через пее I(a все вершины, имеющие электрический контакт с первой вершиной. Одновременно сигналы с вершин, образующи.с связацпу!о часть, поступают на сброс триггеров 14, соответствующих этим вершинам. Если первая вершина отсутствует, сигнал с генератора поступает через ключ 8, управляемый пулевым выходом запоминающего триггера первой вершины, на аналогичные ключи, управляемые триггером последующей вершины. Первый импульс с генератора 2, проходя через ключи 8 и 9, оонару>кивает присутствующую вершину. Триггеры 14, соответствующие этой вершине си вершинам, связанным с ней, перебрасываются в нулевое .положение. Второй импульс с генератора обнаруживает присутствующую вершину из оставшихся вершин, триггеры 14 которых на:содятсВ в единичном положении. Импульсы с генератора поступают па ключи 8 и 9 до тех пор, иоки имеется хотя ()bl одна вс))(ill(((!() триггер

14 которой находится в единичном положении. 1хак только Dce триггеры будут переброшены в нулевое положение, на всех входах схемы «И» .появляются сигналы, схема «И» сработает, такт 13 остановит генератор импульсов и по ши !е 3 подаст сигнал съема результата. Число частей, а которые распадается исходный граф по результатам розыгрыша (о верши(и и ребер, равно числу импульсов, поступивших с генератора, которые фиксируются

cчстчиком 7.

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

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

«ИЛИ», схему «И», запоми(ающие триггеры

20 гершин, запоии((а!ощие триггеры реоер, управляемые кл(очевые схемы ребер, которые входами у правления подк:почены к выходам запоминающих триггеров ребер, управляемые

1;л!очевые с.семы вершин, которые в."содамн управления подключены к единичным выходам запоминающих триггеров вершин, а выходамн соединены с выходами управляемых ключевых схем ребер в схему, отображающую граф, отлича!ощееся тем, что, с целью определения числа частей, на которые распадается исходный граф в результате розыгрыша, выход генератора импульсов подключен к входу счетч ика li входа ъ1 кл(оча переда и II клlоч а Bblделения сигснала проверки проводимости первой вершины, выход ка.кдого ключа передачи сигнала предыдуп(ей вершины соединен со входами ключа передачи и ключа выделения сигнала последующей вершины, нулевой выход каждого запоминающего триггера вершины подключен к входу управления соответствующего ключа передачи сигнала и к одному нз входов соответствующей схемы «ИЛИ», а единичный выход подключен к в.соду управления соответствующего к!по lа выделения

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

50 ИЛИ» подкл!очспы к входам схемы «И», а выход схемы «И» соединен с управляющим входом генератора нмпуlbcoB.

314214 ъ

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

Тскред Т. П. Курилко linpp»;;торы Т. А. Гревцова ii

Л. В. Орлова

Редактор M. Аникеева

Заказ 5403 Изд. ¹ !231 Тира)к 500 Подписное

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

Москва, Ж-35, 1 аугискап иаб., д. 1/5

Загорскаи типографии