Устройство для исследования характеристик вероятностных графов Советский патент 1987 года по МПК G06F15/173 

113040332

Изобретение относится к вычисли-процесс определения: связности графа, I тельной технике и может быть исполь-Этот процесс протекает следующим об- зовано для построения специализиро-разом. Те поз1щии гервой строки мат- ванных вычислительных устройств, пред-рицы смежности, в которых стоят еди- назначенных, например, для автомати- 5ничные элементы, возбуждают строки, зированного решения задач конструк-номера которых совпадают с номерами торского этапа проектирования радио-возбуждающих позиций первой строки, электронной и электронной вычислитель-Каждая возбужденная строка возбуждает ной аппаратуры.соответствующие строки и, если

Цель изобретения - повьпиение быст- Ювсе строки окажутся возбужденными

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

схема устройства. ДРУГим), то это свидетельствует о

Устройство содержит генератор 1 связности графа, В противном случае

тактовых импульсов, элемент И 2, рас-граф является несвязным, пределитель 3 импульсов, генератор А Перед началом работы на вход 16

пуассоновского потока импульсов, счет -подается единичный сигнал, Распредечик 5, триггер 6, элемент ИЛИ-НЕ 7,литель 3 и триггер 6 устанавливаются

триггер 8, элементы И 9, 10 и 11, эле- Ов исходное состояние. На первом эта менты ИЛИ 12 и 13, элемент И 14, пе-пе работы устройства формируется исреключатель 15 установки начальногоходный случайный граф. Это происходит

состояния, вход 16, выход 17 сигнали-следующим образом. С помощью генеразации связности графа и выход 18 сиг-тора 4 и счетчика 5 формируются двонализации несвязности графа, матрицуичные коды случайных чисел. Эти коды

ячеек формирования топологии.с помощью распределителя 3 последоваПринцип работы устройства состоиттельно заполняют вс;е строки треугольв следующем, ,ной матрицы ячеек формирования топоСвязность графа определяется пологии: при поступлс;нии первого тактоматрице смежности S, элементы S-j ко- - вого импульса единичный сигнал,нахоторой определяются какдится на первом выходе распределителя

3, поэтому через открытые элементы

- р, если вершины X , и X . смеж- 9 случайные коды записываются в триг iJ I геры 8, При поступлении второго такЮ, в противном случае. импульса на распределитель 3

Матрица смежности является симмет-единичный сигнал переходит на второй

