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

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

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

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

такта 6-1 и подключению к источнику 4 управляющих входов ключей 14 всех моделей 8 первой группы. Ключи 14 моделей 8 первой группы закрываются, обеспечивая протекание тока только по ребрам первого кратчайшего пути независимо от того, что при дальнейшей работе устройства будут срабатывать реле моделей 2, принадлежащих другим кратчайшим путям, и замыкать контакты 16 в соответствующих моВ состав устройства входит источник 1

регулируемого напряжения, основные модели 10 делях 8 всех групп. 2 ребер графа, источник 3 тока, источникДалее продолжают увеличивать выходное

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

В состав модели 2 входит обмотка 9 моделей 8 не замыкается цепь протекания реле, блок 10 задания веса ребра графа, вы- тока источника 3 за счет замыкания контактов 15. Во второй группе моделей 8 ток протекает уже только по ветвям, образуюполненныи, например, в виде переменного регистора и контакты 11-1,..., 1-К реле соответствующих моделей 8 каждой группы.

В состав модели 8 входит обмотка 12 20 - первого шага работы устройства за счет реле, элемент 13 индикации, ключ 14, кон- размыкания контактов 11 - 1 ребра первого такт 15 реле соответствующей модели 2, контакт 16 реле той же модели 8.

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

В исходном состоянии напряжение на

щим второй кратчайший путь, поскольку поскратчайшего пути из топологии графа исключены.

После образования цепи протекание тока по модели 8 ребер второй группы работа уствыходе источника 1 равно нулю. С помощью 25 ройства происходит аналогично. В резуль- блоков 10 устанавливают величины сопротивлений, пропорциональные весам ребер графа..Все ключи 14 открыты.

При плавном увеличении выходного напряжения источника 1 токи в моделях 2 увеличиваются обратно пропорционально их весу. В отдельных моделях 2 ток увеличивается до величины, при которой в обмотке 14 протекает ток достаточный для замыкания контактов 15 в моделях 8 первой группы. Напряжение на выходе источника

тате после индикации последнего К-го кратчайшего пути ток, протекающий по обмотке 5-К, разомкнет контакт 7-К, исключив возможность дальнейшего повышения выходного напряжения источника 1.

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

Устройство для определения К независимых кратчайших путей на графе, содержаувеличивается до тех пор, пока в первой груп- 35 шее источник регулируемого напряжения, пе моделей 8 за счет замыкания опреде- источник тока, К реле индикации, Р основ- ленного числа контактов 15 образуется нь1х моделей ребер, соединенных согласно цепь протекания тока источника 3, что обус- топологии графа, где Р - количество ребер лавливает, во-первых, зажигание элементов на графе, и К групп дополнительных моде- индикации 13, отображаюших ребра первого 40 ребер, соединенных согласно топологии кратчайшего пути, во-вторых, протекание графа, причем М-я основная модель ребра тока в обмотках 12 моделей 8 этих ребер и, (тде ,..., Р) содержит последовательно в-третьих, протекание тока в обмотке 5-1. соединенные обмотку реле, блок задания Протекание тока в обмотке 12 приводит к за- массы ребра и нормально замкнутые кон- мыканию контактов 16 и блокировке моде- такты реле М-х дополнительных моделей лей 8 до конца работы устройства. Это обеспе-45 ребер каждой группы, каждая дополнитель- чивает индикацию первого кратчайшего пути ная модель ребра содержит последовательно соединенные обмотку реле, элемент индикации и нормально замкнутый контакт того же реле, выход источника регулируемого напряжения через первый нормаль- 50 но замкнутый контакт К-го реле индикации

до конца работы устройства. Кроме того, протекание тока через обмотку 12 в каждой модели 8 приводит к размыканию контакта 11 - 1 в соответствующей модели 2. Тем самым после первого шага работы устройства благодаря размыканию контактов 11 - 1 из топологии графа будут исключены все ребра первого кратчайшего пути. Протекание тока через обмотку 5- 1, с одной стороны, обуславливает замыкание контакта 7-1 и подготовку к работе второй группы модели 8 за счет подключения источника 3 к входу модели 8 начала пути второй группы, а с другой стороны, приводит к замыканию кон55

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

такта 6-1 и подключению к источнику 4 управляющих входов ключей 14 всех моделей 8 первой группы. Ключи 14 моделей 8 первой группы закрываются, обеспечивая протекание тока только по ребрам первого кратчайшего пути независимо от того, что при дальнейшей работе устройства будут срабатывать реле моделей 2, принадлежащих другим кратчайшим путям, и замыкать контакты 16 в соответствующих моделях 8 всех групп. Далее продолжают увеличивать выходное

- первого шага работы устройства за счет размыкания контактов 11 - 1 ребра первого

щим второй кратчайший путь, поскольку пос- первого шага работы устройства за счет размыкания контактов 11 - 1 ребра первого

кратчайшего пути из топологии графа исключены.

После образования цепи протекание тока по модели 8 ребер второй группы работа устройства происходит аналогично. В резуль-

ройства происходит аналогично. В резуль-

тате после индикации последнего К-го кратчайшего пути ток, протекающий по обмотке 5-К, разомкнет контакт 7-К, исключив возможность дальнейшего повышения выходного напряжения источника 1.

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

5

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

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

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

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