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

 

Изобретение относится к вычислительной технике, может быть использовано для разбиения графа произвольной 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 со

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1348849 А ) (51) 4 С 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

В q °

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4038844/24-24 (22) 20.03,86 (46) 30. 10.87. Бюл, tt 40 (72) Г.Н.Лаврик, А.Ю.Печунов, И,А.Бычковский и A.Т.Захаров (53) 68 1.333(088.8) (56) Авторское свидетельство СССР

Ф 716043, кл. С 06 F 15/20, 1980.

Авторское свидетельство СССР

У 1075268, кл. С 06 F 15 /20, 1982. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике, может быть использовано для разбиения графа произвольной структуры на два максимально независимых подграфа и позволяет определять числа связности вершин двух подграфов. Устройство содержит матричную модель 1 графа, триггеры 2, элементы

И 3 и 4, схемы 5 сравнения,.элементы HE 6, триггеры 7, арифметические устройства 8, вход 9 пуска. Устройство позволяет определить значения величин

r „,(G — г„(С ), К ЕХ

z.(ê) =

r „(G — г„(С, ), К E. Х где 1. (К) — число связности К-й вершины, К = 1, ..., M, где М вЂ” количеОПИСАНИЕ ИЗОБРЕТЕНИЯ

13 ство вершин в графе; r (G ) — количество ребер, соединяющих К-ю вершину с вершинами подграфа С, (i = 1,2);

Х, — множество вершин i-го подграфа.

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

P-го вычитаемого К-ro арифметического устройства, а в противном случае на вход его Р-го слагаемого. 1 ил.

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

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

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

Устройство содержит матричную модель 1 графа, триггеры 2, элементы И

3 и 4, схемы 5 сравнения, элементы НЕ

6, триггеры 7, арифметические устройства 8, вход 9 пуска устройства.

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

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

r„(G,) — r (G ), K e Х „ т.(к) =

r„(G i — rí С ), К E. Х,, где L — число связности К-й вершины, (К = 1, ..., M, где М вЂ” коли30 чество вершин в графе), r (G ) — количество ребер, соединяюК 1 щих К-ю вершину с вершинами подграфа G (i = 1, 2);

Х вЂ” множество вершин i † под- 35

1 графа (эта величина называется числом связности К-й вершины) .

В исходном состоянии в триггеры 2 матричной модели 1 графа заносится информация о топологии графа путем установки соответствующих триггеров

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

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

В этом случае К,P é узел (P = 1, M) производит сравнение сигналов на входах схемы 5. Если сигналы одинаковы, что соответствует случаю принадлежности вершин К и P к одному подграфу, то сигнал с выхода триггера 2 проходит через элемент И 3 на

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

Составитель А.Мишин

Техред А.Кравчук

Корректор В.Бутяга

Редактор Е.Копча

Заказ 4803/49 Тираж 670

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

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

3 134 сигнала с выхода триггера 2 через элемент И 4 и на P-й суммирующий вход

К-го арифметического устройства 8. В результате объединения всех входных сигналов на К-м арифметическом устройстве 8 будет сформировано значение числа связности для К-й вершины.

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

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

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

8849

НЕ, причем выход К-го триггера (К =

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

P-го узла (P = 1, ..., M) К-й строки матричной модели графа подключен к второму входу элемента И того же узла матричной модели графа и к входу элемента НЕ того же узла матричной модели графа, выход элемента HE P-го узла

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

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