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

(59 ГОСУДАРСТВЕННЫИ КОМИ ПО ДЕЛАМ ИЗОБРЕТЕНИЙ СССРРЫТИЙ ИСАНИЕ ИЗОБРЕТЕНИЯ СКОМУ С ЕЛЬС А(56) Авторское свидетельство СССРК 304604, кл, С 06 С 7/48, 1969,Проблемы распределения информации.Сборник. М,: Наука, 1974, с. 27-28.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДЕТЕР 1 ЯНИРОВАННЫХ ХАРАКТЕРИСТИК ГРАФА(57) Изобретение относится к областивычислительной техники и может бытьиспользовано в электронных моделирующих установках сетей связи для решения задач, возникающих при перераспределении потоков информации на узлахкоммутации. Целью изобретения является расширение функциональных возможностей за счет определения минимальныхсечений графа, Устройство содержитблок 1 перебора сочетаний, триггеры2, коммутаторы 3, элементы И 4, элемент ИЛИ 5, счетчик 6, регистры 7 и11, схему сравнения 8, блок 9 управления, блок 10 формирования топологииисследуемого графа. Устройство позволяет определять характеристики сетейсвязи. 2 ил.13040Изобретение относится к вычислительной технике и может быть использовано в электронных моделирующих установках сетей связи для решения задач, возникаюших при перераспределении потоков информации на узлах коммутации.Целью изобретения является расширение функциональных возможностей устройства за счет определения минимальных сечений графа,На фиг.1 представлена функциональная схема устройства; на фиг.2 - функциональная схема блока управления.Устройство содержит блок 1 пере бора сочетаний, который может представлять собой счетчик числа импульсов, триггеры 2 выбора ветвей, группу из и коммутаторов 3, группу элементов И. 4, многовходовый элемент 20 ИЛИ 5, счетчик 6 числа разорванных ветвей, первый регистр 7 памяти числа разорванных ветвей, схему 8 сравнения, блок 9 управления, блок 10 формирования топологии исследуемого 25 графа и второй регистр 11 памяти состояния ветвей.Выходы блока 1 перебора сочетаний соединены с входами триггеров 2 выбо ра ветвей, выходы которых подключены к управляющим входам коммутаторов 3, выходами подключенных к первым входам блока 10, Выходы элементов И через многовходовый элемент ИЛИ 535 подключены к первому входу счетчика 6 числа разорванных ветвей, второй вход которого соединен с первым выходом схемы 8 сравнения, К первым разрядным входам последней подключены первые выходы счетчика б числа разорванных ветвей и первые входы регистра 7 памяти числа разорванных ветвей, разрядные выходы которого подключены к вторым разрядным входам схемы 8 сравнения, третий вход которой соединен с вторым выходом блока 9 управления, Второй выход схемы 8 сравнения соединен с вторым входом регистра 7 памяти числа разорванных ветвей и с вторым входом регистра 11 памяти состояния ветвей, первые входы которого подключены к прямым выходам триггеров 2 выбора ветвей. Третий выход блока 9 управления подключен к первому входу блока 1 перебора сочетанийЧетвертый выход блока 9 управления подключен к второму входу блока 10 формирования топологии, выход ко 32торого соединен с первым входом блока 9 управления,Глок управления содержит элемент12 запрета, элементы И 13-15, элемент16 задержки, триггер 17, генератор18 одиночных импульсов, элементыИЛИ 19 и 20, регистр 21 сдвига, генератор 22 тактовых импульсов.Устройство рабс тает следующим образом.В исходном состоянии счетчик 6числа разорва. нных ветвей, регистр 11памяти и регистр 21 сдвига очищены,триггеры 2 выбора ветвей находятся внулевом состоянии, триггер 17 и всеячейки памяти регистра 7 памяти числаразорванных ветвей - в единичном, Вблоке 10 формирования топологии выходы коммутации соединены в соответствии с топологией сети. Четвертыйвыход блока 9 управления в блоке 10соединен с парой вершин, для которыхопределяется минимальное сечение. Генератор 22 тактовых импульсов вырабатывает импульсы с частотой 2 = 1/Т,причем= Т, где Т =+ 1 + Т ррвремя срабатывания схемы 8сравнения;- ремя срабатываниясчетчика 6; 1:- время срабатываниярегистра 7 памяти,1По сигналу запуска, который можетвводиться вручную, генератор 18 одиночных импульсов в блоке 9 управления вырабатывает импульс, которыйпроходит через элемент И 4, открытый по второму входу высоким потенциалом с единичного выхода триггера17, Импульс с выхода элемента И 14поступает на вход элемента 16 задержки, переводит триггер в нулевое состояние и через третий выход блока 9управления поступает на вход блока 1перебора сочетаний, на выходах которого появляется первая комбинация,Триггеры 2 выбора ветвей при этом устанавливаются в единичное состояние,если данная ветвь присутствует в испытании, и в нулевое - если нет. Высокие потенциалы на прямых выходахтриггеров 2 выбора ветвей открываюткоммутаторы 3, причем если коммутаторы 3 открыты, т,.е. есть электрическая связь между их выходами. Элемент1 б задержки задерживает импульс иавремя, большее или равное времениустановки комбинации и срабатывания 1коммутаторов 3, По истечении этоговремени на выходе элемента 16 задержки появляется импульс, который через четвертый выход блока 9 управления поступает по второму входу в блок 10 на одну из выбранных вершин. Если при данном наборе работающих ветвей имеется связность между выбранными вершинами, то посланный из блока 9 управления импульс сразу же появится на входе блока 9 управления, пройдя через блок 10 и открытые ком- фо мутаторы 3, Таким образом, будет открыт элемент И 13 и закрыт элемент 12 запрета и импульс с выхода элемента 16 задержки пройдет через открытый элемент И 13. Одновременно импульс, пришедший с входа блока 9 управления через элемент ИЛИ 20, переведет триггер 17 в единичное состояние. Импульс с выхода элемента И 13 через элемент ИЛИ 19 запустит генератор 18 одиноч ных импульсов. Последний вырабатывает импульс, который, пройдя через открытый элемент И 14, поступит на вход элемента 16 задержки, переведет триггер 17 в нулевое состояние, при котором элемент И 15 открыт по второму входу высоким потенциалом с инверсного выхода триггера 17, и этот же импульс через третий выход блока 9 управления поступит на вход блока 1 перебора сочетаний, который вьдаст очередную комбинацию ветвей. Триггеры 2 выбора ветвей и ключевые схемы 3 срабатывают аналогично описанному. Допустим, что при этой очередной комбинации ветвей связность между выбранными вершинами отсутствует. Импульс, вышедший, через определенное время из элемента 16 через четвертый выход блока 9 управления, поступает по второму входу в блок 1 О коммутации вершин. Так как связность между выбранными вершинами отсутствует, то на выходе блока 10 и, следовательно, .45 на входе блока 9 управления сигнал не появится, Поэтому импульс с выхода элемента 16 задержки пройдет через открытый элемент 12 запрета и элемент ИЛИ 19 и запустит генератор 18 одиноч.5 ных импульсов, который выработает импульс; Этот импульс с выхода генератора 18 единичных импульсов пройдет через открытый элемент И 15, поступит на вход регистра 21 сдвига и через элемент ИЛИ 20 переведет триггер 17 в исходное положение. Импульс, поступивший на вход регистра 21 сдвига, появляется последовательно на выходах 13040324регистра 21 сдвига с частотой Г, которую задает генератор 22 тактовыхимпульсов, Импульсы с выходов регистра 21 сдвига через первые входы блока 9управления поступают на вторые входыэлементов И 4. Через многовходовыйэлемент ИЛИ 5 импульсы,число которыхравно числу разорванных вершин, поступают в счетчик 6 числа разорванныхветвей, По окончании подсчета, те,при появлении импульса на п-м выходерегистра 21 сдвига, импульс с (и+1)- го выхода регистра 21 сдвига черезвторой выход блока 9 управления поступает на схему 8 сравнения. По этомусигналу в схеме З.сравнения производится поразрядное сравнение содержимого счетчика 6 числа разорванныхветвей и регистра 7 памяти числаразорванных ветвей, Если в счетчике6 числа разорванных ветвей записаночисло, равное или большее, чем в регистре 7 памяти числа разорванныхветвей, то со схемы 8 сравнения подается сигнал, который стирает содержимое счетчика 6 числа разорванных ветвей,. В последнем при этом записываются нули. Если же число, записанное в счетчике 6 числа разорванныхветвей, меньше, чем число, записанноев регистре 7 памяти числа разорванных ветвей, то схема 8 сравнения выдает сигнал в регистр 7 памяти числаразорванных ветвей, по которому содержимое счетчика 6 переписывается в регистр 7 памяти. Также схема 8 сравнения вьдает сигнал, по которомусчетчик 6 устанавливается в исходноесостояние. Одновременно по сигналуперезаписи, который подается такжена регистр 11 памяти состояния ветвей, в последний записывается состояние триггеров 2 выбора ветвей. Послезавершения этих операций на (и+2)-мвыходе регистра 21 сдвига появляетсяимпульс, который через элемент ИЛИ19 запускает генератор 18 одиночныхимпульсов.Аналогично описанному импульс свыхода генератора 18 одиночных импульсов через элемент И 14 и третийвыход блока 9 управления устанавливает очередную комбинацию в блоке 1перебора сочетаний. Далее устройствоработает аналогично описанному, После перебора всех сочетаний в регистре 7 памяти числа разорванных ветвейоказывается записанным минимальное13040 число ветвей, которое необходимо удалить, чтобы нарушить связность между выбранными вершинами, а в регистре 11 памяти состояния ветвей - номера ветвей минимального сечения.г Формула изобретенияУстройство для определения детерминированных характеристик графа, содержащее блок формирования топологии исследуемого графа, блок перебора сочетаний, группу из и коммутаторов, группу из триггеров, каждый -й выход (1=1, 2, ,и), блока перебора сочетаний подключен к входу установки в "1" .-го триггера группы, прямой выход которого подключен к управляющему входу -го коммутатора,. выход 1-го коммутатора группы подключен к входу 1-й вершины группы входом блока 20 формирования топологии исследуемого графа, выход -й вершины группы выходов блока формирования топологии исследуемого графа подключен к информационному входу -го коммутатора группы, о т л и ч а ю щ е е с я тем что, с целью расширения функциональных возможностей за счет определения минимальных сечений графа, в него введены группа из и элементов И, эле мент ИЛИ, счетчик, схема сравнения, два регистра памяти и блок управления, который содержит элемент запрета, первый ивторой элементы И, элемент задержки, триггер генератор одиночных 35 импульсов первый и второй элементы ИЛИ, регистр сдвига, генератор тактовых импульсов, причем первый вход первого элемента И соединен с выходом конечной вершины блока формирования топологии исследуемого графа, первыми входами элемента запрета и второго элемента ИЛИ блока управления, выход элемента задержки подключен к входу начальной вершины блока формирования топологии исследуемого графа, к вторым входам элемента запрета и первого элемента И блока управления, выход которого подключен к первому входу первого элемента ИЛИ блока управления 50У второй вход которого подключен к выходу элемента запрета, третий вход первого элемента ИЛИ блока управления 326подключен к выходу (и+2)-го разрядарегистра сдвига, выход каждого -горазряда которого подключен к первомувходу -го элемента И группы, второй вход которого подключен к инверсному выходу -го триггера группы, выход (и+1)-го разряда регистра сдвига подключен к входу разрешения сравнения схемы сравнения, вход синхронизации регистров сдвига. блока управления подключен к выходу генератора тактовых импульсов, вход сдвига регистра сдвига объединен с вторым входом второго элемента ИЛИ и подключен к выходу второго элемента И блока управления, выход первого элемента ИЛИ блока управления поцключен к входу запуска генератора одиночных импульсов блока управления, выход которого подключен к первым входам второго и третьего элементов И блока управления, второй вход третьего элемента И блока управления подключен к г.рямому выходу триггера блока упра.вления, инверсный выход которого подключен к второму входу второго элемента И блока управления, выход второго элемента ИЛИ блока управления подключен к входу установки в "1" триггера блока управления, вход установки в п 0 которого объединен с входом элемента задержки блока управления, с входом разрешения сравнения схемь 1 сравнения и подключен к выходу третьего элемента И блока управления, выход каждого -го элемента И группы подключен к 1-му входу элемента ИЛИ, выход которого подключен к счетному входу счетчика, группа разрядных выходов которого годключена к первой группе разрядных входов схемы сравнения и к группе информационных входоз первого регистра памяти, группа разрядных выходов которого подключена х второй группе разрядных входов схемы сравнения, выход "Больше" которой подключен к входу установки в "0 счетчика, а выход Меньше" подключен к входам разрешения перезаписи первого и второго регистров памяти, каждый -й выход группы разрядных входов которого подключен к прямому выходу ь-го триггера группы.1304032 Составитель Т.СапуноваТехред В. Кадар Корректор Н.Король Редактор А.Лежнина Заказ 1313/50 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Иосква, Ж, Раушская наб., д, 4/5