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

(Л

С

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

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

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

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

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

со со

00 00

ел

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

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

Устройство содержит блок 1 задания матрицы смежности графа из п (п-1) моделей дуг 2ij, l,j 1, n, I & j (n - число вершин исследуемого графа), каждая модель Дуги состоит из триггера 3, элемента И 4 и диода 5, входы триггера 6, 7 являются установочными входами модели дуги, и группу элементов ИЛИ 8i, i 1,n. Цифровые обозначения на схеме имеют такие входы устройства 9i, I - 1,п и выходы устройства 10i, l 1,n.

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

Перед началом решения, подачей импульсов на входы б моделей дуг, соответствующих дугам, имеющимся в Исследуемом грёфе, задается топология графа. При этом триггеры 3 соответствующих моделей дуг Переходят в единичное состояние и сигнал с их единичного выхода поступает на вход элемента И этих моделей дуг.

Решение по определению 1-й строки матрицы достижимостей исследуемого графа начинается подачей сигнала уровня логической единицы на вход устройства 9| (). При этом сигнал с входа 9i поступает на вход элемента ИЛИ 8i. С выхода элемента ИЛИ 8i сигнал уровня логической единицы поступает на выход устройства 10i и объединенные входы моделей дуг l-той строки матрицы смежности. С входов моделей дуг 2ij, j 1, n, J & i сигнал поступает на вход элемента И 4 этой модели дуги. Если в исследуемом графе есть i.j-я дуга, то на второй вход элемента И 4 соответствующей модели дуги поступает единичный сигнал с единичного выхода триггера 3. С выхода элемента И 4 сигнал через диод 5 поступает на вход соответствующего элемента ИЛИ, например, 8п. С выхода элемента 8П сигнал поступает на выход 10п и объединенные вхоДь моделей дуг n-ой строки матрицы смежности. Дальнейшая работа устройства аналогично и описанный лавинообразный процесс через время t 2n г,гдег- время задержки сигнала на схемах логических элементов И, ИЛИ завершается. При этом информация на входах устройства 101, I 1,п соответствует 1-й строке матрицы достижимостей исследуемого графа, то есть единичный сигнал на выходе 10i означает, что m

1, а нулевой сигнал, например, на выходе 10i - что m 0. Аналогичным образом определяется и любая другая строка матрицы достижимостей графа.

Для определения матрицы контрадостижимостей достаточно перед началом работы в блок 1 ввести не матрицу смежности, а транспонированную матрицу смежности исследуемого графа. Работа устройства по определению строк матрицы контрадостижимостей будет аналогична рассмотренной.

Таким образом, предлагаемое устройство обеспечивает определение за. n шагов решения как матрицы достижимостей, так и

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

коммутации элементов.

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

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

строкам матрицы, выход элемента И каждой модели дуги соединен с катодом диода, анод диода объединен у всех моделей дуг по столбцам матрицы и соединен с первым входом соответствующего элемента ИЛИ группы, второй вход которого подключен к соответствующему задающему входу устройства, а выходы элементов ИЛИ группы соединены с соответствующим выходом устройства и объединенными входами моделей дуг соответствующей строки матрицы.