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

 

Изобретение относится к вычислительной технике и может быть использовано для определения K-кратных отображений множества вершин исследуемого графа /K = 1,2,3 . . . /. Устройство содержит n моделей вершин (n - число вершин в исследуемом графе), блок задания матрицы смежности из n (n - 1) моделей дуг, группу элементов И и группу элементов ИЛИ. Модель дуги состоит из триггера, элемента И и диода. Работа устройства при определении Г^к(Q), осуществляется за K тактов. При этом на первом определяется Г(Q), на втором - Г²(Q) и т. д. Для определения обратных соответствий Г^-к(Q) в блок задания матрицы смежности вводится транспонированная матрица смежности исследуемого графа. 1 ил.

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

Известно устройство для исследования графов [1] , содержащее модели вершин, соединенные согласно топологии исследуемого графа, регистр, группу элементов ИЛИ и группу элементов И.

Однако данное устройство не обеспечивает определение отображений множества вершин графа.

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

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

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

На чертеже показана функциональная схема устройства.

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

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

Решение начинается подачей импульса на вход 11. При этом длительность этого импульса должна быть достаточна для срабатывания триггера модели вершины, но меньше чем время перехода триггера из одного состояния в другое. Импульс с входа 11 поступает на объединенные входы элементов И 8_i, i = . Так как при этом на другом входе сигнал присутствует только у элементов И, соответствующих вершинам множества Q, то сигнал с выхода этих элементов И поступает на входы элементов И 4 моделей дуг, соответствующих строк матрицы смежности графа. Если в исследуемом графе дуга (x_i, x_j) есть (i| x_i∈ Q), то на обоих входах элемента И 4 модели дуги 2_ij будет сигнал высокого уровня и с выхода элемента И сигнал через диод 5 поступает на единичный вход триггера модели вершины 10_j.

Триггер переходит в единичное состояние и сигнал с его единичного выхода поступает на выход 13_j и вход элемента ИЛИ 9_j.

С выхода элемента ИЛИ 9 сигнал поступает на вход элемента И 8_j, однако к этому моменту времени сигнала на втором входе элемента И уже не будет. Триггеры моделей вершин 10_i, i = , перешедшие за первый такт работы устройства в единичное состояние, однозначно определяют множество вершин отображения Г(Q). Для определения Г²(Q) необходимо подать на вход 11 второй импульс. Работа устройства при этом будет аналогична рассмотренной на первом такте. Для определения Г³(Q) подается третий импульс на вход 11 и так далее. При необходимости определить отображения для другого множества Q предварительно возвращаются в исходное модели вершин 10_i, i = подачей импульса на вход 14, с которого сигнал поступает на объединенные нулевые входы триггеров моделей вершин 10_i, i = .

Обратные соответствия Г^-k(Q), k = = 1,2,3, . . . , n определяются устройством аналогично, но перед работой в блок 1 вводится не матрица смежности, а транспонированная матрица смежности исследуемого графа. (56) 1. Авторское свидетельство СССР N 408312, кл. G 06 F 15/20, 1971.

2. Авторское свидетельство СССР N 43880, кл. G 06 F 15/20, 1975.

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

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее n моделей вершин (n-число вершин исследуемого графа) и группу элементов И, отличающееся тем, что, с целью расширения класса решаемых задач путем определения отображений множества вершин графа, в него введены блок задания матрицы смежности, выполненный в виде матрицы n(n - 1) моделей дуг, каждая из которых содержит триггер, элемент И и диод, а также группу элементов ИЛИ, причем входы триггера модели дуги образуют установочные входы модели дуги, а единичный выход триггера соединен с первым входом элемента И модели дуги, а второй вход элемента И объединен у всех моделей дуг по строкам матрицы и соединен с выходом соответствующего элемента И группы, выход элемента И модели дуги соединен с катодом диода, аноды диодов моделей дуг объединены по столбцам матрицы и соединены с первыми входами соответствующих моделей вершин, вторые входы которых объединены и соединены с входом возврата моделей вершин в исходное состояние, выход каждой модели вершин соединен с соответствующим выходом устройства и первым входом соответствующего элемента ИЛИ группы, второй вход каждого элемента ИЛИ группы соединен с соответствующим входом задания устройства, а выход - с первым входом соответствующего элемента И группы, вторые входы элементов И группы объединены и соединены с входом запуска устройства.

РИСУНКИ

Рисунок 1