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

сл

с

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

00

00

v3

ел

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

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

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

Устройство содержит матрицу из регистров 1, где В - количество вершин в графе, матрицу из ключей 2, матрицу из схем 3 сравнения, матрицу из ВхВ триггеров l, первую группу из I В элементов ИЛИ 5, вторую группу элементов ИЛИ 6, группу из В времяимпульсных интегрирующих преобразователей 7, группу из В регистров 8, группу из В схем 9 сравнения, элемент 10 ИЛИ, элемент 1 1 НЕ, первый элемент 2 И, времяим- пульсный интегрирующий преобразователь 13, второй элемент 14 И и блок 15 синхронизации.

Кроме того, на фиг, I цифровое обозначение имеют входы 16 задания веса пути из М-ой в К-уго BepmtiHy графа устройства (М i , ., , ,Б , К 5 . ,,,В), вход 17 начальной установки устройства, вход 18 пуска устрой- ства, выход 19 совпадения К-ой вершины графа с внешним (внутренним) центром графа устройства, выход 20 признака окончания работы устрорЧства, первый выход 2 синхронизации блока 15, второй выход 22 синхронизации блока 15, первая группа из В выходов 23 блока 15 и вторая группа , из В выходов 24 блока 15,

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

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

5

10

5

0

5

0

5

0

5

0

5

устанавливается нулевой код, ключи

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

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

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

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

определении вершины для которой S(Xi) мин

рицу весов графа транспонируют.

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

х ;(х;..

15 S(Xj , НСХ) мин ( R(Xj ) i, J 1,...,В, S(Xi), MaKc() - внешний радиус вершины Х J R(xO макс ((У ji) - внутренний радиус вершины X-i; С4 ij - длина кратчайшего пу20 ти из i-й вершины графа в .-ю; СР(Т длина кратчайшего пути из j-вершины графа в i-ю.

При этом преобразователи 7 и 13 могут быть выполнены не только на

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

30 не требуется сколько-нибудь существенных изменений функциональной схемы устройства.

35

40

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

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

50

55

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

При определении внутренних центров графа устройство работает аналоопределении вершины для которой S(Xi) мин

рицу весов графа транспонируют.

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

х ;(х;..

S(Xj , НСХ) мин ( R(Xj ) i, J 1,...,В, S(Xi), MaKc() - внешний радиус вершины Х J R(xO макс ((У ji) - внутренний радиус вершины X-i; С4 ij - длина кратчайшего пути из i-й вершины графа в .-ю; СР(Т длина кратчайшего пути из j-вершины графа в i-ю.

При этом преобразователи 7 и 13 могут быть выполнены не только на

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

не требуется сколько-нибудь существенных изменений функциональной схемы устройства.

5

0

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

Устройство для анализа параметров графа, содержащее матрицу из регистров, где В - количество вершин в графе, матрицу из BtB ключей, матрицу из схем сравнения, матрицу из ВхВ триггеров, две группы из В элементов ИЛИ, группу из В времяимпульс- ных интегрирующих преобразователей, группу из В регистров, первый элемент И и блок синхронизации, причем 5 выход К-го ключа М-й строки матрицы (К 1,...,В; М ,...,В) подключен к первому информационному входу Кй схемы сравнения М-й строки матрицы, выход признака равенства которой подключен к входу установки в 1 К-го триггера М-й строки матрицы, выход которого подключен к М-му входу К-го элемента ИЛИ первой группы, информационный вход К-гр регистра М-й строки матрицы является входом задания веса пути из М-й в К-ю вершину графа устройства, вход признака записи К-го регистра М-й строки матрицы является входом начальной установки устройст0

5

514

ва, отличающееся тем, что, с целью расширения класса решаемых задач за счет определения внешних и внутренни центров графа, в него введены группа из В схем сравнения, второй элемент И, элемент ИЛИ, элемент НЕ и времяимпульсный интегрирующий преобразователь, причем вход начальной установки устройства подключен к входу установки в О время- импульсного интегрирующего преобразователя, выход К-го элемента ИЛИ первой группы подключен к управляющим входам всех ключей К-го столбца мат- ри1№, и К-му входу второго элемента И и к первому входу К-го элемента ИЛИ второй группы, выход которого подключен к входу разрешения работы К-го времяимпульсного I интегрирующего преобразователя, выход которого подключен к информационным входам всех ключей К-й строки матрицы и к информационному входу К-го регистра группы, выход которого подключен к первому информационному входу К-й схемы сравнения группы, выход приз- Н1зка равенства которой является выходом признака совпадения К-й вершины с внешн.им (внутренним) центром графа устройства и подключен к К-му входу элемента ИЛИ, выход которого

рие.1

56

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

вторым входам всех схем сравнения группы-, выход К-го регистра М-й строки матрицы подключен к второму информационному входу К-й схемы сравнения М-й строки матрицы, выход второго элемента И подк;дачен к тактовому входу блока синхронизации, вход пуска которого является входом пуска устройства, первьй выход синхронизации блока синхронизации подключен к входам установки в О всех

триггеров матрицы и к входам установки в О всех времяимпульсных интегрирующих преобразователей группы, второй выход синхронизации блока синхронизации подключен к второму входу пер-, вого элемента И, К-й.выход синхронизации первой группы блока синхронизации подключен к второму входу К-го элемента ИЛИ второй группы, К-й выход

синхронизации второй группы блока синхронизации подключен к входу признака К-го регистра группы.

rff

8 2

2 20

фиг. 2