Устройство для определения максимальных величин путей в графах Советский патент 1975 года по МПК G06F15/173 

1

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

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

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

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

Поставленная цель достигается тем, что в устройство введены элементы «И по числу столбцов матричной модели сети. Выходы формирователей весов дуг каждого столбца соединены со входами соответствующего элемента «И, выход которого соединен со входами формирователей весов дуг строки, одноименной со столбцом. Выходы и управляющие входы элементов «И подключены соответственно к входам и выходу блока управления.

Формирователь весов дуг в устройстве содержит счетчик,. вход которого подключен ко

входу формирователя, выход - через триггер к выходу формирователя.

Схема устройства представлена на чертеже.

Оно содержит матричную модель сети 1,

блок 2 управления, генератор импульсов 3,

формирователи 4 весов дуг, включающие

счетчик 5 и триггер 6, и элементы «И 1.

Модель 1 сети представляет собой матрицу

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

Формирователь содержит счетчик 5, выполняющий функции задержки, и триггер 6.

Нулевые выходы триггеров 6 формирователей весов дуг, расположенных в одном столбце, подключены ко входам элемента «И 7, число которых определяется числом (/г) строк и столбцов матрицы. Выход элемента 7

соединен со входами формирователей весов дуг 4, принадлежащих строке, одноименной со столбцом, с которым своими входами соединен данный элемент 7. Управляющие входы элементов 7 и их выходы подключены к

блоку 2 управления.

Устройство работает следующим образом. Первоначально в модель 1 заносится информация о топологии моделируемого графа и весах дуг. При этом триггеры 6 формирователей 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, соответствует максимальной величине пути графы (величине длиннейшего пути в графе).

Предмет изобретения

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

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

и выходу блока управления.

2.Устройство по п. I, отличающееся тем, что формирователь весов дуг содержит счетчик, вход которого подключен ко входу формирователя, выход - через триггер к выходу формирователя.