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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

43 А1 (19) 01) (51)4 G 06 Р )5/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3900065/24-24 (22) 21 ° 05.85 (46) 15 .02.87, Бюл. ¹ 6 (72) В,А. Осипов, И.А. Баранов, А.И. Бобровский, Р,Г. Ноткин и А. В. Мазин (53) 681. 333(088. 8) (56) Авторское свидетельство СССР № 959090, кл. 6 06 Р 15/20, 1980, Авторское свидетельство СССР

¹ 991434, кл. G 06 F 15/20, )981.

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

¹ 1242982, кл. G 06 F 15/20, )984. .(54) УСТРОЙСТВО ДЛЯ ВИЧИСЛЕНИЯ ХАРАКТЕРИСТИК СЕТЕВЫХ ГРАФОВ ,(57) Изобретение относится к области вычислительной техники и может быть использовано при исследовании сетевых графови построении проверяющих тестов для цифровых устройств. Устройство позволяет определять величину минимального множества путей, покрывающих сетевой граф, Целью изобретения является упрощение устройства и повышение надежности его работы.

Устройство содержит матрицу формирователей дуг, каждый формирователь дуги содержит триггер и два элемента И, устройство также содержит генератор импульсов, триггер, восемь элементов И, счетчик, дешифратор, два регистра, накапливающий сумматор, два сумматора, две группы элементов ИЛИ, две группы элементов И, группу реверсивных счетчиков, группу элементов задержки, группу триггеров, два регистра и линию задержки. I з,п. ф-лы, 3 ил.

1 12903

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

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

На фиг. 1 приведена структурная схема устройства, фиг. 2 — сетевой

rp аф G= (Х, W), где Х вЂ” множе ство вершин; W — множество дуг графа; на фиг. 3 — таблица, в которой для сетевого графа по фиг, 2 определены 1!. 9

W . W„ — количество соответственно

I входных и выходных дуг вершины Х

+, 9

W. W, — количество соответственно входных и выходных дуг для вершин, принадлежащих 1-му рангу. 20

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

95 мизационной задаче, в которой определяется максимальное число дуг, при— надлежащих разрезу i-го ранга среди всех рангов сетевого графа, — t

Пусть W„, =1! -W„,; W. =W;-W;, Тогда W, =KW„.

30 х, Определим понятие разреза i-ro ранга, Для подмножества вершин А;, принадлежащих ) -му рангу, характеризующегосяя Х е А., разрезом i-го ранга сетевого графа называется множество 35

У, дуг, выходящих из А,. Количество

У+. дуг обозначим через W т.е.

I <. Аа !

1„ . = !уд;!

Таким образ ом, формализ ованная

40 постановка задачи имеет следующий

* вид: найти W =max W л, Поскольку задача принадлежит к классу дискретных оптимизационных задач, то ее решение в той или иной 45 степени связано с перебором всевозможных решений и выбором среди них лучшего. Алгоритм решения такой задачи сводится к проведению разреза сетевого графа для каждого ранга, 5л

t вычислению W, и выбору среди них максимальной величины. Однако устройство, реализующее такой алгоритм, имеет б ол ьши е аппар ат урные э атр аты, Для их уменьшения предлагается алгоритм решения задачи, основанный на рекуррентном соотношении

9 Ф

W =М„. +W i =On

А \ 9 9 9 причем W<; =О,цля =0.

43 2

Реализация такого алгоритма сводится к тому, что предварительно определяются величины !,- (i=0,п), а далее вычисляются И (i=O,n) с вы 1

1f делением максимального значения W среди этих величин, Полученное значение W равно минимальному множеству путей, покрывающих сетевой граф.

Устройство для вычисления характеристик сетевых графов содержит матрицу 1 формирователей дуг, причем каждый формирователь дуги матрицы 1 содержит триггеры 2 и элементы И 3, 4; генератор 5 импульсов, триггер 6, элементы И 7, 8, счетчик 9, вход !

О запуска устройства, вход ll установки нуля устройства, группу установочных входов 12 устройства, дешифратор 13, группу элементов ИЛИ 14, группы элементов И 15, 16, группу элементов ИЛИ 17, группу реверсивных счетчиков 18, группу элементов 19 задержки, группу триггеров 20, элемент

И 21, элементы И 22-26,элемент ИЛИ

27, накапливающий сумматор 28, сумматоры 29 и 30, регистры 31 и 32, линию 33 задержки ° Элементы И 3;, элемент ИЛИ 14; и реверсивный счетчик

18; определяют число выходных дуг

W. для Х,-й вершины графа.

Триггер б совместно с элементами

И 7, 8 и генератором 5 импульсов обеспечивают предварительный и основной режимы работы устройства, В предварительном режиме импульсы через второй элемент И 8 поступают на счетчик 9, Это вызывает поочередное возбуждение выходных шин дешифратора 13, что позволяет для каждой вершины графа с помощью группы реверсивных счетчиков 18 получить результирующую величину Wx. между числом выходных и входных дуг. В основном режиме работы устройства импульсы через первый элемент И 7 поступают на управляющие входы элементов И третьей группы 15„ (j=19 и) и вход линии 33 задержки, что позволяет определить минимальное множество путей, покрывающих сетевой граф.

