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

 

Изобретение предназначено для решения задач определения р-центров неориентированных графов, являющихся математическими моделями широкого класблок синхронизации IL-J3 са прикладных задач оптимизации размещения различного рода пунктов обслуживания , баз снабжения, аварийных служб и т.п. Устройство содержит блок 1 синхронизации , блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, времяимпульсный интегрирующий преобразопатель 4, элемент памяти 6, регистр 7 и блок 5 сравнения. Работа устройства основана на аппаратно реализованном переборе всех сочетаний из о по р(р - число вершим графа) и определении сочетания, для которого г чличина расстояния до наиболее удаленной от них вершины минимально. Этим достигается расширение функциональных возможностей за счет определения р-центров графа. 1 ил. - 18„ о-| иг- I - пп Г А А S блок задания матрицы смежности 3 /5, 19, 19П I--. .L-rr-LL .--t /7, 17, П„ J/5 блок определение кратчайшего пути 2 Ю (Л С XI О ел 00 со Ю

СОК)3 СОГ1ЕТСКИХ

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

РЕСПУБЛИК (я)5 G 06 F 15/419

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

Г1О ИЗОБРЕТЕНИЯМ И Ol КРЫТИЯМ

Г РЛ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и сии (21) 4807169/24 (22) 09.01,90 (46) 15.01.92. Бюл. йг 2 (72) О.Г.Алексеев. А,M.Áîðèñîâ, С.А.Васильковский и Н,И,Ячкула (53) 681,333(088. 8) (56) Авторское свидетельство СССР

N 1348850, кл. G 06 F 15/20, 1986.

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

N. 1559354, кл. С 06 F 15/20, 1988 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ПАРАМЕТРОВ ГРАФА

{57) Изобретение предназначено для решения задач определения р-центров неориенти рован ных графов, являloùèх;я математическими моделями широкого клас„.,, Ж„„1705839 А1 са прикладных задач оптимизации размещения различного рода пунктов обслуживания, баз снабжения, аварийных служб и т.п.

Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности. времяимпульсный интегрирующий преобразователь 4, элемент памяти 6, регистр 7 и блок 5 сравнения. Работа устройства основана на аппаратно реализованном перебопе всех сочетаний иэ и по р {р — число вершин графа) и определении сочетания. для которо о . личина рас "тояния до наиболее удаленной от них вершины минимальна. Этим достигается расширение функциональнь" воэможностей эа счет определения р-центров графа. 1 ил.

1705839,<Овку в исходное нулевое состояние время»1 пульсного интегрирующего преобраз<1<<ягеля 4, а через вход 15 — начальную подготовку блока 2 Определения крат <айше<о пути. По э",вершении этих операций сиг- 5 нал с г -,хода 12 <;íèMàåòñë и формируется . < Овня 1" на втором управляющем

3

l- a ..-.:Хода 1," Сигнал пОСтупает н ВХОД э"<,.. y г .р ля- импульсного интегрир;- юще- 10 г< п<1еобр-зэлателя 4. который начинает вырабэтыва<ь ли <ейно возрастающий сигнал, пос1упающий на первый информационный вход блсKA 5 сравнения и информационный вход элемен га ", памяти, С соответствующих 15 выходов групп<: выходов 14<, 1=-1,п сигналы поступают на <ходь< 17< блока 2, входы 19 блока 3 и инфор ациг нные входы регистра . Р блоке 2 фиксируется исполнение вершин графа, соответствующих р входам 17< с 20 едини ным сигналом, а в блоке 3 моделируется определение кратчайших путей от вершин, соответствующих входам 19< с ед<иничным сигналом, до остальных tl р вершин, соответствующих входам 19< с нуле- 25 вым сигналом. По мере моделирования в блоке 3 достижен«я вершин графа сигналы уров „л "1":, ормир, Отся на соотве.ствующих выходах 19, блока. откуда они поступа<от на входы 17: блока 2. Через время, 30 достаточное для моделирования дг.снижения всех Вершин исследуемого граФа блок

2 ф. Ок" 1рует сигнал уговня "1" на выходе 16, которь и <<Оступает на управляю ций вход 11 блока 1 синх.1О«иэа<<ии и управляющий 35 вход блока 5 сравнения. При этом <:нимается сигнал с Втс<рого управляюше о выхода

13 блока 1 «рекращастся изменение сигнала на Выхг<де преобразователя 4, а в блок<. ". сравнения осуществляется соавнение сиг- 40 налов, «Огтупающи» на перв,lvl и второй

l1H<11< I/MR<<; <1<:<<ь<с в, Оды <-.. Выход < прсобра зователя и зле лента памяти соответс<венно. Если сигнал на первом входе меньше или равен сигналу на втором входе, то на 45 выходе схемы 5 формируется импульс уровня "1, поступающий на входы записи элемента > памяти и регистра 7, При этом в эле;лент б памяти вносится сигнал, пропорциональный кратчайшему расстоянию до 50 вершины, наиболее удаленной от заданного на данном шаге набора вершин графа. а в регистре 7 фиксируется ход, соответствующий данному набору. Через время, необходимое для сравнения и возможностей 55 перезаписи содержимого элемента б памяти и регистра 7. снимаются сигналы с соответствующих выходов 14 и формируется сигнал на выходе 12. Вновь осуществляется подготовка блока 2 и возврат в нулевое состояние преобразователя 4, по завершении которых формируется сигнал на выходе 13 и ледующем наборе из р выходов группы вы одов 14;. 1=1,п.

Далее работа устройства повторяется до полного перебора всех сочетаний иэ и по р. По окончанию работы номера вершин, соответствующих р-центру графа, однозначно определены номерами разрядов регистра 7с единичным содержанием, а величина, пропорциональная кратчайшему расстоянию от данных вершин графа до вершины, наиболее удаленной от них, записана в элементе б памяти, При вводе по входу 9 блока 1р=1, предлагаемое устройство обеспечивает определение 1-центра графа, как и известное устройство, Таким образом, введение новых элементов и связей позволяет за конечное число шагов определять р-центры графа как при р=1. так и при р >1. Это свидетельствует о существенном расширении функциональных воэможностей по сравнению с известным устройством. Кроме того, предлагаемое устройство существенно проще известного, так как содержит меньше на (n-1} элементов памяти. а вместо и-входового блока выбора минимума содержит схему сравнения с двумя информационными входами.

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

Усгройство для с<пределения <эряметf308 графа, содержа<«ее блол <<

Составитель О, Алексеев

Редактор Л. Пчолинская Техред M,Ìîðãåíòàë Корректор Т Патай

Заказ 195 Тираж Подписное

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

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

Производственно-издательский комбинат Патент", г. Ужгород, ул.Гагарина, 101 писи элемента памяти и регистра, разряды информационного входа регистра подключены к соответствующим выходам группы блока синхронизации, первый информационный вход блока сравнения подключен к входу элемента памяти и выходу время-импульсного интегрирующего преобразователя, второй информационный вход блока сравнения подключен к выходу элемента памяти, управляющий вход блока сравнения—

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