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

Авторы патента:

G06F15/419 - Цифровые компьютеры вообще (конструктивные элементы G06F 1/00-G06F 13/00); оборудование для обработки данных вообще (нейронные сети для обработки данных изображений G06T)

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

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

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

РЕСПУБЛИК (я)5 G 06 F 15/419

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

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

ПРИ ГКНТ СССР

1 йЖОВЗМЯ ,< L.-Pm- Ща ЧЛЕН В . 5 ЛИС)ТЕН,А

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

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

Q (Х

Л эом. (21) 4642209/24 (22) 24.01,89 (46) 23,06.91. Бюл. N. 23 (72) А.Г. Луценко, В,М, Балакирев и К.С. Карпенко (53) 681.333 (088.8) (56) Авторское свидетельство СССР

N. 468244, кл. G 06 F 15/20, 1972.

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

М 1575199, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ

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

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

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

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

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

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

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

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

НЕ 7, выход которого подключен к первому входу К вЂ” го элемента И 8, выход которого является выходом 10 признака равенства нулю степени К вЂ” и вершины блока 2, вход 11 опроса которого подключен к вторым входам всех элементов И группы, Блок 6 удаления исходящих дуг содержит матрицу из ВхВ ключей 12, причем вход

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

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

1658172 в Ь! Ь

° ° °

° ° ° ° ° 9 ° °

° ° °

1и 11 42 у ®ь

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

Техред М.Моргентал Корректор С.Черни

Редактор А. Пекарь

Заказ 1714 Тираж 418 Подписное

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

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

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

° ° 6 ° ° ° ° °

° ° ° ° ° ° ° °

° ° °

° ф °

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

Устройство для поиска данных // 1658170

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

Устройство для определения среднего арифметического значения // 1658169

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

Устройство для моделирования систем сбора и передачи информации // 1658168

Изобретение относится к вычислительной технике и технике связи

Устройство для перебора сочетаний // 1658167

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

Устройство для умножения разреженных матриц // 1656560

Изобретение относится к вычислительной технике и может Ьыть использовано в специализированных вычислительных машинах для умножения разреженных и сверхрэзреженных матриц Цель изобретения - сокращение аппаратурных затрат Устройство содержит два блока памяти для хранения ненулевых элементов разреженных матриц, блок памяти для хранения ненулевых элементов i-й строки одной из исходных матриц со значениями индексов строк, вычислительный блок, регистры, блоки элементов ИЛИ И, элементы ИЛИ, НЕ, элемент И

Матричный мультиплексор-демультиплексор // 1656559

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

Устройство для определения интервала корреляции // 1656558

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

Устройство для контроля параметров // 1656557

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

Анализатор экстремумов // 1656556

Изобретение относится к автоматике и вычислительной технике, в частности к устройствам для обработки цифровых данных, и может быть использовано в системах экстремальною регулирования а также для цифровой фильтрации помех Анализатор содержит ключ 1

Вычислительное устройство с чередующимся обслуживанием нескольких командных потоков // 2101759

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

Способ проведения электронной игры и система для его осуществления // 2105586

Изобретение относится к электронным играм

Управляемая от эвм телекоммуникационная установка // 2106008

Микроэвм // 2108619

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

Цифровой компьютер с возможностью параллельного выполнения двух и более команд // 2109333

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

Параллельный процессор с перепрограммируемой структурой // 2110088

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

Схемное устройство для параллельной обработки двух или более команд в цифровом компьютере // 2111531

Изобретение относится к цифровым компьютерным системам и предназначено для обработки двух и более команд параллельно

Многопроцессорная векторная эвм // 2113010

Изобретение относится к вычислительной технике, точнее к построению многопроцессорных векторных ЭВМ

Вычислитель с перепрограммируемой архитектурой // 2115161

Изобретение относится к вычислительной технике и может найти применение в автоматизированных системах управления АСУ индустриального и специального назначения

Способ и устройство изготовления выкроек предметов одежды // 2120219

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