Устройство для определения двух независимых кратчайших путей на графе Советский патент 1987 года по МПК G06G7/122 

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

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

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

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

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

В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помош,ью переменных резисторов 11 в моделях 3 и 4 ребер устанавливают токи в управляющих цепях тиристоров 10, соответствующие заданным напряжениям их переключения, пропорциональным весам ребер.

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

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

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

5

Устройство для определения двух незавиr симых кратчайших путей на графе, содержащее первый источник регулируемого напряжения, основные модели ребер, соединенные согласно топологии графа, и дополнительные модели ребер, причем каждая основная модель ребра содержит соединенные последо0 вательно пороговый элемент, элемент индикации и обмотку реле, каждая дополнительная модель ребра содержит соединенные последовательно пороговый элемент и элемент индикации, выход первого источника регулируемого напряжения подключен к входу порогового элемента основной модели ребра начала пути, вывод обмотки реле основной модели ребра конца пути подключен к опорному входу источника регулируемого напряжения, отличающееся тем, что, с целью

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

Изобретение относится к области аналоговой вычислительной техники, может быть использовано для решения задач поиска оптимальных путей на графе и позволяет находить кратчайшие пути, независимые по вершинам и ребрам. В устройство входят два источника 1 и 2 регулируемого напряжения, основные модели 3 ребер графа, дополнительные модели 4 ребер графа и модели 5 вершин графа. В каждой модели 3 имеется пороговый элемент 6, элемент 7 индикации и обмотка 8 реле. Модель 5 содержит включенные последовательно контакты 9 реле моделей 3 тех ребер графа, которые выходят из данной вершины. Пороговый элемент может быть выполнен, например, на базе тиристора 10, переменного резистора 11 и источника 12 постоянного напряжения. В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помош,ью переменных резисторов 1 I в моделях 3 и 4 устанавливают веса ребер графа. При плавном увеличении выходного напряжения источника 1 происходит переключение тиристоров 10 тех моделей 3, через которые проходит первый кратчайший путь, отображаемый элементами 7 индикации. Ток протекающий по обмоткам 8 моделей 3 кратчайшего пути, размыкает соответствующие контакты 9. Тем самым из топологии графа исключаются все модели 5 первого кратчайшего пути. Далее плавно увеличивают выходное напряжение источника 2, и аналогично находят второй кратчайший путь на графе. 1 ил. о (Л со со О5 О N