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

(56) Авторское свидетельство СССРМ 1277130, кл. 6 06 Р 15/20, 1984,Авторское свидетельство СССРМ 1174937, кл. 6 06 Г 15/20, 1983.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕ МАТРИЦ ДОСТИЖИМОСТЕЙ ГРАФА (57) Изобретение относится к вычисли ной технике и может быть использован решения задач на графах, связанных с о делением матриц достижимостей и к адостижимостей ориентированных гра Изобретение относится к вычислительной технике и может быть использовано для решения задач нэ графах, связанных с определением матриц достижимостей и контрэдостижимостей ориентированных графов, являющимися математическими моделями сетей связи, информационно-расчетных систем и т,д.Цель изобретения - повышение эксплуатационных качеств за счет обеспечения независимости функциональной схемы от топологии исследуемого графа.Сущность изобретения заключается в том, что наборное поле с выпрямительными элементами заменено блоком задания матрицы смежности графа и в устройство введена группа элементов ИЛИ. При этом блок задания матрицы смежности графа содержит бездиагонэльную матрицы из п(п) моделей дуг, каждая из которых содержит)5 С 06 Р 15/20, 15/4 являющихся математическими моделями сетей связи, информационно-расчетных систем и т,д. Цель изобретения - повышение эксплуатационных качеств за счет обеспечения независимости функциональной схемы от топологии исследуемого графа. Устройство содержит блок задания матрицы смежности графа из и (и) моделей дуг (и - число вершин исследуемого графа) и группу элементов ИЛИ. Каждая модель дуги содержит элемент И, триггер и диод. Решение осуществляется последовательным формирован ием строк матрицы достижимостей за счет лавинообразного процесса "включения" моделей дуг в соответствующих столбцах строк матрицы смежности, соответствующих уже "достигнутым" вершинам, 1 ил,триггер, элемент И и диод. Входы триггера являются установочными входами модели дуги, единичный выход триггера соединен с входом элемента И, другой вход которого является входом модели. дуги, он обьединен у всех моделей дуг по строкам матрицы смежности, Это обеспечивает независимость функциональной схемы устройства от топологии исследуемого графа, Выход элемента И моделей дуг соединен с катодом диода, анод которого соединен с выходом модели дуги, который объединен у всех моделей дуг по столбцам матрицы смежности и соединен с входом соответствующего элемента ИЛИ группы, другой. вход которых соединен с соответствующим входом устройства, а выход элементов ИЛИ группы, другой вход которых соединен с соответствующим входом устройства, а выход элементов ИЛИ группы соединен с соответ 1833885ствующим выходом устройства и объединенными входами моделей дуг соответствуощей строки матрицы смежности. Такая коммутация обеспечивает автоматическое опРеделение строк матрицы достижимостей ориентированных графов.Функциональная схемаустройства приведена на чертеже.Устройство содержит блок 1 задания матрицы смежности графа из и (и) моделей 10 дуг 2 Ц = 1, и,Ф ) (и - число вершин исследуемого графа), каждая модель дуги состоит из триггера 3, элемента И 4 и диода 5, входы триггера Б, 7 являются установочными входами модели дуги, й группу 15 элементов ИЛИ 8,= 1,и. Цифровые обозначения на схеме имеют такие входы устройства 9 ь= 1,п и вьиоды устройства 10 ь= 1,п,Устройство работает следующим обра зом.Перед началом решения, подачей импульсов на входы 6 моделей дуг, соответствующих дугам, имеющимся в Исследуемом графе, задается топология графа. При этом триггеры 3 соответствующих моделей дуг переходят в единичное состояние и сигнал с их единичного выхода поступает на вход элемента И этих моделей дуг.Решение по определению -й строки 30 матрицы достижимостей исследуемого графа начинается подачей сигнала уровня логической единицы на вход устройства 9 ( "Тп). При этом сигнал с входа 9 поступает на вход элемента ИЛИ 8 ь С выхода элемента ИЛИ 8 сигнал уровня логической единицыпоступает на выход устройства 10 и объединенные входы моделей дуг -той строки матрицы смежности. С входов моделей дуг 21,= 1, и, )сигнал поступает на вход 40 элемента И. 4 этой модели дуги. Если в исследуемом графе есть ,-я дуга, та на второй вход элемента И 4 соответствующей модели дуги поступает единичный сигнал с единичного выхода триггера 3. С выхода элемента 45 И.4 сигнал через диод 5 поступает на вход соответствующего элемента ИЛИ, например, 8. С выхода элемента 8 сигнал поступает на выход 10 л и объединенные вхоДИ моделей дуг и-ой строки матрицы смежно сти. Дальнейшая работа устройства аналогично и описанный лавинообразный процесс через время 12 п т,где т- время задержки сигнала на схемах логических элементов И, ИЛИ завершается. При этом ин формация на входах устройства 10,- 1,п соответствует -й строке матрицы достижимостей исследуемого графа, то есть единичный сигнал на выходе 10 означает, что и = =1, а нулевой сигнал, например, на выходе 101 - что г 1 = О, Аналогичным образом определяется и любая другая строка матрицы достижИмостей графа.Для определения матрицы контрадостижимостей достаточно перед началом работы в блок 1 ввести не матрицу смежности, а транспонированную матрицу смежности исследуемого графа, Работа устройства по определению строк матрицы контрадостижимостей будет аналогична рассмотренной.Таким образом, и редлагаемое устройство обеспечивает определение эа, и шагов решения как матрицы достижимостей, так и матрицы контрадостижимостей неориентированных графов. При этом функциональная схема предлагаемого устройства не. зависит от топологии исследуемого графа и не требует предварительной механической коммутации элементов. Формула изобретения Устройстводля определения матриц достижимостей графа, содержащее блок задания матрицы смежности графа, о т л и ч аю щ е е с я тем, что, с целью повышения эксплуатационных качеств за счет обеспечения независимости функциональной схемы от топологии исследуемого графа, в устройство введена группа элементов ИЛИ, а блок задания матрицы смежности графа. содержит п(п) моделей дуг, каждая из которых содержит триггер, элемент И и диод (и - число вершин исследуемого графа), первый и второй входы триггера соединены с установочными входами модели дуги, единичный выход триггера соединен с первым входом элемента И, второй вход которого объединен у всех моделей дуг по строкам матрицы, выход элемента И каждой модели дуги соединен с катодом диода, анод диода объединен у всех моделей дуг по столбцам матрицы и соединен с первым входом соответствующего элемента ИЛИ группы, второй вход которого подключен к соответствующему задающему входу устройства, а выходы элементов ИЛИ группы соединены с соответствующим выходом устройства и объединенными входами моделей дуг соответствующей строки матрицы,1833885Составитель А, БорисТехред М.Моргенталедакторрректор М. Самборскаяаказ 2687 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035. Москва, Ж, Рауаская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 10