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

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

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

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

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

Устройство работает следукяцим образом.

В исходном состоянии сигнал пуска 12 имеет значение О, что блокирует прохождение импульсов с генератора 7 через элемент И 8 на выходе которого присутствует , блокирующий работу элементов И 2 моделей дуг 1, на третьем входе элемента И 8 присут-

ствует 1 с выхода элемента НЕ 9,

40

так как счетчик 11 обнулен и на выхое дешифратора 10 с 01 по (К+1) - О

Исходная информация о топологии графа заносится в виде матрицы смеж- в триггеры 3 моделей дуг 1 через информационные входы устройства, совпадающие с входами начальной установки триггеров 3 моделей дуг 1, после чего устройство готово к работе. При подаче на вход 12 сигнала Пуск уровня 1 импульсы с генератора тактовых импульсов 7 через элементы И 8 начинают поступать к счетчику.1, состояние которого преобразуется дешифратором 10 в позиционный код. В i ходе работы устройства с каждым тактовым импульсом с генератора 7 Р последовательно нзменя.ется от О до (К+1), соответственно этому изме- 55 няется позиционньй код на выходах дешифратора 10. При этом на тактах Р 1..„К в триггерах 3 моделей дуг

50

5

л

5

0

1 происходит преобразование строки Р матрицы с.межности заданного графа в соответствующие строки матрицы достижимости. Преобразование происходит следуиядим образом. На такте Р М на выходе М дешифратора 10 появляется сигнал 1, который через элемент ШШ 4 и открытый тактовым импульсом с элемента И 8 элемент И 6 поступает на входы элементов И 2 М строки матрицы моделей дуг. Если в некоч-ором триггере 3.модели дуги 1 записана 1, то на выходе соответствующего элемента И 2 появится сигнал 1, означающий достижимость вершины данной из вершины М. Этот сигнал через элемент, ИЛИ 4 и И 6 поступит на входы элементов И Z соответствукядей строки матрицы моделей дуг .1, на выходах которых также появляются 1 при наличии 1 в соответствующем триггере 3 модели дуг 1, поступающие на входы элементов ИЛИ .4 с индексами, совпадающими с индексами достижимых вершин, а значит достижимых и из вер

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

31

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

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

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

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

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

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

дуги.

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