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

 

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

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

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

РЕСПУБЛИН (19) (И) А1 (5D4 06 F 20

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

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

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4155319/24-24 (22) 02 ° 12.86 (46) 15.07.88. Бюл. В 26 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк (53) 681.333 (088 8) (56) Авторское свидетельство СССР

У 1134946, кл. G 06 F 15/20, 1985.

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

У 1174937, кл. С 06 F 15/20, 1985. (54) .УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАТРИЦЫ ДОСТИЖИМОСТЕЙ ГРАФА (57) Изобретение относится к области вычислительной техники и может быть использовано для исследования графов а также для автоматизированного решения задач обработки информации, допускающих теоретико-графовое представление. Цель изобретения — повышение быстродействия за счет сокращения времени задания исходной информации о топологии графа. Устройство содержит матрицу моделей дуг 1., группу элементов И 6, генератор тактовых импульсов 7, элемент И 8, элемент

НЕ 9, дешифратор 10, счетчик !1, группу элементов И 4 и группу элементов задержки 5, причем каждая из моделей дуг 1 состоит из.элемента

И 2, триггера 3 и элемента И 15.

1 з.п. ф-лы, 1 ил.

i 410054

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

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

На чертеже приведена структурная схема устройства.

Устройство содержит матрицу моделей дуг i каждая из которых состоит из первого элемента И 2 и триггера 3, группу элементов ИЛИ 4, группу элементов задержки 5, группу элементов И 6, генератор тактовых импульсов 7, элемент И 8, элемент НЕ 9, дешифратор 10, счетчик 11, вход пуска 12 устройства, вход начальной установки 13 устройства, выход 14

oK0Híàíèÿ работы устройства, кроме 25 того, каждая модель дуги 1 содержит второй элемент И 15.

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

В исходнОм сОстОянии сигнал пуска 30

12 имеет значение "0", что блокирует прохождение импульсов с генератора 7 через элемент И 8, на выходе которого присутствует "0", блокирующий работу элементов И 2 моделей дуг 1, на третьем. входе элемента И 8 присут- 35 ствует "1" с выхода элемента НЕ 9, так как счетчик 11 обнулен и на выходе дешифратора 10 с 01 по (К+1) — "0"

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

При подаче на вход 12 сигнала "Пуск" уровня "1" импульсы с генератора тактовых импульсов 7 через элементы И 8 начинают поступать к счетчику,1, состояние которого преобразуется де- 50 шифратором 10 в позиционный код. В ; ходе работы устройства с каждым тактовым импульсом с генератора .

7 P последовательно изменяется от 0 до (K+1) соответственно этому изме- 55 няется позиционный код на выходах дешифратора 10. При этом на тактах

P = 1...К в триггерах 3 моделей дуг

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

ИЛИ 4 и открытый тактовым импульсом с элемента И 8 элемент И 6 поступает на входы элементов И 2 М строки матрицы модЕлей дуг. Если в некотором триггере З,модели дуги 1 записана

"1", то на выходе соответствующего элемента И 2 появится сигнал "1", означающий достижимость вершины данной из вершины М. Этот сигнал через элемент ИЛИ 4 и И 6 поступит на входы элементов И 2. соответствующей строки матрицы моделей дуг .1, на выходах которых также появляются "1". при наличии 1 в соответствующем триггере 3 модели дуг 1, поступающие на входы элементов ИЛИ .4 с индексами, совпадающими с индексами достижимых вершин, а значит достижимых и из вершины И и т.д. Таким образом, на каждом такте P на выходах элементов

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

Информация с выходов элементов ИЛИ 4 . поступает через открытые элементы

И 6 и элементы И 15 на информационные входы триггеров 3 всех строк матрицы моделей дуг 1, но ее фиксация осуще- ствляется только в триггерах 3 строки Р, т.е. строки с номером равным номеру текущего такта. Фиксация обеспечивается подачей на вторые входы элемента И 15 сигнаЛа занесения информации в триггеры 3 P-й строки . матрицы моделей дуг 1, с P-го выхода дешифратора 10, задержанного соответствующим элементом задержки 5 по переднему фронту на время, необходимое для формирования строки матрицы достижимостей в группах элементов

ИЛИ 4 и элементов И 6. После записи строки P матрицы достижимостей тактовый сигнал с выхода элемента И 8 принимает значение "0", что обеспечивает кратковременную блокировку

Элементов И 6 и обнуление выходов всех элементов И 2 моделей дуг 1, а также выходов элементов ИЛИ 4. При этом обеспечивается исключение влия1410054 ния обратных связей, имеющих место при наличии в графе сильносвязных компонент, на достоверность информации в формируемой матрице достижимостей. Следукяций тактовый импульс с генератора 7 переводит счетчик 1 в Р+1 состояние и устройством формируется следующая строка матрицы достижимостей и т.д . до достижения состояния К+1, когда в триггерах 3 моделей дуг 1 полностью сформирована матрица достижимостей, при этом на выходе (К+1)-ro дешифратора 10 появляется "1", блокирующая через элемент НЕ 9 и элемент И 8 прохождение импульсов с генератора 7, что блокирует работу устройства в целом. Íàличие " 1" на (К+1)-м выходе дешифратора 10 служит также сигналом окончания работы 14, по которому с входов устройства снимается сигнал 12 "Пуск" и выдается сигнал 13 начальной установки, при этом счетчик 11 обнуляется и после занесения в триггеры

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

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

1. Устройство для определения матрицы достижимостей графа, содержащее .генератор тактовых импульсов, элемент И, элемент НЕ, группу элементов

И, матрицу моделей дуг, дешифратор, счетчик, информационные выходы которого соединены с информационными входами дешифратора, (К+1)-й выход которого (где К вЂ” количество вершин в графе) соединен с входом элемента

НЕ, выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого является входом пуска устройства, о т л и— второго по (К+1)-й М-го элемента

ИЛИ группы соединен с выходом соответствующей модели дуги M-го столбца матрицы, выход M-го элемента ИЛИ

2я группы (где М = 1,...,К) соединен с вторым входом M-ro элемента И группы, выход которого соединен с вторыми входами моделей дуг M-го столбца матрицы и с третьими входами моделей дуг M-й строки матрицы, (К+1)-й выход дешифратора является выходом признака окончания работы устройства.

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

40 являются соответственно первым и вто" рым входами модели дуги, второй вход первого элемента И .является третьим входом модели дуги,. а выход элемента И является выходом модели

45 дуги.

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

ИЛИ, группа элементов .задержки, выход элемента НЕ соединен с третьим входом элемента И, выход которого соединен с первыми входами элементов

И группы и со счетным входом .счетчика, вход сброса которого является входом сброса устройства, М-й выход дешифратора (где M = 1,...,К) соединен с первым входом соответствующего

М-го элемента ИЛИ группы и с входом соответствующего М-ro элемента задержки группы, выход которого соединен с первыми входами моделей дуг

M-й строки матрицы, каждый вход с