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

 

Изобретение относится к вычислительной технике и может быть использовано для определения характеристик связности графов , в частности, для разбиения графа на сильные компоненты при структурном анализе сложных систем. Цель изобретения состоит в расширении функциональных возможностей за счет разбиения графа на сильные компоненты. Устройство содержит наборное поле с выпрямительными элементами, генератор тактовых импульсов, три счетчика, три дешифратора, шесть элементов И, четыре группы элементов И, три элемента НЕ, две группы из N регистров (N - число вершин исследуемого графа), две матрицы N<SP POS="POST">.</SP>N элементов И, N-1 коммутаторов - мультиплексоров, элемент задержки. 6 ил.

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

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

РЕСПУБЛИК

5 8229 А1 (19) (11) (51) 4 G 06 F 15/20

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

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ элементов И 5,-5„, 6q-6„, 8,-8, 9„ -9д, образующих матрицу из пхп элементов И (n — число вершин графа), .вход 10 пуска устройства, дешифратор 11, счетчик 12, первый элемент И 13, элемент HE 14, генератор 15 тактовых импульсов, второй элемент И 16, наборное поле 17, вып, рямительные элементы !8, третий 19 и четвертый 20 элементы И, второй счетчик 21, второй элемент НЕ 22, второй дещифратор 23, пятый 24 и

° шестой 25,элементы, И< третий счетчик

26, третий дешифратор 27, третий элемент НЕ 28, вторую группу регистров 29,-29п и групп элементов И

30(-30,, 31„-31„, 32<-32„, 33)-33),, 34 -34„, образующих вторую матрицу иэ пКп элементов И, третью группу элементов И 35, и-1 коммутатор-муль-. типлексор 36 -36„,четвертую группу

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4122839/24-24 (22) 16.06.86 (46) 15.09.89. Бюл. У 34 (72) E.È. Бороденко, В.Е. Назаренко, В.В, Верияскин и И.С. Бондарь (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 637822, кл. С 06 F 15/20, 1978.

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

N - 1174937, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ГРАФОВ (57) Изобретение .относится к вычислительной технике и может быть использовано для определения характеристик связности графов, в частносИзобретение относится к вычислительной технике и может быть использовано для определения характеристик

,связности графов, в частности для разбиения графа на сильные компоненты при структурном анализе сложных систем.

Цель изобретения — расширение функциональных возможностей за счет . разбиения графа на сильные компоненты, На фиг,1 и 2 представлена функциональная схема устройства; на фиг.3— граф на фиг. 4 и 5 — матрицы достижимостей (R) и контрдостижимостей, 1 (q) соответственно; на фиг. 6 — их прямое произведение (матрица R®Q) .

Устройство содержит первую группу элементов И 1<-1„, вторую группу элементов И 24-2)1, вход 3 сброса

A.

:устройства, регистры1 4 -4 и, n групп

2 ти для разбиения графа на сильные компоненты при структурном анализе сложных систем. 11ель изобретения состоит в расширении функциональных возможностей за счет разбиения графа на сильные компоненты. Устройство содержит наборное поле с выпрямительными элементами, генератор тактовых импульсов, три счетчика, три дешифратора, шесть элементов И, четыре группы элементов И, три элемента НЕ, две группы из и регистров (n — число вершин исследуемого графа), две матрицы пКп элементов И, п 1 коммутато- . ров-мультиплексоров, элемент задерж- ки, 6 ил.

8229

3 150 элементов 37<-37„,и элемент 38 задержки.

Устройство работает следующим образом.

В пол е 7 набир ает ся т о поло гия графа путем включения выпрямительных элементов ) 8. При подаче сигнала на вход 3 счетчики )2, 2) и 26 и регистры 4 -4 „, и 29„-29„устанавливаются и нулевое состояние. Дпя запуска устройства подается потенциал "1" на вход 10 пуска устройства, через элемент И ) 6 тактовые импульсы с выхода генератора 15 поступают на элемент И 13, которыи в исходном состоянии открыт, так как на (и+1)-м выходе дешифратора 11 присутствует потенциал "0" . Потенциал "1" с выхода элемента НЕ 14 открывает также элементы И 2.

После записи в счетчик 12 первого импульса на первом выходе дешифратора 11 устанавливается потенциал

"1",который поступает на элементы

И 5, открывает их и подключает входы регистра 4 к выходам соответствующих элементов И 2 „-2,. Потенциал

"1" с первого выхода дешифратора 11 подается также на первый столбец наборного поля 17 и устанавливает пер-. вый разряд регистра 4 в единичное состояние.

