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

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

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

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

Устройство содержит блоки 1 моделирования ветвей, источник 2 напряжения, блок 3 коммутации, блоки Ар 1-й группы, где 1 1,.,.,п, m 1,...,п, первую группу блоков выбора наибольшего параметра, первый генератор 6 линейно изменяющегося напряжения, первую группу компараторов 7 7f,, первый блок 8 отобра- жения, первый элемент РШИ 9, второй генератор 10 линейно изменяющегося напряжения, вторую группу блоков выбора наибольшего параметра вторую группу компараторов , второй блок 13 отображения и второй элемент ИЛИ 14,.

.Блок моделирования ветви образуют тиристоры 15, переменные резисторы .16, выпрямительные диоды 17 и источ- ник 18 напряжения (модели ветви). Блок 3 коммутации содержит переключатели 19, 20, и кнопки 22.,- 22р. Переключатель 20 -предназначен для подключения шины нулевого потен- циала к вершине графа, от которой определяются длины путей ко всем остальным вершинам графа. Переключатель 19 служит для поочередного подключения источника 2 напряжения ко всем вершинам, кроме заземленной. Переключатели коммутируют источник напряжения на входы соответствующих накопительных элементов 4. Кнопки предназначены для по- строчного подключения источника 2 напряжения к накопительным элементам 4 через переключатели 21 -21ri.

Блок 4 накопления выполнен в аи- де. накопительной емкости с параллельно подршюченным ключом сброса для разряда емкости. Накопительная емкость через разделительный диод.

включенный в соответствующей полярности, подключен к второму выходу блока 3 коммутации. Диод предназначен для предотвращения разряда накопительной емкости через источник 2 напряжения. Накопительная емкость подключена параллельно источнику 2 напряжения и входу блоков 5 и 11.

Блоки 5 и 11 выбора наибольшего параметра сравнивают аналоговые значения напряжения на входе и коммутируют на выход наибольшее значение параметра.

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

Источник 2 - регулируемый источник постоянного напряжения, напряжение на выходе которого изменяется по линейному закону от О до

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

Сущность изобретения заключается в том, что определяется расстояние

между вершинами rd(x-,x,)3 , затем

#

отыскиваются такие две вершины х

их, для которых соответственно выполняются равенства:

So(x) min tSo(x.,)3 ;

X

