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

«/7

со

м

Од

о со

00

1ЧЭ

дящих в состав сильно связного под- ; графа. Информация о составе сильно- связных подграфов, ,полученных в результате разбиения исходного графа, запоминается на регистрах 19 сдвига. 1 ил.

Изобретение относится к вычислительной технике, может быть использовано для исследования сетевых графов и позволяет определять вершины, образующие транзитивное и обратное транзитивное замыкание для всех вершин графа. Целью изобретения является расширение функциональных возможностей устройства за счет обеспечения возможности разбиения графа на сильно связные подграфы. Устройство содержит матричную модель 1 графа, триггеры 2, элементы И 4 и 3, две группы элементов ИЛИ 5 и 6, две группы 7 и 8 триггеров, дешифратор 9, счетчик 10, элементы 11 задержки ; ; элемент И 12, генератор 13 тактовых импульсов, вход 14 пуска, две группы информационных выходов 15 и 16, выход 17 признака окончания работы, группу элементов И 18 и грзтпу регистров 19. Группа элементов И 18 введена для определения вершин, образукщих одновременно транзитивное и обратное транзитивное замыкания для заданной вершины, что равносщтьно определению вершин, вхо(Л

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

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

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

Устройство содержит матричную модель 1 графа, триггеры 2, элементы И 3 и 4, две группы элементов ИЛИ 5 и 6, две группы 7 и 8 триггеров, дешифратор 9, счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых импульсов, вход 14 пуска, две группы информационных выходов 15 и 16, выход 17 признака окончания работы, группу элементов И 18 и группу регистров 19 сдвига.

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

Первоначально в нулевое состояние устанавливаются все триггеры 7,8 и счетчик 10. Информация о топологии моделируемого графа заносится путем установки соответствующих триггеров 2 в единичное состояние согласно матрицы смежности графа.

После подачи управляющего сигнала на выход 14 импульсы с генератора 13 начинают поступать через элемент И 12 на вход счетчика 10,и вход элемента 11 задержки, одновременно происходит Сдвиг в сторону младших разрядов содержимого регистров 19, С выхода счетчика 10 код номера импульса поступает на вход дешифратора 9, в результате чего последовательно возбуждаются его выходы, и единичный сигнал через элементы ИЛИ 5 и 6 переводит в единичное состояние соответствующие триггеры 7,8,

Единичный сигнал с выхода К-го триггера 7 (,,.Р) проходит через

открытые элементы 3 И М-ной строки матричной модели (.,,Р) и устанавливает в единичное состояние соответствующие три1теры 7.

Так определяются все вершины, об-

разующие транзитивное замыкание для М-и вершины. Таким вершинам соответствует единичное состояние триггеров 7. При этом единица на К-ом выходе 15 соответствует номеру вершины, входящей в транзитивное замьшание для М-ой вершины моделируемого графа.

Одновременно единичный сигнал с выхода М-го триггера 8 проходит через открытые элементы И 4 М-го столб-

ца матричной модели 1 и устанавливает в единичное состояние соответствующий триггер 8. Так определяются все вершины, образующие транзитивное замыкание для М-й вершины. Таким

вершинам соответствует единица на

К-м выходе 16 устройства.

Одноименные триггеры 7 и 8, одновременно находящиеся в единичном состоянии. Свидетельствуют о том,

30 что соответствующие им вершины моделируемого графа являются достижимыми из заданной дешифратором 9 вершины и в то же время из этих вершин достигается заданная вершина, а сле35iдовательно, соответствующие вершины принадлежат сильно связному подграфу, из вершин которого является заданная вершина.

Определение вершин, входящих в

40 сильно связный подграф осуществляется путем отыскания с помощью элементов И 18 триггеров одноименньпс 7 и 8, одновременно находящихся в единичном состоянии. При нахождении тад5 кой пары производится запись единицы в соответствующий разряд регистра 19 сдвига.

После завершения определения транзитивного и обратного транзитивного замыканий единичный сигнал с выхода элемента 11 задержки устанавливает все триггеры 7 и 8 в нулевое состояние ,

При постугшении на вход счетчика 10 очередного импульса транзитивное, обратное транзитивное замыкания и сильносвязньй подграф определяются для второй вершины моделируемого графе и так далее до тех пор, пока на счетчик не достигнет числа Р, после чего с приходом очередного Импульса происходит переполнение счетчика 10 и на выходе 17 устройства появляется единичный сигнал признака окончания работы.

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

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

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

возможности разбиения графа на сильно связные подграфы, в Het o введены группа из Р элементов И, где Р - количество вершин в графе и группа из Р регистров сдвига, причем выход

К-го триггера первой группы (,.., Р) подключен к первому входу К-го элемента И группы, выход К-го триггера второй группы подключен к второму входу К-го элемента И группы, выход

которого подключен к информационному входу К-го регистра сдвига группы, выход элемента И подключен к входам признака сдвига всех регистров сдвига группы.