Устройство для операций над графом

,80146234 4 С 06 Р 15/20 ГОСУДАРСТВЕННЫЙ КОМИТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР М ПИСАНИЕ ИЗОБРЕТЕНИЯ ЛЬСТВУ АВТОРСНОМУ С е относится к выч ке и может бьггь исследования над зи, описываемых афами. Устройств(56) Авторское свидетельство СССР У 1256050, кл, С 06 Р 15/20, 1986.Авторское свидетельство СССР У 959090, кл. С 06 Р 15/20, 1981. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД ГРАФОМ(57) Изобретени ис лительной техни и пользовано для ежности сетей свя ве роятностными гр о содержит блок 1 определения смежныхвершин графа, группу элементов ИЛИ 2,группу счетчиков 3, матрицу генераторов 4 случайных событий, группуэлементов ИЛИ 5, входы 6 опроса вершин графа устройства и выходы 7признаков связности вершин графа уст"ройства. Перед началом работы с помощью генераторов 4 случайных событий .задают значения и законы распределения вероятности существованиядуг между вершинами графа. Подаваясигналы на входы 6 опроса устройства, можно определить наличие путиво все вершины графа, а повторяяопросы, - зафиксировать на счетчикка3 вероятности существования путей.1 зепф ф лы 1 иле1462349 с помощью счетчиков 3 определитьвероятность существования пути влюбую вершину графа. Составитель А.Мишин Редактор А.Огар Техред Л. ОлийныкКорректор С.Черни Заказ 15(49 Тираж 667 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101 Изобретение относится к вычислительной технике и может быть использовано для исследования надежности сетей связи, описываемых вероятност" ными графами.Цель изобретения - расширение функциональных возможностей устройства путем определения связных вершин графа.На чертеже представлена функпиональная схема устройства.Устройство содержит блок 1 определения смежных вершин графа, группу из В элементов ИЛИ.2, где В - количество вершин в графе, и группу из В счетчиков 3.Блок 1 определения смежных вершин графа включает матрицу из ВхВ генераторов 4 случайных событий и группу из В элементов ИЛИ 5,Кроме того, иа чертеже обозначены входы 6 опроса устройства и выходы 7 признаков связности вершин графа.Устройство работает следующим образом.Перед началом работы в К-й генератор случайных событий М-й строки матрицы (К = 1 В, М = 1 А) заносят значение и закон распределения вероятности существования дуги из М-й в К-ю вершину графа. После подачи сигнала на один из входов 6 устройства (например, 4-й) происходит опрос генераторов 4 случайных событий 4-й строки матрицы. Если одик (например, Р-й) или несколько генераторов 4 подтвердят наличие пути из М-й в Р-ю вершину графа, будут опрошены генераторы 4 Р"й строки матрицы и т.д. На выходах 7 устройства будет определен состав связных вершин графа. Повторяя опросы, можно 5 Формула изобретения Устройство для операций над графом, содержащее блок определения 10 смежных вершин графа и группу из Вэлементов ИЛИ, где В - количествовершин в графе, о т л и ч а ю щ ее с я тем, что, с целью расширенияфункциональных возможностей устрой ства за счет определения связныхвершин графа, вход опроса М-й вершины устройства (М = 1 В) подключенк первому входу М-го элемента ИЛИгруппы, выход которого подключен к 20 входу опроса М-й вершины блока определения смежных вершин графа, выходпризнака смежности К-й вершины которого (К = 1 В) является выходомпризнака связности К-й вершины гра фа устройства и подключен к второмувходу К-го элемента ИЛИ группы.2, Устройство по и. 1, о т л ич а ю щ е е с я тем, что, с цельюрасширения фцнкциональных возможнос тей устройства за счет обеспечениявозможности выполнения операций надвероятностными графами, блок определения смежных вершин графа содержитматрицу из ВхВ генераторов случайныхсобытий и группу из В элементов ИЛИ,причем вход опроса М-й вершины блокаопределения смежных вершин графаподключен к входам опроса всех генераторов случайных событий матрицы, 40 выход К-го генератора случайных событий М-й строки матрицы подключенк М-му входу К-го элемента ИЛИ группы, выход которого является выходомпризнака смежности К-й вершины бло ка определения смешных вершин графа.