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

 

ОПИСАНИЕ

ИЗОБ ИЙ

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

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

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

Республик (61) Дополнительное к ввт. свид-ву (22) Заявлено 02.0180 (21) 2861750/18-24 (51jpA. Кл з с присоединением заявки Н9

G 06 F 15/20

Государственный «омнтет

СССР но делам изобретений н открытий (23) Приоритет.Опубликовано 0 10М1 бюллетень М 33

Дата опубликования описания 070981 (53) УДК 681.333 (088.8) (72) Авторы изобретения

В, A. Титов, В. Л, Гайдуков, С. М аров (71) Заявитель (54) УСТРОИСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ

ПУТЕЙ В ГРАФАХ

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

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

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

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

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

О которого соответствует "веса" работ, а дугам — информационные связи между работами.

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

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

Целью изобретения является повышение надежности устройства эа счет

30 сокращения аппаратурных затрат.

862145

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

12 одноименной строки матричной модели находятся в нулевом состоянии, Поэтому на выходе соответствующих элементов ИЛИ-НЕ 2 будет высокий потенциал, благодаря чему на управляемом входе одноименного элемента И 5 будет высокий потенциал.

Отсчитав число импульсов, пропорциональное "весу" моделируемой вершины, счетчик 6 переполняется, устанавливает в единичное состояние соответствующий триггер 7, а все тригге- ры 12 в данном столбце матричной модели — в нулевое состояние. Переброс триггера 6 в единичное состояние обеспечивает прекращение подачи счетных импульсов через элемент И 8 на вход регистрирующего счетчика 9, на котором фиксируется код максимального пути иэ данной вершины до конечной вершины графа сети °

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

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

И 4 на информационными входы элемен« тов И 5 и 8.

; Работа устройства при определении . максимальных путей для всех вершин в графе пояснена на следующем примере.

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

ИЛИ, элемент И, счетчики по числу столбцов матричной модели сети, триггеры управления по числу столбцов матричной модели сети и элементы

ИЛИ-НЕ по числу строк матричной модели сети, выходы которых подключены к управляющим входам одноименных элементов И второй группы, выходы которых соединены с входами одноименных счетчиков группы. Выходы последних подключены к установочным входам триггеров одноименных столбцов матричной модели сети и к входам одноименных триггеров управления, выходы .которых соединены с управляющими входами одноименных элементов И первой группы и с входами элемента ИЛИ, выход которого подключен к первому входу элемента И, выход которого со-. единен с информационными входами элементов И первой и второй групп. Вы-30 модели сети элементы ИЛИ-НЕ 2 -2„, генератор тактовых импульсов 3, элемент И 4 по числу столбцов матрицы, вторую группу элементов И 5< -5„, счетчики ("весов" дуг) 6 -би, триггеры управления 3 „ -7и, первую группу элементов И 8- -8«регистрирующие счетчики 9 -9, элемент ИЛИ 10, пусковой вход устройства 11 и триггеры

121 по числу строк и столбцов матричной модели сети, где 1,j = 1, и (И- число вершин в моделируемом графе), Устройство работает следующим 50 образом, Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети), При этом триггеры 12 ", которые являются формирова.ц 1 телями дуг, устанавливаются в единичное состояние, если есть информационная связь из i-ой вершины в 1 -ю вершину. Соответствующий формирователь 12 определяется пересечением строки с номером 1, (1-я вершина) 44 и столбца с номером j (j-я вершина), В счетчики 6 соответствукщих вершин графа заносятся числа импульсов, дополняющие "веса" вершин до полной

0 1 1 1 0 0 0 0 0 емкости счетчиков. Триггеры 7 и счет ход генератора тактовых импульсов подключен к второму входу элемента И, На чертеже показана структурная схема устройства, Устройство содержит матричную мо- 35 дель 1 сети, по числу строк матричной

862145

00001

О О О О О

00000 .О О О О О

1 3 2 5 4

1 1 0 1 0

О 1 О 0 О

0 0 1 1 0

О О 1 1 1

О О О 1 О

0 0 О О 1

0 О О О 1

0 О О О О

3,4, 3 2,2) Т=

I I I I I ,где элементы

О,если нет дуги из 1-й вер» шины в j-юу

1, если есть дуга из 1 -й вершины в -ю, "вес" 1-й вершины моделируемого графа, После занесения исходной информации на входах элементов ИЛИ-НЕ 2,, будет низкий потенциал, а на выходе высокий. На выходах элементов ИЛИ-НЕ

2 -29 будет низкий потенциал, поэтому .после подачи пускового сигнала на 2О вход 11 устройсвта счетные импульсы с выхода генератора 3 через элемент

