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

Ла.1

«f,.. t,«./

krfli,.,

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

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

На фиг.1 представлена функциональ ная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации; на фиг.З - функциональная схема блока определения концевых вершин дуг; на фиг.4 - функциональная схема блока определения начальньк вершин дуг; на фиг.5 - функциональна схема блока удаления дуг.

Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин дуг, блок 3 определения начальных вершин дуг, блок 4 удаления дуг, разряды 5 информационного входа первого регистра, регистры 6 и 7, ключ 8, вход 9 начальной уста- новки, вход 10 пуска с первого по В-й входы 11 признаков принадлежности вершин массиву стягиваемых, где В - количество вершин в графе, выход

12признака окончания работы, выходы

13признаков Наличия дуг в исходном графе устройства, вькоды 14 признаков наличия дуг, исходящих из (В+1)вершины устройства, выходы 15 признаков наличия дуг, заходящих в (В+1)-ю вершину, выходы 16-19 блока 1 синхронизации.

На фиг.З цифровые обозначения представляют матрицу из ВхБ элементов И 20, группу из В элементов ИЛИ 21, входы 22 признаков наличия дуг блока 2, входы 23 опроса начальных вершин блока 2, выходы 24 признаков принадлежности вершин массиву концевых, причем вход 23 опроса М-й начальной вершины (М . 1,...,В) подключен к первым входам всех элементов И 20 М-й строки матрицы,вход 22 признака наличия К, М)-й дуги блока 2 (К 1,...,В) подключен к второму входу К-го элемента И 20 М-й строки матрицы, выход которого подключен к К-му входу М-го элемента ИЛИ 21 группы, выход которого является выходом признака принадлежности М-й вершины массиву концевых.

На фиг.4 представлены: матрица из ВхВ элементов И 25, группа .из В элементов ИЛИ 26, входы 27 опроса кон

д 15

рп 25

j

дс

35

5

-цевых вершин, входы 28 признаков наличия дуг и выходы 29 признаков принадлежности вершин массиву начальных, причем вход 27 опроса К-й концевой вершины подключен к первьм входам всех.элементов И 25 К-го столбца матрицы, вход 28 признака наличия (К, М)-й дуги подключен к второму входу К-го элемента И 25 М-й строки матрицы, выход которого подключен к К- му входу М-го элемента ИЛИ 26, выход которого является выходом 29 признака принадлежности М-й вершины массиву начальных блока 3.

На фиг.5 представлены: матрица из ВхВ элементов ИЛИ 30, матрица из ВхВ элементов 31 памяти, ключи 32 и 33, входы 34 установки признаков наличия дуг блока 4, входы 35 задания концевых точек удаляемых дуг, вход 36 признака удаления исходящих дуг, вход

37признака удаления заходящих дуг и выходы 38 признаков наличия дуг блока 4, причем вход 35 задания К-й концевой точки удаляемых дуг подключен к К-му разряду информационного входа ключа 32 и к К-му разряду информационного входа ключа 33, К-й разряд информационного выхода которого подключен к первым входам всех элементов ИЛИ 30 К-го столбца матрицы, М-й разряд информационного выхода ключа 32 подключен к вторым входам всех элементов ИЛИ 30 М-й строки матрицы, выход К-го элемента 30 ИЛИ М-й строки матрицы подключен к входу установки в ноль К-го элемента 31 памяти М-й строки матрицы, выход которого является выходом

38признака наличия (К, М)-й дуги блока 4, вход 34 установки признака наличия (к, М)-й дуги которого подключен к входу установки в единицу К-го элемента памяти М-й строки матрицы, входы 36 и 37 блока 4 подключены к управляющим входам (входам включения) ключей 32 и 33 соответственно. На фиг.5 не показан вход начальной установки элементов 31 памяти, но он может быть реализован обь- единением третьих входов элементов ИЛИ 30.

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

Пусть необходимо стянуть одну или несколько вершин графа во внешнюю точку или, считая что исходный граф имеет В вершин, в (В+1)-ю вершину.

Перед началом работы, подавая на вход 9 импульс уровня логической единицы, обнуляют регистры 6 н 7.

В блок 4 удаления дуг заносят информацию о топологии графа (его матрицу смежности), по входам 11 признаков принадпежности вершин массиву стягиваемых задают состав стягиваемых вершин графа.

