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

 

УСТРОЙСТВО ДПЯ ОПРЕДЕЛЕНИЯ СВЯЗНОСТИ ОРИЕ,НТИРОВАННОГО ГРАФА, содержащее генератор тактовых импульсов , два элемента И, две группы по п элементов И, матрицу Пп элементов И, элемент НЕ, дешифратор и счетчик, выход которого подключен к входу дешифргтора, первый вход первого элемента И является входом пуска устройства, второй вход первого элемента И подключен к выходу генератора тактовых импульсов, а i -и ( l,2,...,yi) выход дешифратора соединен с первыми входами элементов И 1 -го столбца матрицы п h элементов И, отличаю щ есе с я тем, что, с целью расширения функциональных возможностей за счет определения достижимости вершин, в него введены П регистров, выходы которых являются выходами устройства , выпрямительные элементы, наборное поле, строки которого через вьшрямительные элементы соединены с соответствующими столбцами в соответствии с топологией графа, причем строки наборного поля соединены с выходами одноименных элементов И первой группы, выходы столбцов наборного поля подключены к первым входам элементов И второй группы, выход 1 -го элемента И второй группы соединен с входом одноименного элемента И первой группы и подключен к вторым входам элементов И i -и строки матрицы D элементов S И, выходы элементов И i -го столбца (Л которой соединены с .одноименными информационными входами -го регистра , управляющий вход счетчика, соединен с управляющими входами регистров и является входом остано .ва устройства, суммирующий вход счетчика подключен к выходу второ го элемента И, первый и второй входы 4 которого соединены соответственно с СО со выходом первого элемента И и выходом элемента НЕ, который подключен также к вторым входам элементов И второй группы, а вход элемента НЕ соединен с (п+1)-м выходом дешифратора .

„„SU„„1174937

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

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

РЕСПУБЛИК (si>4 С 06: 15./20 т

ОПИСАНИЕ ИЗОБРЕТЕНИ (,"„" :;-:-:::::::::;.:::::. М

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

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ тора. (21) 3648553/24-24 (22) 04, 10, 83 (46) 23. 08. 85. Бюл. ¹- 31 (72) Ю. В. Пшеничный, В. Е. Назаренко, E. И. Бороденко и В. Ф. Черньпп (53) 681.3(088.8) (56) Авторское свидетельство СССР № 717787, кл. G 06 G 7/122, 1980.

Авторское свидетельство СССР № 943738, кл. G 06 F 15/20, 1982. (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

СВЯЗНОСТИ ОРИЕНТИРОВАННОГО ГРАФА, содержащее генератор тактовых импульсов, два элемента И, две группы по и элементов И, матрицу и и элементов И, элемент НЕ, дешифратор и счетчик, выход которого подключен к входу дешифрвтора, первый вход первого элемента И является входом пуска устройства, второй вход первого элемента И подключен к выходу генератора тактовых импульсов, а 1 -й (=1,2,...,n) выход дешифратора сое. динен с первыми входами элементов

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

И 1 -й строки матрицы П и элементов

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

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

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

На чертеже представлена структурная схема устройства.

Устройство содержит первую группу

15 элементов И 1< -l, вторую группу элементов И 2 -2> выход 3 останова . устройства, регистры 4 -4, 11 групп элементов И 5 -5„, 6 -6„,..., 9 -9„, образующих матрицу из п.п элементов

И (и — число вершин графа), вход 1

10 пуска устройства, дешифратор 11, счетчик 12, второй элемент И 13, элемент НЕ 14, генератор 15 тактовых импульсов, первый элемент И 16, 25 наборное поле. 17, выпрямительные элементы 18.

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

На наборном поле 17 набирается топология графа путем включения выпрямительных элементов 18 в проводящем направлении между -й строкой и -м столбцом при наличии связи ! между -й и 1 -й вершинами. Путем З5 подачи сигнала на вход 3 счетчик

12 и регистры 4 устанавливаются в нулевое состояние. Для запуска устройства подают потенциал на вход 10 и ска, тогда через элемент И 16 40 тактовые импульсы с выхода генератора 15 поступают на вторую схему И 13> которая открыта напряжением логической единицы с выхода инвертора 14, так как на выходе п +1 дешифратора 45

11 присутствует напряжение логического нуля. Напряжение логической "1" с. выхода инвертора 14 открывает также элементы И 2.

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

17 и записывает в первый разряд регистра 41 единицу, Рассмотрим работу устройства на примере включения в наборное поле 17 трех диодов 18, Через элемент И 11 единичное напряжение поступает на первую строку наборного поля 17 и через диод 181 и элемент И 2 записывает в третий разряд регистра 41 единицу, поступает через элемент И 1 на третью строку и через диод 18 записывает в четвертый разряд регистра 4 единицу, поступает через элемент И 1„ на четвертую строку.

После прихода второго импульса напряжение логической "1" появляется на втором выходе дешифратора 11, а на первом выходе будет логический "0", который поступает на вторые входы элементов И 5<-5 „ и отключает регистр 4 1 от наборного поля! одновременно "снимается напряжение логической "1" с первого столбца. Единичное напряжение с второго выхода дешифратора ll открывает элементы

И 6 -6, подключая тем самым регистр 4 к наборному полю 17, а также подается на второй столбец.

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

4 -4> содержится информация о дости.жимости вершин графа.

1174937

Составитель Л. Сахно

Редактор В. Петраш Техред Т.Фанта Корректор И . Г1аксимишинец

Заказ 5201/50 Тираж 710 Подписное

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

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

Филиал ППП "Патент, г. Ужгород, ул. Проектная, 4