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

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

Известно устройство для исследования ||угг,й н графе, содержащее. : эддмагональ

кую матрицу из -,у и (п-1) моделей дуг (п

число вершин графа) две i руг. пы элемент он И, группу ллеменгов НЕ, две группы счетчм ,ов, группу pei иг i рев и группу схем срапнс имя.

Усгройс ггю о; ..(.печиваег определение

ЙРШИС но: 1 :: ie -кз цих максимальному . гр.:1).-.). ни -ч-, быть использован для определения центров графа.

Наиболее близким к. предлагаемому ян :..к.я устройство для исследования парм ..i ij Od i раФ -.. aep «euuee блок задания ма :viц01 с.М ., мое ги, бяок определения

idwmero пути, блок регистрации време ;:.р 1(.полнения ьяршнн, блок синхрониза цич, блок выбора минимума.

Одн :;ко уел :)ОИ Л Е:0 обеспечивает опре ,;о/:1-чП1., ч ji;(..: 1 центры графа, тогда кэ1 Ц|Мрокий класс, iij.ii.кладных задач сводится .; определению р центров при р 1.

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

Сущность изобретения заключается в .гоы, что s устройство, содержащее блок за матрицы смежности, блок определения кратчайшего riyrn, блок синхронизации-. блока регистрации времени исгк.л непи:) зер пян и блока выбора миииму ,: введены время -ь- лульсный интегриру5.. преобразователь, схема сравнения. j(ie.-. c-H7 памяти и регистр примам информационные входы репчг:: рй соединены еы ..

Г,аМИ (.у|1ПЫ РЫ (},. В 6НО.Э СИНХРОН ..и у о/.1, записи регистра оОиедмнем с нг-. ззписм зломен 1 а Г|3мяги и соединим с информационным оыходом схемы срзвнеш-ш. управпяющий :;ход которой объединен с уп- рлвтяющис входом блока синхронизации и соединен с выходом признака исполнения всг-х вершин блока определения крзтчайч. е- гс пути, перчый инфоомационпь/й -г.ход схемы сравнения соединен с :;ыходоГ ( феобразов,1тя/р. .порой -- с информчцмон мым выходог- iifiv-ncina п:м ,яти, вход ют., рого под к л ю1 с н к выходу г ч обрззонател) Внодение нов. ix элеионто& и снячей iif ЗБОЛ-МО pea ;-130L.1; определение р-ц -н; ров графа пгг ;. -

На чертеже приведена функциональная схема предлагаемого устройства.

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

Блок 1 синхронизации обеспечивает формирование сигналов уровня 1 на зле- менты и блоки устройства в соответствии с реализуемым алгоритмом р-центров. Позицией 9 обозначен вход для задания числа р. позицией 10 - вход пуска усфойства позицией 11 управляющий вход бпока, позици- ми 12 и 13 - управляющие выходы, позициями 14 ipynna выходов (, М,м).

Блок 2 определения кра чайшего пути рогистрирует исполнение вершим графа м

|ч.)рмирует сигнал уровня 1 при И ..полне п;1и всех вершин графа На схеме мпо.наче ны вход 15 начальной усглнов:--.и бпока. it/уппы информационных входов 17,, ,п и РЫХОД 16 признака исполнения всех вершин графа.

Блок 3 задания матрицы смежности предназначен для задания топологии и ве (х-в дуг исследуемого графа. По информационным входам 18ij, .n задаются веса дуг, выходы 19i. i;-i,n сигнализируют об ис-юл- нении 1-й вершины графа.

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

Бпок 5 сравнения при поступленмп на

, правллющий вход сигнала cpai4:iHBi ;ei сигналы, поступающие на орвый и второй информационные входы (в аналог опой или . iHCKpe tiow форме) и формирует на информационном в i-IX оде сигнал уровня 1, если ::пг|:з,- чз ,ч runor-i и нФормацион но м входе (.-ri/u.i/ie, чем на первом

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

Перед началом работы, по входу 9 в блок 1 синхронилации вводится значение р, а по входам 18i|, i.,n блока 3 - значения весов ду исследуемого (рзфа, в элемент б памя- . и предельно допустимое большое значение. Работа устропсгва начинается подачей чтлпупьса на вход 10 пуг.ка устройства. При ;I OM блок 1 синхронизации формирует последовательность cHTHdnoB уровня 1,пре- .кую временной диаграммой его пяботь. и . гнал пояйллется на первом уп; .Л 1Ю ;0:; ВЫХОДИ I . )СуЩеСТВЛЯвТ уСТЭ

новку в исходное нулевое состояние время- импульсного интегрирующего преобразппа- теля 4, а через вход 15 - начальную подготовку блока 2 определения кратчайшего пути. По завершении этих операций сигнал с я-иода 1 снимается и формируется ); .ровня 1 на втором управляющем 3 и р выходах группы выходив 14|. I п. .. (.ь:ходз сигнал поступает HJ вход аремя-импульсного интегрирующе- гг ппеобр ппателя 4. который начинает вырабатывать линейно возрастающий сигнал, поступающий на первый информационный вход блока 5 сравнения и информационный вход элемен га В памяти. С соответствующих выходов групп выходов 14i, М,п сигналы поступают на пходы 17| блока 2, входы 19i блока 3 и информационные входы регистра 7. В блоке 2 фиксируется исполнение вершин графа, соответствующих р входам 17| с единичным сигналом, а в блоке 3 моделируется определение кратчайших путей от вершин, соответствующих входам 19i с единичным сигналом, до остальных n-р вершин, соответствующих входам 19i с нулевым сигналом. По мере моделирования в блоке 3 достижения вершин графа сигналы уровмл 1 формируются на соответствующих выходах 19i блока, откуда они поступают на входы 1 блока 2. Через время, достаточное для моделирования достижения всех вершин исследуемого графа fjnox 2 ф( Ог трует сигнал уровня 1 на выходе 1 б, который поступает на управляющий вход 11 блок,-; i синхронизации и управляющий вход блс;;э 5 сравнения, При этом снимается сигнал с второго управляющего выхода 13 блока 1 прекращается изменение сигнала на выходе преобразователя 4, а в блоке сравнения осуществляется сравнение сигналов, поступающих на первый и второй информационные в: оды с. выход преобра зователя и элемента памяти соответственно. Если сигнал на первом входе меньше или равен сигналу на втором входе, то на выходе схемы 5 формируется импульс уровня 1 , поступающий на входы записи элемента 5 памяти и регистра 7. При этом в элемент 6 памяти вносится сигнал, пропорциональный кратчайшему расстоянию до вершины, наиболее удаленной от заданного на данном шаге набора вершин графа, а в регистре 7 фиксируется ход, соответствующий данному набору. Через время, необходимое для сравнения и возможностей перезаписи содержимого элемента 6 памяти и регистра 7. снимаются сигналы с соответствующих выходов 14 и формируется сигнал на выходе 12. Вновь осуществляется подготовка блока 2 и возврат в нулевое состояние преобразователя 4, по завершении которых формируется сигнал на выходе 13 и следующем наборе из р выходов группы вы- одов 14|. ,п.

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

При вводе по входу 9 блока , предлагаемое устройство обеспечивает определение 1-центра графа, как и известное устройство.

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

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

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

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

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

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

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

Изобретение предназначено для решения задач определения р-центров неориентированных графов, являющихся математическими моделями широкого класблок синхронизации 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 со Ю