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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСИОМУ СВИДИТИЗЬСТВУСоюз Советскнк Соцналнстнчесннк Республик(51)М ( 3 с присоединением заявки йо 6 Об Г 15/20 Государственный омитет СССР ио делам изобретениИ и открытий,Опубликовано 020981,Бюллетень ЙЯ 33 Дата опубликования описания 070981(088.8) 72) Авторь Титов, В. Л, Гайд обретения М ров 1) Заявите 54) УСТРОИСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ПУТЕЙВ ГРАФАХратор равления лючающие И, элеементы И тиыть а вершины, араннего свновременноперехода ошинами кми, как эт ерше й их т гр граф о пр е.Целью изобретения ние надежности уст кращения аппаратур вляется повнйства эа счет ных затрат. ше30 со Изобретение относится к обласвычислительной техники и может биспользовано при исследовании параметров сетевых графиков.Известно устройство для определения максимальных величин путей в граФах 1 содержащее блок управления,импульсный вход которого соединен свыходом генератора импульсов, элементы И по числу столбцов матричноймодели, цепочки из последовательносоединенных счетчика и триггера почислу строк и столбцов матричной модели сети, выход триггера каждогостолбца подключен к входу элемента Исоответствующего столбца, входы которых соединены с счетными входамисчетчиков одноименной строки матричной модели сети и с соответствукщимвходом блока управления, выход которого подключен к управляющим входамэлементов И.Недостат ства является ления максимаНаиболее решением к из тройство дляных путей в ее триггеры по ов ком известного устрой невозможность опреде льных путей. близким ;ехническим обретению является ус определения максималь графах 2 , содержащ числу строк и столбцматричной модели сети, генетактовых импульсов, блок упФформирователь весов дуг, вксчетчик и триггер, элементыменты НЕ, дополнительные эли регистрирующие счетчики.Недостатком известного устройствявляется его чрезмерная сложность при моделировании графов, вершинам О которого соответствует "веса" работ,а дугам - информационные связи между работами.Необходимость в этом возникает,например, при решении задач планиро вания организации выполнения некоторого множества работ, представляемых сетевым графиком. В этом случае возникает необходимость определения критических путей от произвольной 20 вершины графа сети до ее конечнойтакже моменты наиболеения событиЯ работ с од идентификацией, без афа с нагруженными вер 25 у с нагруженными дугаедусмотрено в прототичики 9 находятся в сброшенном (нулевом) состоянии, После занесения исходной информации на входах элементов 2 ИЛИ-НЕ, объединяющих выходыформирователей в строках, соответствующих конечным вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов ипетель конечные вершины не содержатвыходящих ветвей, а следовательно,и триггеры 12, находящиеся в этойстроке, будут в нулевом состоянии(входы элементов 2 соединены с нуле-.выми выходами триггеров 12 одноименной строки матрицы).С появлением пускового сигнала вавходе 11 элемента И 4 импульсы д вихода генератора 3 будут поступатьна входы элементов И 5 и 8 груип,При этом имдульсы прОхОдят на всесчетчики 9, так как в исходном положении все триггеры 7 находятся в нулевом состоянии, а управляемые входыэлементов И 8 подключены к нулеваюавыходам триггеров 7. Эти счетные импульсы поступают через элементы И 5на счетчики б, для которых триггеры12 одноименной строки матричной модели находятся в нулевом состоянии,Поэтому на выходе соответствующихэлементов ИЛИ-НЕ 2 будет высокий потенциал, благодаря чему науправляемом входе одноименного элемента И 5 будет высокий потенциал.Отсчитав число импульсов, пропорциональное "весу" моделируемой вершины, счетчик б переполняется, устанавливает в единичное состояние соответствующий триггер 7, а все тригге-ры 12 в данном столбце матричной мо"дели - в нулевое состояние. Перебростриггера б в единичное состояниеобеспечивает прекращение подачи счетных импульсов через элемент И 8 навход регистрирующего счетчика 9, накотором фиксируется код максимального пути иэ данной вершины до конечной вершины графа сети.Вычислительный процесс продолжается до тех пор, пока на выходахвсех триггеров 7 не будут присутствовать низкие потенциалы. Это свидетельствует о том, что все вершимыисследуемого графа сформированы,На выходе элемента ИЛИ 10 будет низкий потенциал, в результате чего прекращается подача счетных импульсов.с выхода генератора 3 через элементи 4 на информационные входы элементов И 5 и 8,; Работа устройства при определении. максимальных путей для всех вершин в графе пояснена на следующем примере.Пусть задан граф, описываемый мат,рицей смежности А и вектором Т "веЭта цель достигается тем, что в устройство для определения максимальных путей в графах, содержащее триггеры по числу строк и столбцов матричной модели сети, генератор тактовых импульсов, первую группу элементов И по числу столбцов матричной модели сети, выходы которых подключены к входам одноименных регистрирующих счетчиков группы, вторую группуэлементов И по.числу столбцов матричной модели сети, введены элементИЛИ, элемент И, счетчики по числустолбцов матричной модели сети,триггеры управления по числу столбцов матричной модели сети и элементыИЛИ-НЕ по числу строк матричной модели сети, выходы которых подключены к управляющим входам одноименных элементов И второй группы, выходы которых соединены с входами одноименныхсчетчиков группы. Выходы последнихподключены к установочным входамтриггеров одноименных столбцов матричной модели сети и к входам одноименных триггеров управления, выходыкоторых соединены с управляющимивходами одноименных элементов И первой группы и с входами элемента ИЛИ,выход которого подключен к первомувходу элемента И, выход которого со-.единен с информационными входами элементов И первой и второй групп. Вымодели сети элементы ИЛИ-НЕ 2 -2,генератор тактовых импульсов 3, элемент И 4 по числу столбцов матрицы,вторую группу элементов И 5 -5,счетчики ("весов" дуг) б -би, триггеры управления 7 -7 и, первую груп-.пу элементов И 8. -8 и, регистрирующиесчетчики 9 -9, элемент ИЛИ 10, пусковой вход устройства 11 и триггеры121 по числу строк и столбцов матричной модели сети, где 1,1 = 1, и( И- число вершин в моделируемомграфе),Устройство работает следующим 50образом,Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети), При этом триггеры 12 , которые являются формирова,цтелями дуг, устанавливаются в единичное состояние, если есть информационная связь из 1-ой вершины в 1 -ювершину. Соответствующий формирователь 12 определяется пересечениемстроки с номером 1, ( 1-я вершина) 6и столбца с номером 1 (-я вершина),В счетчики б соответствукщих вершинграфа заносятся числа импульсов, дополняющие "веса" вершин до полной 0111000000 емкости счетчиков, Триггеры 7 и счет ход генератора тактовых импульсовподключен к второму входу элемента И,На чертеже показана структурнаясхема устройства,Устройство содержит матричную модель 1 сети, по числу строк матричной,где элементыО,если нет дуги из 1-й вершины в -ю101 1, если есть дуга из 1 -йвершины в -ю,"вес" 1-й вершины моделируемого графа,после занесения исходной информации на входах элементов ИЛИ-НЕ 2 обудет низкий потенциал, а на выходевысокий. На выходах элементов ИЛИ-НЕ2-2 будет низкий потенциал, поэтому .после подачи пускового сигнала на 20вход 11 устройсвта счетные импульсыс выхода генератора 3 через элементИ 4,будут поступать через элементыИ 8 -84 с на входы регистрирующихсчетчиков 9 - 9 о, а также через элементы И 5 р на вход счетчика б . Через Ф.о = 2, т.е. с приходом второго импульса, который заполняет дополной емкости счетчик б о, перебрасывается в единичное состояние триг- рргер 7 о . Одновременно сигнал переполнения счетчика 6 о переводит все триггеры 12,о -12 о.аз нулевое состояние. Переброс триггера 7 в единичное состояние вызывает прекращениеподачи, счетных импульсов на регистрирующий счетчик 90, таким образом,с выходов элементов ИЛИ-НЕ ф, 2 и2 после прихода второго импульса свыхода генератора 3 через элемент Ина входы элементов И 5 к 8,появляется 40высокие потенциалы, после чего счетные импульсы будут поступать также навходы счетчиков 68 н бе . С приходомчетвертого импульса переполняетсясчетчик б, после чего перебрасывают- Яся в нулевое состояние триггеры12 9 -120 з, прекращается подача.счетных импульсов на счетчик 9,и начинается подача счетных импульсов на вход счетчика 67; С приходом 4 Опятого импульса переполняется счетчик 68, и прекращается подача импульсов на счетчик 9 з и т,д, Вычислительный процесс заханчиваетсяс приходом четырнадцатого импульсапосле чего прекратится подача счетных импульсов на вход счетчика 9(на другие счетчики 9 подача импульсов прекращается раньше), Одновременно прекращается подача высокогопотенциала с нулевых выходов тригге- еОров 7 7.а, поэтому на выходе элемента ИЛИ 10 будет низкий потенциал,вследствие чего прекращается подачасчетных импульсов с генератора 3 через элементы И 4, 5 и 8 на входы счет чиков .б и 9. Показания счетчиков 9соответствуют максимальным величинамв графе для каждой вершины, при этомкаждому номеру вершины сопоставленсоответствующий счетчик, В данномпримере эти показания (начиная с первого) следущие: 14, 12, 11, 13, 9,8, 8, 5, 4 к 2.Работа предлагаемого устройствапри определении наиболее ранних ввментов свершения событий. идентичнаработе устройства при определенна.величин максимальных путей для всехвершки в графе, Разница лишь в том,что матрица смежности А графа заносится в матричную модель сети спредварительным транспортированиемее относительно не главной дкагОиали, с соответствующим изменением нумерации элементов вектора Т,Для данного примера наиболее ранние моменты свершения событий для исходного графа будут следующие: 1, 4,3, б, 8, б, 10, 11, 12 и 14,1 таким образом, предлагаемое устройство за счет введения дополнительных элементов с новыми связями обес-,печивает получение положительногоэффекта, который заключается в том,что для определения максимальных величин путей в графах значительно сокращаются аппаратурные затраты приблизительно, о точностью до одноготриггера, на(и -и) счетчиков, в ко"аторые заносятся числа импульсов, дополняющие "весаф вершин до полнойемкости счетчиков, по сравнению спрототипом. Сокращение аппаратурныхзатрат в устройстве, выполняющем теже функции, повышает надежность устройства,Формула изобретенияустройство для определения максимальных путей в графах, содержащее триггеры по числу строк к столбцов матричной модели сети,:.енератор так товых импульсов, первую группу элементов И по числу столбцов матричной модели сети, выходы которых под. ключены к входам одноименных регистрирующих счетчиков группы, вторую группу элементов И по числу столбцов матричной модели сети, о т л к ч а ю щ е е с я тем, что, с цеью повышения надежности устройства, в него введены элемент ИЛИ, элемент И, счетчики но числу столбцов матричной модели сети, триггеры управления по числу столбцов матричной модели сети. и элементы ИЛИ-НЕ по числу строк матричной модели сети, выходы которых подключены к управляющим входам одноименных элементов И второй группы, выходы которых соединены с входами одноименных счетчиков группы, выходы котовых подключены к устано862145 Составитель И. Дуб Техред й. Бабинец инаКорректо ешетни Редактор Подписноекомитета СССРи открытийкая наб., д, 4/ э 6614 иал ППП Патент", г. Ужгород, ул, Проектная,вочным входам триггеров одноименных столбцов матричной модели сети и к входам одноименных триггеров управления, выходы которых соединены с управляющими входами одноименных элементов И первой группы и с входами элемента ИЛИ, выход которого подключен к первому входу элемента И, вы ход которого соединен с информационнымии входами элементов И первой и 4 Тираж 745 .ВНИИПИ Государственногпо делам иэобретени 13035, Москва, Ж, Рау второй групп, выход генератора тактовых импульсов подключен к второмувходу элемента И,Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРР 491132, кл, С Об Г 15/20, 1974,2. Авторское свидетельство СССРпо заявка Р 2587569/24,кл. С Об Г 15/20, 1978 (прототип),