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

 

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

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

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

PECllYBfIHH (58 4 G 06F 15 20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНЯТИЙ (21) 4192371/24-24 (22) 25.11.86 (46) 15.11.88, Бюл. У 42 (72) О.Г. Алексеев, В.Т. Данцев и Н.И.Ячкула (53) 681.333(088,8) (56) Авторское свидетельство СССР

Р 1241266, кл. G 06 G 7/48, 1984.

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

Р 1392574, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА .

„,Я0„„1437 75 А1 (57) Изобретение относится к вычислительной технике, может быть использовано для исследования путей в графе и позволяет определять внешние и внутренние радиусы графа. Цель изобретения — расширение класса решаемых задач — достигается за счет использования в устройстве матрицы регистров, в которые перед началом работы заносят информацию о весах ребер графа. При определении внутренних центров графа матрицу весов транспонируют. 2 ил.

1437875

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

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

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

Устройство содержит матрицу из

В В регистров 1, где  — количество вершин в графе, матрицу из В В ключей 2, матрицу из В В схем 3 сравнения, матрицу из В»»В триггеров 4, пер( вую группу из t В элементов ИЛИ 5, вторую группу из В элементов ИЛИ 6, группу из В времяимпульсных интегрирующих преобразователей 7, группу из

В регистров 8, группу из В схем 9 сравнения, элемент !О ИЛИ, элемент

11 НЕ, первый элемент 12 И, времяимпульсный интегрирующий преобразователь 13, второй элемент 14 И и блок

15 синхронизации.

Кроме того, на фиг. 1 цифровое обозначение имеют входы lб задания веса пути из М-ой в К-ую вершину 30 графа устройства (М = 1,...,B, К

1,...,В), вход 1? начальной установки устройства, вход 18 пуска устройства, выход 19 совпадения К-ой вершины графа с внешним (внутренним) центром графа устройства, выход 20 признака окончания работы устройства, первый выход 21 синхронизации блока 15, второй выход 22 синхронизации блока 15, первая группа из В выходов 23 блока 15 и вторая группа . .из В выходов 24 блока 15.

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

Перед началом работы на входы 16 устройства подают, информацию о весе соответствующих ребер графа, которая поступает на информационные входы регистров 1. На вход 17 начальной установки устройства подают импульсный сиг50 нал единичного уровня, который поступает на входы признаков записи регистров 1, вход установки в ноль времяимпульсного интегрирующего преобразователя 13 и входы начальной установки ключей 4. При этом информация о весе ребер графа записывается в регистры 1, на выходе времяимпульсного интегрирующего преобразователя 13 устанавливается нулевой код, ключи

2 замыкают цепи между информационным входом и выходом. На вход 18 пуска устройства подают импульсный сигнал единичного уровня, который поступает на вход пуска блока 15 синхронизации. При этом блок 15 синхронизации начинает вырабатывать последовательность импульсов, предусмотренную временной диаграммой его работы (цифры на временной диаrpамме сooтветстнуют номерам позиций использованных при обозначении входов и выходов устройства и блока 15 синхронизации).На выход 21 блок 15 синхронизации выдает им»»ульсный сигнал единичного уровня, который поступает на входы установки в ноль всех триггеров 4 и всех времяимпульсных интегрирующих преобразователей 7. При этом все триггеры 4 устанавливаются в нулевое состояние,на выходе всех времяимпульсных интегрирующих преобразователей 7 устанавливается нулевой код. Через время Т, отсчитанное от переднего фронта сигнапа с выхода 21, необходимое для установки триггеров 4 и преобразователей 7, блок 15 синхронизации выдает импульсный сигнал единичного уровня на первый выход 23 первой группы, который поступает на вход разрешения пуска первого преобразователя 7 группы. При этом первый преобразователь 7 начинает вырабатывать код, величина которого пропорциональна времени разрешения его работы. Информация с выхода первого преобразователя 7 поступает на первые информационные входы всех схем

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

1. К-я схема 3 сравнения при условии равенства кодов на первом и втором информационных входов вырабатывает сигнал единичного уровня (достигнута К-ая верц»ина графа), который поступает на вход установки в единицу

К-ro триггера 4 первой строки матрицы. При этом К-й триггер 4 первой строки матрицы переходит в единичное состояние. Единичный потенциал с выхода К-го триггера 4 первой строки матрицы поступает на управляющие входы всех ключей 2 К-ro столбца матрицы и на вход разрешения работы К-ro преобразователя 7 группы.

55

3 143

При этом ключи 2 К-го столбца матри", цы размыкают цепи между своими информационными входами и выходами (блокируется повторное начало исполнения ветвей исходящих из К-й вершины графа), К-й преобразователь 7 начинает вырабатывать код, величина которого пропорциональна времени разрешения его работы (начинается исполне. ние ветвей исходящих из К-й вершины графа), Работа устройства продолжается аналогичным образом до тех пор, пока на выходе элемента 14 И не появится потенциал единичного уровня (достигнуты все вершины графа), который поступает на тактовый вход блока 15 синхронизации. При этом блок 15 синхронизации снимает сигнал единичного уровня с первого выхода 23 первой группы и вырабатывает импульсный сигнал на первом выходе 24 второй группы, который поступает на вход признака записи первого регистра 8. При этом в первый регистр 8 записывается информация о величине внешнего радиуса из первой вершины графа. Через время Т, достаточное для записи информации в первый регистр 8, блок 15 синхронизации формирует импульсный сигнал единичного уровня на выходе 21, который поступает на входы установки в

"0" всех преобразователей 7 и всех триггеров 4. Через время Тз, достаточное для установки в ноль преобразователей 7 и триггеров 4, блок 15 синхронизации выдает на второй выход .

23 первой группы потенциал единичного уровня. Далее устройство работает аналогично. (Определяются величины внешних радиусов из всех вершин графа). Через В тактов работы блока

15 синхронизации, появляется сигнал на выходе 22 блока 15, который поступает на вход разрешения работы преобразователя 13. При этом преобразователь 13 начинает вырабатывать код, величина которого пропорциональна времени разрешения его работы. Информация с вых да преобразователя 13 поступает на вторые информационные входы всех схем 9 сравнения, на первые входы которых поступает информация с выходов регистров 8. Через время, равное весу минимального внешнего радиуса на выходе К-ой схемы сравнения появляется единичный сигнал, который поступает на выходы 19 и 20

4 устроиства и на вход элемента HE 11.

При этом на выходе элемента HE 11 появляется нулевой потенциал, который блокирует разрешение работы преобразователя 13. Работа устройства закончена, При определении внутренних центров графа устройство работает аналогично, но перед началом работы матрицу весов графа транспонируют.

Таким образом, суть изобретения заключается в определении вершины

Х,(Х„ ), для которой Я(Х„.) = мин

)S(X„. )), R(X> ) = мин (R(Xj ))

