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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН (gg 4 С 06 Р 15/20

3СХ1 ""

«%

1.

I) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHGMY СВИДЕТЕЛЬСТВУ

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (61) 1075268 (21) 4105336/24-24 (22) 03.06.86 (46) 23.02.88. Бюл. У 7 (72) Г,Н.Лаврик, Ю.И.Скорик, А.Ю.Печунов, С.А.Прилуцкий и А.А.Прилуцкий (53) 681.333 (088.8) (56) Авторское свидетельство СССР

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

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

20

40 дящих в состав сильно связного под, графа. Информация о составе сильносвяэньм подграфов, полученных в реИзобретение относится к вычислительной технике, может быть использовано для исследования сетевых графов и позволяет определять вершины, образующие транзитивное и обратное транзитивное замыкание для всех вершин графа и является усовершенствованием устройства по авт. св. N - 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 перезультате разбиения исходного графа, запоминается на регистрах 19 сдвига.

1 ил. водит в единичное состояние соответствующие триггеры 7,8.

Единичный сигнал с выхода К-ro триггера 7 (К=1...Р) проходит через оTKpblTbIB элементы 3 И М-ной строки матричной модели (M=1...P) и устанавливает в единичное состояние соответствующие триггеры 7.

Так определяются все вершины, образующие транэитивное замыкание для

M-й вершины. Таким вершинам соответствует единичное состояние триггеров

7. При этом единица на К-ом выходе

15 соответствует номеру вершины,входящей в транзитивное замыкание для

M-ой вершины моделируемого графа.

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

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

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

Определение вершин, входящих в сильно связный подграф осуществляется путем отыскания с помощью элементов И 18 триггеров одноименных 7 и

8, одновременно находящихся в единичном состоянии. При нахождении такой пары производится запись единицы в соответствующий разряд регистра 19 сдвига.

1376098

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

Техред А. Кравчук Корректор С Ч Рни

Редактор С.Патрушева

Заказ 789/48 Тираж 704 Подписное

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

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

««

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

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

При поступлении на вход счетчика

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

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

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

10 возможности разбиения графа на сильно связные подграфы, в неЬо введены группа из P элементов И, где Р— количество вершин в графе и группа из

P регистров сдвига, причем выход

15 К-го триггера первой группы (К=1,...

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

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