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

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

Устройство для исследования графов, содержащее n моделей вершин, выполненных в виде триггеров (где n - число вершин исследуемого графа), группу элементов И, первую группу элементов ИЛИ, а также блок задания матрицы смежности, выполненный в виде верхней треугольной подматрицы из моделей ребер, каждая из которых содержит триггер и элемент И, причем входы триггера каждой модели ребра являются установочными входами этой модели ребра, прямой выход триггера каждой модели ребра соединен со вторым входом элемента И этой модели ребра, вход сброса триггера каждой модели вершины соединен с входом возврата моделей вершин в исходное состояние, прямой выход триггера каждой модели вершины соединен с соответствующим выходом устройства и первым входом соответствующего элемента ИЛИ первой группы, второй вход каждого элемента ИЛИ первой группы соединен с соответствующим входом задания устройства, а выход - с первым входом соответствующего элемента И группы, второй вход каждого элемента И группы соединен со входом запуска устройства, отличающееся тем, что в него дополнительно введены элемент ИЛИ в каждую модель ребра и вторая группа элементов ИЛИ, причем выход элемента И модели ребра (x_i, x _j) соединен с i-м входом j-го элемента ИЛИ второй группы и с j-м входом i-го элемента ИЛИ второй группы выход i-го элемента ИЛИ второй группы соединен со входом установки триггера модели i-й вершины , выход i-го элемента И группы соединен с первыми входами элементов ИЛИ всех моделей ребер i-й строки и со вторыми входами элементов ИЛИ всех моделей ребер i-го столбца выход элемента ИЛИ каждой модели ребра соединен с первым входом элемента И этой модели ребра.

Описание изобретения к патенту

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

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

Недостатком данного устройства является отсутствие возможности формирования отображений множества вершин графа.

Наиболее близким по технической сущности к заявляемому изобретению является устройство для исследования графов [2], содержащее n моделей вершин (где n - число вершин исследуемого графа), группу элементов И, группу элементов ИЛИ, а также блок задания матрицы смежности, выполненный в виде матрицы из n(n-1) моделей дуг, каждая из которых содержит триггер, элемент И и диод.

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

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

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

моделей ребер, каждая из которых содержит триггер и элемент И, причем входы триггера каждой модели ребра являются установочными входами этой модели ребра, прямой выход триггера каждой модели ребра соединен со вторым входом элемента И этой модели ребра, вход сброса триггера каждой модели вершины соединен с входом возврата моделей вершин в исходное состояние, прямой выход триггера каждой модели вершины соединен с соответствующим выходом устройства и первым входом соответствующего элемента ИЛИ первой группы, второй вход каждого элемента ИЛИ первой группы соединен с соответствующим входом задания устройства, а выход - с первым входом соответствующего элемента И группы, второй вход каждого элемента И группы соединен со входом запуска устройства, согласно изобретению дополнительно введены элемент ИЛИ в каждую модель ребра и вторая группа элементов ИЛИ, причем выход элемента И модели ребра (x_i, x_j) соединен с i-м входом j-го элемента ИЛИ второй группы и с j-м входом i-го элемента ИЛИ второй группы , выход i-го элемента ИЛИ второй группы соединен со входом установки триггера модели i-й вершины , выход i-го элемента И группы соединен с первыми входами элементов ИЛИ всех моделей ребер i-й строки и со вторыми входами элементов ИЛИ всех моделей ребер i-го столбца , выход элемента ИЛИ каждой модели ребра соединен с первым входом элемента И этой модели ребра.

Устройство для исследования графов (чертеж) содержит блок 1 задания матрицы смежности, выполненный в виде верхней треугольной подматрицы из моделей 2_ij ребер , каждая из которых содержит триггер 3, элемент И 4, элемент ИЛИ 5 и оборудована установочными входами 6 и 7, вторую группу элементов ИЛИ 8, группу элементов И 9, первую группу элементов ИЛИ 10, n триггеров моделей вершин 11_i, входы 12 _i задания устройства, n-разрядный выход 13, вход 14 возврата моделей вершин в исходное состояние, вход 15 запуска устройства, причем установочные входы 6 и 7 всех моделей ребер соединены со входами сброса и установки триггеров 3 этих моделей ребер соответственно, прямой выход триггера 3 каждой модели ребра соединен со вторым входом элемента И 4 данной модели ребра, первый вход которого соединен с выходом элемента ИЛИ 5 этой модели ребра, выход элемента И 4 модели ребра (x_i, x_j ) соединен с i-м входом j-го элемента ИЛИ группы 8 и с j-м входом i-го элемента ИЛИ группы 8 , выход i-го элемента ИЛИ группы 8 соединен со входом установки триггера 11_i модели i-й вершины , вход сброса каждого из триггеров 11 моделей вершин соединен со входом 14 возврата моделей вершин в исходное состояние, прямой выход триггера 11 _i модели i-й вершины соединен с i-м разрядом выхода 13 устройства и с первым входом i-го элемента ИЛИ группы 10 , второй вход каждого элемента ИЛИ группы 10 соединен с соответствующим входом 12 задания устройства, а выход - с первым входом соответствующего элемента И группы 9, второй вход каждого элемента И группы 9 соединен со входом 15 запуска устройства, выход i-го элемента И группы 9 соединен с первыми входами элементов ИЛИ 5 всех моделей ребер i-й строки и со вторыми входами элементов ИЛИ 5 всех моделей ребер i-го столбца .

