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

«

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

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

Суть изобретения состоит в определении вершины х, для которой S,(x)r.(x.),

х;ех , .

где S(x;) max о (х, , х;);х ех,

а (х,,х ) - длина пути в вершину J, достижимую из вершины i.

На фиг.I изображена структурная схема устройства; на фиг.2 - структурная схема модели ветви.

Устройство содержит модели I ветвей, коммутатор 2, источник 3 напря- женин, накопительные элементы 4, компараторы 5, генератор 6 линейно изменяющегося напряжения, элемент ИЛИ 7, блок 8 отображения, ключи 9 (тиристоры) переменные резисторы 10, вьтрямительные диоды 11, нагрузочный резистор 12, источник 13 напряжения (модели ветви).

Модели 1 ветвей соединяются сог- лас.го топологии исследуемого графа и на ;л; устанавливается вес дуги графа.

Коммутатор 2 предназначен для под клгоченип рассматриваемой вершины и соответствующего ей накопительного элемента 4 к одному из полюсов источника 3 напряжения, а также поочередной коммутации второго полюса источника ко всем остальным вершинам.

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

Генератор 6 линейно изменяющегося напряжения - управляемый. Вход запуска его является одновременно входом устройства. Вход останова предназначен для запрещения дальнейшей работы генератора, причем напряжение на его

412662

выходе остается таким; каким оно было в момент прихода сигнала запрета с элемента ИЛИ 7.

Блок 8 отображения представляет

5 собой набор п светодиодов, каждый из которых соответствует определенной вершине графа.

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

0 Из моделей 1 ветвей собирается схема в соответствии с топологией графа. В каждой модели устанавливается ее вес с помощью резисторов 10 и источника 13 напря ке15 НИН модели ветви. При помощи коммутатора 2 производится подключение источника 3 напряжения последовательно межд,у вершиной i и всеми остальными вершинами j, е, k, g.H т-.д. При

20 этом к соответствующему выходу коммутатора (параллельно источнику 3 напряжения) подключается г-й накопи-тельный элемент 4. При каждой коммутации производится увеличение напря25 л(ения источника 3 от О до определенного U|,(.,|j, которое определяется количеством ветвей в кратчайшем пути между вершинами, к которым при помощи коммутатора 2 подключен источник

30 3 напряжения. При увеличении напряжения источника от О до какого-то UfrtOKc определенный момент времени происходит переключение тиристоров, принадлежащих цепи,.для которой

35 -71 U min Ui

это минимальное напря

жение, при котором начинает протекать ток по ofiiioMy кратчайшему пути из множества возможных путей мелсду вершинами i и j или i и е и т.д. Каждый произвольный путь имеет свой вес (свою длину)5равный суьте весов входящих в него ветвей. Эта сумма весов в соответствии с логикой работы модели ветви пропорциональна суммарному напряжению, подаваемому на управляюш -1е электроды тиристоров 9 данного пути с резисторов 0. С увеличением напряжения на выходе источника 3, когда его значение

достигает ве-личшш U SI U. min,

Происходит переключение (открывание) 5-5 гиристоров 9 кратчайглего пути между вершиной i и j и т.д. Этот путь отме чается элементами индикации (не показаны) .

3

Дальнейшего увеличения напряжения источника 3 не производится так как в этом случае поочередно (по мере увеличения дпины) определяются все пути из вершины i в j ,. а необходимо определить только кратчайший путь.

После этого определяется кратч.ай- ший путь между i и е и т.д. аналогичным образом, i-й накопительньш эле- мент 4 заряжается до максимального значения Z ,,., соответствующего самому длинному из всех кратчайших, путей между вершиной i и одной из вершин J, е, k, g. После этого при помощи коммутатора 2 подключают ис- точник 3 напряжения между вершиной j и всеми остальными вершинами е, k, g, i. К источнику 3 при помощи коммутатора 2 подключается j-ft накопительный элемент 4. Накопительный элемент 4 j заряжается до максимального напряжения , ; , соответствую- ш,его самому длинному кратчайшему пути между вершиной j и вершинами е, k, g, i. Аналогично производится on- ределение кратчайших путей из вер- псин е, k и g.

После окончания этой операции со- ответствуюш1 е накопительные элементы 4 заряжаются до напряжений Е, , которые пропорциональны максимальным кратчайшим путям из данной вершины во все остальные. На этом первый этап нахождения внешнего центра графа заканчивается. Для нахождения цен тра графа на вход запуска генератора 6 подается сигнал Пуск. На вторые входы компаратора 5 начинает посту-, i пать линейное возрастающее напряже- ние от О до какого-то определенного значения, которое соответствует ми- нимальному напряжению, поданному на первый вход одного из компараторов 5 с соответствующего накопительного элемента 4. Как только эти напряже- ния станут равными, на выходе соответствующего компаратора появится напряжение 1, которое поступит на соответствующий вход элемента РШИ 7 и блока 8. Единичный сигнал с выхода элемента ИЛИ 7 подается на в ход останова генератора 6 и запрещает дальнейшее увеличение напряжения на его выходе (с целью предотвращения отображения ложных внешних центров). Кроме того, напряжение- 1 с выхода соответствующего компаратора подается на вход блока 8, где засвечивает со

5

5 0 5

0

2664

ответствующий светодиод, относяцупЧ- ся к вершине графа, являющейся его внешним центром.

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

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

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

г-НЭ-гйТгтО-.

MbJQf

1

ч -®-ад

8. 1

т

Редактор Е.Копча

PU8. г

Составитель А.Шеренков

Техред В.Кадар Корректор 0.Луговая

Заказ 3601/45- Тираж 67 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие г,5 жгород,ул,Проектная,4

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