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

 

I Ц 6403 I4

ОПИСАН И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 04.03.77 (21) 2458633/18-24 с присоединением заявки № (51) М. Кл.-

G 06G 7/122 по делам изобретений (43) Опубликовано 30.12.78. Бюллетень № 48 (53) УДК 681.333 (088.8) и открытий (45) Дата опубликования описания 30.12.78 (72) Авторы изобретения

В. А. Титов, Е. А. Дроздов и В. А. Тафинцев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

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

ЬсУдаР"еенный комитет (23) Приоритет

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

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

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

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

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

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

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

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

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

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

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

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

640314

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

Устройство содержит матричную модель

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 одного из формирователей переполняется, устанавливает в

65 единичное состояние соответствующий триггер 6 и на вход соответствующего элемента

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

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

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

Вычислительный процесс продолжается до тех пор, пока на выходах всех триггеров

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

Блок 2 управления при этом прекращает подачу импульсов на входы элементов И

7, 10 и подает импульс па нулевой вход триггера 11, тем самым с него снимается высокий потенциал.

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

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

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

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

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

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

1(Составитель И. Загорбинина

Техред А. Камышникова Корректоры: А. Николаева и Л. Корогод

Редактор Б. Герцен

Заказ 2223/16 Изд. Ме 782 Тираж 799 Подписное

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

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

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

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

Источники информации, принятые во внимание при экспертизе

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

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