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

ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ 21) 4768432/24(71) Чувашский государственный университет им. И.Н, Ульянова(72) Б.М. Калмыков и И.А. Обломов (56) Авторское свидетельство СССР М 1658171, кл. 6 06 Р 15/20, 1988.Авторское свидетельство СССР В 1675907, кл. 0 06 Р 15/419, 1988, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования кратчайших и длиннейших (экстремальных) путей в графе, Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремальных путей в графе. Устройство содержит блок 1 определения Ы 2 1767506 А дерева экстремальных путей, блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и выходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства. Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной в заданную конечную вершину графа, По входам 4 устройства задают матрицу смежности исходного графа, по входам 5 и 6 - его начальную и конечную вершины. При этой на выходе 8 устройстза будет сформировано искомое множество дуг, п ринадлежащих экстремальному пути, 1 ил,1767506 Составитель А.МишинРедактор Л,Волкова Техред М.Моргентал Корректор М,Максимишинец Заказ 3549 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 Изобретение относится к вычислительной технике и может быть использовано для исследования кратчайших и длиннейших (экстремальных) путей в графе.Целью изобретения является расшире ние функциональных возможностей устройства за счет определения экстремальных путей в графе.На чертеже представлена функциональная схема устройства 10Устройство содержит блок 1 определения дерева экстремальных путей, блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, 15 входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и вы ходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства.Устройство работает следующим образом, 25Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной д заданную конечную вершину графа.По входам 4 устройства задают матрицу 30 смежности исходного графа, по входам 5, 6 - его начальную и конечную вершины. При этом блок 1 формирует сигналы уровня логической "1" на тех своих выходах, соответствующие которым дуги принадлежат 35 дереву экстремальных путей, блок 2 формирует сигналы уровня логической "1" на тех своих выходах, соответствующие которым вершины принадлежат множеству достижимых (поскольку в качестве топологии графа 40 в этом случае используется дерево экстремальных путей, корневой вершиной которого является начальная вершина пути, то будет выбран единственный возможный экстремальный путь из конечной вершины 45 пути в корневую вершину дерева), блок 3 формирует сигналы уровня логического "1" на тех своих выходах, соответствующие которым дуги принадлежат множеству соединяющих заданное множество опрошенных вершин. При этом на выходе 8 устройства будет сформировано искомое множество дуг, принадлежащих экстремальному пути.Формула изобретения Устройство для решения задач на графах, содержащее блок определения достижимых вершин, отл ичаю щеес я тем, что, с целью расширения функциональных возможностей устройства путем определения экстремальных путей в графах, в него введены блок определения дерева экстремальных путей и блок определения соединяющих дуг, причем вход признака наличия(К, М)-й дуги графа устройства (К = 1, ., В; М = 1, , В, где В - количество вершин в графе) подключен к одноименному входу блока определения дерева экстремальных путей, вход опроса К-й вершины которого является К-м входом"задания начальной вершины пути устройства, а выход признака принадлежности (К, М)-й дуги дереву экстремальных путей подключен к входам признаков наличия (М, К)-х дуг блока определения соединяющих дуг и блока определения достижимых вершин, М-й вход задания конечной вершины пути устройства подключен к входу опроса М-й вершины блока определения достижимых вершин, выход признака принадлежности К-й вершины множеству достижимых которого является выходом признака принадлежности К-й вершины множеству вершин экстремального пути устройства и подключен к входу признака принадлежности К-й вершины множеству опрошенных блока определения соединяющих дуг, выход признака принадлежности (К, М)-й дуги множеству соединяющих которого является выходом признака принадлежности (К, М)-й дуги множеству дуг экстремального пути устройства,