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

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