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

 

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

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

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

РЕСПУБЛИН (5D 4 G 06 F 15/20

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

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

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4211038/24-24 (22) 18.03.87 (46) 23.07.88. Бюп. Р 27 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк и Г.В.Моисеенко (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 1218392, кл. G 06 F 15/20, 1986.

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

Н 1174937, кл. G 06 F 15/20. 1985.

1.Я0„, 14117?3 А1 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть применено для исследования достижимости вершин графа при .решении задач, допускающих теоретико-графовое представление. Целью изобретения является расширение функциональных возможностей устройства за счет определения матриц ограниченных достижмостей исследуемого графа ° Устройство содер1411773 жит генератор тактовых импульсов элементы 2 И, 3 НЕ, 4 И, матрицу моделей дуг 5 из элемента 6 И и триггеров 7,8, дешифратор 9, счетчик 10, выходы которого подключены к входам дешифратора 9, соединенного выходами с первыми входами элементов 4 И, элементы задержки 13, триггеры 14, регистр 15, реверсивный счетчик 16> информационные входы которого нодключе1

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

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

На чертеже приведен пример реали-. зации структурной схемы устройства.

Устройство содержит генератор 1 тактовых импульсов, элемент И 2, эле- 15 мент НЕ 3, группу из и элементов И 4„

;матрицу из и х и моделей 5; дуг,каждая из которых состоит иэ элемента

И 6, первого 7 и второго 8 триг геров, дешифратор 9, счетчик 10, выход 11 признака окончания работы устройства, группу из и элементов ИЛИ

1I2, группу из и элементов 13; задержки, группу из и триггеров 14, регистр 15, реверсивный счетчик 16, Формирователь 17 импульсов, элемент 18 задержки, вход 19 признака ограничения достижимости устройства, вход 20

Начальной установки устройства и вход

21 пуска устройства.

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

В исходном состоянии сигнал "Пуск"

21 отсутствует, что блокирует прохождение импульсов с генератора 1 через

- лементы И 2, на выходе KQToporo npuс,утствует логический "0", блокируюп ий работу триггеров 14 и элементов

И 6 моделей 5 дуг, счетчик 10 обнулен сигналом 20 начальной .установки, на ны к выходам регистра 15. Информация о топологии графа заносится в триггеры 7 моделей дуг 5, а значение числа ограничения достижимости — в регистр

15. При работе устройства происходит преобразование исходной информации в матрицу ограниченной достижимости с заданным числом ограничения, которая заносится в триггеры 8 моделей дуг 5. 1 ил. выходах дешифратора 9 с первого по (и+1) -й сигналы логического "0", блокирующие прохождение сигналов разрешения записи к вторым триггерам 8 моделей 5 дуг, состояние триггеров

14 и реверсивного счетчика )6 — произвольное.

Исходная информация о топологии исследуемого графа заносится в виде матрицы смежности в триггеры 7 моделей 5 дуг через информационные входы устройства, значение числа R ограничения достижимости заносится через входы 19 в регистр 15 по сигналу 20 начальной установки, одновременно устанавливаются в "0" счетчик 10, после чего устройство готово к работе.

При подаче на выход 11 сигнала

"Пуск", уровня логической "1", импульсы с генератора 1 через элемент И 2, открытый по третьему входу логической

"1" с выхода элемента НЕ 3, начинают поступать к реверсивному счетчику

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

14, по которому также осуществляется перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение содержимого счетчика 10 на "+1". После этого устройством отрабатывается цикл, содержащий и шагов по числу строк матрицы достижимостей.

На каждом j-ом шаге осуществляется формирование j-й строки матрицы достижимостей (j l,п) следующим образ оме

14 11773

После (j-1)-ro шага содержимое счетчика 10 равно j-t, à j-ый шаг начинается с его увеличения на единицу сигналом с выхода элемента 18 задерж5 ки с одновременным обнулением триггеров 14 и перезаписью кода числа ограничения достижимости с регистра 15 в реверсивный счетчик 16. Обнуление 1 риггеров 14 обеспечивает наличие логического "0" на выходах всех элементов И б моделей 5 дуг. Состояние счетчика 10 преобразуется дешифратором 9 в унитарный код вида ООО,...

О, 1; 0 „...0„... где j — номер выхода дешифратор а 9. "1" с j-го выхода дешифратора 9 поступает через элемент ИЛИ 12 на информационный вход триггера 14> и по первому на данном шаге сигналу с генератора 1 тактовых 20 импульсов записывается в триггер 14 в остальные триггеры 14 первоначально переписывается "0" с выходов элементов ИЛИ 12р (1 = 1,п, 1 Ф j), поскольку на входах этих элементов при-25 сутствуют только "0" с выходов дешифратора 9 и выходов элементов И 6 моделей 5 дуг. "1" с выхода триггера

14 р задержанная элементом 13- задержки на время окончания тактового им- «gp пульса с генератора 1, поступает к элементам И б „(k = 1,п) и появляется на выходе только тех элементов И

6 моделей 5 „дуг, у которых соот1и ветствующие им первые триггеры 7 моделей дуг содержат " 1". Множество

fk<) k, k = 1,п в исследуемом графе соответствует индексам вершин достижимых из вершины j с числом достижимости, равным единице. Сигналы с 40 выходов элементов И 6 поступают