ричной относительно главной диагона- поэтому случайные коды зали, т.е. S .-у - S- , Исходя из этойписываются в тригг(гры 8 второй строки

особенности матрицы смежности, длятреугольной матриш.1 и т.д., пока не

исследования связности графа можно ис-4озаполнятся все строки матрицы. После

пользовать только ее половину - верх-этого очередной тактовьй импульс пенюю или нижнюю без главной диагонали.реводит триггер 6 Б нулевое состояКо поскольку для определения связное- j g g результате этого открываются

ти необходима полная матрица, то элементы И 10 и 11 и с этого мо достающие элементы каждой строки тре- мента начинается второй этап работы

угольной матрицы дополняются опреде-устройства. При этом происходит асинленными элементами соответствующиххронное распространение сигналов от

столбцов из этой же треугольной мат-триггеров 8 первой строки треугольной

рицы.матрицы ко всем последующим.

Использование именно треугольной д

матрицы принципиально важно и с точки В соответствии с приведенной мат- зрения формирования исходного случай-рицей смежности распространение сиг- ного графа. Это обуславливается тем,налов начинается с триггера 8, При что при одновременном заполнении слу-этом единичный сигнал с указанного чайным кодом всех элементов каждой триггера поступает на вход первого строки невозможно получить симметрич-(верхнего) элемента ИЛИ 13 и с его ную матрицу,выхода через элементы ИЛИ 12 строки

После того, как случайный графтреугольной матрищ. открывает все элесформирован, начинается асинхронныйменты И 1J этой же строки и, кроме того, стоит на 1-м входе элемента Н 14. Единичные сигналы с выходов триггеров Sjj и 8 через соответствующие открытые элементы И 11 поступают на входы второго и четвертого элементов ИЛИ 13 и также стоят на втором и четвертом входах элемента И 14. С выхода четвертого элемента ИЛИ 13 единичный сигнал поступает на все элементы ИЛИ 12 последнего столбца тре- угольной матрицы. При этом открывается элемент И 11 в последней строке и единичный сигнал с выхода триггера через третий элемент ИЛИ 13 пройдет на третий вход элемента И 14. Теперь на всех его входах стоят единичные сигналы. Поэтому на его выходе 17 появляется сигнал, указывающий на то, что сформированный случайньш граф

является связным. Этот сигнал через элемент ИЛИ-НЕ 7 закрывает элемент И 2 и тактовые импульсы не проходят с выхода генератора 1 на вход распределителя 3, т.е. происходит останов

работы устройства. Для запуска уст- 25 строки матрицы выход триггера подклю- ройства необходимо вновь, нажать кнопку 15.

Если же сформированный граф оказывается несвязным, то на выходе 17 единичный сигнал не появляется, а 30 тактовые импульсы, продолжая поступать на распределитель 3, в некоторый момент возбуждают тп-й выход распределителя 3. Это свидетельствует о нечен к первому входу первого элемента И, а выход второго элемента И этой же ячейки формирования топологии исследуемого графа подключен к входу триггера этой же ячейки матрицы формирования топологии исследуемого графа, в каждой ячейке матрицы формирования топологии исследуемого графа, кроме ячеек первой строки матрицы, выход

связности графа. Этот же сигнал через 35 второго элемента И подключен к входу

элемент ИЛИ-НЕ 7 перекрывает элемент И 2 и также происходит останов работы устройства.

о р м у л а

изобретения 40

45

Устройство для исследования характеристик вероятностных графов, содержащее матрицу ячеек формирования топологии исследуемого графа, каждая ячейка которой содержит триггер, все ячейки матрицы формирования топологии исследуемого графа, кроме яче ек первой строки матрицы, содержат первый элемент И, кроме этого, устройство содержит генератор тактовых импульсов группу из п элементов ИЛИ (где п - число столбцов в матрице) и выходной элемент И, выход которого является выходом сигнализации связности устройства, выход каждого j-ro элемента ИЛИ группы (, 2,..., п) подключен к j-му входу выходного элемента И, в каждой ячейке матрицы фор5

0

мирования топологии исследуемого графа, кроме ячеек первой строки матрицы, выход триггера подключен к первому входу первого элемента И, выход каждого элемента И каждой i-й строки матрицы ячеек формирования топологии исследуемого графа подключен к i-му входу j-ro (j,2,...,п) элемента ИЛИ группы, отличающееся тем, что, с целью повьпие- ния быстродействия и упрощения устройства, в него введены генератор пуас- соновского потока импульсов, счетчик, распределитель импульсов, триггер останова, второй элемент И, элемент ИЛИ- НЕ и переключатель, в каждую ячейку формирования топологии исследуемого графа первой строки матрицы введены Г1ервый и второй элементы И, а в каждую ячейку матрицы формирования топологии исследуемого графа, кроме ячеек первой строки, введены второй элемент И и элемент liJlIi, при этом в каждой ячейке формирования топологии первой

строки матрицы выход триггера подклю-

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

0

триггера, выход элемента ИЛИ подключен к второму входу первого элемента И, выход генератора пуассоновского потока импульсов подключен к счетному входу счетчика, каждый j-й выход группы разрядных выходов которого подключен к первым входам вторых элементов И всех ячеек j-ro столбца матрицы формирования топологии исследуе-- 5 мого графа, вторые входы вторых элементов И всех ячеек каждой i-й строки матрицы формирования топологии исследуемого графа объединены и подключены к i-му выходу распределителя

импульсов, (п+1)-й выход которого под- I

ключен к входу установки в О триггера останова, (п+2)-й выход распределителя импульсов подключен к первому входу элемента ИЛИ-НЕ и является выходом сигнализации несвязности графа, вход задания начальных условий распределителя импульсов объединен с входом установки в I триггера останова и

0

5

513040336

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

ной установки устройства, выход пер-к третьим входам элементов И всех

вого элемента И подключен к второмуячеек каждой строки матрицы формировхОду элемента ИЛИ-НЕ, выход которого 5вания топологии исследуемого графа,

подключен к первому входу второго эле-кроме ячеек первой строки матрицы, вымента И, второй вход второго элементаход первого элемента И каждой i-й

И подключен к выходу генератора так-ячейки j-ro столбца матрицы формиротовых импульсов, выход второго эле-вания топологии исапедуемого графа,

мента И подключен к тактовому входу 0кроме ячеек первой строки, подключен

распределителя импульсов, инверсныйк j-му входу (j-l)-ro элемента ИЛИ

выход триггера останова подключен кгруппы, вторым входам первых элементов И всех

Изобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств,предназначенных, например, для автоматизированного решения задач конструк - торского этапа проектирования радиоэлектронной аппаратуры. Целью изобретения является повьшение быстродействия устройства. Устройство содержит генератор 1 тактовых импульсов, элемент И 2, распределитель 3 импульсов, генератор 4 пуассоновского потока импульсов, счетчик 5, триггер 6, элемент ИЛИ-НЕ 7, триггер 8, элементы И 9, 10 и 11, элементы ИЛИ 12 и 13, элемент И 14, переключатель 15, вход 16, выходы 17 и 18, матрицу ячеек формирования топологии. 1 ил. с