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

13Д

ство вершин в графе; г (G ) - количество ребер, соединяющих К-ю вершину с вершинами подграфа G, (i 1,2); Х - множество вершин i-ro подграфа. Перед началом работы в соответствующие триггеры 2 установкой в 1 заносится информация о топологии моделируемого графа, а в триггеры 7 - информация о вершинах, включаемых в первый подграф. Импульсный сигнал пуска, подаваемый на вход 9 устройства, обнуляет арифметические устрой

1

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

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

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

Устройство содержит матричную модель 1 графа, триггеры 2, элементы И 3 и А, схемы 5 сравнения, элементы НЕ 6, триггеры 7, арифметические устройства 8, вход 9 пуска устройства.

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

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

frjG,) - r(G), Kt Х, L(K)IrjG) - rjG), K X, , где L - число связности К-й вершины, (К 1, ..., М, где М - количество вершин в графе), г(С.)- количество ребер, соединяющих К-ю вершину с вершинами подграфа G (i 1,2);

Х. - множество вершин i-ro под- графа (эта величина называется числом связности К-й вершины) .

849

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

0

5

5

0

5

0

В исходном состоянии в триггеры 2 матричной модели 1 графа заносится информация о топологии графа путем установки соответствующих триггеров 2 в единичное состояние. В единичное состояние устанавливаются триггеры 2 только тех узлов матричной модели 1, которым соответствует наличие в графе дуги. Триггеры 7, соответствующие вершинам, включаемым в первый подграф, устанавливаются в единичное состояние. Пуск устройства осуществляется путем подачи импульсного сигнала на вход 9. Этот сигнал устанавливает в нулевое состояние все арифметические устройства В.

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

В этом случае К,Р-й узел (Р 1

М) производит сравнение сигналов на входах схемы 5. Если сигналы одинаковы, что соответствует случаю принадлежности вершин К и Р к одному подграфу, то сигнал с выхода триггера 2 проходит через элемент И 3 на Р-й вычитающий вход К-го арифметического устройства. Если же сигналы на входах схемы 5 не совпадают, что соответствует случаю принадлежности вершин К и Р к разным подграфам, элемент НЕ 6 обеспечивает прохождение

сигнала с вьгхода триггера 2 через элемент И 4 и на Р-й суммирующий вход К-го арифметического устройства 8. В результате объединения всех входных сигналов на К-м арифметическом устройстве 8 будет сформировано значение числа связности для К-й вершины. Формирование значений чисел связности для всех вершин графа происходит параллельно и практически мгновенно.

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

20

25

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

ор Е.Копча 4803/49

Составитель А.Мишин Техред А.Кравчук

Кор Под

Тираж 670 ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

НЕ, причем . выход К-го триггера (К 1, ..., М) подключен к первым информационным входам схем сравнения всех узлов К-й строки матричной модели графа и к вторым информационным входам схем сравнения всех узлов К-го столбца матричной модели графа, выход признака равенства схемы сравнения

Р-го узла (Р 1М) К-й строки

матричной модели графа подключен к второму входу элемента И того же узла матричной модели графа и к входу элемента НЕ того же узла матричной модели графа, выход элемента НЕ Р-го узла к-й строки матричной модели графа подключен к второму входу второго эле

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

Корректор В.Бутяга Подписное

Изобретение относится к вычислительной технике, может быть использовано для разбиения графа произвольной 1 7 структуры на два максимально независимых подграфа и позволяет определять числа связности вершин двух подграфов. Устройство содержит матричную модель 1 графа, триггеры 2, элементы И 3 и 4, схемы 5 сравнения,.элементы НЕ 6, триггеры 7, арифметические устройства 8, вход 9 пуска. Устройство позволяет определить значения величин Гг,(С - r(G), К€Х,, L(K) -) lr,(G - r(G,), кех, где L (К) - число связности К-й вершины, К 1, ..., м, где М - количе 4 00 00 42 со