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

 

Изобретение относится к вычислительной технике и может быть использовано для определения независимых по ребрам кратчайших путей на графе. В состав устройства входят источник 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 СО

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1

„„SU„„1336043 (sD 4 G 06 G 7/122 юс 4 (,4

Ь,!

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4060112/24-24 (22) 25.04.86 (46) 07.09.87. Бюл. № 33 (72) В. А. Клишин, A. A. Лелис и Г. С. Полищук (53) 681.333 (088.8) (56) Авторское свидетельство СССР

¹ 913398, кл. G 06 G 7/122, 1977.

Авторское свидетельство СССР № 1!23035, кл. G 06 G 7/122, 1983. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

К НЕЗАВИСИМЫХ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано для определения независимых по ребрам кратчайших путей на графе. В состав устройства входят источник 1 регулируемого напряжения, основные модели 2 ребер графа, источник 3 тока, источник 4 напряжения, обмотки 5-1,...,5-К реле индикации, где К количество искомых кратчайших путей на графе, контакты 6-1,...,6-К, и 7-1,...,7-К реле индикации и К групп дополнительных моделей 8 ребер графа. В состав модели 2 входят обмотка 9 реле, блок 10 задания веса ребра, выполненный, например, в виде переменного резистора, и контакты

11-1,...,11-К реле соответствующих моделей 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 ил.

1336043

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

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

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

В состав устройства входит источник 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 ток увеличивается до величины, при которой в обмотке 14 протекает ток достаточный для замыкания контактов 15 в моделях 8 первой группы. Напряжение на выходе источника увеличивается до тех пор, пока в первой группе моделей 8 за счет замыкания определенного числа контактов 15 образуется цепь протекания тока источника 3, что обуславливает, во-первых, зажигание элементов индикации 13, отображающих ребра первого кратчайшего пути, во-вторых, протекание тока в обмотках !2 моделей 8 этих ребер и, в-третьих, протекание тока в обмотке 5 — 1.

Протекание тока в обмотке 12 приводит к замыканию контактов 16 и блокировке моделей 8 до конца работы устройства. Это обеспечивает индикацию первого кратчайшего пути до конца работы устройства. Кроме того, протекание тока через обмотку 12 в каждой модели 8 приводит к размыканию контакта

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

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

Далее продолжают увеличивать выходное напряжение источника 1 до тех пор, пока за счет возрастания тока в моделях 2 ветвей и обусловленного этим срабатывания тех или иных реле моделей 2, во второй группе моделей 8 не замыкается цепь протекания тока источника 3 за счет замыкания контактов 15. Во второй группе моделей 8 ток протекает уже только по ветвям, образующим второй кратчайший путь, поскольку после первого шага работы устройства за счет размыкания контактов ll — 1 ребра первого кратчайшего пути из топологии графа исключены.

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

5 — К, разомкнет контакт 7 — К, исключив возможность дальнейшего повышения выходного напряжения источника l.

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

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

1336043

Составитель A. Мишин

Редактор С. Патрушева Техред И. Верес Корректор A. Обручар

Заказ 3805 46 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

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

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