S(xp (x.)

X;ex

где Sp(x) (x ,x. ) ;

X- e X

S(.(x) (x|, X;) ;

X e X

d(x.,x. - длина пути в вершину j, достижимую из вершины i;

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

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

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

переключателя 20 подключен к первой вершине графа, переключатель 19 - к второйj переключатель 21, - к блоку . При нажатии кнопки 22 устройство готово для определения длины пути из первой вершины во вторую. Затем увеличивается напряжение блока 2 до значения U , при котором срабатывают пороговые элементы моделей ветвей, входящие в кратчайший путь между первой и второй вершинами (светятся индикаторные элементы моделей ветвей), При этом до напряжения U заряжается и накопительная емкость блока 4. , так как она через кнопку 22 и переключатель 21 подключена к источнику 2 напряжения. Для определения кратчайшего пути из первой вершины в третью необходимо уменьшить напряжение на выходе блока 2 до нуля и соединить подвижный контакт переключателя 19. с третьей вершиной, переключатель 21 с блоком 4, . Затем

25

увеличивают напряжение на выходе источника 2 до значения, при котором срабатывают пороговые элементы моделей ветвей, ВХОДЯПЦ1Х в кратчайший путь между первой и третьей вершинами. Накопительная емкость блока 4 заряжается до значения . Аналогич- 30 .TibiM образом определяются и запоминаются все длины путей из первой вершины в остальные. Для определения путей из второй вершины в остальные подвижный контакт переключателя 20 соединяется с второй вершиной, переключателя .19 - с первой, переключацнала по шине Пуск напряжение на выходе генератора 6 начинает увеличиваться по линейному закону и при достижении значения, пропорционально (х .) , срабатывает компаратор 7. , на выходе которого появляется потенциал логической единицы. Этот потенциал засвечивает L-Й с.ветодиод на блоке 8 Ci-я вершина является

fO внешним центром графа), а с выхода элемента ИЛИ 9 потенциал поступает на вход останова генератора 6, запрещая дальнейшее увеличение напряжения на его выходе, и на вход запус(5 -ка генератора 10. Напряжение на выходе генератора 10 начинает увеличиваться и при достижении значения, пропорционального (xj.)j, , срабатывает компаратор 12., на выходе

20 которого появляется потенциал логической единицы. Этим потенциалом за- .свечивается j-й светодиод на блоке 13 (J-я вершина является внутренним центром графа), а с выхода ИЛИ 14 потенциал поступает на вход останова генератора 10, запрещая дальнейшее увеличение напряжения на его выходе.

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

теля

24 с блоком 4j. . Кнопка 22, размьцсаётся, а кнопка. 22, замыкается.

Устройство для определения параметров графов, содержащее блоки моделирования ветвей по числу ветвей моделируемого графа, источник нап35 ряжения, блок коммутации, п групп по п блоков накопления, где п - число

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

J:

В соответствии С

ние на выходах блоков накопления со-45 наличием дуги между i-й и j-й вершиответствуют кратчайшему расстоянию между соответствующими вершинами.

нами моделируемого графа, выход ис точника напряжения подключен к вход блока коммутации, т-й выход k-й гру пы, где п 1,....,п, k 2,...,п+

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

все остальные, из второй вершины во все остальные,..., из вершины п во все остальные, т.е. напряжения на выходе блоков 5 пропорциональны S(x j) а на выходах блоков 11 пропорциональ ны

S(x). Эти напряжения подаются

соответственно на первые входы, компараторов 7 и 1-2. После подачи потен

цнала по шине Пуск напряжение на выходе генератора 6 начинает увеличиваться по линейному закону и при достижении значения, пропорционально (х .) , срабатывает компаратор 7. , на выходе которого появляется потенциал логической единицы. Этот потенциал засвечивает L-Й с.ветодиод на блоке 8 Ci-я вершина является

внешним центром графа), а с выхода элемента ИЛИ 9 потенциал поступает на вход останова генератора 6, запрещая дальнейшее увеличение напряжения на его выходе, и на вход запус-ка генератора 10. Напряжение на выходе генератора 10 начинает увеличиваться и при достижении значения, пропорционального (xj.)j, , срабатывает компаратор 12., на выходе

которого появляется потенциал логической единицы. Этим потенциалом за- свечивается j-й светодиод на блоке 13 (J-я вершина является внутренним центром графа), а с выхода ИЛИ 14 потенциал поступает на вход останова генератора 10, запрещая дальнейшее увеличение напряжения на его выходе.

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

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

вершин моделируемого графа, первую руппу из п компараторов, первый блок отображения, выход i-ro блока моделирования ветвей объединен с i-м выходом первой группы блока коммута

ции и подключен к входу j-ro блока моделирования ветвей, где i,j

J:

В соответствии С

нами моделируемого графа, выход источника напряжения подключен к входу блока коммутации, т-й выход k-й группы, где п 1,....,п, k 2,...,п+1,

блока коммутации подключен к входу т-го блока накопления k-й группы.

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

вторая группа из п компараторов, два генератора линейно изме11ЯЮ1цегося напряжения, два элемента ИЛИ и. второй блок отображения, выход т-го блока накопления 1-й группы, где 1 1,... п, подключен к т-му входу 1-го блока выбора наибольшего параметра первой группы и к 1-му входу т-го блока накопления второй группы, выход 1-го блока выбора наибольшего параметра первой группы подключен к первому входу 1-го компаратора первой группы, выход т-го блока выбора наибольшего параметра второй группы подключен к первому входу га-го компара- тора второй группы, выход 1-го компаратора первой группы подключен к 1-му входу первого элемента ИЛИ, вы

)5 2 i0256

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

жения, выход которого подкяюченк вторым входам компараторов первойгруппы.

Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением внутреннего и внешнего центров графов, являю- йщхся математическими моделями сетей связи и информационно-расчетных сие- . тем. Цель изобретения - расширение функциональных возможностей устройства за счет определения внутреннего центра графа. Поставленная цель достигается тем, что устройство содержит блоки 1 моделирования ветвей по числу ветвей моделируемого графа, источник напряжения 2, блок 3 коммутации, блоки 4f| 1-й группы, где 1 1,...,п; m 1,...,п, первую группу блоков выбора наибольшего параметра, первый генератор 6 линейно изменяющегося напряжения, первую группу компараторов , первый блок 8 отображения, первьй элемент ИЛИ 9,-второй генератор 10 линейно изменяющегося напряжения, вторую группу блоков выбора наибольшего параметра, вторую группу компараторов , второй блок 13 отображения, второй элемент ИЛИ 14. 3 ил. i (Л оо to 4 СЛ

.11±.

(pus-.Z

±

Р.едактор А.Огар

Составитель В.Смирнов Техред И.Попович

Заказ 2966/52 Тираж 672Подписное

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

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

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

фиг.З

Корректор н. Король