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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(53)М. Ял.2 6 06 Г 15/20 с присоединением заявки Мо Государственный комитет СССР по дедам изобретений и открытибДата опубликования описания 30,06.80(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ВЕЛИЧИН ПУТЕЙ В ГРАФАХИзобретение относится к области вычислительной техники и может быть использовано при исследовании параметров сетевых графиков.По основному авт,св. М 491132 известно устройство для определения максимаЛьных величин путей в графах, содержащее блок управления, импульсный вход которого соединен с выходом генератора импульсов, элементы И по числу столбцов матричной модели сети, цепочки из последовательно соединенных счетчиков и тригГера по числу строк и столбцов матричной модели сети, выход триггера .каждого 15 столбца подключеи к входу элемента И соответствующего столбца, входы которых соединены со счетными входами счетчиков одноименной строки матричной модели сети и с соответ ствуюшим входом блока управления, выход которого подключен к управляющим входам, элементов И.Недостатком известного устройства является невозможность определения величин максимальных путей, моментов наиболее раннего свершения событий с одновременной. идентификацией соответствующих номеров всех вершин сетевого графика. 30 2Необходимость в этом возникает, например, - прй" решениизадач плайирования организации выполнения некоторого множества работ, представлен- ных сетевым графиком. В этом случае бывает необходимо определить величину критического пути от произвольной вершины сети до ее конечной вершины или моменты наиболее раннего свершения событий вершин с одновременной их идентификацией.Целью изобретения является расширение Функциональных возможностей устройства за счет определения максимальных путей и моментов наиболее раннего наступления событий для всех вершин сетевого графика. Поставленная цель достигается тем,что в каждый столбец матричной моделисети введены регистрирующий счетчик,дополнительный элемент И и элементНЕ, вход которого подключен к выходуэлемента И, выход элемента НЕ соединен с первым входом дополнительногоэлемента И, второй вход которого подключен к выходу блока управления,выход дополнительного элемента Исоединен с входом регистрирующегосчетчика,На чертеже показана структурнаясхема предлагаемого устройства.Оно содержит матричную модель 1сети,. блок 2 управления, генератор3 тактовых импульсов формирователи4 весов дуг, включающие счетчик 5 итриггер б, элементы И 7, элементыНЕ 8, дополнительные элементы И 9 ирегистрирующие счетчики 10,устройство работает следующимобразом.Первоначально в модель 1 заноситОся. информация о топологии моделируемого графа (сети) . При этом триггеры 6 формирователей 4, моделирующих ветви графа, устанавливаютсяв единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равнымномеру начального узла моделируемойветви, и столбца с номером, равнымномеру ее конечного узла, В счетчики 205 соответствующих формирователей 4заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков. После занесения исходной инофрмации на выходах элементов 7 И, объединяющих выходы Формирователей 4 в столбцах,соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что воднонаправленном графе без циклов ипетель начальные узлы не содержатвходящих ветвей, а следовательно,и триггеры б формирователей 4, находящихся в этом столбце, будут в нулевом состоянии (элементы 7 соединены с нулевыми выходами триггеров 6).Счетчики 10 в исходном состояниисброшены в нулевое состояние.Исходный граф заносится в матричную модель сети в инверсном порядке, 40т.е. матрица смежности заносимогографа транспортирована относительнонеглавной диагонали. Это позволяетиспользовать для расчета максимальных путей в графе процедуру динамического программированияС появлением пускового сигналаблок 2 управления разрешает прохождение импульсов с выхода генератора3 на,входы всех элементов И 9. Приэтом импульсы проходят только на входы счетчиков 5 тех формирователей 4,которые моделируют веса дуг, исходящих из начальных узлов.Эти же импульсы проходят на регистрирующие счетчики 10 всех вершин графа, кроме начальной, так как на выходе соответствующего элемента 7высокий потенциал, а следовательно,на выходе элемента НЕ 8 низкий.Отсчитав число импульсов, пропорциональное весу моделируемой дуги,счетчик 5 одного из формирователейпереполняется, устанавливает.в нулевое состояние соответствующий триггер б, и на вход соответствующего 65 элемента И 7 поступает разрешениес нулевого выхода этого триггера.Если на остальных входах этого элемента И 7 - разрешающие потенциалы,то на его выходе появляются импульсные сигналы. Это свидетельствует отом, что все веса дуг, входящих вузел, номер которого соответствуетномеру столбца формирователей 4,объединенных этим элементом 7, сформированы. При этом формируется разрешение поступления импульсов на входысчетчиков 5 формирователей 4, моделирующихветви графа, исходящие изсформированного узла, Одновременно.с этим на вход элемента НЕ 8 одноименного столбца подается высокийпотенциал, а с его выхода - низкий,следовательно, подача импульсов навход счетчика 10 через элемент И 9прекратится и на выходе счетчика 10зафиксируется время максимальногопути для данной вершины графа.Вычислительный процесс продолжается до тех пор, пока на выходахвсех элементов И 7 не будут присутствовать высокие потенциалы. Этосвидетельствует о том, что все узлыисследуемого графа сформированы.Блок 2 управления при этом прекраща-,ет подачу импульсов на входы формирователей 4 и элементов 9.число импульсов, зафиксированноена счетчиках 10, соответствует максимальной величине пути для данной вершины (величине максимального пути вграфе от данной вершины до конечной).Работа устройства при определениинаиболее ранних моментов поступлениясобытий идентична работе устройствапри определении величин максимальныхпутей для всех вершин в графе. Разница лишь в том, что матрица смежности графа заносится в матричную модельсети без предварительного транспортирования, т.е. так, как это сделанов прототипе.Таким образом, устройство за счетвведения дополнительных элементовс новыми связями обеспечивает получение нового положительного эфФекта,который заключается в том, что в зависимости от способа занесения исходной информации о сетевом графе вычисляются максимальные пути от всехвершин графа до конечной, а такжемоменты наиболее раннего наступлениясобытий для всех вершин исследуемогографа с одновременной идентификациейэтих вершин,ФорМула изобретенияУстройство для определения максимальных величин путей в графах по авт .св. Р 491132, о т л и ч а ю щ ее с я тем, что, с целью расширения Функциональных возможностей за счет.Ужгород, ул.Проектная,4 ал ППППатентопределения максимальных путей и моментов наиболее раннего наступлениясобытия для всех вершин сетевогографика, в каждый столбец матричноймодели сети устройства введены регистрирующий счетчик, дополнительныйэлемент И и эЛемент ЙЕ, вход котороТираж 7ИИПИ Государстпо делам иэоб5, Москва, Ж-З го подключен к выходу элемента И,выход элемента НЕ соединен с первымвходом дополнительного элемента И,второй вход которого подключен к выходу блока управления, выход допол-нительного элемента И соединен с входом регистрирующего счетчика.