Устройство для определения экстремальных путей в графе
Союз Советских
Социалистических республик
ОПИСЛНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВЙДЕТЕЛЬСТВУ
С» 06 Р 15/З6 с присоелкнениент заявки ИГесудерстеенный неинтет СССР не делам нзебретеннй н еткрытнй (23) Приоритет— Опубликовано 15.10.79„бюллетень J% ä8 Дата опубликования описания 20,10.79 (53) УЛК 681.3 33 (088.8 ) (72) Автор изобретения В. H. Червяцов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ В ГРАФЕ Изобретение относится к области вычислительной техники и может- быть использовано при проектировании сети связи в графе. Известно устройство для определения характеристик связности графа, содержа3 щее элемент И, запоминающие триггеры вершин и ветвей, управляемые ключевые схемы, схему отображения графа (1). Недостатком етого устройства является 1О то, что оно позволяет проводить сравнение и выбор различных сетей связи только по такому критерию, как связность графа. Этот критерий характеризует нижнюю границу на максимум числа узлов 15 (ветвей), разьединяющих пути между любой парой узлов. Использование атого устройства для выбора надежной сети связи в большинстве случаев ограничено. Наиболее близким по технической сут1;ности к рассматриваемому является устройство, содержащее блок формирования топологии, входы которого подключены к выходам блока управления, первый и вто 2 рой выходы которого соединены соответственно с первым и вторым входами пер вого коммутатора, группа входов которог.o подключена к выходам блока формирования тогологии, один выход первого коммутатора соединен со входом блока управления, другие выходы первого коммутатора подключены ко входам функционального преобразователя, выход которого соединен с первым входом триггера, выход которого подключен к третьему Ъходу первого коммутатора l23Основным недостатком указанного устройства является низкая точность. Целью изобретения является повышение точности устройства. Это достигается тем, что в устройство введены регистры, второй и третий коммутаторы, распределители, счетчики и бп ъки сравнения, один выход первого из кото рых соединен со вторым входом триггера, а другой выход первого блока сравнения соединен с одним входом распределителя, другие входы которого подключены сьотз 693 BeтственнО к выходам первого коммута тора, выходы первого распределителя через регистры соединены соответственно с информационными входами второго и третьВыход блока 12 сравнения подключен к входу распределителя 7, управляющий вход которого соединен с четвертым выходом блока управления 1, а выходы подключены к входам счетчиков 13. Устройство работает следующим образом, 0 По сигналам, поступающим с управляющих выходов блока 1 управления, в блоке 2 формирования топологии заполняется матрица смежности, которая однозначно . задает сеть связи между уз15 лами. При этом,", выходов блока 2 формирования топологии, соответствующих существующим ветвям, через коммутатор 3 поступают сигналы на входы функционального преобразователя 4, который реа-, 2О mayer функцию проводимости между входным ивыходным узлом. По сигналу с первого управляющего выхода блока 1 управления в коммутаторе 3 устанавливается значение rn(m= Л., 2, ..., п)число прерываемых ветвей. По сигналу со второго управляющего выхода блока 1 управления коммутатор 3 прерывает rn сигналов, поступающих от блока 2 формирования топологии на функциональный преобразователь 4 в различных комбинациях. При нарушении условия проводимости с выхода функционального преобразователя 4 поступает сигнал на единич- ный вход триггера 5, который устанавливается в состоянии 1 и подает сигнал на третьи управляющие входы коммутаторов 3 и 9. При этом выключается коммутатор и на его выходе фиксируется разделяющий набор сигналов. Коммута40 тор 9 последовательно подключает выходы регистров 8 ко входу блока сравнения 11. Если s результате сравнения оказывается, что ни один из наборов, записанных ранее в регистрах при меньших значенияхго, не поглощает набора, зафиксированного на выходах коммутаторами .3, то с первого выхода блока 11 сравнения подается сигнал на управляющий вход распределителя 6 и данный разделяющий набор записывается в соответствующий регистр. После сравнения подается сигнал со второго BbIxoaa блока 11сравнения на нулевой вход,триггера 5,.который устанавливается в состояние "О" и вновь включает коммутатор 3 в работу. После завершения перебора комбинаций сигналов при данном гг выключается коммутатор 3„ а с его выхода поего коммутаторов, выход второго коммутатора подключен к одному входу первого блока сравнения, другие входы первого блока сравнения соединены с выходами первого коммутатора, управляющий вход второго коммутатора подключен к выходу триггера, третий и четвертый выходы блока управления соединены соот»ветственно с управляющими входами третьего коммутатора и второго распределителя, выходы которого подключены ко входам счетчиков, выходы второго ком мутатора соединены со входами второго блока сравнения, выход которого подключен к информационному входу второго расцределителч. Функциональная схема устройства пред= ставлена на чертеже. Устройство содержит блок 1управления, блок 2 формирования топологии, коммутатор 3, функциональный преобразователь 4, триггер 5, распределители6, 7, р регистров 8, комму татары 9, 10, блоки 11, 12 сравнения, счетчиков 13. Рабочие выходы блока 1 управления подключены к соответствующим входам блока 2 формирования тсъпологии, выходы которого через коммутатор 3 подключены к соответствующим входам функционального преобразователя 4, выход которого соединен с единичным входом триггера 5. Первые два управ ляющих входа коммутатора 3 соединены с соогветствующими выходами блока 1 1 управления, третий управляющий вход блока 3 соединен с единичным выходом триггера 5, а выход подключен к входу блока управления 1. Одноименные входы распределителя 6 и блока 1 1 сраь- нения обьединены и с единены с соответствующйми выходами коммутатора 3. Второй выход блока 11 сравнения подсоединен к нулевому входу триггера 5, а первых выход подсоединен к управляющему входу распределителя 6, выходы которого соединены со входами соответ ствуюших регистров 8. Выходы этих регистрог подсоединены к соответствующим входам коммутатора 9, Единичный выход триггера 5 подсоединен к управляющему входу коммутатора 9, выход которого подключен к входу блока 11 сравнения„ Выходы регистров 8 подсоединены к вхо,дам коммутатора 10, управляющий вход ;которого подсоешьчен к третьему выхо ду блока управления 1, а выходы подсоединены к входам блока 12 сравнения. ???.Ъ - — - -- - «:««Ю -: ., - «- .- « «.«,=«: ««-":.. -« I (6 дается сигнал на вход блока 1управле, ния. При этом по сигналу с третьего вы; хода блока 1 управления распределитель 7 подключает соответствующий счетчик 13 к выходу блока сравнения 12. По сигйалу с четвертого выхода блока 1, уп равления коммутатор 10 подключает выходы регистров 8, в которых записаны разделяющие наборы сигналов при данном гп ко входам блока 12 сравнения.В» блоке 12 сравнения разделяющие наборы сравниваются друг с другом. На выходе блока 12 сравнения появляется сигнал, если сравниваемые разделяющие наборы перекрываются. Количество перекрывающихся разделяющих наборов подсчитыва, ется в соответствующем счетчике 13. После подсчета количества перекрываю« шихся разделяющих наборов при данном гдсигнал с первого выхода блока 1 упран- пения увеличивает в коммутаторе 3 значение rn на единицу. Начйнается работа устройства при новом значении щ После перебора всех значений гд по прог рамме блока 1 управления в блок2 фор2 мирования топологии записывается новая матрица смежности. Лалее работа устройства происходит описанным выше образом. По завершении программы в блоке 1 управления в счетчиках 13 фиксируется ко3 ли чество пере кры ваюшихся разделяю1цих наборов для всех m относительно каждой сети. Максимально надежной сетью является та, для которой числа перекрывающихся разделяющих наборов минимальз ны для всех значений гп . Устройство отличается более высокой точностью по сравнению с известными устройствами, благодаря введению новых 4 элементов и связей между ними. Формула изобретения Устройство для определения экстремальных путей в графе, содержащее блок формирования топологИи, входы которого подключены к выходам блока управления, 91868 6 первый и второй выходы которого соеди нены соответственно с первым и вторым входами первого коммутатора, группа входов которого подключена к. выходам блс ка формирования топологии, один Bbfgog первого коммутатора соединен со входом блока управления, другие входы первого коммутатора подключены к входам функционального преобразователя, выход ко10 торого соединен с первым входом три гера, выход которого подключен к третьему входу первого коммутатора, о т л и— чающееся тем, что, с цельюповышения точности, и него введены регистры, второй и третий коммутаторы, распределители, счетчики и блоки сравнения, один выход первого из которых соединен со вторым входом триггера, а другой выход первого блока сравнения соединен с одним,входом, распределителя, apyr re входы которого подключены соответственно к выходам первого коммутатора, выходы первого распределителя через регистры соединены соответствено с информационными входами второго и третьего коммутаторов, выход второго коммутатора подключен к одному входу первого блока сравнения, другие входы первого блока сравнения соединены с выходами первого коммутатора, управляющий вход второго коммутатора подключен к выходу триггера, третий и четвертый выходы блока управления соединены соответственно с управляю ними входами третьего коммутатора и второго распределителя, выходы которого подключены ко входам счетчиков, выходы второго коммутатора соединены со входами второго блока сравнения, выход которого подключен к информационному входу второго распределителя. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР N 468244, кл. G 06 Р 15/36, 1971. 2. Авторское свидетельство No 486322, кл. 6 06 Р 15/36, 1972 50 прототип). 691868 Составитель Л. Горская Редактор С. Равва Техред О. Андрейко Корректор H. Степ Заказ 6218/40 . Тираж 780 Подписное ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, ?К-35, Раушская наб., д. 4/5 Филиал ППП Патент", г. Ужгород, ул. Проектная, 4