Пример. Пусть исследуемый граф имеет вид, показанный на фиг.3, На наборном поле 17 с помощью элементов 18 набрана структура графа. Через элемент И 1 < единичный потенциал поступает на первую строку наборного поля )7 и через элементы 18 < и 2 устанавливает третий разряд регистра 4 „н "1", поступает через элемент И 1 на третью строку и и и через элемент 18 записывает 1 в четвертый разряд регистра 4 <, поступает через элемент И 1 на четвер-; тую строку. После прихода второго импульс с а уровень l появляет ся на втором выходе дешифратора 11, а на первом выходе устанавливается потенциал

"0", который отключает р егистр 4 от наборного поля. Одновременно снимается "1 с первого- столбца. Hpè.ничный потенциал с второго выхода дешифратора 11 открывает элементы

И 6, -6„, а также подается на второй столбец наборного поля. Далее работа устройства аналогична описанной в

1 первом такте. С приходом третьего и

55 четвертого тактовых импульсон информация о достижимости вершин графа записывается в регистры 4 и 4 . С приходом (и+1)-го тактового импульса на выходе элемента НЕ 14 появляется потенциал "1", который запрещает дальнейшее прохождение тактовых импульсов н счетчик 12 и закрынает элементы И 2.g-2, отключая столбцы наборного поля 17 от регистров 4„";4„.

В результате в регистрах 4 -4 содержится матрица R достижимостей исследуемого графа. На этом заканчивается первый этап работы устройства.

Как видно из фиг.4, на которой представлена матрица достижимостей

R графа, на фиг ° 5, на которой представлена матрица контрдостижимостей

Я того же графа, матрицу контрдостижимостеч R графа можно получить из матрицы достижимостей путем замены строк на столбцы. Поэтому для того, чтобы найти прямое произведение матриц RO>Q достаточно перемножить строки на столбцы матрицы достижимостей.

Этот процесс осуществляется на вто- ром этапе работы устройстна. Напряжение на (и+1)-м выходе дешифратора

11 открывает элемент И 18 и тактовые импульсы с генератора 15 начинают поступать на элемент И 20, открытый потенциалом "1", .поступающим с выхода элемента НЕ 22. К первым входам элементов И 30,-30„ подключены информационные выходы одноименных разрядов регистра 4, в котором записа"

7 на первая строка матрицы достижимост ей rp афа, т . е. код 101 1. Вторые входы элементов И 30„-30 подключены к выходам первых разрядов регистров

4 -4„,в которых записан первый столбец матрицы достижимостей (соответствующий первой строке матрицы контрдостижимостей ), т. е, комбинация 1111.

При поступлении первого тактового импульса на счетчик 21 на первом вы- ходе дешифратора 23 появляется единичный потенциал, поступающий на третьи входы элементов И 30, -30< первой строки матрицы. При этом происходит логическое перемножение первой строки и .первого столбца матрицы достижимостей. Таким образом, в первой строке матрицы К®0 (в регистре 29 ) записывается комбинация 1011. При поступлении очередных тактоных импульсов происходит перемножение оче" редных одноименных строк и столб5

15

25

5 15 цов матрицы достижимостей, что соответствует перемножению одноименных строк матриц достижимостей и контрдостижимостей R u Q. При поступлении 5-ro тактового импульса на 5-м выходе денифратора 23 появляется единичный потенциал 1на всех остальных выходах — нулевой потенциал}, который запрещает через элемент И 20 дальнейшее прохождение тактовых импульсов на счетчик 21. В регистрах

29 -29ц записана матрица КЩ (фиг.б).

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

На третьем этапе производится разбиение графа на сильные компоненты.

На первый вход элемента И 24, открытого по второму входу, поступают тактовые импульсы с генератора 15. Первые информационные входы коммутаторов-мультиплексоров подключены к соответствующим информационным выходам первого регистра 29,, вторые входы— к соответствующим информационным выходам второго регистра и т.д. При поступлении первого тактового импульса на элемент И 25, открытый единичным потенциалом с выхода элемента

НЕ 28, в счетчик 26 записывается "1" и на адресные входы коммутаторовмультиплексоров поступает единичный адрес. При этом на выход коммутаторов-мультиплексоров подключены соответствующие разряды регистра 29 .

Так как в первом регистре 29< записана комбинация lOll на первые входы элементов И 371 37, 374. подаются уровни напряжения "1", на 37 — "0".

Через время t = Тс„ /2 (где Т > период следования тактовых импульсОв) на вторые входы поступает тактовый импульс, который через элементы

