Устройство для определения экстремальных путей в графе

Союз СоветскихСоциалистическихреспублик ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВЙДЕТЕЛЬСТВУ(6 ) Дополннтельное к авт. свил-ву(22)Заявлено 26.10,76(2) 2414862/18-24,(5 )М. Кл. Я 06 Р 15/36 с присоелкнениент заявки 1 теГесудзрстеенный еинтет СССР не делам нзебретеннй н еткрытнй(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ В ГРА Изобретение относится к области вычислительной техники и может.быть использовано при проектировании сети связи в графе.Известно устройство для определения характеристик связности графа, содержащее элемент И, запоминающие триггеры вершин и ветвей, управляемые ключевые схемы, схему отображения графа1.Недостатком етого устройства является то, что оно позволяет проводить сравнение и выбор различных сетей связи только по такому критерию, как связность графа. Этот критерий характеризует нижнюю границу на максимум числа узлов (ветвей), разьединяющих пути между любой парой узлов. Использование атого устройства для выбора надежной сети связи в большинстве случаев ограничено.Наиболее близким по технической сут 1; ности к рассматриваемому является ус- . тройство, содержащее блок формирования топологии, входы которого подключены к выходам блока управления первый и вто рой выходы которого соединены соответственно с первым и вторым входами первого коммутатора, группа входов которого подключена к выходам блока формирования тогологии, один выход первого ком 3мутатора соединен со входом блока управления, другие выходы первого коммутатора подключены ко входам функционального преобразователя, выход которого соединен с первым входом триггера,товыход которого подключен к третьемуЪходу первого коммутатору 123.Основным недостатком указанного устройства является низкая точность.Целью изобретения является повыше 15ние точности устройства,Это достигается тем, что в устройствовведены регистры, второй и третий коммутаторы, распределители, счетчики и бло 20ки сравнения, один выход первого из которых соединен со вторым входом триггера,а другой выход первого блока сравнениясоединен с одним входом распределителя,другие входы которого подключены сьотз 693ветственно к иь",ходам первого коммутащщтора, выходы первого распределителя черезрегистры соединены соответственно с"информационными входами второго и третьВыход блока 12 сравнения подключен квходу распределителя 7, управляющийвход которого соединен с четвертым выходом блока управления 1, а выходы подключены к входам счетчиков 13.Устройство работает следующим образом,О По сигналам, поступающим с управляющих выходов блока 1 управления, вблоке 2 формирования топологии заполняется матрица смежности, которая однозначнозадает сеть связи между уз 15 лами. При этом ,", выходов блока 2 формирования топологии, соответствующихсуществующим ветвям, через коммутатор3 поступают сигналы на входы функционального преобразователя 4, который реа-,2 О лизует функцию проводимости междувходным ивыходным узлом. По сигналус первого управляющего выхода блока 1управления в коммутаторе 3 устанавливается значение Го ( п = Л., 2, п )- число прерываемых ветвей. По сигналусо второго управляющего выхода блока 1управления коммутатор 3 прерывает Гтсигналов, поступающих от блока 2 формирования топологии на функциональныйпреобразователь 4 в различных комбинациях. При нарушении условия проводимости с выхода функционального преобразователя 4 поступает сигнал на единич-ный вход триггера 5, который устанавливается в состоянии 1 и подает сигнална третьи управляющие входы коммутаторов 3 и 9. При этом выключается коммутатор и на его выходе фиксируетсяразделяющий набор сигналов, Коммутатор 9 последовательно подключает выходы регистров 8 ко входу блока сравнения 11. Если в результате сравненияоказывается, что ни один из наборов, записанных ранее в регистрах при меньшихзначенияхГР, не поглощает набора, зафиксированного на выходахкоммутатора 1,3, то с первого выхода блока 11 сравнения подается сигнал на управляющийвход распределителя 6 и данный разделяющий набор записывается в соответствующий регистр. После сравнения подается сигнал со второго выхода блока11 сравнения на нулевой вход триггера5, который устанавливается в состояние55 дд и"О" и вновь включает коммутатор 3 вработу. После завершения перебора комбинаций сигналов при данном го выключается коммутатор 3 а с его выхода по распределители 6, 7, л регистров 8, комму его коммутаторов, выход второго комму- татора подключен к одному входу первого блока сравнения, другие входы первого блока сравнения соединены с выходами первого коммутатора, управляющий вход второго коммутатора подключен к выходу триггера, третий и четвертый выходы блока управления соединены соот- ветственно с управлявшими входами третьего коммутатора и второго распределителя, выходы которого подключены ко входам счетчиков, выходы второго коммутатора соединены со входами второго блока сравнения, выход которого подключен к информационному входу второго раснределителч.функциональная схема устройства пред= ставлена на чертеже. Устройство содержит блок 1 управления, блок 2 формирования топологии, коммутатор 3, функциональный преобразователь 4, триггер 5,татары 9, 10, блоки 11, 12 сравнения, г счетчиков 13. Рабочие выходы блока 1 управления подключены к соответствующим входам блока 2 формирования тсъпологии, выходы которого через коммутатор 3 подключены к соответствующим входам функционального преобразователя 4, выход которого соединен с единичным входом триггера 5. Первые два управляюцгих входа коммутатора 3 соединены с соответствующими выходами блока 11 управления, третий управляющий вход блока 3 соединен с единичным выходом триггера 5, а выход подключен к входу блока управления 1. Одноименные входы распределителя 6 и блока 11 сраь- нения обьединены и с единены с соответствующйми выходами коммутатора 3. Второй выход блока 11 сравнения подсоединен к нулевому входу триггера 5, апервых выход подсоединен к управляющему входу распределителя 6, выходыкоторого соединены со входами соответствующих регистров 8. Выходы этих регистрог ггопсоединены к соответствующимвходам коммутатора 9. Единичный выходтриггера 5 подсоединен к управляющемувходу коммутатора 9, выход которогоподключен к входу блока 11 сравнения Выходы регистров 8 подсоединены к вхо,дам коммутатора 10, управляющий вход;которого подсоешгген к третьему выходу блока управления 1, а выходы подсоединены к входам блока 12 сравнения.(6дается сигнал на вход блока 1 управле,ния. При этом по сигналу с третьего вы;хода блока 1 управления распределитель7 подключает соответствующий счетчик13 к выходу блока сравнения 12. Посигйалу с четвертого выхода блока 3., упгравления коммутатор 10 подключает выходы регистров 8, в которых записаныразделяющие наборы сигналов при данном гп ко входам блока 12 сравнения,В,блоке 12 сравнения разделяющие наборысравниваются друг с другом, На выходеблока 12 сравнения появляется сигнал,если сравниваемые разделяющие наборыперекрываются. Количество перекрывающихся разделяющих наборов подсчитыва, ется в соответствующем счетчике 13.После подсчета количества перекрываюшихся разделяющих наборов при данномгп сигнал с первого выхода блока 1 упранпения увеличивает в коммутаторе 3значение гп на единицу. Начйнается работа устройства при новом значении щПосле перебора всех значений гп по .программе блока 1 управления в блок 2 фор 2мирования топологии записывается новаяматрица смежности. Далее работа устройства происходит описанным выше образом,По завершении программы в блоке 1 управления в счетчиках 13 фиксируется ко 3личество перекрывающихся разделяющихнаборов для всех щ относительно каждой сети. Максимально надежной сетьюявляется та, для которой числа перекрывающихся разделяющих наборов минималь 3ны для всех значений гп,Устройство отличается более высокойточностью по сравнению с известнымиустройствами, благодаря введению новых4элементов и связей между ними. Формула изобретения Устройство для определения экстремальных путей в графе, содержащее блок формирования топологИи, входы которого подключены к выходам блока управления,91868 6первый и второй выходы которого соеди нены соответственно с первым и вторым входами первого коммутатора, группа входов которого подключена к, выходам блока формирования топологии, один выход первого коммутатора соединен со входом блока управления, другие входы первого коммутатора подключены к входам функционального преобразователя, выход ко О торого соединен с первым входом три- гера, выход которого подключен к третьему входу первого коммутатора, о т л и - чающееся тем, что, с цельюповышения точности, и него введены регистры, второй и третий коммутаторы, распределители, счетчики и блоки сравнения, один выход первого из которых соединен со вторым входом триггера, а другой выход первого блока сравнения соединен с одним ,входом, распределителя, другие входы которого подключены соответственно к выходам первого коммутатора, выходы первого распределителя через регистры соединены соответствено с информационными входами второго и третьего коммутаторов выход второго коммутатора подключен к одному входу первого блока сравнения, другие входы первого блока сравнения соединены с выходами первого коммутатора, управляющий вход второго коммутатора подключен к выходу триггера, третий и четвертый выходы блока управления, соединены соответственно с управляющими входами третьего коммутатора и второго распределителя выходы которого подключены ко входам счетчиков, выходы второго коммутатора соединены со входами второго блока сравнения, выход которого подключен к информационному входу второго распределителя. Источники информации,принятые во внимание при экспертизе 45 1, Авторское свидетельство СССР Мо 468244, кл. 6 06 Р 15/36, 1971. 2, Авторское свидетельство Мо 486322 кл. 6 06 Б 15/36, 1972 50 прототип).691868 оставитель Л. ГорскаяО, Андрейко Корректор Н, Степ Редактор С. Т лиал ППП фПатент", г. Ужг л. Проектная, 4 каз 6218/40 Тираж 780 Подписное ЦНИИПИ Государственного комитета ССС по делам изобретений и открытий 113035, Москва, К, Раушская наб., д.