Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/419 

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - функциональная схема варианта исполнения устройства; на фиг. 3 - функциональная схема блока определения полустепеней захода; на фиг. 4 - функциональная схема блока удаления исходящих дуг.

Устройство содержит блок 1 задания матрицы смежности, блок 2 определения полустепеней захода, блок 3 сравнения, вход 4 опроса и выход 5 признака отсутствия циклов.

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

Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа.

На вход 4 опроса устройства подают потенциал уровня логической единицы. При этом блок 2 выдает потенциалы уровня логической единицы на те свои выходы, полустепени захода соответствующих вершин которых равны нулю (т. е. потенциалы уровня логической единицы появляются на тех выходах блока 2, номера которых равны номерам вершин, в которые не заходит ни одна дуга). При этом блок 1 удаляет из матрицы смежности графа выбранные строки (тем самым из топоплогии графа удаляются дуги, исходящей из всех вершин с нулевой

полустепенью захода). При этом топология графа изменяется, блок 2 выделяет новые вершины с нулевой полустепенью захода и так далее, до полного удаления всех дуг. не входящих в циклы графа. Через время, достаточное для окончания указанных процесЁ

О

о

(X

V N

сов, при отсутствии циклов в графе на всех выходах блока 2 появятся потенциалы уровня логической единицы, При этом блок 3 сравнения сформирует на своем выходе по- тонциал уровня логической единицы (признак отсутствия циклов). При наличии циклов в графе на одном или нескольких выходах блока 2 сохранятся потенциалы уровня логического нуля и на выходе блока 3 сравнения (он может быть выполнен в виде элемента И) сохранится потенциал логического нуля (признак наличия циклов в графе),

На фиг. 2 показан вариант исполнения устройства, который отличается тем, что, с целью сохранения первоначальной топологии графа, в него введен блок б удаления исходящих дуг, причем выход значения (К, М)-го элемента блока 1 задания матрицы смежности подключен к входу признака наличия (К, М)-й дуги блока удаления исходящих дуг (К 1 В, М 1 В, где В количество вершин в графе), одноименный выход которого подключен к одноименному входу блока 2 определения полустепеней, захода, выход признака равенства нулю по- лустепени захода К-й вершины подключен к К- му информационному входу блока 3 сравнения и к входу удаления дуги, исходящих из К-й вершины блока 6.

Блок 2 определения полустепеней захода содержит группу из В элементов ИЛИ- НЕ 7 и группу из В элементов И 8, причем вход 9 признака наличия (К.МЬй дуги подключен к М-му входу К-го элемента ИЛИ- НЕ 7, выход которого подключен к первому входу К-го элемента И 8, выход которого является выходом 10 признака равенства

нулю степени К-й вершины блока 2, вход 11 опроса которого подключен к вторым входам всех элементов И группы,

Блок 6 удаления исходящих дуг содержит матрицу из ВхВ ключей 12, причем вход 13 признака наличия (К,М)-1 дуги блока 6 подключен к информационному входу М-го ключа 12 К-й строки матрицы, информационный выход которого является одноименным выходом 14 блока 6, вход 15 удаления дуг, исходящих из К-й вершины которого подключен к отключающим входам всех ключей 12 К-й строки матрицы.

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

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

Фиг.1

1

Фиг.2

Я

П 18 % 2В

Фиг.З

я я а

. . Р0

% /

//г