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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для исследования систем, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи стягивания вершин ориентированного графа. Устройство содержит блок 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 ил.

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

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИН (51)5 С 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСН0МУ СВИДЕТЕЛЬСТВУ

ГОсудАРстВенный КОмитет

r1O ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4417231/24-24 (22) 26. 04.88 (46) 23. 08. 90. Бюл. Р 31 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк, Д.В.Табачников и С.Ю. Бездежский (53) 681.333(088.8) (56) Авторское свидетельство СССР

У. 1174937, кл. G 06 F 15/20, 1983.

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

N - 1501084, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НА ГРАФАХ . (57) Изобретение относится к вычислительной технике и может быть использовано для исследования систем,описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи стягивания вершин ори-" ентированного графа. Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин дуг, блок 3 определения начальных вершин дуг, блок 4 удаления дуг, регист„,Я0„„1587535 А1

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

Эу ю в&1, 1587535 4

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

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

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

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

В-й входы 11 признаков принадлежности вершин массиву стягиваемых, где

 — количество вершин в графе, выход 12 признака окончания работы, выходы

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

На фиг. 3 цифровые обозначения представляют матрицу из ВхВ элементов И 20, группу из В элементов

ИЛИ 21, входы 22 признаков наличия дуг блока 2, входы 23 опроса начальных вершин блока 2, выходы 24 признаков принадлежности вершин массиву концевых, причем вход 23 опроса

M-й начальной вершины (M = 1,...,В) подключен к первым входам всех элементов И 20 M-й строки матрицы, вход

22 признака наличия (К, М)-й дуги блока 2 (К = 1,...,В) подключен к второму входу -ro элемента И 20

M-й строки матрицы, выход которого подключен к К-му входу М-го элемента

ИЛИ 21 группы, выход которого является выходом признака принадлежности М-й вершины массиву концевых.

На фиг.4 представлены: матрица из

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

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

На фиг.5 представлены: матрица из

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

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

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

ИЛИ 30.

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

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

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

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

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

Через время, достаточное для определения концевых вершин дуг блоком 2, отсчитанное от момента выдачи информации на входы 11, блок. 1 формирует 2С сигнал уровня логической единицы на выходе 16. При этом в регистр 6 заносится информация с выхода блока 2 (т.е. происходит формирование дуг,исходящих из (В+1)-й вершины). Через 25 время, достаточное для записи, блок

1 синхронизации снимает сигнал .с выхода 16 и формирует сигнал уровня логической единицы на своем выходе 17„

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

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

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

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

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

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

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

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

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

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

На вход 37 подают. сигнал уровня логической единицы„ При этом открывается ключ 33 и сигналы уровня логической единицы с его информационного выхода обнуляют элементы 31 памяти соответствующих столбцов матрицы (тем самым удаляют все дуги, заходящие в вершины, заданные по входам 35). формула,изоб ре тения устройство для операций на графах, содержащее блок синхронизации, блок определения концевых вершин дуг и первый регистр, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи стягивания вершин ориентированного графа, в него введены второй регистр, ключ, блок удаления дуг и блок опре1587535 деления начальных верши дуг, причем вход начальной установки устройства подключен к входам установки в "0" блока удаления дуг и первого и второго регистров, вход признака принадлежности К и вершины массиву отягиваемых (К = 1,...,В, где  — количество вершин в графе) подключен к

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

° °

° °

° °

° ° ° е е е е °

Ф ° В

° ° °

22 22 0 22zr 22 ю ° 1

1 ° 1

27в

Б! js

° е а

° ° °

° °

° °

38у egg

Фьг. 5

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

Редактор С.Патрушева Техред А.Кравчук Корректор Q.Черни

Заказ 2422 Тираж 568 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101