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

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ПУТЕЙВ ГРАФАХ

1

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

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

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

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

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

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

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

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

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

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

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

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

На чертеже показана структурная схема устройства.

Устройство содержит матричнукг модель 1 сети, по числу строк матрично модели сети элементы ИЛИ-НЕ , генератор тактовых импульсов 3, элемент И 4 по числу столбцов матрицы, вторую группу элементов И 5 -5 , счетчики { весов дуг) , триггеры управления 7 7, первую группу элементов И , регистрирующие счетчики Я(-9, элемент ИЛИ 10, пусковой вход устройства 11 и триггеры по числу строк и столбцов матричной модели сети, где i ,j 1, и ( П- число вершин в моделируемом графе),

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

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

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

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

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

Вычислительный процесс продолжается до тех пор, пока на выходах всех триггеров 7 не будут присутствовать низкие потенциалы. Это свидетельствует о том, что все вершишь исследуемого графа сформированы, На выходе элемента ИЛИ 10 будет низкий потендиал; в результате чего прекращается подача счетных импульсов с выхода генератора 3 через элеме 1Т И 4 на информационнь1е входы элементов И 5 и 8,

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

Пусть задан граф, описываемый матрицей смежности А и вектором Т ве,ров дуг

110 1 1 1 о о о о о Ojj ||0 00010100 0|| 000011 0000001000 0000000110 00000001 11 000 00 00010 0000000001 0000000001 {0000000000 1;3 2;5;4;3;4;3;2,2 ,где элемейты О,если нет дуги из i-и вер шины в i-toj если есть дуга из i -и вершины в , вес 1-й веряины моделируемого графа, После занесении исходной информа одги на входах элементов ИЛИ-НЕ 2 убудет низкий потенциал, а на выходе в|зсокий. На выходах элзлентов ИЛИ-Н будет низкий потенциал, поэто му .после подачи пускового сигнгша н вход 11 устройсвта счетные импульсы с выхода генератора 3 через элемент И 4 .будут поступать через элементы И из входы регистрирующих счетчиков 9 - 9 , а также через эл менты И на вход счетчика 6 . Ч рез 2, т.е. с приходом второго импульса, который заполняет до полной емкости счетчик б, , перебра сывается в единичное состояние триг гер . Одновременно сигнал перепо нения счетчика переводит все три геры 12.о -12fp.oB нулевое состояние . Переброс триггера 7/ в единич ное состояние вызывает прекращение подачи.счетных импульсов на регистрирующий счетчик , Таким образом с выходов элементов ИЛИ-НЕ TQ , 29 и после Прихода второго импульса выхода генератора 3 через элемент И на входы элементов И 5 и 8, появляет высокие потенциалы, после чего счет ные иютульсы будут поступать также входы счетчиков 6g и 69. С приходом четвертого импульса переполняется счетчик 6у, после чего перебрасываю ся в нулевое состояние триггеры 12 а .9 , прекращается подача счётных импульсов на счетчик 9, И начинается подача счетных импульсов на вход счетчика 67. С приходом пятого импульса переполняется счетчик 6g, и прекращается подача импульсов на счетчик 9в и т.д. Шачислительный процесс за(саичивается с приходом четырнадцатого импульса после чего прекратится подача счетных импульсов на вход .счетчика 9 (на другие счетчики 9 подача импульсов прекращается раньше). Одновременно прекращается подача высокого потенциала с нулевых выходов триггеров 7j , поэтому на выходе элемен та ИЛИ 10 будет низкий лотенциал, вследствие чего прекращается подача счетных импульсов с генератора 3 элементы И 4, 5 и 8 на входы сче чиков .6 и 9. Показания счетчиков 9 соответствуют максимальным величинам в графе для каждой вершины, при этом каходому номеру вершины сопоставлен соответствующий счетчик, В данном примере эти показания (начиная с первого) следуйзщие: 14, 12, 11, 13, 9, 8, 8, 5, 4 к 2. Работа предлагаемого устройства при определении нгтболее ранних мом ментов свершения событий идентична работе устройства при определении величин максимальных путей для всех вершин в графе. Разница лишь в том, что матрица о вежиости А графа заносится в матричную модель сети с предварительным транспортированием ее относительно не главной диагонали , с соответствующим изменением иумерация элементов вектора Т, Для данного примера наиболее ранние моменты свершения событий для исходного графа будут следующие: if 4, 3, б, 8, б, 10, 11, 12 и 14, I Таким образом, предлагаемое устройство за счет введения дсжолнительных элементов с новыми связями обес. печивает получение полояштельного эффекта, который заключается в том, что для определения максимальных величин путей в графах значительно сокращаются аппаратурные затраты приблизительно, с точностью до одного триггера, на() счетчиков, в которые заносятся Числа импульсов, дополняющие веса вершин до полной емкости счетчиков, по сравнению с прототипом. Сокращение аппаратурных затрат в устройстве, выполняющем те же функции, повышает надежность устройства. Формула изобретения Устройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели сети, .;-енератор так товых импульсов, первую группу элементов И по числу столбцов матричной модели сети, выходы которых подключены к входам одноименньпс регистрирующих счетчиков группы, вторую группу элементов И по числу столбцов матричной модели сети, отличаю щ е е с я тем, что, с цеУ1ью повышения надежности устройства, в него введены элемент ИЛИ, элемент И, счетчики по числу столбцов матричной модели сети, триггеры управления по числу столбцов матричной модели сети и элементы ИЛИ-НЕ по числу строк матричной модели сети, выходы которых подключены к управляющим входгм одноименных элементов И второй группы, выходы которых соединены с входами одноименных счетчиков группы, выхода КОТОРЫХ подключены к установочным входам триггеров одноименных столбцов матричной модели сети и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных элементов И первой группы и с входами элемента 1ЛЛ1Л, выход которого подключен к первому входу элемента и, вы-г ход которого соединен с инфО «ационIными входами элементов И первой и

второй групп, выход генератора тактовых импульсов подключен к второму входу элемента И.

Источники информации, принятые во внимание при экспертизе 1, Авторское свидетельство СССР № 491132, кл, G Об F 15/20, 1974.

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