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

 

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

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

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

РЕСПУБЛИК (19) (11) (51) 4 С 06 G 7/122

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

Н ABTOPCHOIVIV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4018709/24-24 (22) 06.02.86 (46) 15.07.87. Бюл. Ф 26 (72) Е.И.Бороденко, В.Е.Назаренко, Л.Г.Трусей, Д.И.Гиренко и А.Г.Ларионов (53) 681.325 (088.8) (56) Авторское свидетельство СССР У 1241266, кл.. G 06 F 7/122, 1984.

Авторское свидетельство СССР

Ф 1290364, кл. G 06 F 7/122, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПАРАМЕТРОВ ГРАФОВ (57) Изобретение относится к вьтчислительной технике и может быть использовано для решения задач на графах, связанных с определением внутреннего и внешнего центров графов, являющихся математическими моделями сетей связи и информационно-расчетных систем. Цель изобретения — расширение

Г !

1

I функциональных возможностей устройства за счет определения внутреннего центра графа. Поставленная цель достигается тем, что устройство содержит блоки 1 моделирования ветвей по числу ветвей моделируемого графа, источник напряжения 2, блок 3 коммута.ции, блоки 4 1-й группы, где 1

1,...,n; ш = 1,...,n, первую группу блоков 5„-5„ выбора наибольшего параметра, первый генератор 6 линейно изменяющегося напряжения, первую группу компараторов 7„-7» первый блок 8 отображения, первый элемент

ИЛИ 9,- второй генератор 10 линейно изменяющегося напряжения, вторую группу блоков 11 „-11 „выбора наибольшего параметра, вторую группу компараторов 12, -12„, второй блок 13 отображения, второй элемент ИЛИ 14.

3 ил.

1 13240

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

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

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

Устройство содержит блоки 1 моделирования ветвей, источник 2 напряжения, блок 3 коммутации„ блоки 4

1-й группы, где 1 = 1,...,n, m = 20

1,...,n, первую группу блоков 5„ -5„ выбора наибольшего параметра, первый генератор 6 линейно изменяющегося напряжения, первую группу компараторов 7„ -7„, первый блок 8 отобра- 25 жения, первый элемент ИЛИ 9, второй генератор 10 линейно изменяющегося напряжения, вторую группу блоков

11 -11„ выбора наибольшего параметра, вторую группу компараторов 12 -12„, 30 второй блок 13 отображения и второй элемент ИЛИ 14. .Блок моделирования ветви образуют тиристоры 15, переменные резисторы

16, выпрямительные диоды 17 и источник 18 напряжения (модели ветви).

Блок 3 коммутации содержит переключатели 19, 20,21„-21„ и кнопки 22

22„. Переключатель 20 .предназначен для подключения шины нулевого потен- 40 циала к вершине графа, от которой определяются длины путей ко всем остальным вершинам графа. Переключатель 19 служит для поочередного подключения источника 2 напряжения 45 ко всем вершинам, кроме заземленной.

Переключатели 21„ — 21„ коммутируют источник напряжения на входы соответствующих накопительных элементов 4.

Кнопки 22 -22„ предназначены для построчного подключения источника 2 напряжения к накопительным элементам 4 через переключатели 21„ -21„,.

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

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

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

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

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

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

Sо(xо) m n 4 $о(x )

X;E Õ

$ (х ) = min ($ (х.)j, Х;Е Х где S (х,.) = maxed(x;,x ));

Х.Е Х

$ (х ) = maxed(x, x;));

Х Е Х

d(x.,õ ) †. длина пути в вершину

1 )

), достижимую из вершины i;

d(х .,х .) — длина пути в вершину

) 1 достижимую из вершины j.

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

В исходном положении устанавливаются веса моделей .ветвей 1, пропорциональные соответствующим расстояниям между вершинами, Все кнопки 22„-22„ отжаты, Подвижный контакт. 3 13240 переключателя 20 подключен к первой вершине графа, переключатель 19 к второй, переключатель 2 1„ — к блоку 4, При нажатии кнопки 22„ устройство готово для определения длины пути из первой вершины во вторую.