Рассмотрим процесс функционирования предлагаемого устройства.

Перед началом работы устройства задается топология исследуемого графа. Для этого выполняется подача импульсов на входы 5 и 6 всех моделей ребер, соответствующих ребрам графа. При этом триггеры 3 этих моделей ребер переходят в единичное состояние и сигналы с их прямых выходов открывают соответствующие элементы И 4. Множество вершин Q, для которого необходимо определить отображение, задается подачей единичного сигнала на соответствующие входы 12_i, , x_i Q.

Решение начинается подачей импульса на вход 15 устройства. Длительность этого импульса должна быть достаточной для срабатывания триггеров моделей вершин, но не превышать времени перехода триггеров из одного состояния в другое. Импульс со входа 15 поступает на входы элементов всех элементов И группы 8. Так как на других входах единичный сигнал присутствует только у тех элементов И группы 8, которые соответствуют вершинам множества Q, единичный уровень сигнала появится только на выходах этих элементов. Сигнал с выхода указанных элементов И группы 8 поступает через элементы ИЛИ 5 на входы элементов И 4 всех моделей ребер соответствующих строк матрицы смежности графа. Если в исследуемом графе присутствует ребро (x_i, x_j), (x _j, x_i), x_i Q, то на обоих входах элемента И4 модели ребра

2_ij будет единичный сигнал. Этот сигнал с выхода элемента И4 через элемент ИЛИ 8_j поступает на вход установки триггера 11_j модели вершины. Триггер переходит в единичное состояние и сигнал с его прямого выхода поступает на выход 13 устройства и проходит через элемент ИЛИ 10_j. С выхода элемента ИЛИ 10_j единичный сигнал поступает на вход элемента И 9_j. Однако поскольку к этому моменту времени сигнала на втором входе данного элемента И уже не будет, на его выходе зафиксируется нулевой уровень сигнала.

Триггеры моделей вершин 11_i, перешедшие за первый такт работы устройства в единичное состояние, однозначно определяют множество вершин отображения Г(Q). Для определения отображения Г²(Q) необходимо подать на вход 15 устройства второй импульс. Устройство при этом будет функционировать аналогично рассмотренному выше. Для определения отображения Г³ (Q) на вход 15 подается третий импульс и так далее. При необходимости определить отображения для другого множества Q предварительно необходимо вернуть в исходное состояние все модели вершин. Для этого осуществляется подача импульса на вход 14 устройства, что обеспечивает сброс триггеров 11_i моделей вершин.

Оценим преимущества предлагаемого устройства по сравнению с прототипом с точки зрения аппаратной сложности.

Устройство [2] содержит n 2-входовых элементов ИЛИ, n 2-входовых элементов И, n триггеров моделей вершин и n(n-1) моделей дуг, в состав которых входят n(n-1) триггеров, n(n-1) 2-входовых элементов И и n(n-1) диодов; его аппаратная сложность, таким образом, составляет R=n+n+2n+n(n-1)(2+1+1)=4n² эквивалентных вентилей. Предлагаемое устройство содержит n 2-входовых элементов ИЛИ, n 2-входовых элементов И, n триггеров моделей вершин, n(n-1) - входовых элементов ИЛИ и моделей ребер, в состав каждой из которых входит триггер, 2-входовой элемент И и 2-входовой элемент ИЛИ; его аппаратная сложность в числе эквивалентных вентилей, таким образом, составляет R=n+n+2n+n(n-2)+ (2+1+1)=3n². Значения величины R для прототипа и предлагаемого устройства, рассчитанные для различных n по выведенным формулам, приведены в нижеследующей таблице.

n	Предлагаемое устройство эквивалентных вентилей	Прототип эквивалентных вентилей	Разница эквивалентных вентилей
10	300	400	100
100	30000	40000	10000
1000	3000000	4000000	1000000

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

Источники информации

1. Авторское свидетельство СССР № 1304033, кл. G06F 15/20, заявл. 25.07.85, опубл. 15.04.87, бюл. № 14.

2. Патент РФ № 2011218, кл. G06F 15/20, кл. G06F 15/419, заявл. 17.04.91, опубл. 15.04.94 (прототип).