Устройство для решения задач на графах
Изобретение относится к вычислительной технике и может быть использовано для исследования кратчайших и длиннейших (экстремальных) путей в графе. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремальных путей в графе. Устройство содержит блок 1 определения дерева экстремальных путей, блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и выходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства. Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной в заданную конечную вершину графа. По входам 4 устройства задают матрицу смежности исходного графа, по входам 5 и 6 - его начальную и конечную вершины. При этом на выходе 8 устройства будет сформировано искомое множество дуг, принадлежащих экстремальному пути 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)л G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4768432/24 (22) 20.11.89 (46) 07.10.92. Бюл. ¹ 37 (71) Чувашский государственный университет им. И.Н. Ул ья нова (72) Б.М. Калмыков и И.А. Обломов (56) Авторское свидетельство СССР
N- 1658171, кл. 6 06 F 15/20, 1988.
Авторское свидетельство СССР
¹ 1675907, кл. G 06 F 15/419, 1988, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования кратчайших и длиннейших (экстремальных) путей в графе. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремальных путей в графе.
Устройство содержит блок 1 определения
„„Я „„1767506 А1 дерева экстремальных путей, блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и выходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства. Пусть необходимо определить состав дуг и вершин экстремального пути из заданной на.чальной в заданную конечную вершину графа. По входам 4 устройства задают матрицу смежности исходного графа, по входам
5 и 6 — его начальную и конечную вершины.
При этом на выходе 8 устройстза будет ) сформировано искомое множество дуг, п ринадлежащих экстремальному пути, 1 ил, 1767506
Составитель А.Мишин
Редактор Л,Волкова Техред М.Моргентал Корректор M.Ìàêñèìèøèíåö
Заказ 3549 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб„4/5
Производственно-издательский комбинат "Патент", г. Ужгород, yn,Гагарина, 101
Изобретение относится к вычислительной технике и может быть использовано для исследования кратчайших и длиннейших (экстремальных) путей в графе.
Целью изобретения является расшире- 5 ние функциональных возможностей устройства за счет определения экстремальных путей в г рафе.
На чертеже представлена функциональная схема устройства.. 10
Устройство содержит блок 1 определения дерева экстремальных путей, блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, 15 входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и вы- 20 ходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства.
Устройство работает следующим образом. 25
Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной в заданную конечную вершину графа.
По входам 4 устройства задают матрицу 30 смежности исходного графа, по входам 5, 6 — его начальную и конечную вершины. При этом блок t формирует сигналы уровня логической "1" на тех своих выходах, соответствующие которым дуги принадлежат 35 дереву экстремальных путей, блок 2 формирует сигналы уровня логической "1" на тех своих выходах, соответствующие которым вершины принадлежат множеству достижимых (поскольку в качестве топологии графа 40 в этом случае используется дерево экстремальных путей, корневой вершиной которого является начальная вершина пути, то будет выбран единственный возможный экстремальный путь из конечной вершины 45 пути в корневую вершину дерева), блок 3 формирует сигналы уровня логического "1" на тех своих выходах, соответствующие которым дуги принадлежат множеству соединяющих заданное множество опрошенных вершин. При этом на выходе 8 устройства будет сформировано искомое множество дуг, принадлежащих экстремальному пути.
Формула изобретения
Устройство для решения задач на графах, содержащее блок определения достижимых вершин, отл и чаю щеес я тем, что, с целью расширения функциональных возможностей устройства путем определения экстремальных путей в графах, в него введены блок определения дерева экстремальных путей и блок определения соединяющих дуг, причем вход признака наличия (К, М)-й дуги графа устройства (К = 1, .„, В; М =
1, ..., В, где  — количество вершин в графе) подключен к одноименному входу блока определения дерева экстремальных путей, вход опроса К-й вершины которого является
К-м входом"задания начальной вершины пути устройства, а выход признака принадлежности (К, М)-й дуги дереву экстремальных путей подключен к входам признаков наличия (М, К)-х дуг блока определения соединяющих дуг и блока определения достижимых вершин, М-й вход задания конечной вершины пути устройства подключен к входу опроса М-й вершины блока определения достижимых вершин, выход признака принадлежности К-й вершины множеству достижимых которого является выходом признака принадлежности
К-й вершины множеству вершин экстремального пути устройства и подключен к входу признака принадлежности К-й вершины множеству опрошенных блока определения соединяющих дуг, выход признака принадлежности (К, М)-й дуги множеству соединяющих которого является выходом признака принадлежности (К, М)-й дуги множеству дуг экстремального пути устройства.
