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

г

о

5

гж

2

т

J

S

И

VJ О VI

сл

|О

о

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

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

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

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

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

Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной в заданную конечную вершину графа.

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

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

М)-й дуги графа устройства (К 1В; М

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

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