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

 

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

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

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

РЕСПУБЛИН 5п ь, G 06 G 7/48

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

H А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3711907/24-24 (22) 16.03.84 (46) 30.06.86.Бюл. 24 (72) Е.И.Бороденко и В.Е.Назаренко (53) 681.14(088.8) (56) Авторское свидетельство СССР

Ф 553628, кл. G 06 С 7/122, !977.

Авторское свидетельство СССР 552617, кл. G 06 G 7/122, 19?7. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач на rpa„„SU,» 1241266 A 3 фах, связанных с определением внешнего центра графов, являющихся математическими моделями сетей связи, информационно-расчетных систем и т.д.

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

1 124 i

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

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

Суть изобретения состоит в определении вершины х,, для которой

So(x )- min(So(x;)3 х; Х

1 где S (х;) = max (с(х,, х ));

15 х Е Х, а (х,х ) — длина пути в вершину

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

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

Устройство содержит модели 1 ветвей, коммутатор 2, источник 3 напря- жения, накопительные элементы 4, ком- 25 параторы 5, генератор 6 линейно изменяющегося напряжения„ элемент ИЛИ

7, блок 8 отображения, ключи 9 (тиристоры)> переменные резисторы 10, выпрямительные диоды 11, нагрузочный у1 резистор 12, источчик 13 напряжения (модели ветви).

Po,цели 1 ветвей соединяются соглас.. О топ!Ологии исследуемого графа и

1! 1! на 1::*:.:х у".Tàíàâëèâàåòcë вес дуги графа.

Коммутатор 2 предназначен для по,-ключенил рассматриваемой вершины и соответ" òâóþùåãî ей накопительного элемента 4 к одному из полюсов источника 3 напряжения, а также поочередной коммутации второго полюса источника ко всем остальным вершинам.

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

Генератор 6 линейно изменяющегося напряжения — управляемый. Вход запуска его является одновременно входам устройства. Вход осталова предназначен для запрещения дальнейшей работы генератора, причем напряжение на его жение, при котором начинает протеI((ÿ з т! тэк 11О Одном!! I(p атчайшРму пути из мнажР ст1за ваз1"IОжных путей между вершинами 1 и 1 или i и е и т.д.

Каждый произвопьный пут! имеет свой

11 I! вес (свою длину), равный =уммг ве!

1 сон входящих в него ветвей. Зта I I fI сумма весов в соатветст!зии с ла"икай работы модели ветви прапорциональна суммарному напряжению, подаваемо:..1у на управляющие электродь! тиристоpoB 9 данного пути с резисторов

)О. С увеличением напряжения на выходе источника 3, когда ега значение и

Iзе 1ичины Up =, U =тп1и,-! 1 переключение (аткрывание)

9 крат"-1айшего пу ги между и 3 и т,д. Зтот путь отмементами индикации (не падостигает происходит

".ИРИСTOPOII

ВРРШИНО1Л 1. чаетсп эле казаны). выходе остается таким, каким Оно б.,I

7О в Mo> .ент прихода сигнал!а запрета с элемента ИЛИ 7.

Блок 8 отображения предс-,авпяет собой набор п сPåòoäIIoäo7! каждый иэ которых с аответств !е Г ОГ!ределеннай вершине графа.

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

Из мсде.пей 1 ветвей собирается схема в соответствии с топологией графа. В каждой моде 1и ветви устанавливается ее вес с помощью ре— !! II зи сто р ов 1 0 и и с т очник а 1 3 наГ! р я!1(ени я модели ветви . При и амащи коммутатора 2 производится подключение источника 3 напряжени я последовательно между вершиной i и в с еми а с т альными вершинами j, e, k, g . и T . ä, При этом к с о отв е т ст в ующему выходу коммутатораа (пар алл ельно и ст ачни к у 3 напряжения) подключается з -й накопительный элемент 4 . При каждой комму— тации пр ои з в о цит ся увеличение напр я— жения источника 3 о т 0 до опр еделенного U 1(, „,, которое опр едел я е т с я колич е с твам ветвей в кра тч айш ем пути между в ершинами, к которым при помощии коммутатора 2 подключен источник

3 напряжения . При ув елич ении н апряжени я источника от 0 да к ако га- т а

U, „, в опр едел енный мам ент вр ем ени прои сходи т пе р еключ ение тири стар ав, принадлежа1щ1х цепи, для которой !

U = min — это минимальное напря266

3 1241

Дальнейшего увеличения напряжения источника 3 не производится так как

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

После этого определяется кратчайший путь между i и е и т.д..аналогичным образом. 1-й накопительньп» элемент 4 заряжается до максимального 10, значения Х „, соответствующего са1 мому длинному из всех кратчайших путей между вершиной i и одной из вершин j, е, k, g. После этого при помощи коммутатора 2 подключают источник 3 напряжения между вершиной и всеми остальными вершинами е, К источнику 3 при помощи коммутатора 2 подключается j -й нако— пительный элемент 4. Накопительный» элемент 4 1 заряжается до максимального напряжения Е „;, соответствую- . щего самому длинному кратчайшему пу— ти между вершиной ) и вершина»»и е, gр i ° . Анало» ично производится оп 5 ределение кратчайших путей из вершин е, k u

После окончания этой операции соответствующие накопительные элементы 4 заряжаются до напряжении Ещд»„, 30 которые пропорциональны максимальным кратчайшим путям из данной вершины во все остальные. На этом первый этап нахождения внешнего центра графа заканчивается. Для нахождения цен-35 тра графа на вход запуска генератора

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

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

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

1241266

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

Техред B.Êàäàð Корректор О.Луговая

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

Закаэ 3601/45 Тираж 671

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

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

Подписное

Производственно"полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 является одноименным входом устройства, а вход останова подключен к выходу элемента KIH, причем выходы компараторов группы соединены с со— ответствующими входами элемента ИЛИ .и блока отображения.