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

Союз Советских Социалистических Республиклам нзобретении открытий 2) Авторы изобретени А. Титов, Е. А. Дроздов и В. А, Тафинце(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕН ЭКСТРЕМАЛЬНЫХ ПУТЕЙ В ГРАФИзобретение относится к области вычислительной техники и может быть использовано при исследовании сетевых графиков.Известно устройство для моделирования кратчайших путей на графе, содержащее 5 блок формирования топологии, блок управления, формирователь временного интервала, логические элементы и задатчики адресов узлов 111.Известное устройство осуществляет моде лирование только минимальных путей на графе.Наиболее близким техническим решением к рассматриваемому является устройство, содержащее блок управления, импульсный 15 вход которого соединен с выходом генератора импульсов, элементы И по числу столбцов матричной модели сети, цепочки из последовательно соединенных счетчика и триггера по числу строк и столбцов матричной 20 модели сети, выход триггера каждого столбца подключен к информационному входу элемента И соответствующего столбца, управляющие входы элементов И соединены с первым выходом блока управления 2. 25Указанное устройство может быть использовано для определения максимальных путей в графах, т. е. также отличается ограниченными функциональными возможностями. 30 Целью изобретения является расширение функциональных возможностей за счет определения минимальных путей в графах.Поставленная цель достигается тем, что в устройство введены по числу столбцов матричной модели сети элементы ИЛИ, дополнительные триггеры и элементы И и по числу строк и столбцов графа - дифференциручощие цепи, вход каждой из которых соединен с выходом соответствующего триггера, а выходы дифференцируюших цепей одного столбца матричной модели сети подключены ко входам элемента ИЛИ соответствующего столбца, выход элемента ИЛИ каждого столбца матричной модели сети соединен с информационным входом дополнительного элемента И одноименного столбца, управляющие входы дополнительных элементов И подключены ко второму выходу блока управления, третий выход которого соединен с управляющими входами дополнительных триггеров, нулевой вход каждого дополнительного триггера подк:почен к выходу дополнительного элемента И соответствующего столбца матричной модели сети, выход каждого дополнительного триггера объединен с выходом элемента И соответствующего столбца матричной модели сети и подключен к соответствующему входу блока управления.Сущность изобретения поясняется чертежом.Устройство содержит матричную модель 1 сети, блок 2 управления, генератор 3 импульсов, формирователи 4 весов дуг, включающие счетчик 5 и триггер 6, элементы И 7, дифференцирующие цепи 8, элементы ИЛИ 9, дополнительные элементы И 10 и дополнительные триггеры 11,Модель 1 сети представляет собой матрицу однородных ячеек формирователей вссов дуг.Число элементов И 7, ИЛИ 9 элементов И 10 и триггеров 11 с кодовыми входами определяется числом строк и столбцов матрицы.Нулевые выходы триггеров 6 формирователей весов дуг, расположенных в одном столбце, подключены ко входам элемента И 7 и через дифференцирующую цепь 8 ко входам элемента ИЛИ 9 соответствующего столбца.Выход элемента ИЛИ 9 через элемент И 10 соединен с единичным входом триггера 11. Управляющие входы элементов И 7, 10, нулевой вход триггера 11, а также выходы элементов И 7 и триггера 11 соединены с блоком управления 2.Устройство работает следующим образом.Первоначально в модель 1 заносится информация о топологии моделируемого графа и весах дуг. При этом триггеры 6 формирователей 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков, После занесения исходной информации на выходах элементов И 7, объединяющих выходы формирователей 4 в столбцах, соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, а следовательно, и триггеры 6 формирователей 4, находящихся на том столбце будут в нулевом состоянии.Работу устройства проследим при определении минимальной величины пути в графе.С появлением пускового сигнала блок 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов ИЛИ 9, При этом импульсы проходят только на входы счетчиков 5 тех формирователей 4, которые моделируют веса дуг, исходящих из начальных узлов. Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает в 5 10 15 20 25 30 35 40 45 50 55 60 65 единичное состояние соответствующий триггер 6 и на вход соответствующего элемента ИЛИ 9 через дифференцирующую цепь 8 поступит разрешение с нулевого выхода этого триггера, которое в виде импульса проходит через элемент ИЛИ 9, затем через элемент И 10, так как при определении минимальной величины пути в графе на второй вход элемента И 10 с блока 2 подается разрешающий сигнал,С выхода элемента И 10 разрешающий импульс поступает па единичный вход триггера 11, который перебрасывается в единичное состояние. Это свидетельствует о том, что одни из весов дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных элементом ИЛИ 9 через дифференцирующие цепи 8, сформирован. При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящие из сформированного узла.Вычислительный процесс продолжается до тех пор, пока на выходах всех триггеров 11 не будут присутствовать высокие потенциалы, Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управления при этом прекращает подачу импульсов на входы элементов И 7, 10 и подает импульс па г левой вход триггера 11, тем самым с него снимается высокий потенциал.Суммарное число импульсов, поступившее с выхода блока 2, соответствует минимальной величине пути графа (величине кратчайшего пути в графе).При определении максимальной величины пути в графе блок 2 управления запрещает подачу импульсов на элементы И 10.Таким образом незначительным усложнением известного устройства значительно увеличиваются его функциональные возможности для определения экстремальных путей в графах. Формула изобретенияУстройство для определения экстремальных путей в графах, содержащее блок управления, импульсный вход которого соединен с выходом генератора импульсов, элементы И по числу столбцов матричной модели сети, цепочки из последовательно соединенных счетчика и триггера по числу строк и столбцов матричной модели сети, выход триггера каждого столбца подключен к информационному входу элемента И соответствующего столбца, управляющие входы элементов И соединены с первым выходом блока управления, отличающеесяя тем, что, с целью расширения функциональных возможностей устройства за счет определения минимальных путей в графах, в устройство введены по числу столбцов матричной модели сети элементы ИЛИ, доРедактор Б. Герцен Тираж 799 ССР по делам изобретений 5, Раушская наб., д. 4/5Подписноеткрытий пография, пр. Сапунова, 2 полнительные триггеры и элементы И и по числу строк и столбцов графа - дифференцирующие цепи, вход каждой из которых соединен с выходом соответствующего триггера, а выходы дифференцирующих це пей одного столбца матричной модели сети подключены ко входам элемента ИЛИ соответствующего столбца, выход элемента ИЛИ каждого столбца матричной модели сети соединен с информационным входом 10 дополнительного элемента И одноименного столбца, управляющие входы дополнительных элементов И подключены ко второму выходу блока управления, третий выход которого соединен с управляющими входами 15 аказ 2223/16 Изд.782 НПО Государственного комитета 113035, Москва, Ждополнительных триггеров, нулевой вход каждого дополнительного триггера подключен к выходу дополнительного элемента И соответствующего столбца матричной модели сети, выход каждого дополнительного триггера объединен с выходом элемента И соответствующего столбца матричной модели сети и подключен к соответствующему входу блока управления,Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР485451, кл. Ст 06 Р 15/20, 1971.2. Авторское свидетельство СССР491132, кл. Ст 06 Р 15/20, 1974.