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

 

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

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

Известно устройство для определения связности ориентированного графа, содержащее n+2 групп элементов И (n - число вершин исследуемого графа), группу регистров, дешифратор, элемент НЕ, первый и второй элементы И, генератор тактовых импульсов и матрицу смежности графа в виде наборного поля и выпрямительных элементов [1] . Данное устройство имеет низкое быстродействие, ограниченный круг решаемых задач исследования связности, а также характеризуется сложной и зависящей от топологии исследуемого графа функциональной схемой.

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

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

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

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

Устройство содержит матрицу 1 смежности, первую 2i и вторую 3i группы элементов ИЛИ, группу элементов И 4i, первую 5i и вторую 6i группы входов устройства, первую 7i, вторую 8i и третью 9i группы выходов устройства (i = , где n - число вершин исследуемого графа).

Матрица смежности предназначена для задания топологии исследуемого графа и обеспечения связей между элементами устройства в соответствии с решаемой задачей. Она содержит n(n-1) моделей 10ij дуг, ij = , i≠j, каждая из которых содержит триггер 11, первый 12 и второй 13 элементы И, первый 14 и второй 15 диоды, а также установочные входы 16, 17.

Устройство обеспечивает решение следующих задач анализа связности ориентированных графов.

Задача А. Построчное определение матрицы достижимостей графа.

Задача Б. Построчное определение матрицы контрдостижимостей графа. Задача В. Определение существенных вершин между двумя концевыми вершинами графа.

Задача Г. Определение сильных компонент графов.

Перед использованием устройства подачей импульсов на входы 16 моделей дуг соответствующим дугам, имеющимся в исследуемом графе, задается топология графа. При этом импульс с входов 16 поступает на единичный вход триггера 11 соответствующей модели дуги, триггер переходит в единичное состояние и сигнал с его единичного выхода поступает на объединенные входы первого 12 и второго 13 элементов И модели дуги. Триггеры моделей дуг, соответствующие дугам, отсутствующим в исследуемом графе, остаются в исходном нулевом состоянии.

Работает устройство при решении перечисленных задач анализа связности следующим образом.

Задача А. Для определения i-й матрицы достижимостей - R(х_i) подается единичный потенциал на вход 5i первой группы входов. При этом сигнал высокого уровня поступает с входа 5i на элемент ИЛИ 2i, а с его выхода на объединенные первые входы моделей 10i, j дуг, i, j = , j ≠i, выход 8i второй группы выходов устройства и вход элемента И 4i группы. Сигнал с первых входов моделей дуг поступает на вход их первого элемента И 12. Если триггер данной модели дуги находится в единичном состоянии(т. е. если в моделируемом графе есть соответствующая дуга), то сигнал единичного уровня присутствует на обоих входах элемента И 12 этой модели дуги и сигнал с выхода элемента И 12 поступает через диод 14 на вход элемента ИЛИ первой группы, соответствующего по номеру столбцу, в котором находится модель дуги. Далее описанный выше процесс, но уже возможно для нескольких строк матрицы смежностей повторяется и после его завершения потенциалы единичного уровня присутствуют на тех выходах 8i, i = , которым соответствуют единичные элементы i-й строки матрицы достижимостей исследуемого графа. Верхней оценкой продолжительности решения задачи А является Т = 2n τ, где τ - время задержки на логических элементах И, ИЛИ. Учитывая, что τ имеет порядок несколько пикосекунд, Т имеет порядок несколько микросекунд даже для графов с десятком тысяч вершин.

Задача Б. Для определения i-й строки матрицы контрдостижимостей - Q(х_i) подается единичный потенциал на вход 6i второй группы входов устройства. Работа устройства аналогична его работе при решении задачи А с тем отличием, что сигнал с выхода элементов ИЛИ 3i поступает на объединенные вторые входы моделей дуг соответствующих столбцов матрицы смежности и на соответствующие выходы 7i первой группы выходов, а сигналы с вторых выходов моделей дуг, соответствующих единичным элементам данных столбцов матрицы смежности графа, - на входы элементов ИЛИ 3i, соответствующие по номеру строкам, в которых находятся эти модели дуг. По завершении процесса решения потенциалы единичного уровня присутствуют на тех выходах 7i, i = , которым соответствуют единичные элементы i-й строки матрицы контрдостижимостей графа. Верхняя оценка продолжительности решения задачи Б такая же, как и для задачи А.

Задача В. Для определения существенных вершин между двумя концевыми вершинами х_i, х_j (i ≠j, i, j = ) необходимо подать потенциал единичного уровня на вход 5i первой группы и вход 6j второй группы входов устройства. В процессе решения этой задачи в устройстве одновременно осуществляются процессы, описанные для задач А и Б. По завершении процесса решения на выходах 8i, i = будут потенциалы, соответствующие элементам R (x_i), а на выходах 7i, i = , - Q(x_j). Кроме того, сигналы, соответствующие R(x_i) и Q(x_j), поступают на соответствующие элементы И 4i, i = . В элементах И 4i осуществляется операция поэлементного перемножения строк Q(x_j) и R(x_i), и сигналы уровня логической "1" с выходов элементов И 4i поступают на выходы 9i третьей группы выходов, номера которых соответствуют номерам существенных вершин между заданными концевыми вершинами. Верхняя оценка времени решения задачи В Т = 3n τ, т. е. имеет место практически тот же порядок, что и для ранее рассмотренных задач.

Задача Г. Для определения сильной компоненты графа для вершины x_i(i = ) необходимо потенциал единичного уровня подать на вход 5i и вход 6i(i = ). Работа устройства аналогична его работе при решении задачи В, но потенциалы единичного уровня присутствуют на тех выходах 9i, i = , которым соответствуют вершины, образующие сильную компоненту графа для рассматриваемой вершины графа. Верхняя оценка времени решения задачи Г такая же, что и для задачи В.

Таким образом, предлагаемое устройство с многократно большим быстродействием обеспечивает решение более широкого круга задач анализа связности графа, чем известное устройство, а его функциональная схема не зависит от топологии исследуемого графа и не содержит таких сложных узлов, как шифраторы, дешифраторы, мультиплексоры, регистры, счетчики, генераторы импульсов и др. , имеющихся в известном устройстве. (56) 1. Авторское свидетельство СССР N 1174937, кл. G 06 F 15/20, 1983.

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

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

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

РИСУНКИ

Рисунок 1