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

(р ь С 06 6 7/48 АНИЕ ИЗОБРЕТЕНИЯ ЛЬСТ нк СССР977.ССР 1977. чисть исна гра ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ А ВТОРСКОМУ СВИ(56) Авторское свидетельствФ 553628, кл. С 06 С 7/122,Авторское свидетельствоВ 552617, кл. С 06 С 7/122,(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВПАРАМЕТРОВ ГРАФОВ(57) Изобретение относится клительной технике и может быпользовано для решения задач 801241266 А 1 фах, связанных с определением внешнего центра графов, являющихся математическими моделями сетей связи, информационно-расчетных систем и т.д.Цель изобретения - расширение функциональных возможностей за счет определения внешнего центра графа. Устройство содержит модели ветвей, коммутатор, источник напряжения, накопительные элементы, компараторы, генератор линейно изменяющегося напряжения, элемент ИЛИ, блок отображенияключи, переменные резисторы, выпрямительные диоды, нагруэочный резистор, источник напряжения. 2 ил.1 1241Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах,связанных с определением внешнегоцентра графов, являющихся математическими моделями сетей связи, информационно-расчетных систем и т.д,Цель изобретения - расширениефункциональных возможностей за счетопределения внешнего .центра графа. 10Суть изобретения состоит в определении вершины х для которой8 (х ) ОГп 1 пБ (х; ),х;6 Х1где Я(х,) = шахсс (х х );.15х Е Х,а (х,х ) - длина пути в вершинудостижимую из вершины .На фиг,1 изображена структурная 2 Осхема устройства; на фиг.2 - структурная схема модели ветви.Устройство содержит модели 1 ветвей, коммутатор 2, источник 3 напря-жения, накопительные элементы 4, компараторы 5, генератор 6 линейно изменяющегося напряжения элемент ИЛИ7, блок 8 отображения ключи 9 (тиристоры) переменные резисторы 10,выпрямительные диоды 11, нагрузочный зорезистор 12, источчик 13 напряжения(модели ветви). 11 а,цели 1 ветвей соединяются соглас. топологии исследуемого графа ина 1:; х устанавливается в е с дуги графа,Коммутатор 2 предназначен для под-. ключения рассматриваемой вершины и соответствующего ей накопительного элемента 4 к одному из полюсов источника 3 напряжения, а также поочередной коммутации второго полюса источника ко всем остальным вершинам.Накопительный элемент 4 предстацляет собой, например, накопительную емкость с параллельно подключенной кнопкой для ее разряда, Накопитель- ная емкость через диод, включенный в соответствующей полярности (для предотвращения разряда емкости через источник 3 напряжения), подключается к выходу коммутатора.Генератор 6 линейно изменяющегоя напряжения - управляемый. Вход запуска его является одновременно входам устройства. Вход астапова предназначен для запрещения дальнейшей работы генератора, причем напряжение на егожение, при котором начинает протекать тэк Г 1 о одному кратчайшему пути из мяажества вазмОжных путей между ВЕРШИНаМИ 1 ИИЛИ 3. И Е И ТЦ, Каждый произвопьный пут имеет свойв е с ( свою длину ) , равный с уь 1 ме в ем. с о в входящих в него ветвей . 3 т асумма весов в соответствии с логикой работы модели ветви прапорциональна суммарному напряжению, пода- ваемо.1 у на управляющие электродь тиристорав 9 данного пути с резисторов 10, С увеличением напряжения на выходе источника 3, когда ега значение иГП 1.Ппереключение (открывание) 9 краГ"-1 а 1 лего пу ги между и 1 и т,д, Зтат путь отме- ментами индикации (не падостигает происходиттиристаравверГинойчаетсп элеказаны). выходе остается таким, каким Оно бь -ла в момент прихода сигнала запретас элемента ИЛИ 7.Блок 8 Отображения представляетсобой набор п светодиодов, каждый иэкоторых саатветств 57 ет ОГределе:1 ИОЙвершине графа.Устройство работает следующим абразом.Из мсде.пей 1 ветвей собирается схема в соответствии с топологией графа, В каждой моде.1 и ветви устанавливается ее вес с помощью резисторов 10 и источника 13 наГ 1 ря 11 ения модели ветви. При пама 1 Ги коммутатора 2 производится подключение источника 3 напряжения последовательно между вершиной 1. и всеми остальными вершинами 3 е, 1 с я.и т,д, При этом к соответствующему выходу коммутатора (параллельно источнику 3 напряжения) подключается 1.-й накопительный элемент 4. При каждой комму - тации произвоцится увеличение напряжения источника 3 от 0 до определенного П 1 которое определяется количествам ветвей в кратчайшем пути между вершинами, к которым при помощи коммутатора 2 подключен источник 3 напряжения, При увеличении напряжения источника от 0 да какого-та П,ц,в определенный момент времени происходит переключение тиристарав, принадлежащих цепи, для которойоЙ П = ГГ 1 п - это минимальное напря266 3 24Дальнейшего увеличения напряжения источника 3 не производится так как) в этом случае поочередно (по мере увеличения длины) определяются все пути из вершины . в ,. а необходимо определить. только кратчайший путь,После этого определяется кратчайий путь между . и е и т.д.,аналогичным образом. .-й накопительный элемент 4 заряжается до максимального 10, значения Х , соответствующего са 1мому длинному из всех кратчайших. путей между вершиной . и одной из вершин 3, е,1 с, я. После этого при помощи коммутатора 2 подключают ис точник 3 напряжения между вершинойи всеми остальными вершинами е,К источнику 3 при помощи коммутатора 2 подключается 3- иаков пительный элемент 4. Накопительный 0 элемент 4 3 заряжается до максимального напряжения Е ;, соответствую- . щего самому длинному кратчайшему пути между вершиной 1 и вершинами е, 1 су яр .е Аналоично производится оп ределение кратчайших путей из вершине, 1 си После окончания этой операции соответствующие накопительные элементы 4 заряжаются до напряжении Е30 которые пропорциональны максимальным кратчайшим путям из данной вершины во все остальные. На этом первый этап нахождения внешнего центра графа заканчивается. Для нахождения центра графа на вход запуска генератора 6 подается сигнал "Пуск". На вторые входы компаратора 5 начинает посту-. пать линейное возрастающее напряжение от О до какого-то определенного 40 значения, которое соответствует минимальному напряжению, поданному на первый вход одного из компараторов 5 с соответствующего накопительного элемента 4. Как только эти напряже ния станут равными, на выходе соответствующего компаратора появится напряжение "1", которое поступит на соответствующий вход элемента ИЛИ 7 и блока 8. Единичный сигнал с выхода 50 элемента ИЛИ 7 подается на вход оста- нова генератора 6 и запрещает дальнейшее увеличение напряжения на его выходе (с целью предотвращения отображения ложных внешних центров). Кро ме того, напряжение "1 с выхода соответствующего компаратора подается на вход блока 8, где засвечивает соответствующий светодиод, относящийся к вершине графа, являющейся еговнешним центром.о р м у л а и э о б р е т е н и я Устройства для исследования параметров графов, содержащее источник напряжения и модели ветвей, соединенные согласно топологии графа, причем каждая модель ветви содержит два встречно включенных выпрямительных диода, два последовательно соединенных ключа, каждый из которых выполнен в виде тиристора, нагрузочный резистор и два последовательно соединенньгх переменных резистора, к под -вижным контактам которых подключеныуправляющие электроды тиристоров,катоды которых соединены с.анодамивыцрямительных диодов, катод первоговыпрямительного диода соединен с анодом первого тиристора и является входом модели ветви, а катод второговыпрямительного диода подключен каноду второго тиристора и первому выводу нагрузочного резистора, второйвывод которого является выходом модели ветви, о т л и ч а ю щ е е с ятем, что, с целью расширения функ -циональных возможностей за счет определения внешнего центра графа, вустройство введены группа из п накопительных элементов (п - число вершин графа), группа из и компараторов, элемент ИЛИ, блок отображения,генератор линейно изменяющегося напряжения и коммутатора, а в каждуюмодель ветви - источник напряжения,первый вывод которого соединен спервыми выводами переменных резисторов, а второй вывод подключен к вторым выводам переменных резисторов икатодам тиристоров, управляющий входкоммутатора является входом управления режимами работы устройства, информационные входы коммутатора подключены к источнику напряжения устройства, первая группа выходов коммутатора соединена с вершинами графа, а вторая группа выходов - с входами соответствующих накопительныхэлементов, выходы которых подключены к первым входам соответствующих компараторов группы, вторые входы которых объединены и соединены с выходом генератора линейно изменяющегося напряжения, вход запуска которого1241266 является одноименным входом устройства, а вход останова подключен квыходу элемента ИП 1, причем выходы Составитель А.ШеренковТехред Б.Кадар Коррект Лугова Редактор Е.Копч Тираж 671 венного комитета СС етений и открытий Ж, Раушская наб.Подписн иэводственно"полиграфическое предприятие,г.ужгород,ул.Проектная Закаэ 3601/45 ВНИИПИ Государс по делам иэоб 13035, Москва, компараторов группы соединены с соответс гвующими входами элемента ИЛИ