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

( 9) 5 6 06 Г 15/ ГОСУДАРСТВЕННЫЙ КОМИТЕ(ПО ИЗОБРЕТЕНИЯМ И С ТКРЫТИПРИ ГКНТ СССР ПИСАНИЕ ИЗОБРЕТЕНИАВТОРСКОМУ СВИДЕТЕЛ ЬСТВУ Ч(56) Авторское свидетельство СССРМ 1485267, кл. 0 06 Р 15/20, 1987.Авторское свидетельство СССРВ 1660015, кл, 6 06 Е 15/20, 1989,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАНА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано дляисследования характеристик эффективности (надежности, живучести и т. д.) систем,структуру которых можно представить графами и сетями, Целью изобретения является расширение функциональныхвозможностей устройства за счет определения вероятности превышения потоком в графе заданного порога, Устроиство содержит блок 1 синхронизации, многоканальный генератор 2 случайных событий, многоканальный блок 3 памяти, блок 4 определения значения минимального разреза, блок 5 сравнения, вход 6 пуска, вход 7 задания вероятности существования вершин графа. вход 8 задания вероятности существования дуг графа, вход 9 задания веса вершин графа, вход 10 задания веса дуг графа, вход 11 задания истоков графа, вход 12 задания стоков графа, вход 13 задания порога и выход 14 признака превышения порога. При поступлении на вход 6 пуска устройства импульса уровня логической "1" блок 1 синхронизации формирует на своих выходах последовательность сигналов, под управлением которой на выходе 14 устройства формируется признак отказа сети. 1 ил10 15 20 25 30 35 40 45 50 55 Изобретение относится к вычислительной технике и может быть использовано для исследования харакгеристик эффективности (надежности, жизучести и т, д.) систем, структуру которых можно представить графами и сетями,Известны устройства для определения характеристик вероятностных графов, содержащие блок синхронизации, многоканальный блок памяти, блок статистической обработки.Недостатком устройства является то, что характеристики графа определяются без учета подграфов, на которые распадается исходный граф, и не определяется состояние отказа системы, структуру которой отображает анализируемый граф,Наиболее близким по технической сущности к изобретению является устройство для решения задач на графах, содержащее блок синхронизации и многоканальный генератор случайных;обытий, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу опроса многоканального генератора случайных событий, входы установки каналов первой и второй групп которого являются входами задания вероятности существования вершин графа устройства и вероятности существования дуг графа соответственно,К недостатку указанного устройства относится отсутствие возможности определения вероятности превышения потоком в графе заданного порога,Цель изобретения - расширение функциональных возможностей устройства за счет определения вероятности превышения потоком в графе заданного порога.Указанная цель достигается тем, что в устройство, содержащее блок синхронизации и многоканальный генератор случайных событий, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу опроса многоканального генератора случайных событий, входы установки каналов первой и второй групп которого являются входами задания вероятности существования вершин графа устройства и вероятности существования дуг графа устройства соответственно, дополнительно введены многоканальный блок памяти, блок определения значения минимального разреза и блок сравнения, причем выход события К-го канала первой группы и выход событий (К, М)-го канала второй группы многоканального генератора случайных событий (К = 1, 2, ., В, где В - количество вершин в графе) подключены к входу опроса К-го канала первой группы и к входу опроса, (К, М)-го канала второй группы соответственно многоканального блока памяти, информационные выходы К-го канала первой группы и (К, М)- го канала второй группы которого подключены к входам задания веса К-й вершины и (К, М)-й дуги соответственно блока определения значения минимального разреза, информационный выход которого подключен к первому информационному входу блока сравнения, второй информационный вход которого является входом задания порога устройства, входы задания веса вершин графа и веса дуг графа которого подключены к входам установки каналов первой и второй групп многоканального блока памяти соответственно, второй выход блока синхронизации подключен к входу опроса блока сравнения, выход признака "больше" которого подключен к выходу признака превышения порога устройства, входы задания истоков графа и стоков графа которого подключены к одноименным входам блока определения значения минимального разреза.Введение дополнительных узлов и связей позволило определять вероятность превышения потоком в графе заданного порога.На чертеже представлена общая функциональная схема устройства.Устройство содержит блок 1 синхронизации (БС), первый выход которого подключен к входу опроса многоканального генератора 2 случайных событий (ГСС), выход событий К-го канала первой группы и выход события (К, М)-го канала второй группы которого соответственно соединены с входом опроса К-го канала первой группы и входом опроса (К, М)-го канала второй группы многоканального блока 3 памяти (БП), информационный выход К-го канала первой группы и информационный выход (К, М)-го канала второй группы которого соответственно соединены с входом задания веса К-й вершины и входом задания веса(К, М)-й дуги блока 4 определения значения минимального разреза (БОЗМР), информационный выход которого соединен с первым информационным входом блока 5 сравнения, вход опроса которого соединен с вторым входом БС 1, вход пуска которого соединен с входом б пуска устройства, вход 7 задания вероятности существования вершин графа и вход 8 задания вероятности существования дуг графа которого соединены соответственно с входом установки каналов первой группы и входом установки каналов второй группы ГСС 2, вход установки каналов первой группы и вход установкиканалов второй группы БП 3 соединены соответственно с входом 9 задания веса вершин графа и входом 10 задания веса дугграфа устройства, вход 11 задания истоковграфа и вход 12 задания стоков графа которого соединены соответственно с входомзадания истоков графа и входом заданиястоков графа БОЗМР 4, вход 13 заданияпорога устройства соединен с вторым информационным входом блока 5 сравнения,выход признака "больше" которого соединен с выходом 14 признака превышенияпорога устройства,Устройство работает следующим образом,Перед началом работы подается необходимая информация на входы устройства 7- 13, которая записывается в соответствующие блоки,На вход б устройства пуска подают импульс управления "Лог, "1", При этом БС 1формирует на своих выходах "1" и "2" последовательность сигналов, предусмотреннуювременной диаграммой его работы. Сигналуправления "Лог;"1" на его первом выходепоступает на вход опроса ГСС 2. При этомГСС 2 формирует на своих выходах наборпотенциалов управления - "Лог, "1" (наличие элемента графа в розыгрыше) и "Лог. "О"(отсутствие элемента графа в розыгрыше).Наличие "Лог. "1" на выходах ГСС 2 разрешает выдачу значения соответствующегоэлемента графа с выходов БП 3 на входызадания веса БОЗМР 4, определяет минимальный разрез (7) и выдает его значение сосвоего информационного выхода на первыйинформационный вход блока сравнения.Через время, достаточное для окончания указанных процессов, БС 1 формируетсигнал "Лог. "1" на своем выходе "2", поступающий на вход опроса блока 5 сравнения.При этом блок 5 сравнения сравнивает информацию, поступившую на его информационные входы.Если значение величины, поступившейна первый информационный вход, большезначения величин, поступившей на второйинформационный вход, то на выходе признака "больше" блока 5 сравнения формируется сигнал "Лог, "1", поступающий навыход 14 признака превышения порога устройства, В противном случае блок 5 сравнения сохраняет уровень "Лог. "0" на выходепризнака "больше". 5 10 15 20 25 30 35 40 45 50 55 На этом работа заканчивается,Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации и многоканальный генератор случайных событий, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый вход которого подключен к входу опроса многоканального генератора случайных событий, входы установки каналов первой и второй групп которого являются входами задания вероятности существования вершин графа устройства и вероятности существования дуг графа устройства соответственно, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения вероятности превышения потоком в графе заданного порога, в него введены многоканальный блок памяти, блок определения значения минимального разреза и блок сравнения, причем выход события К-го канала первой группы и выход события (К. М)-гоканала второй группы многоканального генератора случайных событий (К = 1, 2, В; М = 1, 2, , В, где В - количество вершин в графе) подключены к входу опроса К-го канала первой группы и входу опроса (К, М)-го канала второй группы многоканального блока памяти соответственно, информационные выходы К-го канала первой группы и (К, М)-го канала второй группы которого подключены к входам задания массы К-й вершины и(К, М)-й дуги соответственно блока определения значения минимального разреза, информационный выход которого подключен к первому информационному входу блока сравнения. второй информационный вход которого является входом задания порога устройства. входы задания массы вершин графа и массы дуг графа которого подключены к входам установки каналов первой ивторой групп многоканального блока памяти соответственно, второй выход блока синхронизации подключен к входу опроса блока сравнения. выход признака "больше" которого подключен к выходу признака превышения порога устройства, входы задания истоков графа и стоков графа которого подключены к одноименным входам блока определения значения минимального разреза.