На вход 10 пуска подают импульс уровня логическдй единицы. При этом блок 1 синхронизации формирует последовательность сигналов уровня логической единицы, предусмотренную временной диаграммой его работы. Через время, достаточное для определения концевых вершин дуг блоком 2, отсчитанное от момента вьщачи информации на входы t1, блок 1 формирует сигнал уровня логической единнщы на выходе 16. При этом в регистр 6 заносится информация с выхода блока 2 (т.е. происходит формирование дуг,исходящих из (В+1)-й вершины). Через время, достаточное для записи, блок 1 синхронизации снимает сигнал с выхода 16 и формирует сигнал уровня логической единицы на своем выходе 17. При этом блок 4 удаляет из топологии графа все, дуги, исходящие из стягиваемых вершин„ Одновременно регистр 6 устанавливает в ноль те свои информационные разряды, номера которых соответствуют номерам стягиваемых вершин (тем самым из топологии графа исключают дуги, соединякяцие стя- стягиваемые вершины).

Через время, достато.чное для окон- чани указанных процессов, блок 1 синхронизации снимает сигнал с выхода

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

ем самым происходит формирование уг, заходящих в (В+1)-ю вершину граа. Через время, достаточное для окончания записи, блок 1 синхронизаии снимает сигнал со своего выхода

18и формирует сигнал уровня логической единицы на сзоем выходе 19. При этом блок 4 удаления дуг удаляет

з топологии графа все дуги заходяие в стягиваемые.

-

-875356

Через время, достаточное для удаления заходящих дуг, блок 1 синхронизации снимает сигнал со своего выхода 19 и формирует сигнал уровня логической .единицы на выходе 12 признака окончания работы. В этот момент времени информация о составе стягиваемых вершин может быть снята с вхо)0 дов 11. К этому моменту времени на выходах 13 находится информация о наличии дуг в топологии исходного графа (т.е. графа, .нумерация вершин которого совпадает с нумерацией вер15 шин исходного графа).

Блок 4 удаления дуг работает сле- дукядим образом.

Перед началом работы подачей сигнала на вход 9 обнуляют все элемен20 ты 31 памяти (цепи начальной установки на фиг.5 не показаны).

По входам 34 задают информацию о топологии графа (задают его матрицу смежности). На входы 35 подают

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

30 На вход 36 подают сигнал уровня логической единицы. При этом открывается ключ 32 и сигналы уровня логической единицы с его инфо1 1аци- ониого выхода обнуляют соответствующие строки элементов 31 памяти (тем самым удаляются все дуги, исходящие из вершин, заданных по входам 35). На вход 37 подают сигнал уровня логической единицы При этом открывается ключ 33 и сигналы уровня логической единицы с его информационного выхода обнуляют элементы 31 памяти соответствующих столбцов матрицы (те.м самым удаляют все дуги,

5 заходящие в вершины, заданные по

35

40

50

55

входам 35).

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

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

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

.

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

0

5

5

0

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

Изобретение относится к вычислительной технике и может быть использовано для исследования систем, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи стягивания вершин ориентированного графа. Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин дуг, блок 3 определения начальных вершин дуг, блок 4 удаления дуг, регистры 6 и 7, ключ 8 и имеет вход 9 начальной установки, вход 10 пуска, с первого по B-й входы 11 признаков принадлежности вершин массиву стягиваемых (B-количество вершин в графе), выход 12 признака окончания работы, выходы 13 признаков наличия дуг в исходном графе, выходы 14 признаков наличия дуг, исходящих их (B + 1)-й вершины, выходы 15 признаков наличия дуг, заходящих в (B + 1)-ю вершину, выходы 16 - 19 блока 1 синхронизации. При подаче на вход 10 импульса уровня логической единицы блок 1 формирует последовательность сигналов, под управлением которой устройство определяет концевые вершины для дуг, исходящих из стягиваемых вершин, заносит признаки наличия дуг из (B + 1)-й в указанные концевые вершины в регистр 6, удаляет дуги, исходящие из стягиваемых вершин, определяет начальные вершины для дуг, заходящих в стягиваемые вершины, заносит признаки наличия дуг в (B + 1)-ю из указанных начальных вершин дуг и удаляет дуги, заходящие в стягиваемые вершины. 5 ил.

tl.

ю.

flL

.Xl, J4

.JDU.

лЧ.

t t

1587535

ПпЩь гг„гггв

О О

гггв

О О

В1 ва о

275

О 28в1 гввв

гиг

Z9t

:

Фиг л

J5; 35e

36 o-

Фиг. 5

81 3800