Входы 12;. устройства предназначены для занесения информации о топологии моделируемого графа.

Элементы И 4., совместно с эле-! ментом ИЛИ 17,. и вычитающим входом счетчика 18; группы реверсивных счетчиков определяют число входных дуг W„, для Х;-й вершины граф1„

3 129034

Группа элементов И 15 совместно с элементом И 21 определяет момент окончания .работы устройства (нулевое состояние всех триггеров 2, 1 формирователей дуг).

Группа элементов И 16 совместно с группой элементов 19 задержки, группой триггеров 20 и элементом

ИЛИ 27 передают содержимое группы счетчиков 1 8 на вход первого сумма- Щ тора 28.

Группа реверсивных счетчиков 18 предназначена для определения результирующего соотношения между выходными и входными дугами W для каждой 15

Х1 вершины графа, Группа элементов 19; задержки реализована таким образом, что выполняется соотношение Т Т;„, где ; задержка i-го элемента, Выполнение 20 такого соотношения позволяет после довательно передавать на вход суммагора 28 содержимое реверсивных счетчиков 18 для вершин, принадлежащих одному и тому же рангу сетевого гра- 25 фа.

Группа триггеров 20 обеспечивает однократную передачу содержимого реверсивных счетчиков 18 на вход

1 первого сумматора 28 при появлении 30 упр авляюще ro сигнала на выходе соответствующего элемента задержки, входящего в состав группы элементов

19 задержки.

Элемент И 21 определяет момент окончания работы устройства (нулевое состояние всех триггеров 2;„) мат,рицы 1 формирователей дуг.

Сумматор 28 является сумматором накапливающего типа. В нем вычисляется результирующая величина входных, и выходных дуг для вершин, принадлежащих i-му рангу.

Сумматор 29 является сумматором комбинационного типа, В нем опреде45 ляется количество дуг Ъ1д., выходящих

A1 из подмножества вершин А,, принадлежащих разрезу i-го ранга графа.

Сумматор 30 является сумматором комбинационного. типа и предназначен для определения величины W минимального множества путей, покрывающих сетевой граф, Сигналы на выходах линии 33 эадер -55 жки появляются последовательно на первом, втором и третьем выходах, причем длительность задержки на первом выходе превышает задержку пос3 4 ледне го элемент а 1 9„группы элементов 19., задержки.

Устройство для вычисления характеристик сетевых графов работает следующим образом.

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа сети, При этом триггеры 2;; формирователей дуг, моделирующие ветви графа, устанавливаются в единичное состояние с помощью установочных входов устройства 12;„, Соответствующие триггеры формирователей дуг определяются пересечением строки с номером, равным номеру начальной вершины моделируемой ветви и столбца с номером, равным номеру конечной вершины. После занесения исходной информации на входах элементов И группы 15, соответствующих начальным вершинам моделируемого графа, устанавливаются высокие потенциалы, так как в однонаправленном графе без циклов и петель начальные вершины не содержат входящих ветвей и триггеры формирователей дуг, находящиеся в этом столбце, находятся в нулевом состоянии. Триггер 6, группа триггеров 20, накапливающий сумматор 28, регистры 31 и 32 установлены в нулевое состояние с помощью сигнала на входе 11 устройства, С появлением пускового сигнала на входе 10 устройства появляются импульсы на выходе генератора 5 импульсов. Поскольку триггер 6 находится в нулевом состоянии, то импульсы с выхода генератора 5 импульсов через элемент И 8 поступают на вход счетчика 9, что приводит к последовательному возбуждению выходных шин дешифратора 13 и поступлению управляющих сигналов на входы элемен" тов И 3 и 4, Это позволяет подавать на суммирующие входы группы ревер-. сивных счетчиков 18 с помощью элементов И 3 „. и элементов ИЛИ 14 группы число импульсов, соответствующих числу выходных дуг для Х; -й вершины графа (числу единичных состояний триггеров формирователей дуг

2, расположенных в i-й строке).

Аналогично на вычитающие входы группы реверсивных счетчиков 18 с помощью элементов И 4 и элементов ИЛИ 17 поступает число импульсов, соответствующих числу входных дуг для;Х -й вершины графа (числу единичных сос"

5 12 тояний триггеров 2,.; формирователей дуг, расположенных в j -м столбце) °

В результате на выходе реверсивных счетчиков группы 18 получается число

W равное разности между числом выходных и входных дуг для Х.-й вершины графа.

Выходной сигнал с последней шины дешифратора устанавливает триггер 6 в единичное состояние. Это позволяет привести устройство в режим вычисления минимального множества путей, покрывающих сетевой граф. В этом режиме работы импульсы через первый элемент И 7 поступают на входы элементов И группы 15 и вход линии 33 задержки. Сигнал появляется на выходе тех элементов И 15 группы, которые соответствуют вершинам, принадлежащим i-му рангу сетевого графа.

