Устройство для вычисления характеристик сетевых графов

)4 С 06 Р 5 ПИСАНИЕ ИЗОБРЕТЕНИЯ ля цифровых зволяет опр тестов д ство по минимал вающих ния явл ого множ тевой гр ется упро е надежно выше ни держи кажды Устроиств вателей д дуги сод та И, ус нератор элементо ержит триг тройство т импульсов, в И, счетчи риггер, восе дешифратор два регистра, накапливающий тор, два сумматора, две гру ментов ИЛИ, две группы элем группу реверсивных счетчико пу элементов задержки, групп геров, два регистра и линию ки. 1 з,п. ф-лы, 3 ил. апы элегрупи рж Ж ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ К АВТОРСКОМУ СВИ ЕТЕЛЬСТ(56) Авторское свидетельство СССР В 959090, кл. С 06 Р 15/20, 1980,Авторское свидетельство СССР У 991434, кл. С 06 Р 15/20, 1981.Авторское свидетельство СССР 9 1242982, кл. С 06 Г 15/20, 1984. ,(54) УСТРОЙСТВО ДЛЯ ВИЧИСЛЕНИЯ ХАРАКТЕРИСТИК СЕТЕВЫХ ГРАФОВ ,(57) Изобретение относится к области вычислительной техники и может быть использовано при исследовании сетевых графови построении проверяющих устроиств. Устройеделять величинуства путей, покрыф. Целью изобретеение устройства ити его работы.т матрицу формирой формировательгер и два элеменакже содержит ге 1 12903Изобретение относится к вычислительной технике и может быть использовано при исследовании сетевых гра. -фов и построении проверяющих тестовдля цифровых устройств, 5Целью изобретения является упрощение устройства и повышение надежности еНа фиг. 1 приведена структурнаясхема устройства, фиг. 2 - сетевой 10граф 6= (Х, Я) 9 где Х - множе ство вершин; И - множество дуг графа; нафиг. 3 - таблица, в которой для сетевого графа по фиг, 2 определены ИЧ. 9 11 - количество соответственновходных и выходных дуг вершины Х+9Ч. 9 Ы, - количество соответственновходных и выходных дуг для вершин,принадлежащих 1-му рангу. 20Если в сетевых графах отсутствуютпетли и циклы, то задача определенияминимального множества путей, покры -вающих сетевой граф адекватна опти 9мизационной задаче, в которой определяется максимальное число дуг, при -надлежащих разрезу д-го ранга средивсех рангов сетевого графа,Пусть 11, =И -4; И. =И;-М Тогда И, =ЕМ.30х,Определим понятие разреза 1-горанга, Для подмножества вершин А;,принадлежащих .-му рангу, характеризующегося Х е А разрезом -го рангасетевого графа называется множество 359У, дуг, выходящих из А,. КоличествоУф. дуг обозначим через М 9 т.е,(, АфЧ =1 Ул,.1Таким образ ом, формализ ованная40постановка задачи имеет следующий%вид: найти У =шах Ыл,Поскольку задача принадлежит кклассу дискретных оптимизационныхзадач, то ее решение в той или иной 45степени связано с перебором всевозможных решений и выбором среди нихлучшего. Алгоритм решения такой задачи сводится к проведению разрезасетевого графа для каждого ранга, 50вычислению М, и выбору среди нихмаксимальной величины, Однако устройство, реализующее такой алгоритм,имеет большие аппаратурные затраты,Для их уменьшения предлагается алгоритм решения задачи, основанный нарекуррентном соотношении9 9И =М. +И д =ОпД; 1 9 9 9причем У,.; =О,цля =О. 43 2Реализация такого алгоритма сводится к тому, что предварительно определяются величины ., (=09 п)9 адалее вычисляются И (1=0,п) с выФделением максимального значения Мсреди этих величин, Полученное значение У равно минимальному множеству путей, покрывающих сетевой граф.Устройство для вычисления характеристик сетевых графов содержит матрицу 1 формирователей дуг, причемкаждый формирователь дуги матрицы 1содержит триггеры 2 и элементы И 3,4; генератор 5 импульсов, триггер 6,элементы И 7, 8, счетчик 9, вход1 О запуска устройства, вход 11 установки нуля устройства, группу установочных входов 12 устройства, дешифратор 13, группу элементов ИЛИ 14,группы элементов И 15, 16, группуэлементов ИЛИ 17, группу реверсивныхсчетчиков 18, группу элементов 19 задержки, группу триггеров 20, элементИ 21, элементы И 22-2 б,элемент ИЛИ27, накапливающий сумматор 28, сумматоры 29 и 30, регистры 31 и 32, линию 33 задержкиЭлементы И 3 элемент ИЛИ 14; и реверсивный счетчик18; определяют число выходных дуг11 для Х,-й вершины графа.Триггер б совместно с элементамиИ 7, 8 и генератором 5 импульсовобеспечивают предварительный и основной режимы работы устройства, Впредварительном режиме импульсы через второй элемент И 8 поступаютна счетчик 9, Это вызывает поочередное возбуждение выходных шин дешифратора 13, что позволяет для каждойвершины графа с помощью группы реверсивных счетчиков 18 получить результирующую величину Я. между числом выходных и входных дуг, В основном режиме работы устройства импульсы через первый элемент И 7 поступают на управляющие входы элементов Итретьей группы 15 Ц=1, и) и входлинии 33 задержки, что позволяет определить минимальное множество путей,покрывающих сетевой граф,Входы 12;. устройства предназначены для занесения информации о топологии моделируемого графа. Элементы И 4, . совместно с элементом ИЛИ 17,. и вычитающим входомсчетчика 18, группы реверсивныхсчетчиков определяют число входныхдуг Ы, для Х;-й вершины графа3 129034Группа элементов И 15 совместнос элементом И 21 определяет моментокончания .работы устройства (нулевое состояние всех триггеров 2,1формирователей дуг).5Группа элементов И 1 б совместнос группой элементов 19 задержки,группой триггеров 20 и элементомИЛИ 27 передают содержимое группысчетчиков 1 8 на вход первого сумматора 28.Группа реверсивных счетчиков 18предназначена для определения результирующего соотношения между выходными и входными дугами Ч для каждой 15Хвершины графа,Группа элементов 19; задержки реализована таким образом, что выполняется соотношение Т.сТ где ;задержка д-го элемента, Выполнение 2 ртакого соотношения позволяет последовательно передавать на вход сумматора 28 содержимое реверсивных счетчиков 18 для вершин, принадлежащиходному и тому же рангу сетевого графа.Группа триггеров 20 обеспечиваетоднократную передачу содержимогореверсивных счетчиков 18 на вход1первого сумматора 28 при появлении 30упр авляюще го сигнала на выходе соответствующего элемента задержки,входящего в состав группы элементов19 задержки.Элемент И 21 определяет моментокончания работы устройства (нулевоесостояние всех триггеров 2, ) мат,рицы 1 формирователей дуг. Сумматор 28 является сумматоромнакапливающего типа. В нем вычисляется результирующая величина входных,и выходных дуг для вершин, принадлежащих -му рангу.Сумматор 29 является сумматоромкомбинационного типа, В нем опреде 45ляется количество дуг 1 д выходящихиз подмножества вершин А принадле"жащих разрезу х-го ранга графа.Сумматор 30 является сумматоромкомбинационного. типа и предназначендля определения величины И минимального множества путей, покрывающихсетевой граф,Сигналы на выходах линии 33 эадер -55 жки появляются последовательно на первом, втором и третьем выходах, причем длительность задержки на первом выходе превышает задержку пос 3 4леднего элемента 19 группы элементов 19,задержки.Устройство для вычисления характеристик сетевых графов работаетследующим образом.Первоначально в матрицу 1 заносится информация о топологии моделируемого графа сети, При этом триггеры 2 формирователей дуг, моделирующие ветви графа, устанавливаются вединичное состояние с помощью установочных входов устройства 12;, Соответствующие триггеры формирователей дуг определяются пересечениемстроки с номером, равным номеру начальной вершины моделируемой ветвии столбца с номером, равным номеруконечной вершины, После занесенияисходной информации на входах элементов И группы 15, соответствующихначальным вершинам моделируемогографа, устанавливаются высокие потенциалы, так как в однонаправленном графе без циклов и петель начальные вершины не содержат входящихветвей и триггеры формирователейдуг, находящиеся в этом столбце,находятся в нулевом состоянии. Триггер 6, группа триггеров 20, накапливающий сумматор 28, регистры 31и 32 установлены в нулевое состояние с помощью сигнала на входе 11устройства,С появлением пускового сигналана входе 10 устройства появляютсяимпульсы на выходе генератора 5 импульсов. Поскольку триггер 6 находится в нулевом состоянии, то импульсы с выхода генератора 5 импульсов через элемент И 8 поступают навход счетчика 9, что приводит к последовательному возбуждению выходныхшин дешифратора 13 и поступлению управляющих сигналов на входы элемен"тов И 3 и 4, Это позволяет подаватьна суммирующие входы группы реверсивных счетчиков 18 с помощью элементов И 3; и элементов ИЛИ 14группы число импульсов, соответствующих числу выходных дуг для Х; -йвершины графа (числу единичных состояний триггеров формирователей дуг2 , расположенных в д-й строке).Аналогично на вычитающие входы группы реверсивных счетчиков 18 с помощью элементов И 4 и элементов ИЛИ 17поступает число импульсов, соответствующих числу входных дуг для;Х -йвершины графа (числу единичных сос"5 12тояний триггеров 2 формирователейдуг, расположенных в -м столбце)В результате на выходе реверсивныхсчетчиков группы 18 получается числоУ , равное разности между числомвыходных и входных дуг для Х,-й вершины графа,Выходной сигнал с последней шиныдешифратора устанавливает триггер 6в единичное состояние. Это позволяетпривести устройство в режим вычисления минимального множества путей,покрывающих сетевой граф. В этом режиме работы импульсы через первыйэлемент И 7 поступают на входы элементов И группы 15 и вход линии 33задержки. Сигнал появляется на выходе тех элементов И 15 группы, которые соответствуют вершинам, принадлежащим -му рангу сетевого графа.Сформированные выходные сигналы сбрасывают триггеры формирователей дугстроки с номером, равным номерустолбца, и через соответствующий элемент задержки передают содержимоереверсивного счетчика в накапливающий сумматор 28, Выполнение соотношения 7.,(Т; для группы элементов 19задержки позволяет на первом сумматоре получить результирующую величинуМ выходных дуг для вершин, принадлежащих -му рангу. Далее на первомвыходе линии 33 задержки появляется. управляющий сигнал, позволяющий с помощью элементов И 22 и 25, сумматора29 получить на регистре 31 число дуг+11 , выходящих из подмножества вершйн А., принадлежащих разрезу -горанга графа (для нулевого ранга величины М и И совпадают) Сигнал соавторого выхода линии 33 задержкипоступает на входы элементов И 23 и24, которые совместно с сумматором30 позволяют проанализировать сост+ 4 +ношение величин Я, и У, =оах У+ -1А;причем если М Ы.", то величинаФА 1-1 ф11, с помощью элемента И 26 из ре 4;гистра 3 переписывается в регистр32,90343 6 Формула и зобр етения Вычислительный процесс продолжается до тех пор, пока все вершины графа не будут распределены по рангам. Этой ситуации соответствует сброс всех триггеров 2" формирователей дуг матрицы 1 в нулевое сос.тояние, появление на выходе элемен- та И 21 высокого потенциала и прекращение работыгенератора 5 импульсов.; 1. Устройство для вычисления характеристик сетевых графов, содержащее матрицу формирователей дуг; первую группу элементов ИЛИ по числу строк матрицы формирователей дуг, вторую группу элементов ИЛИ по числу столбцов матрицы формирователей дуг, первую группу элементов И по числу столбцов матрицы формирователей дуг, вторую группу элементов И, группу триггеров, генератор импульсов, первый элемент И, счетчик и дешифратор,:выход генератора импульсов подключен к первому входу первого элемента И, выход которого подключен к входу счетчика, выход которого подключен к входу дешифратора, первый информационный выход каждого 1-го формирователя дуги каждой 1-ой. строки матрицы подключен к 1-му входу д-го элемента ИЛИ первой группы (где 3=1,2,п), которой информационный выход каждого 1-го формирователя дуги каждого 1-го столбца матрицы подключены к 1-му входу 1-го элемента ИЛИ второй группы, первый информационный вход каждого 1-го формирователя дуги каждой 1-ой строки матрицы подключен к выходу 1.-го элемента И первой группы, выход каждого триггера группы подключен к первому входу одноименного элемента И второй группы, отличающее с я тем, что, с. целью упрощения устройства и повьппения надежности, в устройство введены группа реверсивных счетчиков, труппа элементов задержки, триггер, элемент ИЛИ, линия задержки, восемь элементов И, накапливающий сумматор, два сумматора и два.регистра, причем третий информационный выход каждого -го формирователя дуги каждого -го столбца матрицы подключен к х-му входу 1-го элемента И первой группы, вторые информационные входы формирователей дуг каждого 1-го столбца матрицы объединены и подключены к 1-му выходу первой груп пы выходов дешифратора, третьи информационные входы формирователейдуг каждой 1-й строки матрицы объединены и подключены к х-му выходу второй группы выходов дешифратора.Установочные входы формирователей дуг матрицы являются группой установочных входов устройства, вход запуска генератора импульсов является 1 О 15 РО 25 30 35 40 45 50 551290343 8 выходу пятого элемента И, выход первого сумматора подключен к информационному входу первого регистра, выход которого подключен к первым входам пятого, шестого и седьмого элементов И, выход шестого элемента Иподключен к первому входу второгосумматора, второй вход которого подключен к выходу восьмого элемента И, Ю выход второго сумматора подключен квторому входу седьмого элемента И,выход которого подключен к информационному входу второго регистра, выход второго регистра подключен к пер вому входу восьмого элемента И, вторые входы четвертого и пятого элементов И объединены и подключены кпервому выходу линии задержки, вторые входы шестого и восьмого элемен тов И объединены и подключены к второму выходу линии задержки, третийвход седьмого элемента И подключен ктретьему выходу линии задержки. входом запуска устройства, вход останова генератора импульсов подключен к выходу второго элемента И, каждый 1.-й вход которого подключен к выходу 1-го элемента И первой группы, прямой выход триггера подключен к первому входу третьего элемента И, второй вход которого подключен к выходу генератора импульсов, выход третьего элемента И подключен к (и+1)-му входу каждого из элементов И первой группы и к входу линии задержки, инверсный выход триггера подключен к второму входу первого элемента И, вход установки в единицу триггера подключен к последнему выходу второй группы выходов дешифратора, вход установки в нуль триггера объединен с входами установки в нуль триггеров группы, объединен с входом установки в нуль накапливающего сумматора, объединен с входами установки в нуль первого и второго регистров и является входом установки нуля устройства, выход каж. 25 дого из элементов ИЛИ первой группы подключен к суммирующему входу одноименного реверсивного счетчика группы, а выход каждого элемента ИЛИ второй группы подключен к вычитаю- ЗО щему входу одноименного реверсивного счетчика группы, выход которого подключен к второму входу одноимен. - ного элемента И группы, выход каждо го элемента И первой группы подключен 35 к входу одноименного элемента задержки группы, выход которого подключен к третьему входу одноименного элемента И второй группы, выход каждого д-го элемента И второй группы под ключен к 1.-му входу элемента ИЛИ, выход которого подключен к информационному входу накапливающего сумматора, выход которого подключен к первому входу четвертого элемента И, 45 выход четвертого элемента И подключен к первому входу первого сумматора, второй вход которого. подключен к 2. Устройство по п. 1, - о т л ич а ю.щ е е с я тем, что формирователь дуги содержит триггер и дваэлемента И, причем вход установки вединицу триггера является установочным входом Формирователя дуги, входустановки в нуль триггера являетсяпервым информационным входом Формирователя,дуги, прямой выход триггера подключен к первым входам первогои второго элементов И, второй входпервого элемента И является вторыминформационным входом формирователядуги, второй вход второго элемента Иявляется третьим информационным входом формирователя дуги, выходпервого элемента И является первым информационным выходом Формирователя дуги, выход второгоэлемента И является вторым информационным выходом формирователя дуги,а инверсный выход триггера являетсятретьим информационным выходом Формирователя дуги, 12903431290343х Яиг,бруча Корректор Техред Л, Сердюкова Рыбченк аз 7904/48 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открцтий 113035, Москва, Ж, Раушская наб., д. 4/5