И 4,будут поступать через элементы

И 8 -8 с на входы регистрирующих счетчиков 9„ - 9„o, а также через эле- 35 менты И 5 g на вход счетчика 6 . Через +

rep 7 0 . Одновременно сигнал переполнения счетчика 6 переводит все триггеры 12 р -12 gp, pâ нулевое состояние. Переброс триггера 7 в единичное состояние вызывает прекращение подачи; счетных импульсов на регистрирующий счетчик 9 0, таким образом, с выходов элементов ИЛИ-HE 28, 2 H

2„ после прихода второго импульса с выхода генератора 3 через элемент И на входы элементов И 5 к 8,появляемся 40 высокие потенциалы, после чего счетные импульсы будут поступать также на входы счетчиков 68 н 6 . С приходом четвертого импульса переполняется счетчик б, после чего перебрасывают- 4Я ся в нулевое состояние триггеры

12 -12 0 з, прекращается подача .счетных импульсов на счетчик 9, и начинается подача счетных импульcps на вход счетчика 67; С приходом у пятого импульса переполняется счетчик 68, и прекращается подача импульсов на счетчик 9в и т.д, Вычислительный процесс заханчивается с приходом четырнадцатого импульса „ после чего прекратится подача счетных импульсов на вход счетчика 9 (на другие счетчики 9 подача импульсов прекращается раньше), Одновременно -прекращается подача высокого потенциала с нулевых выходов тригге- еО ров 7„ «7 „, поэтому pà выходе элемента ИЛИ 10 будет низкий потенциал, вследствие чего прекращается подача счетных импульсов с генератора 3 через элементы И 4, 5 и 8 на входы счет чиков 6 и 9. Показания счетчиков 9 соответствуют максимальным величинам

- в графе для каждой вершины, ври этом каждому номеру вершины сопоставлен соответствующий счетчик, 8 данном примере эти показания (начиная с первого) следукицие: 14, 12, 11 13, 9, 8, 8, 5, 4 к 2.

Работа предлагаемого устройства при определении наиболее ранним мо ментов свершения событий. идентична работе устройства при определений. величин максимальных путей для всех вершки в графе. Разница лишь ss том, что матрица смежности А графа заносится в матричную модель сети с предварительным транспортированием ее относительно не главной дкагОиали, с соответствующим изменением нумерации элементов вектора Т, Для данного примера наиболее ранние моменты свершения событий для исходного графа будут следующие: 1, 4, 3, б, 8, 6, 10, 11, 12 и 14, l таким образом, предлагаемое устройство за счет введения дополнительных элементов с новыми связями обес-, печивает получение положительного эффекта, который заключается в том, что для определения максимальных величин путей в графах значительно сокращаются аппаратурные затраты приблизительно, о точностью до одного триггера, на(и -и} счетчиков, в коа торые заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков, по сравнению с прототипом. Сокращение аппаратурных затрат в устройстве, выполняющем те . же функции, повышает надежность устройства. формула изобретения устройство для определения максимальных путей в графах, содержащее триггеры по числу строк к столбцов матричной модели сети,:.енератор так товых импульсов, первую группу элементов И по числу столбцов матричной модели сети, выходы которых подключены к входам одноименных регистрирующих счетчиков группы, вторую группу элементов И по числу столбцов матричной модели сети, о т л к ч а ю. щ е е с я тем, что, с цеЛью повышения надежности устройства, в него введены элемент ИЛИ, элемент И, счетчики ао числу столбцов матричной модели сети, триггеры управления по числу столбцов матричной модели сети. и элементы ИЛИ-НЕ по числу строк матричной модели сети, выходы которых подключены к управляющим входам одноименных элементов И второй группы, выходы которых соединены с входами одноименных счетчиков группы, выходы котовых подключены к устаноВ6 2145

Составитель И. Дубинина

Редактор Л. Утехина Техред й. Бабинец Корректор Г. Решетннк

Заказ 6614/44 Тираж 745 . Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", r, Ужгород, ул, Проектная, 4 вочным входам триггеров одноименных столбцов матричной модели сети и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных эле ментов И первой группы и с входами элемента ИЛИ, выход которого подключен к первому входу элемента И, вы ход которого соединен с информацион нымии входами элементов И первой и второй групп, выход генератора тактовых импульсов подключен к второму входу элемента Н.

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

1, Авторское свидетельство СССР

9 491132, кл, G 06 F 15/20, 1974, 2. Авторское свидетельство СССР по заявка Р 2587569/24, кл. G Об F 15/20, 1978 (прототип),