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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК Оа 16033 15/20 5 С ОБРЕТЕНИ КИИ 5 И 3 ВИЦч- ",.,1 У БИБЛИО, : , О.М. Коп.8)свидетельст06 С 7/122идетельство6 06 Р 15/2ДЛЯ 011 РЕДЕЛ о СССР1967.СССР1988.ЕНИЯ Плотносится к вычисли- и может быть использования путей в систеграфами. Целью изобрасширение функциоостей устройства за ГОСУДАРСТВЕННЫЙ НОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГННТ СССР ОПИСАНИЕ И К АВТОРСКОМУ СВИДЕ(57) Изобретениетельной техникевано для исследомах, описываемыхретения являетсянальных возможн счет определения ребер дерева кратчайших путей в графе. Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления заходящих дуг, блок 3 определения кратчайшего пути, блок 4 регистрации и блок 5 определения конечных вершин дуг, кроме того, вход 6 начальной установки устройства, вход 7 пуска устройства и выходы 8 признаков принадлежности ребер дереву кратчайших путей. При подаче на вход 7 пуска устроиства сигнала, имитиру-ющего исполнение начальной вершины графа, блок 3 определения кратчайшего пути выдает в блок 4 регистрации сигналы, отмечающие исполнение дуг (ре- с бер) графа в порядке окончания их моФ делирования. 4 ил.ЭИзобретение относится к вычислительной технике и может быть использо вано для исследования путей в системах, описываемых графами.Цельюизобретения является расширение функциональных воэможностей устройства за счет определения ребер дерева кратчайших путей в графе.На Фиг. 1 представлена функциональ.1 О ная схема устройства; на Фиг, 2- Функциональная схема блока определения конечных вершин дуг; на фиг, 3- функциональная схема блока удаления заходящих дуг; на Фиг. 4 - Функциональная схема блока регистрации.Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления за" ходящих дуг, блок 3 определения кратчайшего пути, блок 4 регистрации и 2 О блок 5 определения конечных вершин дуг. Кроме того, на Фиг. 1 обозначено: 6 - вход начальной установки устройства; 7 вход - пуска устройства и 8 - выход признаков принадлежности ре"25 бер дереву кратчайших путей.Блок 5 определения конечных вершин дуг содержит матрицу из В х В элементов И 9, где В - количество вершин в графе, и группу из В элементов ИЛИ 10, причем вход 11 признака наличия (К, М)-й дуги блока 5 определения конечных вершин дуг (К = 1В; М = 1В) подключен к первому входу К-го элемента И 9 М-й строки матрицы, выход которого подключен к35 М-му входу К-го элемента ИЛИ 10 группы, выход которого является выходом 12 признака соответствия К-й вершины конечной вершине дуги блока 5 опре деления конечных вершин дуг, вход 13 опроса (К, М)-й дуги графа которого подключен к второму входу К-го элемен" та И 9 М-й строки матрицы.Блок 2 удаления заходящих дуг содержит матрицу из В х В ключей 14, причем вход 15 признака наличия (К, М)-й дуги блока 2 удаления заходящих дуг подключен к информационному входу К-го ключа 14 М-й строки матрицы инф 50 формационный выход которого является выходом 16 признака наличия (К, М)-й дуги блока удаления заходящих дуг, вход 17 задания К-й вершины которого подключен к управляющим (отключающим) входам всех ключей 14 К-го столбца матрицы.Блок 4 регистрации содержит матрицу из В х В триггеров 18, причем (К,М)-й информационный вход 19 блока 4регистрации подключен к входу установки в "1" К-го триггера М-й строкиматрицы, прямой выход которого является (К, М)-м информационным выходом20 блока 4 регистрации, вход 21 установки в "0" которого подключен к входам установки в "0" всех триггеров 18матрицы.Устройство работает следующим образом.Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа, при этомребра графа задают двумя противоположно направленными дугами, обнуляют блок4 регистрации, в блок 3 определениякратчайшего пути заносят информациюо параметрах вершин и ребер (цепи установки параметров моделирования вершин и ребер не показаны). оНа вход 7 пуска устройства подаютсигнал, имитирующий исполнение начальной вершины графа (это может быть сигнал, изменяющийся по амплитуде, представленный серией импульсов уровня"1", потенциал того же уровня и т.пв зависимости от конструкции блока 3).При этом блок 3 определения кратчайше,го пути моделирует систему, заданнуюпараметрами графа. При этом блок .4 регистрирует дуги графа, моделированиекоторых закончено, а блоки 2 и 5 удаляют дуги, заходящие в вершину, конечную для дуги, окончившей моделирование.По исполнении всех вершин графа, очем может свидетельствовать сигнал свыхода (непоказан) признака исполнения всех вершин графа блока 3, в блоке4 регистрации содержится информацияо ребрах (или дугах, если моделируюторграф) дерева кратчайших путей и направление, в котором пройдено ребро(К, М или М, К).Блок 4 регистрации работает следующим образом,При поступлении на вход 21 установки в "0" импульса уровня логическойединицы все триггеры 18 устанавливаются в "0". При появлении сигналовуровня "1" на входах 19 соответствующие им триггеры 18 устанавливаютсяв н 1 фф Формула изобретения Устройство для определения парамет ров графа, содержащее блок задания%РУе е еВВМ фЮ еее УОВе% 5 1 ЬОИ 9 матрицы смежности, блок определения кратчайшего пути и блок регистрации, причем вход задания начальной вершины графа устройства подключен к одноименному входу блока определения крат.5 чайшего пути, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения ребер дерева кратчайших путей в графе, в него введены блок определения конечных вершин дуг и блок удаления заходящих дуг, причем выход признака наличия (К, М)-й дуги блока задания матрицы смежности (К = 1В; М = 1В, где В количество вершин в графе) подключен к одноименному входу блока удаления заходящих дуг и к одноименному входу блока определения конечных вершин 20 дуг, выход признака соответствия К-й ; вершины конечной вершине дуги которо 6 6го подключен к входу задания К-й вершины блока удаления заходящих дуг,выход признака наличия (К, М)-й дугикоторого подключен к одноименномувходу блока определения кратчайшегопути, выход признака окончания моделирования (К, М)-й дуги которого подключен к (К, И)-му информационномувходу блока регистрации, (К, М)-й информационный выход которого являетсявыходом признака принадлежности (К,М)-го ребра дереву кратчайших путейустройства и подключен к входу опроса (К, М)-й дуги блока определенияконечных вершин дуг, вход начальнойустановки устройства подключен к вхо-.ду установки в "О" блока регистрации,вход пуска устройства подключен квходу имитации исполнения начальнойвершины блока определения кратчайшегопути.) Ю г.4 ел шин Редакт орен орректор С. Черни,Ходан Тираж 568венного комитета по изобретения113035, Москва, Ж, Раушская аказ при ГКНТ СССР но-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 10 ств роизво 3387Госуд фп фв в в1 У 19 Соста Техре 16033962вв Раг 3Ь 1 Ущ одписное и открыти б., д, 4/