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

 

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

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

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

РЕСПУБЛИН (19) (1!) (51) 4 G 06 С 7/122

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

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

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

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3863019/24-24 (22) 20.02.85, (46) 15.02.87. Бюл. Ф 6 (72) Е.И.Бороденко, В.Е.Назаренко и А.Г.Ларионов

;(53) 681.333(088.8) (56) Авторское свидетельство СССР

)) 552617, кл. G 06 G 7/122, 1977.

Авторское свидетельство СССР .; Ф 1251097: кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть предназначено для исследования параметров графов, в частности для определения медианы графа и для определения мест размещения аварийных служб и пунктов обслуживания. Целью изобретения является расширение функциональных возможностей за счет возможности определения медианы графа. Поставленная цель достигается тем, что в устройство, содержащее модель ветви, блок отображения, компараторы, коммутатор, переключатели и кнопки, введены источник опорного напряжения, накопи тельные элементы, сумматоры, аналого-цифровые преобразователи и блок выбора наименьшего параметра. 2 ил.

1290364

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

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

Сущность изобретения заключается в том, что определяются расстояния между вершинами (d (х;, х ) и опре" деляется внешняя медиана

6,(х„) = min $5o(x;Q, 15 х;еХ где. „(x ) = с . d(х;,X>), х,еХ

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

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

Модель 1 ветви — двунаправленная модель на пороговых элементах, порог срабатывания которых пропорционален "весу" ветви (т.е. в данном случае расстояние между вершинами), . 35 содержит индикаторный элемент для отображения протекания тока по ветви.

Источник 2 — регулируемый источник . постоянного напряжения, напряжение на выходе которого изменяется по 40 линейному закону от 0 до U„„„,.

Коммутатор 3 (фиг.2) — ручной коммутатор, содержит переключатели 10, 11, 12,-12(, и кнопки 13, — 13„. 45

Переключатель 10 предназначен для подключения шины нулевого потенциала к вершине графа, от которой определяются длины путей к всем остальным вершинам графа. Переключатель 11 используется для поочередного подключения источника 2 напряжения к всем вершинам, кроме заземленной.

Переключатели 12(— 12 необходимы для коммутации источника напряжения на входы соответствующих накопительных элементов 4. Кнопки 13 — 13„предназначены для посгрочного подключения источника 2 напряжения к .накопительным элементам 4 через переключатели 121 †„ . Накопительный элемент 4 представляет собой накопительную емкость с параллельно подключенHI(M ключом сброса для разряда емкости. Накопительная емкость через разделительный диод, включенный в соответствующей полярности, подключен к второму выходу коммутатора 3. Диод предназначен для предотвращения разряда накопительной емкости через источник 2 напряжения. Накопительная емкость подключена параллельно источнику 2 напряжения и входу сумматора 5.

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

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

В исходном положении устанавливаются "веса" моделей 1 ветвей, пропорциональные соответствующим расстояниям между вершинами. Все кнопки

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

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

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

Следовательно, на выходе сумматороров 5, -5„2O кратчайшим суммарным расстояниям из первой, второй,...n-й вершины в остальные. После преобразования этих напряжений в цифровой вид в блоках

6 -6„ производится их сравнение в блоке 7 и выбирается наименьшее, которое равно медиане графа и отображается по первому входу на блоке 8.

Для определения адреса вершины на вторые входы компараторов 9, -9„ пода- 3О ются сигналы, пропорциональные передаточным числам, а на первые входы— пропорциональные медиане. При выпол- нении условия U „= U „на выходе компаратора появляется потенциал ло- 35 гической единицы, который по второму входу отображает адрес медианы.

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

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

j-й строки матрицы накопительных элементов (где i-1,2..., n-1, )=1, 2..., n) подключен к i-му входу

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

1 290364

4 Arr е

4 re

4 юлт

4/7/1- f

Подписное

Произв.-полигр. пр-тие, г, Ужгород, ул. Проектная, 4

ВНИИПИ .Заказ 7905/49 Тираж 673 !

A Î ÍÎË ц,щ емец л с м

Фкг

ВгОлим елггю,яо и

4 лу

9nz

Фю,у