Устройство для исследования параметров графов Советский патент 1989 года по МПК G06F15/173 

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

систем.

Цель изобретения - расширение функциональных возможностей за счет разбиения графа на сильные компоненты.

На 4ИГ.1 и 2 представлена функциональная схема устройства; на фиг.З - граф; на фиг. 4 и 5 - матрицы дости- ,жимостей (R) и контрдостижимостей (Q) соответственно; на фиг. 6 - их прямое произведение (матрица R®Q).

Устройство содержит первую группу элементов И вторую группу элементов И 21-2,вход 3 сброса :устройства, регист рЫ) 4i-4n, ,п групп

элементов И 5,-5, , 7/-7„,

,, 9д-9„, образующих матрицу из пхп элементов И (п - число вершин графа), вход 10 пуска устройства, дешифратор 11, счетчик 12, первьй элемент И 13, элемент НЕ 14, генератор 15 тактовых импульсов, второй элемент И 16, наборное поле 17, вып, ря ш1т.ельные элементы 18, третий 19 и четвертый 20 .э лементы И, второй счетчик 21, второй элемент НЕ 22, второй дешифратор 23, пятый 24 и

Шестой 25 :эдементы .И третий счетчик: 26, третий дешифратор 27, третий элемент НЕ 28, вторую группу регистров 294-29п п групп элементов И 30,-30„, , 32,-32п, 33,-33, ЗА,-34, образующих вторую матрицу

из niifn элементов И, третью группу элементов И 35 , п-1 ко.ммутатор-мхль- типпексор Зб4-36„о,,четвертую группу.

