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

)5 С 06 Р 15/2 АРСТВЕННЫЙ КОМИТЕТБРЕТЕНИЯМ И ОТНРЫТИНТ СССР ГОС ПО И(54) НА ГР (57) тельн зован шин г ся ра носте ния с СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ уФ РЕСПУБЛИК А ТОРСКОМУ СВИДЕТЕЛЬСТВ(21) 4 (22) 2 (46) 2 (71) И долг в (72) Р Н.М. ур (53) 6 (56) В 637Ав Ф 1451 369102/24-245,12.873.11.90. Бюл. Ф 43нститут проблем надежности иечности машин АН БССР.П.Вареник, А.А.Черняк,инович и В.В.Лящук8 1.333(088.8)вторское свидетельство СССР22, кл. С 06 Г 15/20, 1976.орское свидетельство СССР715, кл, С 06 Р 15/20, 1987. СТРОИСТВО ДЛЯ РЕЖДЕНИЯ ЗАДАФАХ зобретение относится к вычислий технике и может быть испольдля исследования связности вер афа. Целью изобретения являетирение функциональных возможустройства за счет определеьной базы графа, Устройство со держит блок 1 задания матрицы смежности, первый блок 2 определения достижимых вершин, блок 3 перечисления взаимодополнительных подмножеств, второй блок 4 определения достижимых вершин, блок 5 логического умножения, тактовый вход 6 устройства, выходы 7 признаков принадлежности вершин множеству вершин сильной базы графа уст ройства и выход 8 признака выдачи мн жества вершин сильной базы графа устройства. Перед началом работы в блок 1 заносят информацию о топологии графа и устанавливают в исходное состояние блок 3. На тактовый вход 6 устройства подают импульсы уровня логической единицы, При этом блок 3 фор- ф мирует на выходах 7 устройства множество вершин сильной базы графа, сопровождая его появление импульсом С уровня логической единицы на выходе 8 устройства, 1 ил.Изобретение относится к вычислительной технике и может быть использовано для исследования связностивершин графа.Цель изобретения - расширение5функциональных возможностей устройства за счет определения сильной базы графа.На чертеже представлена функциональная схема устройства.Устройство содержит блок 1 задания матрицы смежности, первый блок2 определения достижимых вершин, блок3 перечисления взаимодополнительныхподмножеств, второй блок 4 определения достижимых вершин, блок 5 логического умножения, тактовый вход 6 устройства, выходы 7 признаков принадлежности вершин множеству вершинсильной базы графа устройства и выход 8 признака выдачи множества вершин сильной базы графа устройства,Устройство работает следующим образом. 25Пусть требуется .определить всесильные базы графа. При этом под сильной базой графа понимается такоеподмножество множества его вершин,из которых. имеется достижимость подмножества всех остальных вершин графа, но которые (т.е., вершины сильной базы) не достижимы из любой вершины, не принадлежащей подмножествусильной базы,35Перед началом работы в блок 1задания матрицы смежности заносятинформацию о топологии графа и устанавливают в исходное состояниеблок 3. На тактовый вход 6 устройства подают импульсы уровня логическойединицы, При этом по каждому импульсу блок 3 формирует на своих выходахдва взаимодополнительных подмножест"ва множества вершин графа, При этом 45блок 4 выдает на свои выходы составвершин, достижимых из опрошенных(т,е., состав вершин, достижимыхиз подмножества взаимодополнительного к предлагаемой базе графа), аблок 2, если опрошенные вершины образуют базу графа (т.е., если из нихдостижимы все остальные вершины графа), формирует на своем выходе признака достижимости всех вершин по 55тенциал уровня логической единицы.При этом блок 5 выполняет операциюлогического умножения (конъюнкции) ипри равенстве нулю результата логического умножения (т,е если ни одна из вершин базы графа не достижима ни из одной вершины, не принадлежа - щей базе) формирует на своем выходе потенциал уровня логической единицы, который служит признаком того,что текущая база графа является сильной. Подсчитав (например, с помощью сумматора) количество вершин, входящих в состав базы (сильной базы), можно определить ее мощность, Подавая на тактовый вход 6 количество импульсов, достаточное для полного перебора всех подмножеств множества вершин графа, можно йеречислить все сильные базы графа и определить их моцность.Формула из о бр етенияУстройство для решения задач на графах, содержащее блок задания матрицы смежности, первый блок определения достижимых вершин и блок перечисления взаимодополнительных подмножеств, причем тактовый вход устройства подключен к тактовому входу блока перечисления взаимодополнительных подмножеств, выход признака принадлежности К-го элемента первому подмножеству которого (К = 1В, где В - количество вершин в графе) подключен к входу опроса К-й вершины первого блока определения достижимых вершин, выход значения (К,М)-го элемента блока задания матрицы смежности (М = 1 В) подключен к. входу признака наличия (К,М)-й дуги первого блока определения достижимых вершин, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устройства за счет определения сильной базы графа, в него введены второй блок определения достижимых вершин и блок логического умножения, причем выход значения К,М)-го элемента блока задания матрицы смежности подключен к входу признака наличия (К,М)-й дуги второго блока определения достижимых вершин, выход признака принадлежности К-го элемента первому подмножеству блока перечисления взаимодополнительных подмножеств является выходом признака принадлежности К-й вершины множеству вершин сильной базы графа устройства и подключен к К-му разряду первого информационного входа блока . логического умножения, выход признака принадлежности К-го элемента втор в Составитель А.Мишинор Н. Тупица Техред М.Дидык Корректор Т,Малец 3618 Тираж 569 ПодписноеИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5 водственно-издательский комбинат "Патент", г,ужгород, ул, Гагарина, 101. к Р в М Р б 5 160868 му подмножеству блока перечисления аимодополнительных подмножеств подючен к входу опроса К-й вершины втого блока определения достижимых ршин, выход признака достижимости5 й вершины которого подключен к М-му зряду второго инФормационного входа ока логического умножения, выход признака достнжимости всех вершинграйа блока определения достижимыхвершин подключен к входу опроса блокалогического умножения, выход признакаравенства нулю результата которогоявляется выходом признака выдачи множества вершин сильной базы граАа устройства.