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

(51) 4 С 06 Г 15/20 БРЕТЕНИ ВИДЕТЕЛЬСТ ОРСК ческии СУДАРСТВЕННЫЙ КОМИТЕТ ССС О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ ОПИСАНИ(71) Таганрогский радиотехни институт им. В.Д.Калмыкова (72) В.М.Глушань и И.Н.Сердюков (53) 681.333(088.8)(56) Авторское свидетельство СССР У 468244, кл. С 06 Г 15/20, 1975.Авторское свидетельство СССР У 637822, кл. С 06 Г 15/20, 1978. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ХАРАКТЕРИСТИК ВЕРОЯТНОСТНЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть исполь зовано для построения специализированных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструкторского этапа проектирования радиоэлектронной аппаратуры. Целью изобретения является повышение быстродействия устройства, Устройство содержитгенератор 1 тактовых импульсов, элемент И 2, распределитель 3 импульсов,генератор 4 пуассоновского потока импульсов, счетчик 5, триггер 6, элемент ИЛИ-НЕ 7, триггер 8, элементыИ 9, 10 и 11, элементы ИЛИ 12 и 13,элемент И 14, переключатель 15, вход16, выходы 17 и 18, матрицу ячеекформирования топологии. 1 ил.1 13 О 4 ОИзобретение относится к вычислительной технике и может быть использовано для построения специализированных вычислительных устройств, предназначенных, например, для автоматизированного решения задач конструкторского этапа проектирования радиоэлектронной и электронной вычислительной аппаратуры.Цель изобретения - повышение быстродействия устройства и упрощениеустройства,На чертеже приведена структурнаясхема устройства.Устройство содержит генератортактовых импульсов, элемент И 2, распределитель 3 импульсов, генераторпуассоновского потока импульсов, счет -чик 5, триггер 6, элемент ИЛИ-НЕ 7,триггер 8, элементы И 9, 10 и 11, эле -Оменты ИЛИ 12 и 13, элемент И 14, переключатель 15 установки начальногосостояния, вход 16, выход 17 сигнализации связности графа и выход 18 сигнализации несвязности графа, матрицу25ячеек формирования топологии.Принцип работы устройства состоитв следующем,Связность графа определяется поматрице смежности Б, элементы Бкоторой определяются как1, если вершины Х и Х . смежБ = ны;1О, в противном случае,Г 1 атрица смежности является симметричной относительно главной диагонали, т.е. Б . = Б", . Исходя из этойособенности матрицы смежности, дляисследования связности графа можно ис-Опользовать только ее половину - верхнюю или нижнюю без главной диагонали,Но поскольку для определения связности необходима полная матрица, то недостающие элементы каждой строки треугольной матрицы дополняются определенными элементами соответствующихстолбцов из этой же треугольной матрицы.Использование именно треугольнойматрицы принципиально важно и с точкизрения формирования исходного случайного графа. Это обуславливается тем,что при одновременном заполнении случайным кодом всех элементов каждойстроки невозможно получить симметричную матрицу.После того, как случайный графсформирован, начинается асинхронный 33 2процесс определени связности графа,Этот процесс протекает следующим образом, Те позиции г ервой строки матрицы смежности, в которых стоят единичные элементы, всзбуждают строки,номера которых совпадают с номерамивозбуждающих позиций первой строки,Каждая возбужденная строка возбуждаетсоответствующие новые строки и, есливсе строки окажутся возбужденными(первую строку можно считать автоматически возбужденной, если только первый элемент связан хотя бы с однимдругим), то это свидетельствует освязности графа, В противном случаеграф является несвязным,Перед началом работы на вход 16подается единичный сигнал. Распределитель 3 и триггер 6 устанавливаютсяв исходное сос.тояние, На первом этапе работы устройства формируется исходный случайный граф Это происходитследующим обра.зом. С помощью генератора 4 и счетчика 5 Формируются двоичные коды случайных чисел. Эти кодыс помощью распределителя 3 последовательно заполняют все строки треугольной матрицы ячеек Формирования топологии: при поступлении первого тактового импульса единичный сигнал находится на первом выходе распределителя3, поэтому через открытые элементыИ 9 случайные коды записываются в триггеры 8, При поступлении второго тактового импульса на распределитель 3единичный сигнал переходит на второйего выход, поэтому случайные коды записываются в триггеры 8 второй строкитреугольной матрицы и т,д пока незаполнятся все строки матрицы. Послеэтого очередной тактовый импульс переводит триггер 6 в нулевое состояние. В результате этого открываютсявсе элементы И 10 и 11 и с этого момента начинается второй этап работыустройства, При этом происходит асинхронное распространение сигналов оттриггеров 8 первой строки треугольнойматрицы ко всем последующим,В соответствии с приведенной матрицей смежности распространение сигналов начинается с триггера 8 . Приа ф этом единичный сигнал с укаэанного триггера поступает на вход первого (верхнего) элемента ИЛИ 3 и с его выхода через элементы ИЛИ 12 строки треугольной матрицы открывает все элементы И 11 этой же строки и, кроме то3 130403 го, "стоит" на 1-м входе элемента И 14, Единичные сигналы с выходов триггеров 8 и 8через соответствующие открытые элементы И 11 поступают на входы второго и четвертого элементов ИЛИ 13 и также "стоят" на втором и четвертом входах элемента И 14, С выхода четвертого элемента ИЛИ 13 единичный сигнал поступает на все элементы ИЛИ 12 последнего столбца тре угольной матрицы. При этом открывается элемент И 11 в последней строке и единичный сигнал с выхода триггера 8, через третий элемент ИЛИ 13 пройдет на третий вход элемента И 14, Те перь на всех его входах "стоят" единичные сигналы. Поэтому на его выходе 17 появляется сигнал, указывающий на то, что сформированный случайный граф является связным, Этот сигнал через 20 элемент ИЛИ-НЕ 7 закрывает элемент И 2 и тактовые импульсы не проходят с выхода генератора 1 на вход распределителя 3, т,е. происходит останов работы устройства, Для запуска уст ройства необходимо вновь. нажать кнопку 15.Если же сформированный граф оказывается несвязным, то на выходе 17 единичный сигнал не появляется, а 30 тактовые импульсы, продолжая поступать на распределитель 3, в некоторый момент возбуждают щ-й выход распределителя 3, Это свидетельствует о не- связности графа, Этот же сигнал через 35 элемент ИЛИ-НЕ 7 перекрывает элемент И 2 и также происходит останов работы устройства,мирования топологии исследуемого графа, кроме ячеек первой строки матрицы, выход триггера подключен к первому входу первого элемента И, выходкаждого 1-го элемента И каждой -истроки матрицы ячеек формированиятопологии исследуемого графа подключен к -му входу 1-го (1=1,2п)элемента ИЛИ группы, о т л и ч а ю -щ е е с я тем, что, с целью повыщения быстродействия и упрощения устройства, в него введены генератор пуассоновского потока импульсов, счетчик,распределитель импульсов, триггер останова, второй элемент И, элемент ИЛИНЕ и переключатель, в каждую ячейкуформирования топологии исследуемогографа первой строки матрицы введеныпервый и второй элементы И, а в каждую ячейку матрицы формирования топологии исследуемого графа, кроме ячеекпервой строки, введены второй элементИ и элемент ИЛИ, при этом в каждойячейке формирования топологии первойстроки матрицы выход триггера подключен к первому входу первого элементаИ, а выход второго элемента И этой жеячейки формирования топологии исследуемого графа подключен к входу триггера этой же ячейки матрицы формирования топологии исследуемого графа,в каждой ячейке матрицы формированиятопологии исследуемого графа, кромеячеек первой строки матрицы, выходвторого элемента И подключен к входутриггера, выход элемента ИЛИ подключен к второму входу первого элементаИ, выход генератора пуассоновскогопотока импульсов подключен к счетному входу счетчика, каждый 3-й выходгруппы разрядных выходов которогоподключен к первым входам вторых элементов И всех ячеек 1-го столбца матрицы формирования топологии исследуемого графа, вторые входы вторых элементов И всех ячеек каждой д-й строки матрицы формирования топологииисследуемого графа объединены и подключены к -мч выходу распределителя Устройство для исследования характеристик вероятностных графов, содержащее матрицу ячеек формирования топологии исследуемого графа, каждая 45 ячейка которой. содержит триггер, все ячейки матрицы формирования топологии исследуемого графа, кроме яче ек первой строки матрицы, содержат первый элемент И, кроме этого, устройство содержит генератор тактовых импульсов группу из и элементов ИЛИ (где и - число столбцов в матрице) и выходной элемент И, выход которого является выходом сигнализации связности устройства, выход каждого 1-го элемента ИЛИ группы (1=1, 2 п) подключен к 1-му входу выходного элемента И, в каждой ячейке матрицы форимпульсов, (и+1)-й выход которого подключен к входу установки в "0" триггера останова, (п+2)-й выход распределителя импульсов подключен к первомувходу элемента ИЛИ-НЕ и является выходом сигнализации несвязности графа,Формула изобретения 40 вход задания начальных условий распределителя импульсов объединен с входомустановки в "1" триггера останова и1304033 Составитель Т.СапуноваТехред Б,Кадар КоРРектоР Н.Король Редактор М.Товтин Заказ 1313/50 Тираж б 73 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 подключен к выходу переключателя,вход которого является входом начальной установки устройства, выход первого элемента И подключен к второмувходу элемента ИЛИ"НЕ, выход которого 5подключен к первому входу второго элемента И, второй вход второго элементаИ подключен к выходу генератора так"товых импульсов, выход второго элемента И подключен к тактовому входураспределителя импульсов, инверсныйвыход триггера останова подключен квторым входам йервых элементов И всех ячеек первой строки матрицы формирования топологии исследуемого графа ик третьим входам элементов И всехячеек каждой строки матрицы формирования топологии исследуемого графа,кроме ячеек первой строки матрицы, выход первого элемента И каждой -йячейки 1-го столбца матрицы формирования топологии исследуемого графа,кроме ячеек первой строки, подключенк 1-му входу Ц)-го элемента ИЛИгруппы.