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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4918387/24 (22) 11.03.91 (46) 15.08,93. Бюл. ¹ 30 (72) А.M.Áîðèñoâ, С.M Êàøèí, А.Н,Хомяков и Н,И.Ячкула (56) Авторское свидетельство СССР

¹1277130,,кл. 6 06 F 15/20, 1984, Авторское свидетельство СССР

¹ 1174937, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

МАТРИЦ ДОСТИЖИМОСТЕЙ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением матриц достижимостей и контрадостижимостей ориентированных графов, Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением матриц достижимостей и контрадостижимостей ориентированных графов, являющимися математическими моделями сетей связи, информационно-расчетных систем и т,д.

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

Сущность изобретения заключается в том, что наборное поле с выпрямительными элементами заменено блоком задания матрицы смежности графа и в устройство введена группа элементов ИЛИ. При этом блок задания матрицы смежности графа содержит бездиагональную матрицы из п(п-1) моделей дуг, каждая из которых содержит,, А2,„, 1833885 А1 (я)з G 06 F 15/20, 15/419 являющихся математическими моделями сетей связи, информационно-расчетных систем и т,д. Цель изобретения — повышение эксплуатационных качеств за счет обеспечения независимости функциональной схемы от топологии исследуемого графа. Устройство содержит блок задания матрицы смежности графа из и (и-1) моделей дуг (n — число вершин исследуемого графа) и группу элементов ИЛИ. Каждая модель дуги содержит элемент И, триггер и диод. Решение осуществляется последовательным формирован ием строк матрицы достижимостей за счет лавинообразного процесса "включения" моделей дуг в соответствующих столбцах строк матрицы смежности, соответствующих уже "достигнутым" вершинам. 1 ил, триггер, элемент И и диод. Входы триггера являются установочными входами модели дуги, единичный выход триггера соединен с входом элемента И, другой вход которого является входом модели. дуги, он обьединен у всех моделей дуг по строкам матрицы смежности. Это обеспечивает независимость функциональной схемы устройства от топологии исследуемого графа, Выход элемента И моделей дуг соединен с катодом диода, анод которого соединен с выходом модели дуги, который объединен у всех моделей дуг по столбцам матрицы смежности и соединен с входом соответствующего элемента ИЛИ группы, другой. вход которых соединен с соответствующим входом устройства, а выход элементов ИЛИ группы, другой вход которых соединен с соответствующим входом устройства, а выход элементов ИЛИ группы соединен с соответ1833885 ствующим выходом устройства и объединенными входами моделей дуг соответствующей строки матрицы смежности. Такая коммутация обеспечивает автоматическое определение строк матрицы достижимостай ориентированных графов.

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

Устройство содержит блок 1 задания матрицы смежности графа из и (n-1) моделей дуг 2ii, Ц = 1, и, l Ф j (n — число вершин исследуемого графа), каждая модель дуги состоит из триггера 3, элемента И 4 и диода

5, входы триггера Б, 7 являются установочными входами модели дуги, и группу 15 элементов ИЛИ 8l, 1= 1,п. Цифровые обозначения на схеме имеют такие входы устройства 9l, i 1,п и выходы устройства 10l, 1 = 1,n, Устройство работает следующим обра- 20 зом.

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

Решение по определению 1-й строки 30 матрицы достижимостей исследуемого графа начинается подачей сигнала уровня логической единицы на вход уСтройства 9l (i - Тп). При этом сигнал с входа 9l поступает на вход элемента ИЛИ 8ь С выхода элемента

ИЛИ 8l сигнал уровня логической единицЫ поступает на выход устройства 10l и объединенные входы моделей дуг i-той строки матрицы смежности. С входов моделей дуг

2li j = 1, n, ) < i сигнал поступает на вход 40 элемента И.4 этой модели дуги. Если в исследуемом графе есть ц-я дуга, та на второй вход элемента И 4 соответствующей модели дуги поступает единичнмй сигнал с единичного выхода триггера 3. С выхода элемента 45

И.4 сигнал через диод 5 поступает на вход соответствующего элемента ИЛИ, например, 8п. С выхода элемента 8п сигнал поступает на выход 10л и объединенные входы моделей дуг и-ой строки матрицы смежно- 50 сти. Дальнейшая работа устройства аналогично и описанный лавинообразный процесс через время t 2п т,где r- время задержки сигнала на схемах логических элементов И, ИЛИ завершается. При этом ин- 55 формация на входах устройства 10i 1 - 1,п соответствует i-й строке матрицы достижимостей исследуемого графа, то есть единичный сигнал на выходе 10l означает, что nl =

=1, а нулевой сигнал, например, на выходе

10i — что rlt = О. Аналогичным образом определяется и любая другая строка матрицы достижИмостей графа.

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

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

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

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

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

Составитель А, Борисов

Техред М.Моргентал Корректор М. Самборская

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 2687 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035. Москва, Ж-35, Рауяская наб., 4/5