Затем увеличивается напряжение блока

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

22, и переключатель 21 подключена к источнику 2 напряжения. Для определения кратчайшего пути иэ первой вершины в третью необходимо уменьшить напряжение на выходе блока 2 до нуля Zp и соединить подвижный контакт переключателя 19 с третьей вершиной, переключатель 21 с блоком 4, . Затем увеличивают напряжение на выходе источника 2 до значения, при котором 25 срабатывают пороговые элементы моде.лей ветвей, входящих в кратчайший путь между первой и третьей вершинами. Накопительная емкость блока 4 заряжается до значения U . Аналогич- 30 . ным образом определяются и запоминаются все длины путей из первой вершины в остальные ° Для определения путей из второй вершины в остальные подвижный контакт переключателя 20 соединяется с второй вершиной, переключателя .19 — с первой, переключателя 21, — с блоком 4 „,. Кнопка 22, размыкается, а кнопка. 22 замыкается.

Алгоритм определения кратчайших пу- 40 тей аналогичен описанному. Так же оп.ределяются и запоминаются все пути из третьей, четвертой,...,n-й вершин в остальные. Таким образом, напряжение на выходах блоков накопления со- 45 ответствуют кратчайшему расстоянию между соответствующими вершинами.

Напряжение на выходах блоков 5 соответствует наибольшемУ из кратчай-50 ших расстояний из первой вершины во все остальные, из второй вершины во все остальные,..., из вершины и во все остальные, т.е. напряжения на выходе блоков 5 пропорциональны S (х,) а на выходах блоков 11 пропорциональ ны Б (х ). Эти напряжения подаются соответственно на первые входы.компараторов 7 и 12. После подачи потен25 4 циала по шине "Пуск напряжение на выходе генератора 6 начинает увеличиваться по линейному закону и при достижении значения, пропорционально

min)S (х .)), срабатывает компаратор о (7., на выходе которого появляется

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

J которого появляется потенциал логической единицы. Этим потенциалом засвечивается )-й светодиод на блоке

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

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

Устройство для определения параметров графов, содержащее блоки моделирования ветвей по числу ветвей моделируемого графа, источник напряжения, блок коммутации, п групп по п блоков накопления, где n — число вершин моделируемого графа, первую труппу из и компараторов. первый блок отображения, выход i-ro блока моделирования ветвей объединен с i-м выходом первой группы блока коммута-! ции и подключен к входу j-ro блока моделирования ветвей, где i,j — 1,...,п, i Ф j, в соответствии с наличием дуги между i-й и j-й вершинами моделируемого графа, выход источника напряжения подключен к входу блока коммутации, m-й выход k-й группы, где n = 1,....,n, k = 2,...,n+1, блока коммутации подключен к входу

m-го блока накопления k-й группы, выход i-го компаратора первой группы подключен к i-му входу первого блока отображения, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения внутреннего центра графа, в него введены две группы из и блоков выбора наибольшего параметра, 1324025 вторая группа из и компараторов, два генератора линейно изменяющегося »а»ряжения, два элемента ИЛИ и второй блок отображения, выход m-го блока накоплен я 1-й груп 4 где 1 = 1., 5 и, подключен к m-му входу 1-го блока выбора наибольшего параметра первой группы и к 1-му входу m-ro блока накопления второй группы, выход 1-го блока выбора наибольшего параметра 10 первой группы подключен к первому входу 1-ro компаратора первой группы, выход m-го блока выбора наибольшего параметра второй группы подключен к первому входу m-ro компаратора второй группы, выход 1-го компаратора первой группы подключен K

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

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

4а зф д

4л1

4 nz

<08

Составитель В.Смирнов

Редактор А.Orap Техред И.Попович Корректор H. Kîðîëü

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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