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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 01348 06 Г 15/20 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ИСАНИЕ ИЗОБРЕТЕНИ К А ВТОРСКОМУ СВИДЕТЕЛЬСТВ водят Во вт зь Копт ССР82,Р идетельство 6 Р 15/20, 1 етельство СС 6 Р 15/36, 1(54) УСТРОЙС ВЕРОЯТНОСТНЫ (57) Изобрет лительной те ВО ДЛЯ ИССЛЕДОВА ГРАФОВ ычисисполь ние относится к нике, может быт следования сетеиостными графамить веса подграфодну управляющуюшины, Устройством. В первом такт тобр позв эовано для и жения вероят име ляет определщих хотя бы полонительную ве тает по такт произ(21) (22) (46) (72) и ВГ (53) (56) У 896Ав У 656 018737/24-247.02,860.10.87, Бюл. Мф 4,М, Овчинников, ЮПетриенко81,333(088.8)вторское св30, кл, С 0орское свид73, кл, С 0 начальную установку устроистваром такте задают результатыша исполнительных и управляющих вершин, ребер и дуг графа. Кромеэтого, во втором такте проверяетсяналичие исполнительных и управляющих вершин, Если по результатамрозыгрыша исполнительные или управляющие вершины отсутствуют, работаустройства прекращается в данном такте, В третьем такте находят первуюуправляющую вершину и определяютвес подграфа, которому она принадлежит, В четвертом такте опрашиваютустройство, при этом на соответствующий выход веса подграфа устройствавыдается значение веса, Далее работаустройства продолжается чередованием третьего и четвертого тактов дополного перебора всех управляющихвершин графа, 1 ил, 134884640 45 50 55 Изобретение относится к вычислительной технике и может быть использовано для исследования сетей, отображаемых вероятностными графами,Целью изобретения является расширение функциональных воэможностей устройства за счет определения веса исполнения вершин в подграфах, имеющих хотя бы одну управляющую и одну исполнительную вершиныНа чертеже изображена функциональная схема предлагаемого устройства,Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, выход 3 признака окончания работы устройства, установочный вход 4 устройства, первый 5 и второй 6 элементы ИЛИ, первую 7, вторую 8, третью 9, четвертую 10, пятую 11, шестую 12 группы ключей, коммутационное поле 13, первую 14, вторую 15, третью 16, четвертую 17 группы триггеров, второй 18, третий 19 и первый 20 элементы И, сумматор 2 1, седьмую группу 22 ключей, группу 23 элементов И, распределитель 24 импульсов, выходы 25 веса подграфа, выходы 26 управляющих вершин устройства, выходы 27 исполнительных вершин уст 1 ойства, выходы 28-30 признаков отсутствия управляющих верщин, исполнительныхвершин, ребер и дуг графа, вход 31 опроса устройства, вхбды 32 задания управляющих и исполнительных вершин, ребер и дуг графа, элемент 33 задержки, блок 34 памяти, Как вариант показано исполнение первого ключа 9 в виде реле, обмотка которого соединена с шиной нуленого потенциала и прямым выходом первого триггера 14, разделительного диода и контактов реле.Устройство работает следующим образом.Перед началом работы в блок 34заносят веса исполнительных вершинпри помощи наборного поля вершины,ребра и дуги графа соединяют согласно его топологии,Устройство работает по тактам.В первом такте на первые входы установки в "0" триггеров 14-17 с входа4 поступает единичный потенциал иобнуляет их, В третьем такте на входы 32 поступают результаты розыгрыша элементов графа, причем присутствующие в розыгрыше. элементы графа воспроизводятся единичными состоя 5 10 15 20 25 30 35 ниями соответствующих триггерн,которые единичными сигналами со своих прямых выходов замыкают одноименные ключи 9-12. Информационному входу ключа 12 соответствует началодуги,Если в розыгрыше нет управляющихили исполнительных вершин, ребер идуг, то единичные потенциалы с инверсных выходов соответствующихтриггеров проходят через элементы18 (19,20) И и элемент 5 ИЛИ на выход 3 окончания испытания. В противном случае в третьем такте сигналпо входу 1 запускает генератор 2,первый импульс которого обнуляетсумматор 21, а через элемент 33 задержки проходит на информационныевходы первых ключей 7 и 8. Пусть в1розыгрыше присутствует первая управляющая вершина, тогда первый триггер 14 находится в единичном состоянии, первый ключ 7 закрыт нулевымпотенциалом на его управляющем входе,а первый ключ 8 открыт единичнымпотенциалом с прямого выхода первого триггера 14. Импульс, поступивна информационный вход первого ключа7, проходит через контакты наборного поля и все вершины и ребра первого подграфа в результате срабатывания ключей 9-12, соответствующихприсутствующим в розыгрыше элементамподграфа, связанным с первой управляющей вершиной. При этом импульсыс выходов соответствующих ключей поступают на вторые входы установки в "0" соответствующих триггеров 14- 17 и устанавливают их в нулевое состояние, Если в данном подграфе не было ни одной исполнительной вершины, то из блока 34 не будет считан ни один код веса. Если же есть одна или несколько исполнительных вершин, связанных хотя бы с первой управляющей вершиной, то при установке соответствующих триггеров 16 в нулевое состояние единичный сигнал, проходя через элементы ИЛИ 6, откроет элементы И 23, указывающие на присутствие в первом подграфе управляющих вершины. При этом из блока 34 будет считан код веса исполнительных вершин, имеющих н первом подграфе связь хотя бы с одной управляющей вершиной, Единичные потенциалы на соответствующих выходах 27 указывают на наличие исполнительных вершин, связанных впервом подграфе хотя бы с одной управляющей вершиной,В четвертом такте с входа 31 натактовый вход распределителя 24 поступает сигнал опроса, по которомураспределитель 24 выдает сигнал насвоей первый выход при этом открывается первый ключ 22, с выхода которого вес первого подграфа поступаетна первый выход 25Второй импульс генератора 2 обнуляет сумматор 21 и проходит черезвсе открытые ключи 7 до первого открытого ключа 8, соответствующегоочередной присутствующей в данномрозыгрыше управляющей вершине. Аналогично определяются характеристикивторого подграфа в данном розыгрыше,После того, как в единичном состоянии не останется ни одного триггера14-16, или 15, останавливается генератор 2, обнуляется распределитель24 и появляется сигнал на выходе 3,Устройство готово к следующемурозыгрышу,10 15 20 Формула изобретения 30 Устройство для исследования вероятностных графов, содержащее две группы триггеров, элемент задержки, коммутационное поле, четыре группы ключей, генератор импульсов и распре35 делитель импульсов, тактовый вход которого является входом опроса устройства, вход пуска устройства подключен к входу пуска генератора импульсов выход которого подключен к вхо 4 С ду элемента задержки, выход которого подключен к информационным входам первых ключей первой и второй групп, информационный выход К-го ключа второй группы (К=1 А, где А - ко личество управляющих вершин в графе) подключен к информационному входу К-го ключа третьей группы, выход которого подключен к К-й группе контактов первого массива наборного поля и к входу установки в "0" К-го триггера первой группы, прямой выход которого подключен к управляющим входам К-х ключей второй и третьей групп, вход задания К-й управляющей вершины устройства подключен к входу установки в "1" К-го триггера первой группы, инверсный выход которого подключен к управляющему входу К-го ключа первой группы (КФА), информационный выход которого подключен к информационному входу (К+1)-го ключа второй группы и к информационному входу (К+1).-го ключа первой группы (КА, А), вход задания М-го ребра устройства (М, , В, где В - количество ребер в графе) подключен к входу установки в "1" М-го триггера второй группы, прямой выход которого подключен к управляющему входу М-го ключа четвертой группы, исполнительная цепь которого подключена к М-й паре контактов второго массива наборного поля, контакты наборного поля соединены согласно топологии графа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения массы исполнительных вершин в подграфах, имеющих хотя бы одну управляющую и одну исполнительную вершины, в него введены третья и четвертая группы триггеров, пятая, шестая и седьмая группы ключей, группа элементов И, два элемента ИЛИ, три элемента И, блок памяти и сумматор, причем инверсный выход К-го триггера первой группы подключен к первому входу К-го элемента И группы и к К-му входу первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ и является выходом признака отсутствия управляющих вершин устройства, вход задания Р-й исполнительной вершины графа (Р=1.С, где С - количество исполнительных вершин в графе) подключен к входу установки в " 1" Р-го триггера третьей группы, прямой выход которого подключен к управляющему входу Р-го ключа пятой группы, исполнительная цепь которого подключена к Р-й группе контактов третьего массива наборного поля и к входу установки в О" Р-го триггера третьей группы, инверсный выход которого подключен к Р-му входу считывания блока памяти, к Р-му входу второго элемента ИЛИ, к Р-му выходу исполнительных вершин устройства и к Р-му входу второго элемента И, выход которого подключен к второму входу первого элемента И и является выходом признака отсутствия исполнительных вершин устройства, выход второго элемента ИЛИ подключен к вторым входам всех элементов И группы, вы1348846 10 15 ВНИИПИ Заказ 4803/49 Тираж 670 Подписное Произв.-полигр. пр-тие, г. Ужгород, ул, Проектная, 4 ход К-го элемента И группы являетсяК-м выходом управляющих вершин устройства, вход задания Н-й дуги устройства (Н=1 0, где 0 - количество дуг в графе) подключен к входу установки в "1" Н-го триггерачетвертой группы, прямой выход которого подключен к управляюшему входуН-го ключа шестой группы, исполнительная цепь которого подключена кН-й паре контактов четвертого массива наборного поля, инверсный выходМ-го триггера второй группы подключен к М-му входу третьего элементаИ, инверсный выход Н-го триггерачетвертой группы подключен к (В+Н)-мувходу третьего элемента И, выход которого является выходом признакаотсутствия ребер и дуг ус.тройства иподключен к третьему входу первогоэлемента ИЛИ, выход которого является выходом признака окончания работы устройства и подключен к входуостанова генератора импульсов, выходкоторого подключен к. входу установкив 0" сумматора, вход Р-го слагаемого которого подключен к Р-му выходублока памяти, а выход подключен кинформационным входам всех ключейседьмой группы, Р-й выход распределителя импульсов подключен к управляющему входу Р-го ключа седьмойгруппы, выход которого является выходом массы Р-го подграфа устройства,