И 37 и 37 стирает информацию в регистрах 29> и 29+ При поступлении второго тактового импульса на элементы И 37(-37q подается комбинация

0100 (во втором регистре 29 записана комбинация 0100). Через время второй тактовый импульс не стирает информацию ни в одном из регистров.

Во втором регистре 29 остается комбинация 0100. Аналогично при третьем такте также не стирается информация ни в одном из регистров 29, -29„, а в регистрах 29> 294 остается комбинация 0000. С приходом четвертого тактового импульса на 4-м выходе дешифратора 27 появляется напряжение ло08229 6 гической "1", которое через элемент

28 HF. закрывает элемент И 25. На этом работа устрой тва прекращается.

Элементы индикации, подключенные к информационным выходам регистров

29)-29, высвечивают в первой строке комбинацию Х„, Х, Хл,, во второй " Х . Эти вершины графа соответствуют его двум сильным компонентам—

X<, X» Х и Х . Элементы И 37 служат для развязки управляющих входов регистров 29 °

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

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

И второй группы, выход каждого из элементов И второй группы соединен с первым и вторым входом одноименного элемента И первой группы и с первыми входами элементов И одноименной строки матрицы, выходы элементов И столбца матрицы соединены с входами разрядов одноименного регистра группы, вход сброса устройства соединен с входом сброса счетчика и входами сброса регистров группы, счетный вход счетчика подключен к выходу первого элемента И, первый вход которого соединен с выходом второго элемента И, а второй вход соединен с выходом элемента НЕ и вторыми входами элементов И второй группы, вход элемента HF соединен с (и+1)-м выходом дешифратора, выходы разрядов счетчика подключены к информационному входу дешифратора, первый вход второго элемента И является входом пуска устройства, второй вход первого элемента И .подключен к выходу генератора тактовых импульсов, р-е выходы дешифратора (р 1,2,...,n) соединены с вторыми входами элемен1508229 тов И р-го столбца матрицы, о т л и-. ч ающе е ся тем, что, сцелью расширения функциональных возможностей за счет разбиения графа на сильные компоненты, в него введены третий, четвертый, пятый и шестой элементы И, второй и третий счетчики, второй и третий дешифраторы, второй и третий элементы НЕ, вторая группаиз и регистров, вторая матрица п п элементов И, третья и четвертая группы элементов И, и-1 ком)мутаторов-мультиплексоров, элемент задержки, выход которого соединен с первыми входами элементов И четвертой группы, вторые входы которых соединены с выходами соответствующих коммутаторов-мультиплексоров, выход р-ro элемента И четвертой группы (р=-1,2...,,n-l) соединен с входом сброса (р+1)-го регистра второй группы, выходы элементов И k-й строки второй матрицы (k=1,2,...,n) соединены с входами одноименных разрядов k-ro регистра второй группы, выход j-ro разряда i-го регистра

Второй группы (1=1,2 ° ° ° °,Г1-1,,)

+ l,...,n) соединен с i-м информационным входом (j-1)-го коммутатора мультиплексора, адресные вхо- ды коммутаторов-мультиплексоров сое.-. динены с выходом третьего счетчика, счетный вход второго подключен к выходу шестого элемента И, первый вход которого подключен к выходу пятого элемента И, а второй вход — к выходу третьего элемента НЕ, вход которого подключен к и-му выходу третьего дешифратора, первый вход пятого.элемента И подключен к выходу генератора тактовых импульсов, а второй вход

5 подключен к (и+1)-му выходу второго дешифратора, вход которого подключен к выходу второго счетчика, счетный вход которого подключен к выходу четвертого элемента И, первый вход

1Q которого подключен к выходу второго элемента НЕ, вход которого подключен к (n+1)-му выходу второго дешифратора, второй вход четвертого элемента

И соединен с выходом третьего эле15 мента И, первый вход которого подключен к выходу генератора тактовых импульсов, а второй вход — к (и+1)му выходу первого дешифратора, каждый выход второго дешифратора подклю20 чен к первым входам элементов И одноименной строки второй матрицы, второй вход i-ro элемента И j-й строки второй матрицы (i, j 1,2,...,п) подключен к j-му информационному выходу i-го регистра первой группы, третий вход i-го элемента И j-й строки второй матрицы (i j = I 2, ...,n) подключен к i-му информационному выходу j-го регистра первой

ЗО группы, вход элемента задержки подключен к выходу шестого элемента И, первый и второй входы элементов И третьей группы подключены к входу сброса устройства, к которому также

З5 подключены входы сброса второго и третьего счетчиков, выход элемента

И третьей группы подключен к входу сброса одноименного регистра второй группы. 1508229

1508229, .1508229

ФОГ. 3

2 У 4

3

Фиг. Ф Фиаf

Я 3

Составитель И. Ершов

Редактор Л, Пчолинская Техред А.Кравчук Корректор М, Самборская

Заказ 5542/51 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101