за счет учета определения размера частей графа. Указанная цель достигается тем, что устройство содержит счетчик св ных вершин, блок дифференцирования ключ, элемент задержки, счетчики частей графа и распределитель, вых ды которого подключены к входам счетчиков частей графа, первый вхо распределителя подключен к шине опроса, второй вход распределителя соединен с выходом счетчика связных вершин, информационные входы которого подключены к выходам ключа, информационные входы которого через блок дифференцирования соединены с нулевыми выходами соответ ствующих триггеров вершин, вход управления ключа подсоединен к первой шине сброса, первые входы соответствующих ключей обеих групп через элемент задержки подключены к выходу генератора импульсов, выход которого соединен со входом управления счетчика связных вершин . Функциональная схема устройства представлена на чертеже. Устройство для исследования вероятностных графов содержит шину 1 запуска генератора импульсов, генератор импульсов 2, шину 3 оконча ния испытания, шины 4 и 4 . устано ки триггеров вершин и ребер в исходное состояние, элементы ИЛИ би, группу последовательно соединенных ключей 7 7ц , группу ключей 8 , ключи 9„, ключи 9 п ребер 10 - 10, триггеры 11.-11| вершин, триггеры 12 ребер, б 13 отображения графа, шины 14 результатов розыгрыша вершин, шины 1 5, результатов розыгрыша ребер, шину 16 отсутствия вершин в р зыгрыше, распределитель 17, счетчик 18 связанных вершин, элемент задержки 19, счетчики 20f,4acтей графа, ключ 21, блок 22 дифференцирования, шину 23 опроса. Устройство работает следующим образом. С помощью блока 13 ключи вершин 9 - 9f и ребер 10 - 10 сое диняются между собой в соответствии с топологией графа. Далее устройство работает по тактам. В такте i сигналы, поступая по шинам 4 и 4, устанавливают триггеры нулевое положение и с помощью ключа 21 отключают входы счетчика 18 от нулевых выходов триггеров 11 т Иц В такте 12 по 14, поступа ют сигналы результатов розыгрыша состояний вершин на входы тригеров 15f поа по шинам ступают сигналы результатов розыгр ша состояний ребер на входы триггеров 12jj Единичное состояни этих триггеров соответствуют налич 4 вершины или ребра в данном розыгрыше. Между выходами ключей вершин 9 и ключей ребер 10,, присутствующими в данном розыгрыше, образуется электрический контакт. Если в данном розыгрьпие нет ни одной вершины, на все входы элемента И 5 через элементы ИЛИ Ь 6| будут поданы сигналы с нулевы : выходов триггеров . Элемент И срабатывает и на шине 3 появится сигнал об отсутствий вершин в данном розыгрьаие. Если в данном розыгрыше присутствует хотя бы одна вершина, то на шине 3 нет сигнала. В такте t по шине 1 поступает сигнал запуска генератора импульсов 2. Сигналы с выхода генератора импульсов поступают на вход счетчика 18 и через элемент задержки 19 на входы ключей 7, 8. При этом счетчик 18 очищается и подготавливается к подсчету связанных вершин. Если первая вершина присутствует в данном розыгрыше, то .единичным выходом триггера 11 открывается ключ 8,-: через который первый импульс с генератора поступает на вход ключа первой вершины и затем через блок отображения х-рафа на все ключи вершин, связанных с первой. Одновременно эти же сигналы поступают на входы сброса соответствующих триггеров. При установке триггеров в нулевое положение с их нулевых выходов через блок 22 и ключ 21 сигналы поступают на вход счетчика 18. Счетчик 18 подсчитывает число связанных вершин и подает сигнал на распределитель 17, который подключает вход соответствующего счетчика 20 - 20 шине 23. В такте 4 поступает сигнал по шине опроса 23, который фиксируется вв 1бранным счетчиком. Если первая вершина отсутствует в розыгрыше, сигнал с генератора поступает через ключ 7 на входы ключей 7- и 8 g и так далее. Таким образом, первый импульс с генератора импульсов 2, проходя И 8 через ключ руживает присутствующую вершину. Триггеры соответствующие этой вершине и вершинам, связанным с ней, перебрасываются в нулевое положение. Число таких триггеров подсчитывается счетчиком 18. На основании этого числа выбирается соответствующий счетчик 20, в котором в такте опроса записывается единица. Второй импульс с генератора импульсов очищает счетчик 18 и обнаруживает присутствующую вершину из оставшихся вершин, триггеры 11 которых находятся в единичном положении. Импульсы с генератора импульсов поступают на ключи 8 до тех пор, пока имеется хотя бы одна вершина, триггер 11 которой находится в единичном положении. После того, как все триггеры 11 fi будут переброшены в нулевое положение, сработает элемент И 5 и подаст по шине 3 сигнал для перехода к новому розыгрышу вершин и ребер. Число частей, на которые распадается исходный граф по результатам данного розыгрыша вершин и ребер / равно сумме импульсов, подсчитанных счетчиками 20) а размеры этих частей соответствуют номерам заполненных счетчиков. Формула изобретения Устройство для моделирования ха рактеристик графа, содержащее блок отображения графа, триггеры вершин единичные выходы которых подключены к первым входам ключей вершин, нул вне выходы триггеров вершин соедине ны с первыми входами элементов ИЛИ выходы которых подключены к соответ ствующим входам элемента И, выход которого соединен с одним входом генератора импульсов, другой вход которого подключен к шине запуска, триггеры ребер, выходы которых соединены со входами ключей ребер, выходы ключей ребер и вершин подключены к соответствующим входам блока отображения графа, группу ключей и группу последовательно соединенных ключей, при этом первые входы соответствующих ключей обеих групп объединены, вторые входы группы последовательно соединенных ключей подключены к нулевым выходам триггеров вершин, вторые входы груп пы ключей соединены с единичными выходами триггеров вершин, выходы группы ключей подключены ко вторим входам ключей вершин, вторым входам элементов ИЛИ и выходам блока отображения графа, единичные входы триггеров вершин и ребер подключены к шинам результата розыгрыша вершин и ребер соответственно, нулевые входы триггеров вершин и ребер соединены с первой и второй шинами сброса соответственно, о т л и - чающееся тем, что, с целью расширения функциональных возможностей за счет учета определения размера частей графа, устройство содержит счетчик связных вершин, блок дифференцирования, ключ, элемент задержки, счетчики частей графа и распределитель, выходы которого подключены к входам счетчиков частей графа, первый вход распределителя подключен к шине опроса, второй вход распределителя соединен с выходом счетчика связных вершин, информационные входы которого подключены к выходам ключа, информационные входы которого через блок дифференцирования соединены с нулевыми выходами соответствующих триггеров вершин, вход управления ключа подсоединен к первой шине сброса, первые входдл соответствующих ключей обеих групп через элемент задержки подключены к выходу генератора импульсов, выход которого соединен со входом управления счетчика связных вершин. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 433504, кл. G06Q7/4.8, 1972. 2.Авторское свидетельство СССР 314214, кл. G06 G 7/48, 1970.
Wf
Jtn
J
