Устройство для моделирования графа

 

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

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

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

РЕСПУБЛИК

А-2=—

1бц 4 G 06 0 7/122

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

IlO ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМ

ПРИ ГКНТ СССР (61) 1327126 (2)) 4379655/24-24

{22) 17.02.88 (46) 15.08.89. Бюл. и - 30 (72) А.Ю. Лапин (53) 681.333(088.8) (56) Авторское свидетельство СССР

9 1327126, кл. G 06 G 7/122, 1985. (54) УСТРОЙСТВО ДЛЯ ИОДЕЛИРОВАНИЯ

ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в гра..SU„„15010 5

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

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

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

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

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

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

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

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

Одновременно по входу 25 устанавливается коэффициент деления счетчика 21, равный количеству моделей ветвей, входящих в исследуемый путь.

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

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

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

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

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

ТехРед Л.Олийнык

Корректор Л.Бескид

Редактор А. Огар

Заказ 4871/47 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 ступающего на вход записи с выхода элемента ИЛИ 8. Одновременно сигнал с выхода элемента ИЛИ 8 поступает на счетный вход счетчика 21.

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

После того, как все модели 9 заданного пути сработают, на выходе счетчика 21 появляется сигнал, кото- 20 рый устанавливает триггер 22 в нулевое состояние..Сигнал с инверсного выхода триггера 22 поступает на инди" катор 23, сигналиэируя об окончании цикла измерений. Одновременно исчез- 2я новение сигнала на прямом выходе триггера 22 останавливает источник 1.

Для исследования нового пути необходимо выбрать его с помощью ключей 10, установить новое значение счетчика 2Г 3р и подать сигнал на вход 24.

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

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