1,...,В, Я(Х ), = макс(о,1) внешний радиус вершины Х1, В(Х1 )

= макс(м 1;) — внутренний радиус вершины Х1 <х; — длина кратчайшего пути из i-й вершины графа в,)-ю, 0(,. длина кратчайшего пути из -вершины графа в i-ro.

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

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

Устройство для анализа параметров графа, содержащее матрицу из « регистров, где  — количество вершин в графе, матрицу из ВкВ ключей, матрицу из « схем сравнения, матрицу из

В В триггеров, две группы из В элементов ИЛИ, группу из В времяимпульсных интегрирующих преобразователей, группу из В регистров, первый элемент И и блок синхронизации, причем выход К-ro ключа М-й строки матрицы (К = 1,...,Â; M = 1,...,В) подключен к первому информационному входу К-й схемы сравнения M-й строки матрицы, выход признака равенства которой подключен к входу установки в "1" К-ro триггера М-й строки матрицы, выход которого подключен к М-му входу К-го элемента ИЛИ первой группы, информационный вход К-го регистра М-й строки матрицы является входом задания веса пути иэ М-й в К-ю вершину графа устройства, вход признака записи К-го регистра М-й строки матрицы является входом начальной установки устройст!

4 37875 ва, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет определения внешних и внутренних центров графа, в него введены группа из В схем сравнения, второй элемент И, элемент ИЛИ, элемент НЕ и времяимпульсный интегрирующий преобразователь, причем вход начальной установки устройства подключен к входу установки в "0 времяимпульсного интегрирующего преобразователя, выход К-го элемента ИЛИ первой группы подключен к управляющим входам всех ключей К-го столбца матрицы, и К-му входу второго элемента

И и к первому входу К-ro элемента

ИЛИ второй группы, выход которого подключен к входу разрешения работы

К-го времяимпульсного интегрирующего преобразователя, выход которого подключен к информационным входам всех ключей К-й строки матрицы и к информационному входу К-го регистра группы, выход которого подключен к первому информационному входу К-й схемы сравнения группы, выход признака равенства которой является выходом признака совпадения К-й вершины с внешним (внутренним) центром графа устройства и подключен к К-му входу элемента ИЛИ, выход которого является выходом признака окончания работы устройства и подключен к входу элемента HF., выход которого подключен к первому входу первого элемента И, выход которого подключен к входу разрешения работы времяимпульсного интегрирующего преобразователя, выход которого подключен к вторым входам всех схем сравнения группы, выход К-ro регистра М-й строки матрицы подключен к второму информационному входу К-й схемы сравнения M-A строки матрицы, выход второго элемента И подключен к тактовому входу блока синхронизации, вход пуска которого является входом пуска устройства, первый выход синхронизации блока синхронизации подклюр0 чен к входам установки в "0" всех триггеров матрицы и к входам установ1I It ки в 0 всех времяимиульсных интегрирующих преобразователей группы, второй выход синхронизации блока синхро2Б низации подключен к второму входу пер-. вого элемента И, K-й .выход синхронизации первой группы блока синхронизации подключен к второму входу К-го элемента ИЛИ второй группы, К-й выход синхронизации второй группы блока синхронизации подключен к входу признака К вЂ  регистра группы.

1437875

1". 7

Р" D

Р Р4

Составитель А. Мишин

Техред Л.Сердюкова Корректор B. Романенко

Редактор М. Недолуженко

Тираж 704 Подписное

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

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

Заказ 5895/49

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