Устройство для решения задач на графах

 

Изобретение относится к вычислительной технике и может быть использовано для исследования связности вершин графа. Целью изобретения является расширение функциональных возможностей устройства за счет определения сильной базы графа. Устройство содержит блок 1 задания матрицы смежности, первый блок 2 определения достижимых вершин, блок 3 перечисления взаимодополнительных подмножеств, второй блок 4 определения достижимых вершин, блок 5 логического умножения, тактовый вход 6 устройства, выходы 7 признаков принадлежности вершин множеству вершин сильной базы графа устройства и выход 8 признака выдачи множества вершин сильной базы графа устройства. Перед началом работы в блок 1 заносят информацию о топологии графа и устанавливают в исходное состояние блок 3. На тактовый вход 6 устройства подают импульсы уровня логической единицы. При этом блок 3 формирует на выходах 7 устройства множество вершин сильной базы графа, сопровождая его появление импульсом уровня логической единицы на выходе 8 устройства. 1 ил.

(51)5 С 06 F 15/20

ТВЕННЫЙ КОМИТЕТ

НИЯМ И ОТКРЫТИЯМ

СССР

ГОСУ APC

ПО И БРЕТЕ

ПРИ НТ

Г Р (54)

НА ГР (57) тельн зован шин г ся ра носте ния с

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

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

:!Ô -- РЕСПУБЛИК

К А ТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

369102/24-24

5. 12.87

3. 11.90. Бюл. Ф 43 нститут проблем надежности и еч нос ти маши í АН Б CCP .П. Вареник, А.А.Черняк, инович и В.В.Лящук

81.333 (088.8) вторское свидетельство СССР

22, кл. С 06 F 15/20, 1976. орское свидетельство СССР

715, кл. G 06 F 15/20, 1987. (21) 4 (22) 2 (46) 2 (71) И долг в (72) P

Н.М. ур (53) 6 (56)

В 637

Ав

Ф 1451

СТРОИСТВО ДЛЯ РЕЖДЕНИЯ ЗАДАЧ

ФАХ зобретение относится к вычислий технике и может быть испольдля исследования связности верафа. Целью изобретения являетирение функциональных нозможустройства за счет определеьной базы rpaha. Устройство со2 держит блок 1 задания матрицы смежности, первый блок 2 определения достижимых вершин, блок 3 перечисления взаимодополнительных подмножеств, второй блок 4 определения достижимых вершин, блок 5 логического умножения, тактовый вход 6 устройства, выходы 7 признаков принадлежности вершин множеству вершин сильной базы графа уст ройства и выход 8 признака выдачи мн жества вершин сильной базы графа устройства. Перед началом работы в блок 1 заносят информацию о топологии графа и устанавливают в исходное состояние блок 3. На тактовый вход 6 устройства подают импульсы уровня логической единицы. При этом блок 3 формирует на выходах 7 устройства множество вершин сильной базы графа, сопровождая его появление импульсом уровня логической единицы на выходе

8 устройства. 1 ил.

1608683

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

Цель изобретения — расширение

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

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

Устройство содержит блок 1 задания матрицы смежности, первый блок

2 определения достижимых вершин, блок

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

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

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

Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа и устанавливают в исходное состояние блок 3. На тактовый вход 6 устройст- 4 ва подают импульсы уровня логической единицы. При этом по каждому импульсу блок 3 формирует на своих выходах два взаимодополнительных подмножест" ва множества вершин: графа. При этом 45 блок 4 выдает на свои выходы состав вершин, достижимых из опрошенных (т.е., состав вершин, достижимых из подмножества взаимодополнительного к предлагаемой базе графа), а блок 2, если опрошенные вершины образуют базу графа (т. е., если из них достижимы все остальные вершины графа), формирует на своем выходе признака достижимости всех вершин по55 тенциал уровня логической единицы.

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

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

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

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

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

Составитель А.Мишин ор Н. Тупица Техред М.Дидык Корректор Т.Малец

3618 Тираж 569 Подписное

И Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5 оизводственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101. к

P в

P б

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

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