Устройство для моделирования графа Советский патент 1989 года по МПК G06G7/122 

(Л

ел

со ел

N

31501

ции, формирователь 14 одиночных импульсов, шифратор 15, информационный вход 16, информационный выход 17, вход 18 опроса, выход 19 признака на- личия информации и выход 20 номера модели 9, счетчик 21, триггер 22, индикатор 23, вход 24 пуска устройства и вход 25 задания количества дуг в пути между заданной парой вершин гра- фа устройства. Перед началом работы в счетчик 21 заносят информацию о количестве ветвей в пути между заданными вершинами. Если счетчик 21 работает на вычитание, в него можно занести количество ветвей в указанном пути, если на сложение - число,, дополняющее количество ветвей в пути до полной емкости счетчика. По мере срабатывания моделей 9 счетчик 21 накапливает их число и при переполнении устанавливает в ноль триггер 22, прекращая работу устройства. 1 ил.

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Целью изобретения является сокращение времени решения задачи определения веса ветвей в пути между заданной парой вершин графа. Устройство содержит источник 1 регулируемого напряжения, аналого-цифровой преобразователь 2, блоки 3 элементов И, два блока 4 и 5 элементов ИЛИ, блок 6 памяти, источник 7 постоянного напряжения, элемент ИЛИ 8, модели 9 ветвей графа, каждая из которых содержит первый и второй ключи 10, 11, блок 12 задания веса ветви, блок 13 индикации, формирователь 14 одиночных импульсов, шифратор 15, информационный вход 16, информационный выход 17, вход 18 опроса, выход 19 признака наличия информации и выход 20 номера модели 9, счетчик 21, триггер 22, индикатор 23, вход 24 пуска устройства и вход 25 задания количества дуг в пути между заданной парой вершин графа устройства. Перед началом работы в счетчик 21 заносят информацию о количестве ветвей в пути между заданными вершинами. Если счетчик 21 работает на вычитание, в него можно занести количество ветвей в указанном пути, если на сложение - число, дополняющее количество ветвей в пути до полной емкости счетчика. По мере срабатывания моделей 9 счетчик 21 накапливает их число, и при переполнении, устанавливает в ноль триггер 22, прекращая работу устройства. 1 ил.

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

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

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

Устройство содержит источник 1 ре- ,гулируемого напряжения, аналого-диф- ровой преобразователь 2, блоки элементов И 3, два блока 4 и 5 элемен- . тов ИЛИ, блок 6 памяти, источник 7 по постоянного напряжения, элемент ИЛИ 8 модели 9 ветвей графа, в состав каж- дои из которых входят первый и второй ключи 10 и 11, блок 12 задания веса ветви, блок 13 индикации, формирователь 14 одиночных импульсов, шифратор 15, информационный вход 16, информационный выход 17, вход 18 опроса, выход 19 признака наличия информации и выход 20 номера модели, счетчик 21, триггер 22, индикатор 23 вход 24 пуска устройства и йход 25 задания количества дуг в пути между заданной парой вершин графа устройства.

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

В исходном состоянии блок 6 обнулен, , напряжение на выходе источника 1 равно нулю, модели 9 соединены согласно топологии графа.

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

Одновременно по входу 25 устанавливается коэффициент деления счетчика 21, равный количеству моделей ветвей, входящих в исследуемый путь. После этого подают сигнал на вход 24 пуска, вследствие чего тригггер 22 устанавливается.в единичное состояние и сигнал с его прямого выхода поступает на вход пуска источника 1, кото- рьй начинает формировать и выдавать на модели 9 возрастающее напряжение.

При плавном увеличении напряжения источника 1 в моделях ветвей, образующих путь, появляется плавно увеличивающийся ток, а в блоке 12 увеличивается падение напряжения. В некоторый момент времени срабатывает ключ 1 (напряжение на обмотке реле блока 12 достигло напряжения переключения) од- н ой из моделей 9 и напряжение с выхода источника 7 поступает на вход блока 13 индикации и на вход пуска формирователя 14, который выдает импульс на выход 19 модели и на вход шифратора 15, который в параллельном коде вьщает номер данной модели 9 на вход блока 5.

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

ступающего на вход записи с выхода элемента ИЛИ , Одновременно сигнал с выхода элемента ИЛИ 8 поступает на счетный вход счетчика 21.

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

15

После того, как все модели 9 заданного пути сработают, на выходе счетчика 21 появляется сигнал, который устанавливает триггер 22 в нулевое состояние. .Сигнал, с инверсного выхода триггера 22 поступает на индикатор 23, сигнализируя об окончании цикла измерений. Одновременно исчезновение сигнала на прямом выходе триггера 22 останавливает источник 1. Для исследования нового пути необходимо выбрать его с помощью ключей 10, установить новое значение счетчика 2 Г и подать сигнал на вход 24.

б

В качестве блока 12 задания веса ветви может быть использован переменный резистор, параллельно которому подключена обмотка реле, которое может быть использовано в качестве второго ключа 11. В этом случае контакты реле являются исполнительной цепью ключа I1.

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

Устройство для моделирования графа по авт.св. № 1327126, отлича

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

пуска устройства подключен к входу установки в 1 .триггера, в.ыход которого подключен к входу пуска источника регулируемого напряжения, выход элемента ИЛИ подключен к счетному

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

устройства подключен к установочному входу счетчика.