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

1

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

Цель изобретения - расширение функциональных возможностей за счет

12903642

пительным элементам 4 через переключатели . Накопительный элемент А представляет собой накопительную емкость с параллельно подключенным ключом сброса для разряда емкости. Накопительная емкость через разделительный диод, включенный в соответствующей полярности, подключен к второму выходу коммутатора 3. Диод

возможности определения медиан графа ЛО предназначен для предотвращения раз20

25

Сущность изобретения заключается в том, что определяются расстояния между вершинами (d (х;, Xj) и определяется внешняя медиана 6,(So) (х-ЛЪ 5

Хдб- jC

где, б„(х;1 11. cJ{x;,Xj),

Х ,еХ

На фиг.1 приведена функциональная схема устройства , на фиг.2 - функциональная схема коммутатора.

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

Модель 1 ветви - двунаправленная

модель на пороговых элементах, по- рог срабатывания которых пропорционален весу ветви (т.е. в данном случае расстояние между вершинами), 35 содержит индикаторный элемент для отображения протекания тока по ветви. Источник 2 - регулируемый источник . постоянного напряжения, напряжение на выходе которого изменяется по 40 линейному закону от О до ииаке.

Коммутатор 3 (фиг.2) - ручной коммутатор, содержит переключатеряда накопительной емкости через источник 2 напряжения. Накопительная емкость подключена параллельно источнику 2 напряжения и входу сумматора 5.

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

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

ются веса

30

В исходном положении устанавливамоделей 1 ветвей, пропорциональные соответствующим расстояниям между вершинами. Все кнопки 13,-13п отжаты. Подвижный контакт переключателя 10 подключен к первой вершине графа, переключатель 11 - к второй, переключатель 12 - к накопителю 4,2. При нажатии кнопки 13 ( устройство готово для определения длины пути из первой вершины во вторую. Затем увеличивается напряжение блока 2 до значения (j), при котором срабатывают пороговые элементы моделей ветвей, входящие в кратчайший путь между первой и второй вершинами (светятся индикаторнЁш элементы моделей ветвей). При этом до напряжения и заряжается и накопительная емкость элемента 4,, так как она через кнопку 13 и переключатель 12 подключена к источнику 2 напряжения.

ли 10, 11, 12,-12 и кнопки 13,- 13.5 Для определения кратчайшего пути из Переключатель 10 предназначен для подключения шины нулевого потенциала к вершине графа, от которой определяются длины путей к всем остальным вершинам графа. Переключатель 11 используется для поочередного подключения источника 2 напряжения к всем вершинам, кроме заземленной. Переключатели 12;|- 12 необходимы для коммутации источника напряжения на входы соответствующих накопительных элементов 4. Кнопки 13 - 13„пред- назначены для построчного подключения источника 2 напряжения к .накопервой Е1ершины в третью необходимо уменьшить напряжение на выходе блока 2 до нуля и соединить подвижный контакт переключателя 11 с верши50 ной 3, переключателя 12, - с накопительным элементом 4.. Затем увеличивают напряжение на выходе 2 до значе ния и,„, при котором срабатывают пороговые элементы моделей ветвей, вхо

55 дящих в кратчайший путь между первой и третьей вершинами. Накопительная емкость элемента 4, заряжается до значения U,j . Аналогичным образом оп ределяются и запоминаются все длины

делительный диод, включенный в соответствующей полярности, подключен к второму выходу коммутатора 3. Диод

предназначен для предотвращения раз

ряда накопительной емкости через источник 2 напряжения. Накопительная емкость подключена параллельно источнику 2 напряжения и входу сумматора 5.

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

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

5

5 0

ются веса

0

В исходном положении устанавливамоделей 1 ветвей, пропорциональные соответствующим расстояниям между вершинами. Все кнопки 13,-13п отжаты. Подвижный контакт переключателя 10 подключен к первой вершине графа, переключатель 11 - к второй, переключатель 12 - к накопителю 4,2. При нажатии кнопки 13 ( устройство готово для определения длины пути из первой вершины во вторую. Затем увеличивается напряжение блока 2 до значения (j), при котором срабатывают пороговые элементы моделей ветвей, входящие в кратчайший путь между первой и второй вершинами (светятся индикаторнЁш элементы моделей ветвей). При этом до напряжения и заряжается и накопительная емкость элемента 4,, так как она через кнопку 13 и переключатель 12 подключена к источнику 2 напряжения.

Для определения кратчайшего пути из

первой Е1ершины в третью необходимо уменьшить напряжение на выходе блока 2 до нуля и соединить подвижный контакт переключателя 11 с вершиной 3, переключателя 12, - с накопительным элементом 4.. Затем увеличивают напряжение на выходе 2 до значения и,„, при котором срабатывают пороговые элементы моделей ветвей, входящих в кратчайший путь между первой и третьей вершинами. Накопительная емкость элемента 4, заряжается до значения U,j . Аналогичным образом определяются и запоминаются все длины

путей из первой вершины в остальные, Для определения путей из второй вершины в остальные подвижный контакт переключателя 10 соединяется с второй вершиной, переключателя 11 - с первой, переключателя 12 - с накопительным элементом 4,;,. Кнопка 13 рамыкается, 132 замыкается. Алгоритм определения кратчайших путей аналогичен указанному. Так же определяют- ся и запоминаются все пути из третьей, четвертой,...,п-й вершины в остальные. Таким образом, напряжение на выходах накопительных элементов соответствует расстоянию между

соответствующими вершинами. Из матрицы накопительных элементов исключены диагональные элементы4д,4,, . ,4. Следовательно, на выходе сумматоро- ров 5, -5(, напряжения пропорциональны кратчайшим суммарным расстояниям из первой, второй, ,, .n-if вершины в остальные. После преобразования этих напряжений в цифровой вид в блоках производится их сравнение в блоке 7 и выбирается наименьшее, которое Р9ВНО медиане графа и отображается по первому входу на блоке 8, Для определения адреса вершины на вторые входы компараторов 9,-9 пода- ются сигналы, пропорциональные передаточным числам, а на первые входы- пропорциональные медиане. При выполнении условия U,g, на вькоде компаратора появляется потенциал ло- гической единицы, который по второму входу отображает адрес медианы.

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

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

5 О

15

0 5

0

5

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

аналого-цифровых преобразователей и блок выбора наименьшего параметра, причем выход источника опорного напряжения подключен к входу коммутатора, каждый выход второй группы выходов которого подключен к входу соответствующего накопительного элемента матрицы, выход каждого х-го накопительного элемента каждой j-й строки матрицы накопительных элементов (где i-1,2.,.,п-1, ,2,,,,n) подключен к i-му входу j-ro сумматора группы, выход которого подключен к входу одкоименно- го аналого-цифрового преобразователя группы, выход каждого из аналого-цифровых преобразователей группы подключен к одноименному входу блока выбора наименьшего параметра, выход каждого из аналого-щсфровых преобразователей группы подключен к первому входу одноименного компаратора группы, вторые входы всех компараторов группы объединены и подключе ны к выходу блока выбора наименьшего параметра, подключенному к соответствующему входу блока отображения

.конечного результата.

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

ffeflLuuHo/ грскра i J К м д . . /7

Я емен/тгл

гт «гл.

«/г 3

fnm fJfj-t