Сформированные выходные сигналы сбрасывают триггеры формирователей дуг строки с номером, равным номеру столбца, и через соответствующий элемент задержки передают содержимое реверсивного счетчика в накапливающий сумматор 28, Выполнение соотношения 7, Т;„ для группы элементов 19 задержки позволяет на первом сумматоре получить результирующую величину

W. выходных дуг для вершин, принадлежащих i-му рангу. Далее на первом выходе линии 33 задержки появляется . управляющий сигнал, позволяющий с помощью элементов И 22 и 25, сумматора

29 получить на регистре 31 число дуг

11, выходящих из подмножества вершйн А,, принадлежащих разрезу i-ro ранга графа (для нулевого ранга величины W u W совпадают). Сигнал с о о второго выхода линии 33 задержки поступает на входы элементов И 23 и

24, которые совместно с сумматором

30 позволяют проанализировать сост+ 4. + ношение величин W, и W, ax W

+ (- 1

А; причем если W Ы.", то величина

+ А i-!

W . с помощью элемента И 26 и з реА; гистра 3! переписывается в регистр

32, 90343 6

Формула и зобр етения

Вычислительный процесс продолжает ся до тех пор, пока в се в ер шины графа не будут распределены по ранraM. Этой ситуации соответствует сброс всех триггеров 2„" формирователей дуг матрицы 1 в нулевое сос.тояние, появление на выходе элемента И 21 высокого потенциала и прекращение работыгенератора 5 импульсов.;

1. Устройство для вычисления характеристик сетевых графов, содержащее матрицу формирователей дуг; первую группу элементов ИЛИ по числу строк матрицы формирователей дуг, вторую группу элементов ИЛИ по числу столбцов матрицы формирователей дуг, перву!ю группу элементов И по числу столбцов матрицы формирователей дуг, вторую группу элементов И, группу триггеров, генератор импульсов, первый элемент И, счетчик и дешифратор,:выход генератора импульсов подключен к первому входу первого элемента И, выход которого подключен к входу счетчика, выход которого подключен к входу дешифратора, первый информационный выход каждого j-го формирователя дуги каждой i-ой. строки матрицы подключен к j-му входу i-го элемента ИЛИ первой группы (где

j=1,2„. ° .,n), второй информационный выход каждого j-го формирователя дуги каждого j-ro столбца матрицы подключены к i-му входу j-ro элемента

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

i-ro столбца матрицы объединены и подключены к j-му выходу первой груп. пы выходов дешифратора, третьи информационные входы формирователей дуг каждой i-й строки матрицы объединены и подключены к i-му выходу второй группы выходов дешифратора.

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

1290343 8 выходу пятого элемента И, выход первого сумматора подключен к информационному входу первого регистра, выход которого подключен к первым входам пятого, шестого и седьмого элементов И, выход шестого элемента И подключен к первому входу второго сумматора, второй вход которого подключен к выходу восьмого элемента И, f0 выход второго сумматора подключен к второму входу седьмого элемента И, выход которого подключен к информационному входу второго регистра, выход второго регистра подключен к первому входу восьмого элемента И, вто рые входы четвертого и пятого эле1 ментов И объединены и подключены к первому выходу линии задержки, вторые входы шестого и восьмого элемен20 тов И объединены и подключены к второму выходу линии задержки, третий вход седьмого элемента И подключен к третьему выходу линии задержки. входом запуска устройства, вход останова генератора импульсов подключен к выходу второго элемента И, каждый i-й вход которого подключен к выходу i-го элемента И первой группы, прямой выход триггера подключен к первому входу третьего элемента И, второй вход которого подключен к выходу генератора импульсов, выход третьего элемента И подключен к (и+1)-му входу каждого из элементов И первой группы и к входу линии задержки, инверсный выход триггера подключен к второму входу первого элемента И, вход установки в единицу триггера подключен к последнему выходу второй группы выходов дешифратора, вход установки в нуль триггера объединен с входами установки в нуль триггеров группы, объединен с входом установки в нуль накапливающего сумматора, объединен с входами установки в нуль первого и второго регистров и является входом установки нуля устройства, выход каж- 25 дого из элементов ИЛИ первой группы подключен к суммирующему входу одноименного реверсивного счетчика группы, а выход каждого элемента ИЛИ второй группы подключен к вычитаю- 30 щему входу одноименного реверсивного счетчика группы, выход которого подключен к второму входу одноимен.— ного элемента И группы, выход каждо го элемента И первой группы подключен3 к входу одноименного элемента задержки группы, выход которого подключен к третьему входу одноименного элемента И второй группы, выход каждого

i-го элемента И второй группы под- 40 ключен к i-му входу элемента ИЛИ, выход которого подключен к информационному входу накапливающего сумматора, выход которого подключен к первому входу четвертого элемента И, 45 выход четвертого элемента И подключен к первому входу первого сумматора, второй вход которого. подключен к

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

1290343

1290343 х

Оране рп е 2роие 3perea 4 рте

Я г 2

И, Р б енко ТехредЛ.Сердюкова

Заказ 7904/48 Тираж 673 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проект ая, оектная 4