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

 

Изобретение относится к вычислительной технике и может быть использовано для анализа связности верхних графа. Целью изобретения является расширение функциональных возможностей устройства за счет проверки наличия циклов в графе. Устройство содержит блок 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 ° ° ° ° °

° ° ° ° ° ° ° °

° ° °

° ф °

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

 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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