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

.(5,1.)Р 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТд ИЗОБРЕТЕН ОПИС КОМУ СВИДЕТЕЛЬСТ М(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ ПУТЕЙ В ГРАФАХ(5) Изобретение относится к областивычислительной техники, Пель изобретения - повышение быстродействияустройства, Изобретение обеспечивает более высокое быстродействие приидентиФикации вершин грайа, образующих критический путь, за счет выбора иэ граАа вершин, расположенных накритическом пути, исключая длительную процедуру перебора всех вершинграАа. Это достигается введением вустройство группы элементов НЕ, элементов И, ИЛИ, НЕ и триггера. 1 ил.Изобретение относится к вычислительной технике и может быть использовано при исследовании параметровсетевых граАов.Задача определения максимального 5критического пути в графе заключаетсяв определении величины и индентификации вершин, образующих этот путь.Цель изобретения - повышение быстродействия устройства. 10На чертеже представлена структурная схема устройства для определениямаксимальных путей в граАах.Устройство содержит матричнуюи х и модель 1 граАа, триггеры 2 почислу строк и столбцов матричной модели граАа первый и второй элементы И 3 и 4, по числу и столбцов матричной модели графа, группу элементов ИЛИ-НЕ 5, группу из и элементовИЛИ 6, первую группу из и элементовИ 7, группу из и счетчиков 8 "весов" вершины, вторую группу из иэлементов И 9 группу из и регист 125рирующих счетчиков 10, третью группу из и элементов И 11, группу из ирегистрирующих триггеров 12 (П-триггеров с синхронизацией приема инАормаций от генератора тактовых импульсов), четвертую группу из и элементов И 13, блок 14 выбора максимального кода числа, первый элемент ИЛИ15, первыйэлемент И 16, генератор,17 тактовых импульсов, первый эле 1 чент НЕ 18, второй элемент И 19, 35группу из (и - 1) элементов НЕ 20,второй элемент ИЛИ 21, второй элемент НЕ 22, третий и четвертый элементы И 23 и 24, третий элемент НЕ25, триггер 26, пятый элемент И 27,40выход 28, вход 29.Матричная модель 1 граАа представляет собой матрицу однородныхузлов, каждый из которых представляет собой триггер 2 и подсоединенные45к его выходу элементы И 3 и 4. Размер матричной модели ихи, где и -максимальное число вершин моделируемого графа,Устройство работает следующим образом,Первоначально в модель 1 заносит -ся инАормация о топологии моделируемого графа (сети). При этом триггеры 2 1 (1, 1 = 1, 2и), которые55являются Аормирователями дуг, уста. навливаются в единичное состояние,если есть информационная связь из-й вершины в 3-ю вершину. Соответствующий триггер 2 , определяется пересечением 1-й строки и 1-го столбца. другие триггеры 2 а также счетчики 10 находятся в нулевом состоянии. Причем нумерация вершин граАа начинается с йачальной вершины,В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине моделирующего граба, В счетчики Я соответствующих вершин,. граАа заносятся числа импуль 11сов , дополняющие веса вершин до полной емкости счетчиковПосле з а- несения исходной инйо рмации н а выходах элементов ИЛИ-НЕ 5, объединяющих выходы триггера 2 , в строках ,соответствующих конечным вершинаммоделирующего графа, имеются высокие потенциалы. Это объясняется тем,что в однонаправленном графе безциклов и петель конечные вершины несодержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке находятся в нулевом состоянииОпределение вершинграАа, образующих маКсимальный критический путь, осуществляется в два этапа.На первом этапе с появлением пускового сигнала на входе 29 элемента И 16 импульсы с выхода генератора 17 поступают на входы элементов И 7 и 9. При этом импульсы проходятна все счетчики 1 О, так как в исходном состоянии вторые входы элементов И 9 подключены к выходам одноименныхсчетчиков Я, на которых появляется сигнал переполнения. Кроме того, счетные импульсы поступают через элементы И 7 на входы тех счетчиков 8, для которых триггеры 2 одноименной строки матрицы находятся в нулевом состоянии. Это происходит благодаря тому,что на выходе соответствующих элементов ИЛИ-НЕ 5 и на управляемом входеодноименного элемента И 7 имеютсявысокие потенциалы. Отсчитав число импульсов, пропорциональное "весу моделируемой вершины, счетчик Я переполняется, инизкий потенциал с триггера переполнения (не показан) счетчика 8 подается на вторые входы элементов И 4 одноименного столбца матричной модели 1 и одноименный вход элемента ИЛИ 15. Появление низкого потенциала на входе соответствующего элемента И 9 обеспечивает прекращение подачисчетных импульсов через элемент И9 на вход регистрирующего счетчика10, на котором фиксируются код максимального пути из данной вершиныдо конечной вершины графа сети.Вычислительный процесс продолжаетсядо тех пор, пока на выходах всехсчетчиков 8 не будут присутствоватьнизкие потенциалы, На выходе элемента ИЛИ 15,имеется низкий потенциал,в результате чего прекращается подача счетных импульсов с выхода генератора 17 через элемент И 16 на инфор -мационные входы элементов И 7 и 9.На этом первый этап работы устройства заканчивается.Второй этап работы устройства начинается после появления высокогопотенциала на выходе элемента НЕ18, после чего тактовые импульсы свыхода генератора 17 через элементИ 19 поступают на входы элементовИ 13,Высокий потенциал появляется навыходе элемента И 13; в случае, еслитриггер 12; находится в единичном состоянии и его порядковый номер 1 наибольший из группы триггеров 12находящихся в единичном состоянии,так как высокий потенциал с выходатриггера 12; поступает на вход элемента НЕ 20, В результате с выходаэлемента НЕ 20 низкий потенциал поступает на соответствующие входы элементов И 13(1 = 1 - 1, 1 - 2;,1),З 5запрещая тем самым появление высоких потенциалов на выходах элементов И 13 . Высокий потенциал с выхода элемен 40 та И 13, поступает на информационные входы элементов И 3; (1 11, 2,п) одноименной строки матричной модели 1 сети и поступает далее через элементы ИЛИ 6 только45 на те.управляемые входы элементов И 11, которым в данной строке матричной модели сети соответствует дуга графа, т,е, единичное состояние триггера 2. Наличие высоких потенциалов Ма управляемых выходах элементов ИЛИ 6 обеспечивает поступление кодов с выходов счетчиков 10 на входы блока 14, который в свою очередь обеспечивает выбор максимального из поступивших кодов, при этом соответ ствующие триггеры 12 перебрасываются в единичное состояние. Одновременно высокие потенциалы с выходов элементов ИЛИ 6 поступают через элементы И 11 на соответствующие входы элемента ИЛИ 21, В результате на выходе элемента ИЛИ 21 появляется высокий потенциал, которыйпоступает на первый вход элементаИ 24, на второй вход которого поступает тактовый импульс с генератора17 через элемент И 19, Следовательно, на выходе элемента И 24 появляется высокий потенциал, который поступает на второй (Б) вход НЯ-триггера 26 и устанавливает его в единичное состояние.С окончанием действия тактовогоимпульса с генератора 17 низкий потенциал поступает на вход элементаНЕ 25, В результате на выходе злемента НЕ 25 устанавливается высокийпотенциал, который поступает на второй вход элемента И 27, на первыйвход которого поступает низкий потенциал с инверсного выхода триггера 26, В результате с вь 1 хода 28 устройства снимается низкий потенциал -сигнал продолжения идентификациивершин, образующих критический путьв графе. Нроцесс идентификации вершин графа продолжается аналогичнымобразом до конечной вершины графа,лежащей на критическом пути,С поступлением очередного тактового импульса с генератора 17 черезэлемент И 19 на входы элементов И13 на выходе элемента И 13 к (К -порядковый номер конечной вершиныграфа, находящейся на критическомпути) появляется высокий потенциал,так как триггер 12 находится в еди-.ничном состоянии, идентифицирующийК-ю вершину, лежащую на критическомпути.В результате высокий потенциалс выхода элемента И 13 к поступаетна информационные входы элементов3 к ( 1 = 1, 2, , п) одноименной строки матричной модели 1 сети.Конечная вершина графа не имеет выходящих дуг, Следовательно, триггеры 2Ц = 1, 2, , и) находятся в нулевом состоянии. В результатена элементы ИЛИ 6 с элементов. И 3поступают низкие потенциалы. На управляемых выходах элементов ИЛИ 6устанавливаются низкие потенциалы,которые поступают на соответствующие входы элемента ИЛИ 21, Следо 1285487Пусть задан граф, описываемый матрицей смежности А и вектором И "весов" вершин.о 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 00 0 0 О 0 0 0 0 0 0 0 0 0 0 0 0 О, 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 р 3; 2 ; 5 е 4; 3; 4; 3) 2 23элементыО, если нет дуги из 1-йа = вершины в 1-ю;1, если есть дуга из 1-йвершины в 1-ю; где"весн д-й вершины моделиру 1Ремого графа.После занесения исходной информации на входах элемента ИЛИ-НЕ 5 вательно, на выходе элемента ИЛИ21 устанавливается низкий потенциал, который поступает на вход элемента НЕ 22. С выхода элемента НЕ 22высокий потенциал поступает на второй вход элемента И 23, на первыйвход которого поступает тактовый им;пульс с генератора 17 через элементИ 19.В результате с выхода элемента И23 появляется высокий потенциал, который поступает на первый (Н) входКБ-триггера 26 и устанавливает егов нулевое состояние. С окончаниемдействия тактового импульса с генератора 17 низкий потенциал черезэлемент И 19 поступает на вход элемента НЕ 25. В результате на выходе элемента НЕ 25 устанавливаетсявысокий потенциал, который поступает на второй вход элемента И 27,на первый вход которого .поступаетвысокий потенциал с инверсного выхода триггера 26, В результате на выходе элемента И 27 появляется высокий потенциал - сигнал окончанияработы устройства.Работа устройства при определениимаксимальных путей для всех вершинв графе поясняется следующим примером,имеется низкий потенциал, а на вЫходе - высокий, На выходах элементовИЛИ-НЕ 5, - 5 присутствует низкийпотенциал, поэтому после подачи пу 5 скового сигнала на вход 29 устройства счетчика импульсы с выхода ге,нератора 17 через элемент И 16 поступают через элементы И 9, - о, на входы регистрирующих счетчиков 1 О, - 10а также через элементы И 7 ш на входсчетчика 8 .Через= 2,с приходомвторого импульса, который заполняетдо полной емкости счетчик 816, перебрасывается в единичное состояние/триггер разряда переполнения счетчика 8, что вызывает прекращениеподачи счетных импульсов на регистрирующий счетчик 10,Таким образом, на выходах элементов ИЛИ-НЕ 5 б, 5 ,и 5, и после прихода второго импульса с выхода генератора 17 через элементы И 7 и 9появляются высокие потенциалы, по 25сле чего счетные импульсы поступают также на входы счетчиков 8 и8 и т дВычислительный процесс первогоэтапа заканчивается с приходом четыр.надцатого импульса, после чего прекрашается подача счетных импульсовна вход счетчика 10, (на все другиесчетчики 10 подача импульсов прекращается ранее); на выходе элементаИЛИ 15 имеется низкий потенциал,35 вследствие чего прекращается подачасчетных импульсов на входы счетчиков 8 и 10. Показания счетчиков 10соответствуют максимальным величинамв графе для каждой вершины, при40 этом каждому номеру вершины сопоставлен счетчик. В данном случае этипоказания (начиная с первого) следующие: 14; 12; 11; 13; 9; 8; 8; 5;4; 2.45На втором этапе работы устройства после появления высокого потенциала на входе элемента НЕ 18 начинается подача тактовых импульсовс генератора 17 через элемент И 19на вход элементов И 13. Появлениепервого тактового импульса с генератора 17 через элемент И 19 на входыэлементов И 13 приводит к появлению55высокого потенциала на выходе элемента И 13 который поступает науправляемые входы вторых элементовИ 3 первой строки матричной моделиграфа, поэтому на входы блока 14 по5 10 15 20 25 30 35 40 45 50 55 7 12 ступают коды со счетчиков 10, 10 и 10 через элементы И 11, 11 э и 11 соответственно. Максимальный из этих кодов - код со счетчика 10 (13), поэтому н единичное состояние перебрасывается триггер 12 , С выхода триггера 12 высокий потенциал поступает на вход элемента НЕ З;, В результате с выхода элемента НЕ 20 низкий потенциал поступает на соответствующие входы элементов И 13, 13 и 13. Следовательно, на выходе элемента И 13, устанавливается низкий потенциал.Одновременно высокие потенциалы с выходов элементов ИЛИ 6 , бз и 6 через элементы И 11 поступают на входы элемента ИЛИ 21. В результате на выходе последнего появляется высокий потенциал, который .поступает на первый вход элемента И 24, на второй вход которого поступает тактовый импульс с генератора 17 через элемент И 19, Следовательно, на выходе элемента И 24 появляется высокий потенциал, который поступает на второй (Б) вход КБ-триггера 26 и устанавливает его в единичное состояние. С окончанием действия тактового импульса с генератора 17 низкий потенциал через, элемент И 19 поступает на вход элемента НЕ 25, В результате на выходе элемента НЕ 25 устанавливается высокий потенциал, который поступает на второй вход элемента И 27, на первый вход которого поступает низкий потенциал с инверсного выхода триггера 26.В результате с выхода 28 устройства снимается низкий потенциал - сигнал продолжения работы устройства.С поступлением второго тактового 1 импульса с генератора 17 через элемент И 19 на входы элементов И 13, на выходе элемента И 13 устанавливается высокий потенциал. Далее. процесс продолжается до тех пор, пока все вершины графа, расположенные на критическом пути, будут идентийицированы. В данном примере критический максимальный путь составляет 1, 4, 7, 9 и 10 вершины, о чем свидетельствует единичное состояние триггеров 121, 12;, 12 1, и 12, . Поступление пятого тактового импульса с генератора 17 через элемент И 19 на входы элементов И 13 вызывает появление высокого потенциала на выходе 85487 8 элемента И 13, , который поступаетна инФормационные входы элементовИ 3,О (3 = 1, 2 .,10) одноименной- 1 Остроки матричной модели 1 сети, Таккак данная строка триггера 2 установлена в нулевое состояние, то навходы элементов ИЛИ 6 через элементыИ 3 поступают низкие потенциалы.В результате на выходе элементаИЛИ 21 устанавливается низкий потенциал, который поступает на входэлемента НЕ 22, Следовательно, навыходе элемента НЕ 22 появляетсявысокий потенциал, который поступает на второй вход элемента И 23,напервый вход которого поступает тактовый импульс с генератора 17 черезэлемент И 19. В результате высокийпотенциал с выхода элемента И 23 поступает на К в вх триггера 26 и устанавливает его в нулевое состояние,С окончанием действия тактового импульса с генератора 17 низкий потенциал через элемент И 9 поступаетна вход элемента НЕ 25. В результатена выходе элемента НЕ 25 устанавливается высокий потенциал, котсрыйпоступает на второй вход элементаИ 27, на первый вход которого поступает высокий потенциал с инверсноговыхода триггера 26, В результате навыходе элемента И 27 появляется высокий потенциал - сигнал окончанияработы устройства,формула изобретения Устройство для определения максимальных путей в граФах, содержащее матричную модель граФа размерностью ихи, каждый узел которой содержит триггер, первый и второй элементы И, причем в каждом узле выход триггера соединен с первыми входами первого и второго элементов И, группу из и элементов ИЛИ-НЕ, первую,вторую, третью и четвертую группы из и элементов И, группу из и счетчиков "веса" вершин, группу из и регистрирующих счетчиков, блок выбора кода максимального числа, группу из и регистрирующих триггеров, группу из и элементов ИЛИ, первый элемент ИЛИ, первый элемент НЕ, первый и второй элементы И и генератор тактовых импульсов, выход которого соединен с первыми входами первого и второго элементов И, выход первого элеме нта И подключен к первым входам элемен -тов И первой и второй групп, выход 1-го элемента ИЛИ-НЕ (д = 1, 2, п, п - размерность матричной модели граФа) соединен с вторым входом дго элемента И первой группы, выход 5 которого подключен к счетному входу -го счетчика "веса вершины, выход переполнения которого соединен с вторым. входом -го элемента И второй группы, выход которого подключен к счетному входу -го регистрирующего счетчика, выход переполнения которого подключен к первому входу элемента И третьей группы, выход которого соединен с д-м входом блока выбора кода максимального числа, -й выход которого подключен к вхолу -го регистрирующего триггера, выход которого соединен с первым входом -го элемента И четвертой группы, выход котоЭ рого подключен к вторым входам первых элементов И узлов д-й строки .матричной модели графа, выход первого элемента И 1-го узла матричной модели граАа соединен с д-м входом д ,25 го элемента ИЛИ группы, выход котороо подключен к второму входу д-го элемента И третьей группы, выход второго элемента И узла д-й строки матричной модели графа подключен к д-му входу д-го элемента ИЛИ-НЕ группыР выход переполнения -го счетчика . "веса" вершин группы соединен с вторыми входами вторых элементов И узлов -го столбца матричной модели 35 графа и с -м входом первого элемента ИЛИ, выход которого через первый элемент НЕ подключен к второмувходу второго элемента И, выход первого элемента ИЛИ соединен с вторымвходом первого элемента И устройства, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродействия устройства, в него введеныгруппа из (и - 1) элементов НЕ,второй и третий элементы НЕ, второйэлемент ИЛИ, третий, четвертый и пятый элементы И и триггер, выход дго регистрирующего триггера группысоединен с входом К-го элемента НЕгруппы (К = 2,3,и), выход которого соединен с входами 1-х элементов И четвертой группы (11,2- 1), выход д-го элементаИ третьей группы соединен с д-м входом второго элемента ИЛИ, выход которого соединен с входом второгоэлемента НЕ, выход которого подключен к первому входу третьего элемента И, выход которого соединен с первым входом триггера, инверсный выходкоторого подключен к первому входупятого элемента И, выход второго элемента ИЛИ,соединен с первым входомчетвертого элемента И, выход которого подключен к второму входу триггера, выход второго элемента И соединен с вторым входом -го элементаИ четвертой группы, с вторыми входами третьего и четвертого элементов И и с входом третьего элементаНЕ, выход которого соединен с вто-рым входом пятого элемента И, выходкоторого является выходом устройства.