УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ Российский патент 2009 года по МПК G06N7/00 G06F17/00 

Устройство относится к вычислительной технике и может быть использовано для аппаратного определения 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 (прототип).

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

моделей ребер, каждая из которых содержит триггер, элемент И и элемент ИЛИ. 1 ил., 1 табл.

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