(Л

С

01

эо

ГС

ф

3-

элементов ., и элемент 38 задержки.

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

В поле 17 набирается топология графа путем включения выпрямительных элементов 18. При подаче сигнала на вход 3 счетчики 12, 21 и 26 и регистры 4,-4 п., и 29/-29п устаналиваются в нулевое состояние. Для запуска устройства подается потен

20

25

циал 1 на вход 10 пуска устройства, через элемент И 16 тактовые импульсы с выхода генератора 15 поступают на элемент И 13, который в исходном состоянии открыт, так как на (n-f-l)-M выходе дешифратора 11 присутствует потенциал О. Потенциал 1 с выхода элемента НЕ 14 открывает также элементы И 2.

После записи в счетчик 12 первого импульса на первом выходе дешифратора 11 устанавливается потенциал 1,который поступает на элементы И 5, открывает их и подключает входы регистра 4 к выходам соответствующих элементов И 2;,-2. Потенциал 1 с первого выхода дешифратора 11 подается также на первьш столбец наборного поля 17 и устанавливает вый разряд регистра 4 в единичное состояние.

Пример. Пусть исследуемый граф имеет вид, показанный на фиг.З. На наборном поле 17 с помощью элементов 18 набрана структура графа. Через элемент И 1( единичный потенциал поступает на первую строку наборного поля 17 и через элемен- 40 ты 1В( и 2 устанавливает третий разряд регистра 4 в 1, поступает через элемент И 1 -j на третью строку и через элемент 18з записывает 1 в

30

потенциал 1, который запрещает дальнейшее прохождение тактовых им пульсов в счетчик 12 и закрывает элементы И 2,-2р, отключая столбцы наборного поля 17 от регистров В результате в регистрах содержится матрица R достижимостей исследуемого графа. На этом заканчи 5 вается первый этап работы устройств

Как видно из фиг.4, на которой представлена матрица достижимостей R графа, на фиг.З, на которой представлена матрица контрдостижимостей Q того же графа, матрицу контрдости жимостей R графа можно получить из матрицы достижимостей путем замены строк на столбцы. Поэтому для того чтобы найти прямое произведение мат риц R®Q, достаточно перемножить стр ки на столбцы матрицы достижимостей Этот процесс осуществляется на втором этапе работы устройства. Напряж ние на ()-м выходе дешифратора 11 открывает элемент И 18 и тактовы импульсы с генератора 15 начинают поступать на элемент И 20, открытый потенциалом 1, .поступающим с выхода элемента НЕ 22. К первым входа 35 элементов И 30,-30, подключены информационные выходы одноименных раз

рядов регистра

в котором записа

на первая строка матрицы достижимое тей графа т.е. код 1011. Вт орые входы элементов И 30,-30, подключен к выходам первых разрядов регистров которых записан первый матрицы достижимостей (соответствующий первой строке матрицы контрдос

четвертый разряд регистра 4(, посту- 45 тижимостей), т.е. комбинация 1111.

пает через элемент И 1 на четвер-; тую строку. После прихода второго импульса уровень I появляется на втором выходе дешифратора 11, а на первом выходе устанавливается потенциал о, который отключает регистр 4 от наборного поля. Одновременно снимается 1 с первого-столбца. Еди- .ничный потенциал с второго выхода дешифратора П открывает элементы И 6,-6, а также подается на второй столбец наборного поля. Далее работа устройства аналогична описанной в первом такте. С приходом третьего и

При поступлении первого тактового I импульса на счетчик 21 на первом вы ходе дешифратора 23 появляется единичный потенциал, поступающий на

50 третьи входы элементов И , пе вой строки матрицы. При этом происходит логическое перемножение перво строки и .nejfBoro столбца матрицы до тижимостей. Таким образом, в первой

55 строке матрицы R®0 (в регистре 29) записывается комбинация 1011. При поступлении очередных тактовых им- пульсов происходит перемножение оче редных одноименных строк и столб

0

0

5

0

0

4

четвертого тактовых импульсов информация о достижимости вершин графа записывается в регистры 4 и 4;. С приходом (п+1)-го тактового импульса

на выходе элемента НЕ 14 появляется II ill

потенциал 1, который запрещает дальнейшее прохождение тактовых импульсов в счетчик 12 и закрывает элементы И 2,-2р, отключая столбцы наборного поля 17 от регистров . В результате в регистрах содержится матрица R достижимостей исследуемого графа. На этом заканчи- 5 вается первый этап работы устройства.

Как видно из фиг.4, на которой представлена матрица достижимостей R графа, на фиг.З, на которой представлена матрица контрдостижимостей Q того же графа, матрицу контрдостижимостей R графа можно получить из матрицы достижимостей путем замены строк на столбцы. Поэтому для того, чтобы найти прямое произведение матриц R®Q, достаточно перемножить строки на столбцы матрицы достижимостей. Этот процесс осуществляется на вто : ром этапе работы устройства. Напряжение на ()-м выходе дешифратора 11 открывает элемент И 18 и тактовые импульсы с генератора 15 начинают поступать на элемент И 20, открытый потенциалом 1, .поступающим с выхода элемента НЕ 22. К первым входам 5 элементов И 30,-30, подключены информационные выходы одноименных разрядов регистра

в котором записана первая строка матрицы достижимое-; тей графа т.е. код 1011. Вт орые входы элементов И 30,-30, подключены к выходам первых разрядов регистров которых записан первый матрицы достижимостей (соответствующий первой строке матрицы контрдосПри поступлении первого тактового импульса на счетчик 21 на первом вы-1 ходе дешифратора 23 появляется единичный потенциал, поступающий на

третьи входы элементов И , первой строки матрицы. При этом происходит логическое перемножение первой строки и .nejfBoro столбца матрицы достижимостей. Таким образом, в первой

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

На третьем этапе производится разбиение графа на сильные компоненты. На первый вход элемента И 24, открытого по второму входу, поступают тактовые импульсы с генератора 15. Первые информационные входы коммутаторов-мультиплексоров подключены к соответствующим информационным выходам первого регистра 29 , вторые входы - к соответствующим информационным выходам второго регистра и т.д. При поступлении первого тактового импульса на элемент И 25, открытый единичным потенциалом с выхода элемента НЕ 28, в счетчик 26 записывается 1 и на адресные входы коммутаторов- мультиплексоров поступает единичньй адрес. При этом на выход коммутаторов-мультиплексоров подключеи; соответствующие разряды регистра 29 . Так как в первом регистре 29 записана комбинация 10115 на первые входы элементов И 37, 37, 37 подаются уровни напряжения 1, на 37 - О. Через время t Т. /2 (где Т. - период следования тактовых импульсов) на вторые входы поступает тактовый икпульс, который через элементы И и 37 стирает информацию в регистрах 29 и 29. При поступлении второго тактового импульса на элементы И подается комбинация 0100 (во втором регистре 29 записана комбинация 0100). Через время t второй тактовый импульс не стирает информацию ни в одном из регистров. Во втором регистре 29 остается комбинация 0100. Аналогично при третьем такте также не стирается информация ни в одном из регистров , а в регистрах остается комбинация 0000. С приходом четвертого тактового импульса на 4-м выходе дешифратора 27 появляется напряжение логической 1, которое через элемент 28 НЕ закрывает элемент И 25. На зтом работа устройства прекращается. Элементы индикации, подключенные к информационным выходам регистров 29,-29f|, высвечивают в первой строке комбинацию Х, Х, Х, во второй - Х. Эти вершины графа соответ- ствуют его двум сильным компонентам - Х, Х, Хц и Х. Элементы И 37 служат для развязки управляющих входов регистров 29.

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

Устройство для исследования параметров графов, содержал;ее генератор тактовых импульсов , два элемента И, две.

группы элементов И, матрицу п-п элемен- тов И, элемент НЕ, дешифратор, счет- ;чик, группу из п регистров (п - число вершин графа, наборное поле с выпрямительными элементами, причем

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

с первым и вторым входом одноименного элемента И первой группы и с первыми входами элементов И одноименной строки матрицы, выходы элементов И столбца матрицы соединены с входами

разрядов одноименного регистра группы, вход сброса устройства соединен с входом сброса счетчика и входами сброса регистров группы, счетный вход счетчика подключен к выходу первого элемента И, первый вход которого соединен с выходом второго элемента И, а второй вход соединен с выходом элемента НЕ и вторыми входами элементов И второй группы, вход

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

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

дешифратора, первый вход пятого.эле- мента И подключен к выходу генератора тактовых импульсов, а второй вход

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

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

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

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

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

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

Ю

Т

1234

ФагЛ

У 2 J 4

Фиг.З

Фиг. 5

Фиг.В