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

1

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

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

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

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

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

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

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

Сущность изобретения поясняется чертежом.

Устройство содерл ит матричную модель 1 сети, блок 2 управления, генератор 3 импульсов, формирователи 4 весов дуг, включающие счетчик 5 и триггер 6, элементы И 7, дифференцирующие цепи 8, элементы ИЛИ 9, дополнительные элементы PI 10 и дополнительные триггеры 11.

Модель 1 сети представляет собой матрицу однородных ячеек формирователей весов дуг.

Число элементов И 7, ИЛИ 9 элементов И 10 и триггеров 11 с кодовыми входами определяется числом строк и столбцов матрицы.

Нулевые выходы триггеров 6 формирователей весов дуг, расположенных в одном столбце, подключены ко входам элемента И 7 и через дифференцирующую цепь 8 ко входам элемента ИЛИ 9 соответствующего столбца.

Выход элемента ИЛИ 9 через элемент И 10 соединен с единичным входом триггера 11. Управляющие входы элементов И 7, 10, нулевой вход триггера 11, а также выходы элементов И 7 и триггера И соединены с блоком управления 2.

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

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

Работу устройства проследим при определении минимальной величины пути в графе.

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

единичное состояние соответствующий триггер 6 и на вход соответствующего элемента ИЛИ 9 через дифференцирующую цепь 8 поступит разрещение с нулевого выхода этого триггера, которое в виде импульса проходит через элемент ИЛИ 9, затем через элемент И 10, так как при определении минимальной величины пути в графе на второй вход элемепта И 10 с блока 2 подается

разрешающий сигнал.

С выхода элемента И 10 разрешающий импульс поступает па единичный вход триггера 11, который перебрасывается в единичное состояние. Это свидетельствует о

том, что одни из весов дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных элементом ИЛИ 9 через дифференцирующие цепи 8, сформирован. При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящие из сформированного узла. Вычислительный процесс продолжается

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

подачу импульсов на входы элементов И

7, 10 и подает импульс на нулевой вход

триггера 11, тем самым с него снимается

высокий потепциал.

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

При определении максил альной величины путп в графе блок 2 управлепня запрещает подачу импульсов на элементы И 10.

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

путей в графах.

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

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

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

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

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

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 485451, кл. G 06F 15/20, 1971.

2.Авторское свидетельство СССР N° 491132, кл. G 06F 15/20, 1974.

Г/