1к к соответствующим триггерам 14„, через элементы ИЛИ 12„По следующему к, сигналу с генератора 1 тактовых импульсов логическая "I записывается 45 в эти триггеры 14„, и аналогичным образом сформнронано мноиестео р.,)u (k

ro тактового сигнала, когда в единичное состояние установлены триггеры .14g . Р— индексы вершин достижимых в исследуемом графе из вершины с числом ограничения достижимости - R т.е. р = {k,I í (k gu..н н, ото соответствует строке 1 матрицы ограниченной достижимости исследуемого графа. Появление (n+1)-го тактового сигнала вызывает отрицательное переполнение реверсивного счетчика 16, сигнал отрицательного переполнения со счетчика 16 через формирователь 17 и элемент И 4„. обеспечивает прохождение сигнала разрешения записи к вторым триггерам 8 строки j матрицы модепей дуг, в которых занесена информация с выходов триггеров 14, представляющая собой строку j матрицы ограниченной достижимости. Сигнал с формирователя 17, задержанный элементом 18 задержки на время, необходимое для занесения информации во вторые триггеры 8 моделей 5 дуг, обеспечивает обнуление триггеров 14, перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение состояния счетчика 10 на j+1. После этого устройством отрабатывается (+1)-й шаг, по окончании которого сформулирована (j+1) -я строка матрицы ограниченной достижимости графа и так до окойчания шага и когда сформирована последняя строка матрицы достижимости ограниченной числом R. Переход счетчика 10 в состояние и+1 вызывает появление логической "1" на (и+1)-м вьмоде дешифратора 9, которая после инвертирования в элементе НЕ 3 обеспечивает блокировку прохождения импульсов с генератора 1 через элемент И 2, а также служит сигналом 11 окончания работы устройства. По этому сигналу с входа устройства снимается сигнал

21 "Пуск" и устройство после занесения новой информации о значении числа

12 ограничения достижимости или новой исходной информации о топологии исследуемого графа готово к следующему циклу работы по определению матрицы ограниченной достижимости для данного исследуемого графа.

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

Устройство для исследования графов, содержащее генератор тактовых импульсов, элемент И, элемент НЕ, группу из и элементов И матрицу моделей дуг из и х и элементов И (n— число вершин графа), дешифратор и счетчик, выходы которого соединены с

Составитель С.Кошелев

Редактор Н.Бобкова Техред А. Кравчук Корректор Г.Решетник

Заказ 3656/46 Тираж 704 Подписное

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

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

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

5 14117 соответствующими информационными входами дешифратора, первый вход элемента И является входом пуска устройства, второй вход элемента И соединен

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

: определения матриц ограниченных дос тижимостей исследуемого графа, в него введены группа из и элементов (ИЛИ, группа из п элементов зйдерг

,жки, группа из и триггеров, регистр, реверсивный счетчик, формиро ватель импульсов, и элемент задержки, . причем каждая модель дуги матрицы р0 содержит первый и второй триггеры, выход элемента задержки соединен с входами установки в ноль всех тригг еров группы, с счетным входом счетчика и с входом разрешения записи ревер- 25 сивного счетчика, информационные вхо,ды которого соединены с соответст( вующими выходами регистра информаУ ционные входы которого являются входом признака ограничения достижимос- З0 ти устройства, j-й выход дешифратора (j = 1,п) соединен с (ri+1) ì входом

j-го элемента ИЛИ группы и с первым входом j-ro элемента И группы, второй вход которого соединен с вторыми 35 входами всех элементов И группы, с входом 1 го элемента задержки (i

1,n, i = j) и с выходом формирова О теля импульсов, вход которого соединен с выходом признака переполнения реверсивного. счетчика, выход j-го элемента И группы соединен с входами синхронизацпи всех вторых триггеров мЬделей дуг i-й строки матрицы (i

1,п, i = j), входы установки в "1" всех вторых тригrеров моделей дуг го столбца матрицы соединены с выхо-, дом j-ro триггера группы и входом 1ro элемента задержки группы, выход которого соединен с первым входом всех элементов И моделей дуг i-й строки матрицы, второй вход элемента И

i j-й модели дуги матрицы соединен с выходом первого триггера этой модели, выход элемента И i j-й модели дуги матрицы соединен с i-и входом (i = — 1,п) j-ro (j = 1,п) элемента ИЛИ группы, выход которого соединен с входом установки в "1" j-го триггера группы, вход синхронизации которого соединен с входаьж синхронизации всех триггеров группы, с выходом элемента

И и с счетным входом реверсивного счетчика, вход установки в "0" счетчика соединен с входом разрешения sanucu информации регистра и является входом начальной установки устройства, входы установки в " 1" первых триггеров моделей дуг матрицы являются информационным входом устройства, вы- ходы вторых триггеров моделей дуг матрицы являются информационным выходом устройства, (n+1)-й выход дешифратора является выходом окончания работы устройства.