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

Sin.

(Л

с

оо

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

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

t

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

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

Устройство содержит генератор 1 тактовых импульсов, элемент И 2, эле- |мент НЕ 3, группу из п элементов И 4 |матрицу из п X п моделей 5; дуГрКаж- |дая из которых состоит из элемента |И 6, первого 7 и второго 8 триг- IrepoB, дешифратор 9, счетчик 10, |выход 11 признака окончания работы Устройства, группу из п элементов ИЛИ 12j, группу из п элементов 13,- задержки, группу из п триггеров 14|, регистр 15, реверсивный счетчик 16, фор- йирователь 17 импульсов, элемент 18 йадержки, вход 19 признака ограгаче- йия достижимости устройства, вход 20 Начальной установки устройства и вход .21 пуска устройства. . Устройство работает следующим об- ,

В исходном состоянии сигнал Пуск 21 отсутствует, что блокирует прохож- (ение импульсов с генератора 1 через г|лементы И 2, на выходе которого присутствует логический О, блокирую- работу триггеров 14 и элементов И 6 моделей 5 дуг, счетчик 10 обнулен сигналом 20 начальной;установки, на

выходах дешифратора 9 с первого по (п+1)-й сигналы логического О, блокирующие прохождение сигналов разрешений записи к вторым триггерам 8

моделей 5 дуг, состояние триггеров 14 и реверсивного счетчика 16 - произвольное.

Исходная информация о топологии исследуемого графа заносится в виде

матрицы смежности в триггеры 7 моделей 5 дуг через информационные входы устройства, значение числа R ограничения достижимости заносится через входы 19 в регистр 15 по сигналу 20

начальной установки, одновременно ус- танавливаются в О счетчик 10, после чего устройство готово к работе.

При подаче на выход 11 сигнала Пуск, уровня логической 1, импульсы с генератора 1 через элемент И 2, открытый по третьему входу логической 1 с выхода элемента НЕ 3, начинают поступать к реверсивному счетчику 16, который переполняется и на его выходе отрицательного переполнения появляется сигнал логической 1, обеспечивающей выработку формировате- , лем 17 сигнала обнуления триггеров 14, по которому также осуществляется

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

строк матрицы достижимостей.

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

зом.

3МП773

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

j- j j - « +4 J номер вь1- хода дешифратора 9. 1 с j-ro выхода дешифратора 9 поступает через элемент ИЛИ 12j на информационный вход

10

лом огра1тчения достижимости R, т.е. Р k,j U ..,v{k, , что соответствует строке J матрицы ограниченной достижимости исследуемого графа. Появление (п+1)-го тактового сигнала вызывает отрицательное переполнение реверсивного счетчика 16, сигнал отрицательного переполнения со счетчика 16 через формирователь 17 и элемент И 4,- обеспечивает прохождение сигнала разрешения записи к вторым триггерам 8 строки j матрицы моделей дуг, в которых занесена информация 15 с выходов триггеров 14, представляю- щая собой строку j матрицы ограниченной достижимости. Сигнал с формирователя 17, задержанный элементом 18 задержки на время, необходимое для

обнуление триггеров 14, перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение состояния

IK ся на выходе только тех элементов И

6- моделей 5- дуг, у которых соотJK

триггера 14j и по первому на данном

шаге сигналу с генератора 1 тактовых 20 занесения информации во вторые триг- импульсов записывается в триггер I4j , геры 8 моделей 5 дуг, обеспечивает в остальные триггеры 14( первоначально переписывается О с выходов элементов ИЛИ 120 (1 1,п, 1 / j), поскольку на входах этих элементов при-25 счетчика 10 на j + 1. После этого уст- сутствуют только О с выходов дешиф- ройством отрабатывается (3+1)-й шаг, ратора 9 и выходов элементов И 6 но- по окончании которого сформулирована делей 5 дуг. 1 с выхода триггера(j + D-H строка матрицы ограниченной

14, задержанная элементом 13j задерж- достижимости графа и так до окойчания ки на время окончания тактового им- i. 30 шага п, когда сформирована последняя пульса с генератора 1, поступает кстрока матрицы достижимости ограниэлементам И 6j (k 1,n) и появляет- ченной числом R. Переход счетчика 10

в состояние п-И вызывает появление логической f на (п+1)-м выходе дев етствующие им первые триггеры 7 мо- шифратора 9, которая после инвертиро- делей дуг содержат 1. Множествования в элементе НЕ 3 обеспечивает

1 в исследуемом гра-блокировку прохождения импульсов с

фе соответствует индексам вершин дос- генератора 1 через элемент И 2, а тижимых из вершины j с числом дости-также служит сигналом 11 окончания

4Q работы устройства. По этому сигналу с входа устройства снимается сигнал 21 Пуск и устройство после занесения новой информации о значении числа 12 ограничения достижимости или но1 записывается д вой исходной информации о топологии в эти триггеры и аналогичным об- исследуемого графа готово к следую- разом сформировано множество j «J | лЬ щему циклу работы по определению матфиксируемое установкой в длительное

единичное состояние триггеров 14(, где 1 k, и kj|, а - индексы JQ вершин достижимых из вершины j с числом достижимости, равным двум. Уставка триггеров 14|г осуществляется в момент появления следующего тактово-

жимости, равным единице. Сигналы с выходов элементов И б.- поступают к соответствующим триггерам 14, через элементы ИЛИ 12 . По следующему сигналу с генератора 1 тактовых импульсов логическая

рицы ограниченной достижимости для данного исследуемого графа.

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

Устройство для исследования графов, содержащее генератор тактовых

го сигнала и так до появления (R+1)-импульсов, элемент И, элемент НЕ,

го тактового сигнала, когда в единич- группу из п элементов И, матрицу мо- ное состояние установлены триггеры

делей дуг из п х п элементов И (п - число вершин графа), дешифратор и счетчик, выходы которого соединены с

.14 . Р - индексы вершин достижимых в исследуемо графе из вершины с чис

лом огра1тчения достижимости R, т.е. Р k,j U ..,v{k, , что соответствует строке J матрицы ограниченной достижимости исследуемого графа. Появление (п+1)-го тактового сигнала вызывает отрицательное переполнение реверсивного счетчика 16, сигнал отрицательного переполнения со счетчика 16 через формирователь 17 и элемент И 4,- обеспечивает прохождение сигнала разрешения записи к вторым триггерам 8 строки j матрицы моделей дуг, в которых занесена информация с выходов триггеров 14, представляю- щая собой строку j матрицы ограниченной достижимости. Сигнал с формирователя 17, задержанный элементом 18 задержки на время, необходимое для

обнуление триггеров 14, перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение состояния

занесения информации во вторые триг- геры 8 моделей 5 дуг, обеспечивает счетчика 10 на j + 1. После этого уст- ройством отрабатывается (3+1)-й шаг, по окончании которого сформулирована (j + D-H строка матрицы ограниченной

рицы ограниченной достижимости для данного исследуемого графа.

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

Устройство для исследования графов, содержащее генератор тактовых

группу из п элементов И, матрицу мо-

делей дуг из п х п элементов И (п - число вершин графа), дешифратор и счетчик, выходы которого соединены с

51411773

оответствующими информационными вхотене ре ме си мЪ вс 10 го до го ко вс 15 ки вы вы ма 20 гр вх гр со 25 тр И сч чи пи 30 вх ва ге ин хо ос ри ус ра ус

дами дешифратора, первый вход элемента И является входом пуска устройства, второй вход элемента И соединен с выходом генератора тактовых импульсов, третий вход элемента И соединен с выходом элемента НЕ, вход которогхз соединен с (п+1)-м выходом дешифратора, отличающееся тем, чтОр с целью расширения функциональных возможностей устройства за счет определения матриц ограниченных достижимостей исследуемого гра:фа, в него введены группа из п элементов ИЛИ, группа из п элементов задержки, группа из п триггеров, регистр, реверсивный счетчик, формирователь импульсов, и элемент задержки причем каждая модель дуги матрицы содержит первый и второй триггеры, выход элемента задержки соединён с входами установки в ноль всех триггеров группы, с счетным входом счетчика и с входом разрешения записи реверсивного счетчика, информационные входы которого соединены с соответствующими выходами регистра, информационные входы которого являются входом признака ограничения достижимости устройства, выход дешифратора (J 1,п) соединен с (п+1)-м входом j-ro элемента ШШ группы и с первым входом j-rp элемента И группы, второй вход которого соединен с вторыми входами всех элементов И группы, с входом i-ro элемента задержки (i 1,п, i J) и с выходом формирователя импульсов, вход которого соединен с выходом признака пе зепопнения реверсивногооСчетчика, выход j-ro элемента И группы соединен с входами синхронизацт и всех вторых триггеров мЪделей дуг i-й строки матрицы (1 1,п, i j), входы установки в 1 всех вторых триггеров моделей дуг j- го столбца матрицы соединены с выходом j-ro триггера группы и входом j- го элемента задержки группы, выход которого соединен с первым входом всех элементов И моделей дуг i-й стро- 5 ки матрицы, второй вход элемента И i,j-й модели дуги матрицы соединен с выходом первого триггера этой модели, выход элемента И i,j-й модели дуги матрицы соединен с i-м входом (i 0 ) j-ro (j 1,n) элемента ИЛИ группы, выход которого соединен с входом установки в 1 j-ro триггера группы, вход синхронизации которого соединен с входами синхронизации всех 5 триггеров группы, с выходом элемента И и с счетным входом реверсивного счетчика, вход установки в О счетчика соединен с входом разрешения записи информации регистра и является 0 входом начальной установки устройства, входы установки в 1 первых триггеров моделей дуг матрицы являются информационным входом устройства, вы- ходы вторых триггеров моделей дуг мат- с рицы являются информационным выходом устройства, (п+1)-й выход дешифратора является выходом окончания работы устройства.