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

 

Изобретение относится к вычислительной технике и может быть исг пользовано для исследования надежности сетей связи, описываемых вероятностньгми графами. Устройство содержит блок 1 определения смежных вершин графа, группу элементов ИЛИ 2, группу счетчиков 3, матрицу генераторов 4 случайных событий, группу элементов ИЛИ 5, входы 6 опроса вершин графа устройства и выходы 7 признаков связности вершин графа устройства . Перед началом работы с помощью генераторов 4 случайных событий задают значения и законы распределения вероятности существования дуг между вершинами графа. Подавая сигналы на входы 6 опроса устройства , можно определить наличие пути во все вершины графа, а повторяя ) ,опросы, - зафиксировать на счетчика 3 вероятности существования путей. 1 з.По ф-лы, 1 ил. О)

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (50 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4271988/24-24 (22) 13.04.87 (46) 28.02.89. Бюл. 8 (72) О.Г Алексеев, С.А.Васильковский, А,А.Гончар, Е.H.Полевов и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 1256050, кл, G 06 F 15/20, 1986.

Авторское свидетельство СССР

Р 959090, кл. G 06 F 15/20, 1981. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

ГРАФОМ (57) Изобретение относится к вычислительной технике и может бьггь ис пользовано для исследования надежности сетей связи, описываемых вероятностными графами. Устройство

„„SU„„1462349 А1 содержит блок 1 определения смежных вершин графа, группу элементов ИЛИ 2, группу счетчиков 3, матрицу генераторов 4 случайных событий, группу элементов ИЛИ 5, входы 6 опроса вершин графа устройства и выходы 7 признаков связности вершин графа устройства. Перед началом работы с помощью генераторов 4 случайных событий .задают значения и законы распределения вероятности существования дуг между вершинами графа. Подавая сигналы на входы 6 опроса устройства, можно определить наличие пути во все вершины графа, а повторяя, опросы, — зафиксировать на счетчикам

3 вероятности существования путей.

1 зепо ф лы 1 иле

1462349 с помощью счетчиков 3 определить вероятность существования пути в любую вершину графа.

Составитель А.Мишин

Редактор А.Огар ТехРед Л.Олийнык

Корректор С.Черни

Заказ ?15(49 Тираж 667 Подпис ное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101

Изобретение относится к вычислительной технике и может быть использовано для исследования надежности сетей связи, описываемых вероятностными графами.

Цель изобретения — расширение функциональных возможностей устройства путем определения связных вершин графа.

На чертеже представлена функпиональная схема устройства.

Устройство содержит блок 1 определения смежных вершин графа, группу из В элементов ИЛИ.2, где В— количество вершин в графе, и группу из В счетчиков 3.

Блок 1 определения смежных вершин графа включает матрицу из ВхВ генераторов 4 случайных событий и группу из В элементов ИЛИ 5.

Кроме того, иа чертеже обозначены входы 6 опроса устройства и выходы 7 признаков связности вершин графа.

Устройство работает следующим образом.

Перед началом работы в К-й генератор случайных событий M-й строки матрицы (К = 1...В, М = 1...А) заносят значение и закон распределения вероятности существования дуги -из

М-й в К-ю вершину графа. После подачи сигнала на один из входов 6 устройства (иапример, 4-й) происходит опрос генераторов 4 случайных событий 4-й строки матрицы. Если одик (например, P-й) или несколько генераторов 4 подтвердят наличие пути из М-й в P-m sepmay графа, будут опрошены генераторы 4 Р"й строки матрицы и т.д. На выходах 7 устройства будет определен состав связных вершин графа. Повторяя опросы, можно

Формула изобретения

Устройство для операций над графом, содержащее блок определения смежных вершин графа и группу из В элементов ИЛИ, где  — количество вершин в графе, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устрой15 ства за счет определения связных вершин графа, вход опроса М-й вершины устройства (М = 1...В) подключен к первому входу М-ro элемента ИЛИ группы, выход которого подключен к

20 входу опроса М-й вершины блока определения смежных вершин графа, выход признака смежности К-й вершины которого (К = 1...В) является выходом признака связности К-й вершины гра25 фа устройства и подключен к второму входу К-ro элемента ИЛИ группы.

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что, с целью расширения фцнкциональных возможнос30 тей устройства за счет обеспечения возможности выполнения операций над вероятностными графами, блок определения смежных вершин графа содержит матрицу из ВхВ генераторов случайных событий и группу из В элементов ИЛИ, причем вход опроса М-й вершины блока определения смежных вершин графа подключен к входам опроса всех генераторов случайных событий матрицы, 40 выход К-го генератора случайных событий М-й строки матрицы подключен к М-му входу К-го элемента ИЛИ группы, выход которого является выходом признака смежности К-й вершины бло45 ка определения смешных вершин графа.