Устройство для исследования характеристик вероятностных графов

 

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

СОЮЗ СОВЕТСНИХ

СО1.1ИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3934437/24-24 (22) 25.07.85 (46) 15.04.87. Бюл. N - 14 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань и И.Н.Сердюков (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 468244, кл. G 06 F 15/20, 1975.

Авторское свидетельство СССР

N - 637822, кл. G 06 F 15/20, 1978. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ХАРАКТЕРИСТИК ВЕРОЯТНОСТНЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть исполь. зовано для построения специализиро„„SU, 13040 3 А 1 ванных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструк торского этапа проектирования радиоэлектронной аппаратуры. Целью изобретения является повышение быстродействия устройства. Устройство содержит генератор 1 тактовых импульсов, элемент И 2, распределитель 3 импульсов, генератор 4 пуассоновского потока импульсов, счетчик 5, триггер 6, элемент ИЛИ-НЕ 7, триггер 8, элементы

И 9, 10 и 11, элементы ИЛИ 12 и 13, элемент И 14, переключатель 15, вход

16 выходы 17 и 18, матрицу ячеек формирования топологии. 1 ил.

1 !3О4О

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

Цель изобретения — повышение быст- !О родействия устройства и упрощение устройства.

На чертеже приведена структурная схема устройства.

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

25 ячеек формирования топологии.

Принцип работы устройства состоит в следующем.

Связность графа определяется по матрице смежности S элементы S;; ко- 3О торой определяются как (1 если вершины Х и Х, смежБ;; = ны;

О, в противном случае, Матрица смежности является симметричной относительно главной диагонаJIH T ° e ° S S „. Исходя из э той особенности матрицы смежности, для исследования связности графа можно ис- О пользовать только ее половину — верхнюю или нижнюю без главной диагонали.

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

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

После того, как случайный граф сформирован, начинается асинхронный

33 2 процесс определеник связности графа, Этот процесс протекает следующим образом, Те позиции г ервой строки матрицы смежности, в которых стоят единичные элементы, всзбуждают строки, номера которых совг..адают с номерами возбуждающих позиций первой строки.

Каждая возбужденная строка возбуждает соответствующие новые строки и, если все строки окажутся возбужденными (первую строку можно считать автоматически возбужденной, если только пер— вый элемент связан хотя бы с одним другим), то это свидетельствует о связности графа ° В противном случае граф является несвязным.

Перед началом работы на вход 16 подается единичный сигнал. Распределитель 3 и триггер 6 устанавливаются в исходное сос,тояние. На первом этапе работы устройства формируется исходный случайный граф, Это происходит следующим обра.зом. С помощью генератора 4 и счетчика 5 формируются двоичные коды случайных чисел. Эти коды с помощью распределителя 3 последовательно заполняют все строки треугольной матрицы ячеек формирования топологии: при поступлении первого тактового импульса единичный сигнал.находится на первом выходе распределителя

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

И 9 случайные коды записываются в триггеры 8, При поступлении второго тактового импульса на распределитель 3 единичный сигнал переходит на второй его выход, поэтому случайные коды записываются в триггеры 8 второй строки треугольной матрицы и т.д,, пока не заполнятся все строки матрицы. После этого очередной тактовый импульс переводит триггер 6 в нулевое состояние. В результате этого открываются все элементы И 10 и 11 и с этого мо мента начинается второй этап работы устройства, При этом происходит асинхронное распространение сигналов от триггеров 8 первой строки треугольной матрицы ко всем последующим, В соответствии с приведенной матрицей смежности распространение сигналов начинается с триггера 8 . При

l2 этом единичный сигнал с укаэанного триггера поступает на вход первого (верхнего) элемента ИЛИ !3 и с его. выхода через элементы ИЛИ 12 строки треугольной матрицы открывает все элементы И 11 этой же строки и, кроме то3 130403

ro "стоит" на 1-м входе элемента И

14. Единичные сигналы с выходов триггеров 8 и 8 через соответствующие открытые элементы И 11 поступают на входы второго и четвертого элементов

ИЛИ 13 и также "стоят" на втором и четвертом входах элемента И 14. С выхода четвертого элемента ИЛИ 13 единичный сигнал поступает на все элементы ИЛИ 12 последнего столбца тре- 10 угольной матрицы. При этом открывается элемент И 11 в последней строке и единичный сигнал с выхода триггера

8, через третий элемент ИЛИ 13 пройдет на третий вход элемента И 14, Те- 15 перь на всех его входах "стоят" единичные сигналы. Поэтому на его выходе

17 появляется сигнал, указывающий на то, что сформированный случайный граф является связным, Этот сигнал через 20 элемент ИЛИ-НЕ 7 закрывает элемент

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

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

И 2 и также происходит останов работы устройства, мирования топологии исследуемого графа, кроме ячеек первой строки MdTpH цы, выход триггера подключен к первому входу первого элемента И, выход каждого )-го элемента И каждой 1-и строки матрицы ячеек формирования топологии исследуемого графа подключен к i-ìó входу j ãî (j=1,2,...,n) элемента ИЛИ группы, о т л и ч а ю— щ е е с я тем, что, с целью повыщения быстродействия и упрощения устройства, в него введены генератор пуассоновского потока импульсов, счетчик, распределитель импульсов, триггер останова, второй элемент И, элемент ИЛИНЕ и переключатель, в каждую ячейку формирования топологии исследуемого графа первой строки матрицы введены первый и второй элементы И, а в каждую ячейку матрицы формирования топологии исследуемого графа, кроме ячеек первой строки, введены второй элемент

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

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

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

Устройство для исследования характеристик вероятностных графов, содержащее матрицу ячеек формирования топологии исследуемого графа, каждая 45 ячейка которой. содержит триггер, все ячейки матрицы формирования топологии исследуемого графа, кроме яче ек первой строки матрицы, содержат первый элемент И, кроме этого, устройство содержит генератор тактовых импульсов группу из и элементов ИЛИ (где n — число столбцов в матрице) и .выходной элемент И, выход которого является выходом сигнализации связности устройства, выход каждого j-го элемента ИЛИ группы (j=l, 2,..., п) подключен к j ìó входу выходного элемента И, в каждой ячейке матрицы форимпульсов, (п+1)-й выход которого подI ключен к входу установки в "0" триггера останова, (п+2)-й выход распределителя импульсов подключен к первому входу элемента ИЛИ-HE и является выходом сигнализации несвязности графа, Формула изобретения 40 вход задания начальных условий распределителя импульсов объединен с входом установки в "1" триггера останова и

1304033

Составитель Т. Сапунова

Техред В.Кадар Корр тор Н.Король

Редактор М.Товтин

Заказ 1313/50 Тираж б73 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб,, д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 подключен к выходу переключателя, вход которого является входом начальной установки устройства, выход первого элемента И подключен к второму входу элемента ИЛИ"НЕ, выход которого 5 подключен к первому входу второго элемента И, второй вход второго элемента

И подключен к выходу генератора тактовых импульсов, выход второго элемента И подключен к тактовому входу распределителя импульсов, инверсный выход триггера останова подключен к вторым входам йервых элементов И всех ячеек первой строки матрицы формирования топологии исследуемого графа и к третьим входам элементов И всех ячеек каждой строки матрицы формирования топологии исследуемого графа, кроме ячеек первой строки матрицы, выход первого элемента И каждой i-й ячейки j-го столбца матрицы формирования топологии исследуемого графа, кроме ячеек первой строки, подключен к j-му входу (j-1)-:t.o элемента ИЛИ группы.