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

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

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

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

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

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

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

Матрица смежности предназначена для задания топологии исследуемого графа и содержит п(п-1) моделей дуг 7ij,.|,j 1.n, . Все модели дуг идентичны и каждая содержит триггер 8, первый 9 и второй 10 элементы И, первый 11 и второй 12 диоды, а также установочные входы модели дуги 13, 14.

Работа устройства основана на определении для вершины xi,i 1.n пересечения R(xi) П Q(XJ), где R(xi) - l-тая строка матрицы достижимостей графа, a Q(xi) - i-тая строка матрицы контрадостижимостей исследуемого графа.

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

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

Решение по определению сильной компоненты графа, содержащей вершину xi, начинается подачей сигнала уровня логической единицы на вход устройства 5i (). Сигнал с полюса 5i поступает на один из входов элемента ИЛИ 2| и элемента ИЛИ Зь С выхода элемента ИЛИ 2i сигнал поступает на объединенные -входы моделей дуг 1-той строки матрицы смежности. С входов моделей дуг i-той строки сигналы поступают на вход первого элемента И 9 этих моделей дуг. Кроме того, сигнал с выхода элемента ИЛИ 2| поступает на вход элемента И 4|, это моделирует единичное значение элемента Гц матрицы достижимости графа. Если в I- той строке матрицы смежности исследуемого графа есть столбцы с единичными элементами, т.е. если триггер 8 модели дуги в соответствующем столбце находится в единичном состоянии, то на обоих входах элемента И 9 будут сигналы высокого уровня и сигнал с выхода первого элемента И 9 этих моделей дуг поступит через диод 11 на вход соответствующего данному столбцу

матрицы смежности элемента ИЛИ первой группы 2j, J 1,п, j , Появляется сигнал на выходе этого элемента ИЛИ и дальнейшая работа устройства аналогична рассмотренной. По завершению лавинообразного переходного процесса, длительность которого t 2п т (где т- время задержки сигнаЛа на логических элементах И, ИЛИ, имеющее порядок нескольких пикосекунд), сигналы на соответствующих входах элементов И 4), I 1, n будут соответствовать значениям элементов i-той строки матрицы достижимости исследуемого графа. То есть, если сигнал на входе элемента И имеет нулевой уровень, то и соответствующий элемент равен нулю, а если сигнал имеет единичный уровень, то и соответствующий элемент матрицы достижимостей равен единице.

Одновременно с выше описанным процессом и аналогично ему осуществляется лавинообразный процесс определения элементов I-той строки матрицы контрадостижимостей. По завершению его, сигналы на других входах элементов И 4i, i 1 ,п будут соответствовать значениям элементам I-той строки матрицы контрадостижимостей. На выходах элементов И 4i, i 1,n появятся сигналы логического произведения сигналов, поступивших на входы этих элементов И. Сигналы с выходов элементов И 4ь i 1,п поступают на ВЫ.ХРДЫ устройства 6i, i 1,n. Выходы 6j, i 1, n с единичным уровнем сигнала однозначно определяют сильную компоненту исследуемого грифа относительно вершины xi. Аналогично могут быть определены сильные компоненты относительно остальных вершин графа.

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

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

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

Устройство для определения компонент графов, содержащее матрицу смежности и группу из n элементов И (n-число вершин исследуемого графа), отличающееся

0

5

0

5

0

5

0

0

5

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

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

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

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

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