Устройство для решения задач на графах Советский патент 1990 года по МПК G06F15/173 

00

о

00

со

316

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

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

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

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

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

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

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

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

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

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

Устройство для решения задач на графах, содержащее блок задания матрицы смежности, первый блок определения достижимых вершин и блок пе- речисления взаимодополнительных подмножеств, причем тактовый вход устройства подключен к тактовому входу блока перечисления взаимодополнительных подмножеств, выход признака принадлежности К-го элемента первому подмножеству которого (К 1,...,В, где В - количество вершин в графе) подключен к. входу опроса К-й вершины первого блока определения достижимых вершин, выход значения (К,М)-го элемента блока задания матрицы смежности (М 1,..., в) подключен к входу признака наличия (К,М)-й дуги первого блока определени достижимых вершин, отличающееся тем, что, с целью расширения функциональных возможностей устройств за счет определения сильной базы графа, в него введены второй блок определения достижимых вершин и блок логического умножения, причем выход значения UC,MJ-ro элемента блока задания матрицы смежности подключен к входу .признака наличия (К,М)-й дуги второго блока определения достижимых вершин, выход признака принадлежности К-го элемента первому подмножеству блока перечисления .взаимодополнительных подмножеств является выходом признака принадлежности К-й вершины множеству вершин сильной базы графа устройства и подключен .к К-му разряду первого информационного входа блока s логического умножения, выход признака принадлежности К-го элемента втоРС

в:

5 16086836

|му подмножеству блока перечисленияпризнака достижимости всех вершин

аимодополнительных подмножеств под-графа блока определения достижимых

к:|ючен к входу опроса К-й вершины вто-вершин подключен к входу опроса блока

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

:ршин, выход признака достижимостиравенства нулю результата которого

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

М

Р

6J

:ока логического умножения, выход ройства.

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