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

 

011 49И32 о п и чаек-ни- л

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 12.05.74 (21) 2023070/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 05.11.75. Бюллетень № 41

Дата опубликования описания 06.02.76 (51) М. Кл. G 06f 15/20

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.333(088.8) (72) Авторы изобретения

А. Г. Додонов, В. В. Хаджинов и В. М. Шишмарев

Институт электродинамики AH Украинской ССР (71) Заявитель (54) УСТРОИСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

МАКСИМАЛЬНЫХ ВЕЛИЧИН ПУТЕЙ В ГРАФАХ

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

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

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

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

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

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

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

5 Оно содержит матричную модель сети 1, блок 2 управления, генератор импульсов 3, формирователи 4 весов дуг, включающие счетчик 5 и триггер 6, и элементы «И» 7.

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

10 однородных ячеек формирователей и весов дуг размером гг)(гг, где n — максимальное число узлов моделируемого графа.

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

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

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

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

Устройство работает следующим образом.

Первоначально в модель 1 заносится информация о топологии моделируемого графа и весах дуг. При этом триггеры б формироваЗ0 телей 4, моделирующих ветви графа, уста491132 навливаются в единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков.

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

С появлением пускового сигнала блок 2 управления разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов 7. При этом импульсы проходят только на входы счетчиков 5 тех формирователей

4, которые моделируют веса дуг, исходящих из начальных узлов. Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает в единичное состояние соответствующий триггер 6, и на вход соответствующего элемента 7 поступает разрешение с нулевого входа этого триггера.

Если на остальных входах этого элемента

7 — разрешающие потенциалы, то на его выходе появляются импульсные сигналы. Это свидетельствует о том, что все веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом 7, сформированы.

При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящие из сформированного узла.

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

Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управления при этом прекращает подачу им10 пульсов на входы элементов 7.

Суммарное число импульсов, поступившее с выхода блока 2, соответствует максимальной величине пути графы (величине длиннейшего пути в графе).

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

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

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

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

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

491132

Редактор Л. Утехина

Корректоры: В. Петрова и О. Данишева

Заказ 42/12 Изд. № 78 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

Типография, пр. Сапунова. 2! ! ! !

Составитель А, )Керенов

Техред T. Курилко

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

 

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

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

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

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

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

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

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

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

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

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