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

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ВЕЛИЧИН ПУТЕЙ В ГРАФАХ

1

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

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

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

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

10 свершения событий вершин с одновременной .их идентификацией.

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

Поставленная цель достигается -тем,

20 что в казкдый столбец матричной модели сети feведены регистрирующий счетчик, дополнительный элемент И и элемент НЕ, вход которого подключен к выходу элемента И, выход элемента НЕ соеди25нен с первым входом дополнительного элемента И, второй вход которого подключен к выходу блока управления, выход дополнительного элемента И соединен с входом регистрирующего счетчика..

30

На чертеже показана структурная схема предлагаемого устройства,

Оно содержит матричную модель 1 сети, блок 2 управления, генератор .3 тактовых импульсов, формирователи

4весов дуг, включающие счетчик 5 и триггер 6f элементы И 7, элементы

НЕ 8, дополнительные элементы И 9 и регистрирующие счетчики Ю.

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

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

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

однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, -а следовательно, и триггеры б формирователей 4, находящихся в этом столбце, будут в нулевом состоянии (элементы 7 соединены с нулевыми выходами триггеров 6) . Счетчики 10 в исходном состоянии сброшены в нулевое состояние.

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

С появлением пускового сигнала блок 2 управления разрешает прохождениё импульсов с выхода генератора 3 на .входы всех элементов И 9. При этом импульсы проходят только на входы счетчиков 5 тех формирователей 4, Которые моделируют веса дуг, исходящих из начальных узлов.

Эти же импульсы проходят на регисрирующие счетчики 10 всех веряин графа, кроме начальной, так как на. выходе соответствующего элемента 7 высокий потенциал, а следовательно, на выходе элемента НЕ 8 низкий.

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

элемента И 7 поступает разрешение с нулевого выхода этого триггера. Если на остальных входах этого элемента И 7 - разрешающие потенциалы, то на его выходе появляются импульсные сигналы. Это свидетельствует о том, что все веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом 7, сформрованы. При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, .моделирующих ветви графа, исходящие из сформированного уз,ла. Одновременно. ,с этим на вход элемента НЕ 8 одно-именного столбца подается высокий потенциал, а с его выхода - низкий, следовательно, подача импульсов на вход счетчика 10 через элемент И 9 прекратится и на выходе счетчика 10зафиксируется время максимального пути для данной вершины графа.

.Вычислительный процесс продолжается до тех пор, пока на выходах всех элементов И 7 не будут присутствовать высокие потенциалы. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управления при этом прекращает подачу импульсов на входы формирователей 4 и элементов 9. . .

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

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

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

Формула изобретения

Устройство дл$г определения максимальных величин путей, в графах по авт.Ьв. № 491132, ающе е с я тем, что, с цельЪ расширения функциональных возможностей за счет

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

JL