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

(51) 5 6 06 Г 15/4 ГССУДАРСТВЕН 11 ЫИ КОМИТЕТГ 10 ИЗОБРЕ ТЕ НИЯМ И О КРЫТИЯГРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИК АВТОРСКОМУ СВИДЕТЕЛЪСТВУ г - О - - О -- ОГ /дц 1 дО,(56) Авторское свидетельство СССРМ 1348850, кл, 6 06 Е 15/20, 1986.Авторское свидетельство СССРМ 1559354, кл, С 06 Г 15/20, 1988(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯПАРАМЕТРОВ ГРАФА(57) Изобретение предназначено для решения задач определения р-центров неориентированных графов, являющих;яматематическими моделями широкого класса прикладных задач оптимизации размещения различного рода пунктов обслуживания, баз снабжения, аварийных служб и т.п. Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, время- импульсный интегрирующий преобразователь 4, элемент памяти 6, регистр 7 и блок 5 сравнения. Работа устройства основана на аппаратно реализованном перебопе всех сочетаний из и по р(р - число вершин графа) и определении сочетания. для которого . личина рас"тояния до наиболее удаленной от них вершины минимальна. Этим достига. ется расширение функциональньвозможностей за счет определения р-центров рафа. 1 ил.Изобретение относится к вычцслцтельной тРхнцка и манет быть использовано для решения задач определения р-цегровеориепирсвэнных рэфое. являощихся маге,"лэтическлми моделмц широкого класса задач Оптимзль 3010 размещеия различного родэ пунктов обслужиеанля аварийных сл,жб баз ".3 збхе ля ц т,п,11 э ее.но у;т рслст вэ для,сследоезнл уьй е т)зфе, содержащеезддцагонзль1н)10 тцэтрцу из; - ,и - 1) Оделел дуГ (ичисло вершц 3 П)афз) дверу пьлеменое/1, ГруППу ЛЕИЕНтое НГ, дВЕ труЫ СЧЕтЧ 3хан, группу ре 1 гров и -пупу схем с.па 3)ия.у )ройсО с 110 лвзе Г гтрсде 1 нц.13111: ОЕ 3 ЦИХ МЗ,"С 1;ЛЬОМ1 1 . 1: и:. Ь 4 КЕГ Он 10 СПС)ЛЬЗОВЗк1/я Я 1)еделеицентров графа,11 ЗлбОЛЕЕ бЛ ЗХИМ ПрЕДЛЗГаЕМОМу яеся у:,трои,во для цсследовэ ия парэ, спреде/,ен 110 р центс)ов при р1,Цель цзобре-,еия - расширение фу 3слонзгььх еозможтостей эа сче) определения 1 центров графов.Сущность 1 эобретения заклочается втс м ч Го в , стролс 3 во, содеркащее блок эзця матрицы с.кностц, блск опред ения крат зйшего пути, блок сихроиээ;я сто бл кэ регистрации времеи исн,н,:,ь.1 )ер 31 н и блгн а выбора млицвв- дены время ;,гульснй ин) егриру.13 .и преобр.зона)ель, схема сравненияэ е; нт памя)л и реистр при ам цформаЦИОННЫЕ ЯХОДЫ РЕЦ: )З ЛОЕДИНЕНЫ; .Ы/.;эи/ппь Р)ф )г б:3 кз синх.с 1,:".,3т)хскл зз;31 си рс: стра 0.1,:,едне 3 с. Я Г.ЭЗИСЦ ЭЛЕМЕН З ОЗМЯГЦ И СОЕДИЕС, Н.формаионным выходом схемы сравнения/чрзвляющий эход хо) Ороц обье/т Р/1р)вляогцл со/0 л блтч,з,:,инхро 3 л заццц ис едеенсыкодом чллэн,ка исгюлнеияесгх вершин блока )ределенит крзтчай, е.ГО ПУТИ, ПЕРчЫИ ИНФОПМаЦЛПНЬЦ,Х ЭД С 0МЫ СРаВНСНЛЯ гСЕДИНРН С;:ЫХОДОМреобразоезтс/3,)оро 3 с инфо рл-циоИм в 11 холоь лчс 3 1, я)и, входО .т)ого Годк 1 о с к эьхду 33 обр,зс)зте/;Введение /х з/3 с 3;тое ц ся м и:зьо/)цо реал)зз предленв р 3 иров рафа пг На чертеже приведена функццоальнэяСЕМа ПРЕДЛатаЕМОО УС) РОйСтез.устрйство содержит блок 1 синг )Ониэз,иц блок 2 определения кратчзйш. о пут блс 1: 3 задания матрицы смеж ости, е 1. Ямя-импульсный интегрирующий 1 реобрззозз) ель 4, блок 5 сравнения, злеент 6 пэмт.ц, и разрядный регистр 7 (о число 1)ер 3)тн исследуемоо графа) и разде:тельны диОды 81=-1,пБлок 1 синхронизации обесе цвэетФормирование сигналов уровня "1" на элеенть и блоки устройства в соответствю с реа/3 тзуР 11,л алгоритмом р-центров, Позицией 9 обозачен вход для задания ц.ла р, озицлей 11) - вход пуска усройства позицие 3 11 упрэеляощий вход блока, по)ицли 12 и 13 управляющие выходы.. эцц ями 14 руппа выходов(ч,1-1,) 2 3 Б ок 2 определения крачзйшего пути)сГстрирует исполнение вершиграфа и форлцрует сц нэл уровя 1" прл и, полне : и всех нерлц 3рафа Нэхеле боззче ы вх)д 15 начальной уст/)нос.ц блока, т.,уппы ифсрмационных входов 17,1=1,п и Якход 16 признака исгюлненця всех вершин графаБлох 3 задания магрн,ы смежнссти3 ЕДНЭЭЗЧЕН ДЛЯ ЭдДдНИЯ ТОГОЛОГИИ И Ве е Д,/Г л:,: сД) емОГО ГРзфд, 1 О иФОРмзци снньм в содам 181,1,).-1,п задаотсс еесз Дуг, выходы 19, 1 1,п сигнализируют об ис о/1- ен и 1-й вершины графа.Бределя-лмпульсный ин Гегрлруюцийгреобрзэс ватель 4 вьрэба) ываег сц нал 313 эпряжение или 1 Од), сели 133 э котпргГО роп 011 иональнз ццтРльнос Ги и;"/ьсэ ,3 ВХОДЕ ЗЗГ 1" Скд.БЛОК 5 СР;Е 1 РИЯ Г:Г)л и; Т 1/ПЛЕНЦ 11 НЗуп анляющий вход сигнала спая ц)РРслг.1/1/ы, пос/упзющие на е;ереый и второи 31 формаццо,ые входы 1 в аналсч олои ило , л:крР ной форме) ц формирует нэ инфор, гщцоное, ходе сигнал уровня "1", если 1 г з, э )3)031 цнформэционом входеЬ./31, е, ч.м; а гервомУстройстес рзботзет следуощим ОбраПеред ачзлом работы, по входу 9 в блок13 ги, ронц зции вводтся значение р, а по входам 1 д 1,1-1,п блока- значеия весов д, цсс/едуемого рафа, в элемент 6 пзмя,и пр;дельо допустимое большое значение Работа устройс на начинается подачей 55 3,3 ульса з влод 10 пука устройства При: м блок 1 сих 1/О иэзции формирует по- Г/)едонтте 3 Ость си нзлов уровня "1", пред с,лотр уо временной диаграммой его рзботькгнал появляется на первом уп; з30,с выходе 1: существляет уста 1705839овку в исходное нулевое состояние время,мпульсного интегрирующего преобраэплагеля 4, а через вход 15 - начальную подготовку блока 2 определения кратэйшего ПутИ, ПО Э",ВЕрШЕИИ ЭТИХ ОПЕрацИй СИГ нал с я,хода 12 онилается и формируется. овн 1" на втором управляющем в . 3 и р выходах группы выходв 14 к --. хода 1," сигнал поступает н . вход з г 1 етая импульсного интегрирующе г преобр зэлателя 4, который начинает вырабэтываь ли ейно возрастающий сигнал, пос 1 упающий на первый информационный вход блока 5 сравнения и информационный вход элемен га 6 памяти, С соответствующих 15 выходов групгн выходов 14, 1 - -1,п сигналы поступают на входы 17 блока 2, входы 19 блока 3 и инфор ационные входы регистра 7. Р блоке 2 фиксируется исполнение вершин графа, соответствующих р входам 17 с 20 едини ным сигналом, а в блоке 3 моделируется определение кратчайших путей от вершин, соответствующих входам 19 с единичным сигналом, до остальных и-р вершин, соответствующих входам 19 с нуле вым сигналом. По мере моделирования в блоке 3 достиженя вершин графа сигналы уровня "1":,ормируется на соотве.ствующих выходах 19 блока. откуда они поступаот на входы 17 блока 2. Через время, 30 ДОСтатО НОЕ ДЛЯ МОДЕЛИРОВаНИЯ ДОСтИжЕ- ния всех ьершин исследуемого граФа блок 2 ф ок" 1 рует сигнэл уговня "1" на выходе 16, которь и Оступает на управляюций вход 11 блока 1 синх )оиэаии и управляющий 35 вход блока 5 сравнения При этом :нимается сигнал с дторого управляюшео выхода 13 блока 1 рекращастся изменение сигнала на выходе преобразователя 4, а в блок ".сравнения осуществляется соавнение сиг налов, погтупающи на перв лй и второй информац;:О,ье в; ОдыВыход прсобра зователя и злелента памяти соответсвенно, Если сигнал на первом входе меньше или равен сигналу на втором входе, то на 45 выходе схемы 5 формируется импульс уровня "1 , поступающий на входы записи элементапамяти и регистра 1, При этом в эле;лент б памяти вносится сигнал, пропорциональный кратчайшему расстоянию до 50 вершины, наиболее удаленной от заданного на данном шаге набора вершин графа, а в регистре 7 фиксируется ход, соответствующий данному набору. Через время, необходимое для сравнения и возможностей 55 перезаписи содержимого элемента б памяти и регистра 7. снимаются сигналы с соответствующих выходов 14 и формируется сигнал на выходе 12, Вновь осуществляется подготовка блока 2 и возврат в нулевое состояние преобразователя 4, по завершении которых формируется сигнал на выходе 13 и следующем наборе из р выходов группы выодов 14;. 1=1,п,Далее работа устройства повторяется до полного перебора всех сочетаний иэ и по р. По окончанию работы номера вершин, соотве", ствующих р-центру рафа, однозначно определены номерами разрядов регистра 7 с единичным содержанием, а величина, пропорциональная кратчайшему расстоянию от данных вершин графа до вершины, наиболее удаленной от них, записана в элементе б памяти,При вводе по входу 9 блока 1 р=1, предлагаемое устройство обеспечивает определение 1-центра графа, как и известное устройство,Таким образом, введение новых элементов и связей позволяет за конечное число шагов определять р-центры графа как при р=1, так и при р 1. Это свидетельствует о существенном расширении функциональных воэможностей по сравнению с известным устройством. Кроме того, предлагаемое устройство существенно проще известного, так как содержит меньше на (и) элементов памяти. а вместо и-входового блока выбора минимума содержит схему сравнения с двумя информационными входамиФормула изобретенияУсгройство для спределения пэрямЕтров графа, содержаее блол юхронизации, блок определения рат:яннего пути, блок задэния матрицы смежности и время- импульсьй интегрирующий преобразователь, причем выходы группы блока синхронизации через разделительные диоды подключены к соответствующим входам опроса блока задания матрицы смежности и блока опредегеля кратчайшего пути, первый выход блока синхронизации подключен к входу возврата в нулевое состояние время-импульсного интегрирующего преобразователя и входу возврата в исходное состояние блока определения кратчайшего пути, второй выход блока синхронизации подключен к входу запуска время-импульсного интегрирующего преобразователя, выход признака исполнения всех вершин блока определения кратчайшего пути подключен к управляющему входу блока синхронизации,отличаю щеес я тем,что,с целью расширения функциональных воэможностей устройства эа сче 1 определения р-центров графа, в него введсны элемент памяти, регистр и блок сравнения, выход которого подключен к входам признаков за1705839 Составитель О, АлексеевРедактор Л. Пчолинская Техред М,Моргентал Корректор Т Патай Заказ 195 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 писи элемента памяти и регистра, разряды информационного входа регистра подключены к соответствующим выходам группы блока синхронизации, первый информационный вход блока сравнения подключен к входу элемента памяти и выходу время-импульсного интегрирующего преобразователя, второй информационный вход блока сравнения подключен к выходу элемента памяти, управляющий вход блока сравнения - 5 к выходу признака исполнения всех вершинблока определения кратчайшего пути.