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

011 49 И 32 о и ичаек рл ИЗОБРЕТЕН ИЯ Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 1) Дополнительное к авт.2) Заявлено 12,05.74 (21)с присоединением заявк 3) Приоритет 23070/1851) М, Кл. б 061 15/20 Государственный комитет Совета Министров СССР тень406.02.76 5. Бю бликовано(72) Авторы изобретения Г. Додонов, В, В, Хаджино М, Шишмар 71) Заявитель титут электродинамики АН Украинской ССР(54) УСТРОИСТВО ДЛЯ ОПРЕДЕЛЕНИЯ АКСИМАЛЬНЫХ ВЕЛИЧИН ПУТЕЙ В ГРАФ2 рез триг дуг в устройстве со оторого подключен коИзобретение относится к области вычислительной техники.Известны устройства, содержащие по числу узлов графа формирователи в строках и столбцах матричной модели сети, блок управления и генератор импульсов, соединенный с блоком управления.Недостатком известных устройств является или разделение во времени процесса формирования топологии графа и процесса формирования весов дуг, что приводит к снижению быстродействия устройства, или отсутствие возможности определения максимальных величин путей в графе.Целью изобретения является увеличение быстродействия и повышение коэффициента использования оборудования.Поставленная цель достигается тем, что в устройство введены элементы И по числу столбцов матричной модели сети. Выходы формирователей весов дуг каждого столбца соединены со входами соответствующего элемента И, выход которого соединен со входами формирователей весов дуг строки, одноименной со столбцом. Выходы и управляющие входы элементов И подключены соответственно к входам и выходу блока управления,Формирователь весовдержит счетчик вход к входу формирователя, выход - чегер к выходу формирователя.Схема устройства представлена на чертеже.5 Оно содержит матричную модель сети 1,блок 2 управления, генератор импульсов 3,формирователи 4 весов дуг, включающиесчетчик 5 и триггер 6, и элементы И 7.Модель 1 сети представляет собой матрицу10 однородных ячеек формирователей и весовдуг размером гг(гг, где гг - максимальноечисло узлов моделируемого графа,Формирователь содержит счетчик 5, выполняющий функции задержки, и триггер б.15 Нулевые выходы триггеров 6 формирователей весов дуг, расположенных в одном столбце, подключены ко входам элемента И 7,число которых определяется числом (гг)строк и столбцов матрицы. Выход элемента 720 соединен со входами формирователей весовдуг 4, принадлежащих строке, одноименнойсо столбцом, с которым своими входами соединен данный элемент 7. Управляющие входы элементов 7 и их выходы подключены к25 блоку 2 управления.Устройство работает следующим образом.Первоначально в модель 1 заносится информация о топологии моделируемого графаи весах дуг. При этом триггеры б формироваЗО телей 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков.После занесения исходной информации на выходах элементов И 7, объединяющих выходы формирователей 4 в столбцах, соответвующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, а следовательно, и триггеры 6 формирователей 4, находящихся в этом столбце, будут в нулевом состоянии.С появлением пускового сигнала блок 2 управления разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов 7. При этом импульсы проходят только на входы счетчиков 5 тех формирователей 4, которые моделируют веса дуг, исходящих из начальных узлов. Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает в единичное состояние соответствующий триггер 6, и на вход соответствующего элемента 7 поступает разрешение с нулевого входа этого триггера. Если на остальных входах этого элемента 7 - разрешающие потенциалы, то на его выходе появляются импульсные сигналы. Это свидетельствует о том, что все веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом 7, сформированы, При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящие из сформированного узла.Вычислительный процесс продолжается дотех пор, пока на выходах всех элементов 7 не будут присутствовать высокие потенциалы.Это свидетельствует о том, что все узлы исследуемого графа сформированы, Блок 2 управления при этом прекращает подачу им пульсов на входы элементов 7.Суммарное число импульсов, поступившеес выхода блока 2, соответствует максимальной величине пути графы (величине длиннейшего пути в графе).15Предмет изобретения1. Устройство для определения максимальных величин путей в графах, содержащее по 20 числу узлов графа формирователи весов дугв строках и столбцах матричной модели сети, блок управления и генератор импульсов, соединенный с блоком управления, отличающееся тем, что, с целью увеличения быст родействия и повышения коэффициента использования оборудования, в него введены элементы И по числу столбцов матричной модели сети; причем выходы формирователей весов дуг каждого столбца соединены со вхо дами соответствующего элемента И, выходкоторого соединен со входами формирователей весов дуг строки, одноименной со столбцом; выходы и управляющие входы элементов И подключены соответственно к входам 35 и выходу блока управления.2. Устройство по п. 1, отл и ч а ю щеес ятем, что формирователь весов дуг содержит счетчик, вход которого подключен ко входу формирователя, выход - через триггер к вы ходу формирователя,ПодписиССР Типографии, пр. Сапунов г11 Заказ 42/12 Изд.78 Тир ЦНИИПИ Государственного комитета Сове по делам изобретений и отк 113035, Москва, Ж, Раушская