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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 4 С 06 С 7/122 ОПИСАНИЕ ИЗОБРЕТЕ ИГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОРСНОМУ СВИДЕТЕЛЬСТВ ТЛ) 3931386/24-24(56) Авторское свидетельство СССРУ 732898клС 06 С 7/122, 1980.Авторское свидетельство СССРУ 1372335, кл, С 06 С 7/122, 1985.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЖНИЯ ОПТМАЛЬНОГО ДЕРЕВА СВЯЗНОСТИ ГРАФА(57) Изобретение относится к вычистельной технике и моает быть испол ЯО 1411782 зовано для решения задач нахожденияоптимального дерева связности неориентированных графов. Цель изобретения - повышение быстродействия. Дляэтого в устройство введен второй кнопочный выключатель и в каздую модельветви триггер и сумматор по модулюдва. Устройство обеспечивает за конечное число шагов определение опты"мальных деревьев связности линейныхнеориентированных графов. При этомчисло шагов, решения, а значит, и время решения определяются только количеством вершин графа. 2 ил.Изобретение относится к вычислительной технике и может быть использонано для решения задач нахожденияоптимального дерева связности неориентиронанных графов,Цель изобретения - повышение быстродействия.На фиг.1 представлена топологичес кая схема устройства; на фиг,2 10Функциональная схема устройства,Устройство содержит блок 1 заданияисходного веса ветнейь блок 2 выборамаксимального сигнала, блок 3 моделейветвей, кнопочные выключатели 4 и 154 и ключи 5, - 54. Блок 1 содержитпотенциометры 6 -6 . Блок 2 содержитоперационные усилители 7, -7 ь первуюи вторую группы разделительных диодов8 -8, и 91-9 соответственно, резисторы 30 ь -10 обратной связи, масштабные резисторы 11-11 и ключи 12,-12.Блок 3 содержит модели ветвей 13, -13 каждая иэ которых включает триггер 14, сумматор 15 по модулю два,ключ 16 и индикатор 17,Работа устройства основана на определении из ветвей множества, соотнетствующего данному шагу решения,ветви с экстремальным весом, необра"зующей циклон с ветвями, включеннымив оптимальный подграф на предшестнующих шагах решения.Перед решением потенциометрами6, -64 задаются напряжения, пропорциональные весам ветвей моделируемогографа при определении дерева связнос,ти максимального веса или пропорциональные величинам, обратным весамветвей, при определении дерева связности минимального веса,Решение начинается нажатием кнопоч.ного выключателя 4. При этом напря.жение от шины питания поступает навторые входы моделей ветвей 13 и . - 513 ь инцидентных первой вершине граФа, а далее - на первые входы сумматоров 15 по модулю два этих моделейветвей. С выходов сумматоров сигналыуровня логической единицы поступаютна управляющие входы ключей 5, и 5соответственно. Напряжения с потенциометров 61 ь 6 через информационнуюцепь ключей 5 , 5 поступают на масшьтабные резисторы 11, 11 операцион:ных усилителей 7 , 7 , и в блоке 2ьОсуществляется выбор максимальногойз этих сигналов. Так, если определяФтся дерево связности максимального веса (неса ветвей приведены в скобках рядом с цифрами, обозначающими номера ветвей, на фиг,1), замыкается информационная цепь ключа 12 и напряжение от шины питания поступает через нее на единичный вход триггера 14 модели ветви 13. Триггер переходит н единичное состояние. Снимается сигнал уровня логической единицы с входа индикатора, погасание которого сигнализирует о включении первой ветви н решение. С прямого выхода триггера сигнал поступает на управляющий вход ключа 16 этой модели ветви, и информационная цепь ключа 16 шунтирует входы сумматора 15 по модулю дна. При этом снимается сигнал уровня логической единицы с выхода сумматора по модулю дна модели ветви 13 и с управляющего входа ключа 5 ь а напряжение от шины питания поступает через информационную цепь ключа 16 этой модели ветви на перный вход сумматора 15 по модулю дна модели ветви 13 ь.Дальнейшая работа устройства аналогична ранее рассмотренному первому шагу и по окончании решения отпускается кнопочный выключатель. В блоке 3 при этом не "горят" индикаторы мо,цепей ветвей, соответствующих ветвям, образующим максимальное дерево связности графа.Для возврата схемы в исходное состояние кратковременно нажимается кнопочный выключатель 4 . При этом импульс от шины питания через контакты выключателя 4 поступает на нулевые входы триггеров 14 всех моделей ветвей, обеспечивая возврат в нулевое состояние тех триггеров, которые перешли в единичное состояние в процессе решения. 0 возврате схемы в исходное состояние сигнализируют индикаторы моделей ветвей.Таким образом, устройство обеспечивает за (п) шагов определение Оптимальных деревьев связности линейных неориентированных графов (и - количество вершин моделируемого граФа), Время каждого шага решения Т=З+,+ +С ,где 1 - время срабатывания ключей, с - время переключения триггера;- время срабатывания схемы выбора максимального сигнала. Учитывая, что 1 г. и т имеют порядок нескольких наносекунд, устройство обеспечивает практически мгновенное реше4 1411182 ние реальных задач достаточно большого размера. Формула изобретения Устройство для определения оптимального дерева связности графа, еодержащее первый кнопочный выключатель, блок задания исходного веса ветвей, состоящий из потенциометров, одни выводы которых соединены с шиной поло жительного питающего напряжения, а другие выводы подключены к шине нулевого потенциала, блок выбора макси мального сигнала, состоящий из операционных усилителей, масштабных резисторов, ключей, резисторов обратной связи и двух групп разделительных диодов, и блок моделей ветвей, сое диненных согласно топологии моделируемого графа, каждая из которых содержит ключи и индикатор, в блоке выбора максимального сигнала выход каждого операционного усилителя через соот ,ветствующий разделительный диод первой группы соединен с управляющим входом одноименного ключа, а через соответствующий разделительный диод второй группы и одноименный резистор .обратной связи подключен к входу этого операционного усилителя, соединенному с первым выводом одноименного масштабного резистора, аноды раздели-. тельных диодов второй группы являются первыми выходными полюсами моделей ветвей, информационные входы ключей блока выбора максимального сигнала соединены с шиной положительного питающего напряжения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен второй кнопочный выключатель и в каждую модель ветви триггер и сумматор1 по модулю два, нулевые входы триггеров являются первыми входными полюсами моделей ветвей, в каждой модели ветви инверсный выход триггера соединен с входом индикатора, прямой выход триггера подключен к управляющему входу первого ключа, информационный вход которого соединен с первым входом сумматора по модулю два и является вторым входным полюсом модели ветви, вторым выходным полюсом которой является выход первого ключа, соединенный с вторым входом сумматора по модулю два, выход которого подключен к управляющему входу второго ключа, информационный вход которого соединен с средним выводом потенциометра, выход второго ключа подключен к второму выводу масштабного резистора, выводы ключей блока выбора максимального сигнала соединены с единичными входами соответствующих моделей ветвей, шина положительного питающего напряжения через первый и второй кнопочные выключатели подключена соответственно к первым и вторым входным полюсам моделей ветвей.1411182 оставитель И.Загорбинина ехред А.Кравчук К тор Э,Л Редактор Н,Лазаренко ков Заказ 3656/4 Тираж 704ИИПИ Государственного делам изобретений Москва, Ж, Раув одписно а СССР о открытииая наб., д, 4 по13035,улПроектная,Производственно-полиграфическое предприятие, г. Уж