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

СОЮЗ ОЕЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 19) 8 06 С 7/122 ЕННЫЙ НОМИТЕТ ССЗОБРетений и ОтнРыт ОСУДАРСПО ДЕЛА ИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМ ВИДЕТЕЛЬСТВ я к област может быть ания пара(21) 3863019/24-24(56) Авторское свидетельство СССРВ 552617, кл. С 06 С 7/ 122, 1977.Авторское свидетельство СССРВ 1251097. кл. С 06 Г 15/20, 1984.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯПАРАМЕТРОВ ГРАФОВ(57) Изобретение относитсвычислительной техники ипредназначено для исследов метров графов, в частности для определения медианы графа и для определения мест размещения аварийных служб и пунктов обслуживания. Целью изобретения является расширение функциональных возможностей за счет возможности определения медианы графа. Поставленная цель достигается тем, что в устройство, содержащее модель ветви, блок отображения, компараторы, коммутатор, переключатели и кнопки, введены источник опорного напряжения, накопительные элементы, сумматоры, аналого-цифровые преобразователи и блок выбора наименьшего параметра. 2 ил.фИзобретение относится к вычислительной технике и может быть предназначено для исследования параметровграфов, в частности для определения медианы графа и для определениямест размещения аварийных служб ипунктов обслуживания.Цель изобретения - расширениефункциональных возможностей за счетвозможности определения медиану графа,10Сущность изобретения заключаетсяв том, что определяются расстояниямежду вершинами (Й (х;, х ) и опре"деляется внешняя медиана6,(х) = пп.п б,(х;1,15х;еХгде, о (х 1 = с . с 3 (х;, х,х,еХНа фиг.1 приведена функциональная схема устройства", на фиг,2 - функцио-,20 нальная схема коммутатора.Устройство для исследования параметров графов содержит модель 1 вет-, ви, источник 2 опорного напряжения,25 коммутатор 3, накопительные элементы 4, сумматоры 5, аналого-цифровые преобразователи б, блок 7 выбора наименьшего параметра, устройство 8 отображения, компараторы 9, переключатели 10-12, кнопки 13.Модель 1 ветви - двунаправленная модель на пороговых элементах, порог срабатывания которых пропорционален "весу" ветви (т.е, в данном случае расстояние между вершинами), , 35 содержит индикаторный элемент для отображения протекания тока по ветви, Источник 2 - регулируемый источник . постоянного напряжения, напряжение на выходе которого изменяется по 40 линейному закону от 0 до П,. Коммутатор 3 (фиг.2) - ручной коммутатор, содержит переключатели 10, 11, 12,-12 и кнопки 13, - 13. 45 Переключатель 10 предназначен для подключения шины нулевого потенциала к вершине графа, от которой определяются длины путей к всем остальным вершинам графа, Переключатель 11 используется для поочередного подключения источника 2 напряжения к всем вершинам, кроме заземленной. Переключатели 121 в 12 необходимы для коммутации источника напряжения на входы соответствующих накопительных элементов 4. Кнопки 13, - 13 предназначены для посгрочного подключения источника 2 напряжения к .накопительным элементам 4 через переключатели 121-12. Накопительный элемент 4 представляет собой накопительную емкость с параллельно подключенным ключом сброса для разряда емкости. Накопительная емкость через разделительный диод, включенный в соответствующей полярности, подключен к второму выходу коммутатора 3, Диод предназначен для предотвращения разряда накопительной емкости через источник 2 напряжения. Накопительная емкость подключена параллельно источнику 2 напряжения и входу сумматора 5.Блок выбора минимального параметра 7 сравнивает цифровые значения кодов на входе и коммутирует на выходе наименьшее значение параметра.Устройство работает следующим образом. В исходном положении устанавливаются "веса" моделей 1 ветвей, пропорциональные соответствующим расстояниям между вершинами, Все кнопки 13,-13 н отжаты. Подвижный контакт переключателя 10 подключен к первой вершине графа, переключатель 11 - к второй, переключатель 12 - к накопителю 4, . При нажатии кнопки 13 устройство готово для определения длины пути из первой вершины во вторую. Затем увеличивается напряжение блока 2 до значения (П, ), при котором срабатывают пороговые элементы моделей ветвей, входящие в кратчайший путь между первой и второй вершинами (светятся индикаторнйе элементы моделей ветвей). При этом до напряжения П заряжается и накопительная емкость элемента 4 так как она через кнопку 13, и переключатель 12 подключена к источнику 2 напряжения, Для определения кратчайшего пути из первой вершины в третью необходимо уменьшить напряжение на выходе блока 2 до нуля и соединить подвижный контакт переключателя 11 с вершиной 3, переключателя 12 - с накопительным элементом 4, Затем увеличивают напряжение на выходе 2 до значения 0 , при котором срабатывают пороговые элементы моделей ветвей, входящих в кратчайший путь между первой и третьей вершинами. Накопительная емкость элемента 4,з заряжается до значения П,з, Аналогичным образом определяются и запоминаются все длиныпутей из первой вершины в остальные, Для определения путей из второй вершины в остальные подвижный контакт переключателя 10 соединяется с второй вершиной, переключателя 11 - с 5 первой, переключателя 12 - с накопительным элементом 4. Кнопка 13 размыкается, 13 замыкается. Алгоритм определения кратчайших путей аналогичен указанному. Так же определяют ся и запоминаются все пути из третьей, четвертойп-й вершины в остальные, Таким образом, напряжение на выходах накопительных элементов соответствует расстоянию между соответствующими вершинами. Из матрицы накопительных элементов исключены диагональные элементы 44,4 м . Следовательно, на выходе сумматороров 5, -5 д напряжения пропорциональны 20 кратчайшим суммарным расстояниям из первой, второй, ,и-й вершины в остальные. После преобразования этих напряжений в цифровой вид в блоках 6-6 производится их сравнение в блоке 7 и выбирается наименьшее, которое равно медиане графа и отображается по первому входу на блоке 8.Для определения адреса вершины на вторые входы компараторов 9, -9 пода ются сигналы, пропорциональные передаточным числам, а на первые входы - пропорциональные медиане. При выпол- нении условия Б = Б на выходе компаратора появляется потенциал ло гической единицы, который по второму входу отображает адрес медианы.Формула и з о б р е т е н и я40Устройство для исследования параметров графов, содержащее модели ветвей, коммутатор, блок отображения конечного результата, группу компараторов, причем модели ветвейсоединены согласно топологии исследуемого графа, каждый выход первойгруппы выходов коммутатора подключен к соответствующей вершине исследуемого графа, выход каждого компаратора группы подключен к соответствующему информационному входу блока отображения конечного результата,.о т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвозможностей за счет определениямедианы графа, в него введены источник опорного напряжения, матрицап(п) накопительных элементов,(где п - число вершин исследуемогографа), группа сумматоров, группааналого-цифровых преобразователей иблок выбора наименьшего параметра,причем выход источника опорного напряжения подключен к входу коммутатора, каждый выход второй группывыходов которого подключен к входусоответствующего накопительного элемента матрицы, выход каждого -гонакопительного элемента каждой3-й строки матрицы накопительныхэлементов (где -1,2п,3=1, 2,п) подключен к -му входу3-го сумматора группы, выход которого подключен к входу одноименного аналого-цифрового преобразователя группы, выход каждого из аналого-цйфровых преобразователей группыподключен к одноименному .входу блокавыбора наименьшего параметра, выход каждого из аналого-цифровых преобразователей группы подключен к первому входу одноименного компараторагруппы, вторые входы всех компараторов группы объединены и подключены к выходу блока выбора наименьшего параметра, подключенному к соответствующему входу блока отображения1290364 юонол цр емец мстим