Устройство для определения связности графа

 

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

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

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

РЕСПУБЛИК (бд 4 G 06 F 15/20

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3827160/24-24 (22) 20. 12.84 (46) 15. 12.86, Вюл. ¹ 46 (71) Московский институт инженеров гражданской авиации (72) К.P.Ãóàðÿí и Н.В.Давыдов (53). 681.333(088.8) (56) Зыков А.А. Теория конечных графов. Новосибирск: Наука, 1969, с.543.

Авторское свидетельство СССР ,№ 896630, кл. G 06 F 15/20, 1980.

„„SU„, 12??130 А1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

СВЯЗНОСТИ ГРАФА (57) Изобретение относится к области вычислительной техники для определения связности графов и может быть использовано в сетях связи ЭВМ в качестве одного из модулей системы сетеметрии узла коммутации, Целью изобретения является увеличение быстродействия. Поставленная цель достигается тем, что в устройство для определения связности графов, содержащее пять групп элементов И, группу элементов ИЛИ, две группы триггеров, введены группа регистров, две группы схем сравнения, группа блоков сравне- с0 ния, группа элементов ИЛИ, два регистра, четыре элемента И, дешифратор (/) и блок управления. 1 з.п. ф-лы, 3 ил.

1 1277

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

На фиг.1 приведена блок-схема устройства для определения связности графа; на фиг.2 — функциональная схема блока управления; на фиг.3 — структурная схема одного из блоков сравнения.

Устройство для определения связности графа содержит дешифратор первый 2 и второй 3 элементы И„группу элементов И 4, первую группу элементов ИЛИ 5, группу элементов И 6, группу триггеров 7, группу элементов с

И 8, группу регистров 9, группу триггеров 10, группу блоков 11 сравнения, первый 12 и второй 13 регистры, третий 14 и четвертый 15 элементы И, первую группу схем 16 сравнения, вторую группу схем 17 сравнения„ группы элементов И 18, 19, вторую группу элементов ИЛИ 20, блок 21 управления, первый 22, второй 23, третий 24 и четвертый 25 выходы блока управления, вход 26 разрекгения опроса устройства, вход 37 номера начальной вершины отказавшей ветви графи устройства, вход 28 номера конечной вершины отказавшей ветви графа устройства, входы 29 задания топологии исследуемого графа устройства, выход 30 сигнала несвязности графа устройства, выход

31 сигнала связности графа устройства.

Блок 21 управления (фиг.2) содержит одновибратор 32, генератор 33 тактовых импульсов, кольцевой сдвиговый регистр 34, элемент И 35, элемент ИЛИ 36, элементы ЫЕ 37 и 38.

Блок 11 сравнения (фиг.3) содержит группу элементов И 39, группу схем 40 сравнения и элемент ИЛИ 41, Устройство работает следующим образом.

130

Б. Если не имеется ни одной выде/ ленной вершины, то выполняется операция В, иначе — операция Г.

В. Если сеть связи представлена в виде графа, образующего кольцо, то, начиная с любой вершины, выписывают по порядку (по часовой стрелке) все вершины, соединяя их знаком

Я . Перечень вершин заканчивают ноfQ мером той вершины, с которой было

I начато описание.

В противном случае берут любую вершину, у которой число выходных ветвей 1, и выписывают, начиная с

15 данной вершины, по порядку все вершины на пути к другой вершине, у которой число выходных ветвей =1. Номера вершин соединяют знаком Я . Заканчивают описание номером вершины

20 конца пути.

Описание графа составлено, Г. Берут любую выделенную вершину.

Д. По каждому выходному направлению (линии связи) описывают путь

25 (путем перечисления вершин и соединения их знаком Б>) до первой встречной выделенной вершины (включительно) либо до концевой вершины, если такая имеется. Помечают выделенный путь.

30 Е. Для всех остальных выделенных вершин описывают путь согласно операции Д по всем выходным ветвям, не входящим в помеченные (описанные) пути °

Ж. Полученные отдельные описания путей соединяют знаком 8 в единое выражение — описание графа.

В регистры 9 заносятся номера вершин, а значения триггеров 10 ус4Q танавливаются следующим образом: 0", если описание графа Б 1, если описание rpad>a Ц .

Если в сети связи ЭВМ вышла иэ

По входу 29 в регистры 9 и триггеры 10 записывается описание графа, которое составляется на основании графического изображения сети связи

ЗВМ следующим образом.

Л. На графе сети связи ЭВМ выделяют знаком 0 все те вершины, у которых число выходных ветвей >3 (связность больше 3). строя линия связи между вершинами

Х и 7, то их .номера подают соответственно на входы 27 и 28 устройства.

Эти номера записываются в регистры

12 и. 13. На вход 26 подают импульс опроса на проверку связности графа, который поступает на одновибратор 32 (фиг.2). Сигнал с выхода одновибратора 32 через элемент ИЛИ 36 открывает элемент И 35, и генератор 33 тактовых импульсов начинает произвоIt II дить циклический сдвиг кода. 0...01 записанного в сдвиговом регистре 34.

Сигналом "0" с выхода 22 блок 21 управления через элементы И 6 устанавливает триггеры 7 в нуль. Сигна3 l2 лом с выхода 25 блок 21 управления производит корректировку описания графа путем замены операции 2 на Щ между номерами соседних вершин Х и Y

Сравнение номеров вершин, описывающих отказавшую ветвь (линию связи), с номерами вершин в описании графа производится схемами сравнения 1б и

17. Если соседние номера вершин в описании графа Х и У, то элемент

ИЛИ 20 вырабатывает сигнал "1" и устанавливает триггер 10 в состояние

"0". Следующим сигналом (сигналом с выхода 23) блок 21 управления через элемент ИЛИ 5 и открытый элемент

И 6 устанавливает первый триггер 7 в состояние "1". Если триггер 10 находится в состоянии "1", операция И, то через открытий элемент И 8 следующий триггер 7 устанавливается в состояние "1" и т.д. Этот лавинообразный процесс заканчивается на первом же закрытом элементе И 8, т .е. на коде операции Щ . Одновременно с этим работают блоки 11 сравнения.

Если количество вершин в описании графа равно N, то число блоков 11 сравнения равно N-1. На вход элементов И 39 подается номер вершины (из регистра 9) и соответствующее данному номеру состояние триггера 27 связности (если триггер 7 находится в состоянии "1", то данная вершина доступна, если триггер 7 находится в состоянии "0" то — недоступна).

На вход блока 11 сравнения i-го узла (начиная с второго) подаются следующие сигналы (c».фиг.3): номер i-й вершины из регистра 9 подается на все схемы 40 сравнения (вход i) и не подается на входы элементов И 39; на вторые входы элементов И 39 подается сигнал с соответствующего триггера 7 связности.

Блок 11 сравнения определяет, доступен ли i-й узел хотя бы из одного уже доступного узла (узла, у которого триггер 7 связности находится в состоянии "1"). Сигналом с выхода блок 11 сравнения устанавливает соответствующий ему триггер

11 11 связности в состояние 1

Элементы И 8 предназначены для встречнсч установки триггеров 7 в состояние "1", в выражении между двумя знаками операций.

Если все триггеры 7 связностй установлены в состояние "1", то дешифратор 1 вырабатывает сигнал "1"

77130 4 о связности графа. Блок 21 управления сигналом с выхода 24 формирует импульс на одном из выходов устройства (на выходе 30 или 31). Появление "1" на выходе 30 свидетельствует о несвязности графа, а на выходе 31—

20

55 о связности.

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

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

1. Устройство для определения связности графа, содержащее первую, вторую, третью, четвертую и пятую группы элементов И, первую группу элементов ИЛИ, первую и вторую группы триггеров, выход каждого i-ro триггера (где i=1,2,...n) первой группы подключен к первым входам

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

j-ro элемента И третьей группы (где

j=1 2,...,(n+1)) подключен к выходу

j-го элемента ИЛИ второй группы, выход каждого j-ro элемента И третьей группы подключен к входу j -го триггера второй группы, выход каждого

j-ro триггера второй группы, кроме (n+1) — го, подключен к второму входу

i-ro (i=j ), выход каждого j-ro триггера второй группы, кроме первого, подключен к второму входу i-го элемента И второй группы (i=j-1), выход каждого i-го элемента И первой группы подключен к первому входу j-го элемента ИЛИ второй группы (i=j 1), первый вход первого элемента ИЛИ второй группы подключен к второму выходу блока управления, выход каждого i-го элемента И второй группы подключен к втброму входу j-го элемента ИЛИ второй группы (i=j), выход каждого j-го триггера второй группы подключен к

j ìó входу дешифратора и к 1-му входу первой группы входов блоков сравнения группы, второй вход каждого

5 12771 блока сравнения группы подключен к выходу соответствующего регистра группы, входы установки в единицу триггеров первой группы и установочные входы регистров группь:; явля- 5 ются входами задания топологии исследуемого графа устройства, вход ус.."ановки в нуль каждого триггера первой группы подключен к выходу одноименного элемента KIH первой группы, тре- 1|э тий выход блока управления подключен

t к первым входам первого и второго элементов Й, вторые входы которых объединены и подключены к выходу,цешифратора, выход первого элемента И f5 является выходом сигнала несвязности графа устройства, выход второго элемента И является выходом сигнала связности графа устройства, четвертыи выход блока управления подключен к д1 первым входам третьего и четзертога элементов И, второй вход третьего элемента И подключен к выходу первого регистра, второй вход четвертого элемента И подключен к выхоцу второго 25 регистра, вход первого регистра является входом номера начальной вершины отказавшей ветви графа устройства, вход второго регистра является входом номера конечной вершины отказав- ЗО шей ветви графа устройства, выход третьего элемента И подкл|очен к первым входам схем сравнения пергой группы, выход четвертого элемента И подключен к первым входам схем срав35 иения второй группы, втсэрые входы одноименных схем сравнения первой и второй групп обьединены и подключены к выхаду одноименнаго регистра группы, выход первой схемы сравнения первой группы подключен.к первому входу первого элемента И четвертой группы, выход первой схемы сравнения второй группы подключен к первому входу первого элемента И ля|ой группы, выход каждой ъ-й схемы сравнения (х=2,3,...,(п-1)) первой группы подключен к первому входу i-ro эгемента

И четвертой группы и к второму входу

30 6 (i-1)-го элемента И пятой группы, выход каждой э-й схемь; сравнения (i=2,,... (и 1)) ключен к первому входу э.-го элемента

И пятой группы и к второму входу (i-1)-го элемента И четвертой группы, Bblxop, и-й схемы сравнения первой группы подключен к второму входу (n-1)-го элемента И пятой группы, выход п é схемы сравнения второй группы подключен к второму входу (и-1)-го элемента И четвертой группы, выход каждогo i-ro элемента И четвертой группы подключен к первому входу i-го элемента ИЛИ первой группы, выход каждого i-ro элемента И пятой группы подключен к второму входу i-ra элемента ИЛИ первой группы, вход блока управления является входом разрешения опроса устройства, 2. устройство по п.1, о т л и ч а |о щ е е с я тем, чта Ьлак управления содержит генератор тактовых импульсов, элемент И, элемент ИЛИ, два элемента НЕ, одновибратар и кольцевой сдвиговый регистр, выход генератора тактовых импульсов подключен к первому входу элемента И, выход которого подкл|очен к входу кольцевого сдвигового регистра, выход первого разряда кольцевого сдвигового регистра подключен к |зходу первого элемента

БЕ, выход которого является соответственна первым выходам Ьлака управления, выходы второго, третьего и четвертого разрядов кольцевого сдвигового регистра являются соответственно вторым, третьим и четвертым выходами блока управления, ьыход последнего разряда кольцевого сдвигового регистра подключен к входу второго элемента HE выэ:Од ка roporo под ключен к первому входу элемента ИЛИ

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

taп зо

Составитель Т.Сапунова

Редактор И.Рыбченко Техред M.Õoäàíè÷ Корректор Г Решетник

Заказ 6669/44 Тираж 671 Подписное

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

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

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