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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задач нахождения оптимального дерева связности неориентированных графов. Цель изобретения - повышение быстродействия. Для этого в устройство введен второй кнопочный выключатель и в каждую модель ветви триггер и сумматор по мoдyJш два. Устройство обеспечивает за конечное число шагов определение оптимальных деревьев связности линейных неориентированных графов. При этом число шагов .реЁоения, а значит, и вре мя решения определяются только количеством вершин графа. 2 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

@ 4 G 06 С 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

3 »

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

721) 3931386/24-24 (22) 18.07.85 (46) 23.07.88. Бюл. У 27 (72) О.Г.Алексеев, В.Ю.Мершанов и Н.И.Ячкула (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 732898 ° кл. G 06 С 7/122, 1980.

Авторское свидетельство СССР

У 1372335, кл. С 06 С 7/122, 1985. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЖНИЯ ОПТИМАЛЬНОГО ДЕРЕВА СВЯЗНОСТИ ГРАФА (57) Изобретение относится к вычислительной технике и мокет быть исполь„„Я0„„1411782 А1 зовано для решения задач нахождения оптимального дерева связности неориентированных графов. Цель изобретения — повышение быстродействия. Для этого в устройство введен второй кнопочный выключатель и в кавдую модель ветви триггер и сумматор по модулю два. Устройство обеспечивает за конечное число шагов определение оптимальных деревьев связности линейных неориентированных графов. При этом число шагов. решения, а значит, и время решения определяются только количеством вершин графа. 2 ил.

1411782

Изобретение относится к вычислительной технике H может быть использовано для решения задач нахождения оптимального дерева связности неориен-5 тированных графов.

Цель изобретения — повышение быстродействия.

На фиг.1 представлена топологичес-. кая схема устройства; на фиг.2 10 функциональная схема устройства.

Устройство содержит блок 1 задания исходного веса ветвей, блок 2 выбора максимального сигнала, блок 3 моделей ветвей, кнопочные выключатели 4„ и

4> и ключи 5, — 54. Блок 1 содержит потенциометры 6< -6 . Блок 2 содержит операционные усилители 7, -7, первую и вторую группы разделительных диодов

8,-8 и. 91-9 соответственно, резис- 20 торы IO -10 обратной связи, масштабные резисторы l1„ — 11 и ключи 12,-12 .

Блок 3 содержит модели ветвей 13,—

13,, каждая иэ которых включает триггер 14, сумматор 15 по модулю два, ключ 16 и индикатор 17.

Работа устройства основана на определении из ветвей множества, соот( ветствующего данному шагу решения, ветви с экстремальным весом, необразующей циклов с ветвями, включенными ( в оптимальный подграф на предшествующих шагах решения. (Перед решением потенциометрами . 6, -64 задаются напряжения, пропорцио= 35 нальные весам ветвей моделируемого графа при определении дерева связнос,ти максимального веса или пропорциональные величинам, обратным весам

1 ветвей, нри определении дерева связ- 40 ности минимального веса.

Решение начинается нажатием кнопочного выключателя 4 . При этом напря.жение от шинн питания поступает на вторые входы моделей ветвей 13 и

13, инцидентных первой вершине графа, а далее — на первые входы сумматоров 15 по модулю два этих моделей ветвей. С выходов сумматоров сигналы уровня логической единицы поступают на управляющие входы ключей 5, и 5 соответственно. Напряжения с потенциометров 6,6 через информационную цепь ключей 5, 5 поступают на масшУ табные резисторы 11 „, 11 операцион:ных усилителей 7, 7, и в блоке 2 ь осуществляется выбор максимального йз этих сигналов. Так, если определяФтся дерево связности максимального веса (веса ветвей приведены в скобках рядом с цифрами, обозначающими номера ветвей, на фиг.1), замыкается информационная цепь ключа 12„ и напряжение от шины питания поступает через нее на единичный вход триггера 14 модели ветви 13 . Триггер переходит в единичное состояние. Снимается сигнал уровня логической единицы с входа индикатора, погасание которого сигнализирует о включении первой ветви в решение. С прямого выхода триггера сигнал поступает на управляющий вход ключа 16 этой модели ветви, и информационная цепь ключа 16 шунтирует входы сумматора 15 по модулю два.

При этом снимается сигнал уровня логической единицы с выхода сумматора15 по модулю два модели ветви 13 и с управляющего входа ключа 5<, а напряжение от шины питания поступает через информационную цепь ключа 16 этой модели ветви на первый вход сумматора 15 по модулю два модели ветви 13 .

Дальнейшая работа устройства аналогична ранее рассмотренному первому шагу и по окончании решения отпускается кнопочный выключатель. В блоке

3 при этом не "горят" индикаторы мо,цепей ветвей, соответствующих ветвям, образующим максимальное дерево связности графа.

Для возврата схемы в исходное состояние кратковременно нажимается кнопочный выключатель 4 . При этом импульс от шины питания через контакты

BbIKJH0÷àòåëÿ 4 поступает на нулевые входы триггеров 14 всех моделей ветвей, обеспечивая возврат в нулевое состояние тех триггеров, которые перешли в единичное состояние в процессе решения. 0 возврате схемы в исходное состояние сигнализируют индикаторы моделей ветвей.

Таким образом, устройство обеспечивает за (п-1) шагов определение оптимальных деревьев связности линейных неориентированных графов (и — количество вершин моделируемого графа), Время каждого шага решения T=3t +t +

+t,где t — время срабатывания ключей, с — время переключения триггера; t — время срабатывания схемы выбора максимального сигнала. Учитывая, что t t и t имеют порядок нескольких наносекунд, устройство обеспечивает практически мгновенное реше1411782

4. ние реальных задач достаточно большого размера.

Ф о р м у л а и з о б р е т е н и Я

Устройство для определения оптимального дерева связности графа, еодержащее первый кнопочный выключатель, блок задания исходного веса ветвей, состоящий из потенциометров, одни выводы которых соединены с шиной поло жительного питающего напряжения, а другие выводы подключены к шине нулевого потенциала, блок выбора макси- 15 мального сигнала, состоящий из операционных усилителей, масштабных резисторов, ключей, резисторов обратной связи и двух групп разделительных диодов, и блок моделей ветвей, сое- gg диненных согласно топологии моделируемого графа, каждая из которых содержит ключи и индикатор, в блоке выбора максимального сигнала выход каждого операционного усилителя через соот- 25 ,ветствующий разделительный диод первой группы соединен с управляющим входом одноименного ключа, а через соответствующий разделительный диод второй группы и одноименный резистор .обратной связи подключен к входу этого операционного усилителя, соединенному с первым выводом одноименного масштабного резистора, аноды раздели-. тельных диодов второй группы являются первыми выходными полюсами моделей ветвей, информационные входы ключей блока выбора максимального сигнала соединены с шиной положительного питающего напряжения, о т л H ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введен второй кнопочный выключатель и в каждую модель ветви триггер и сумматор

I по модулю два, нулевые входы триггеров являются первыми входными полюсами моделей ветвей, в каждой модели ветви инверсный выход триггера соединен с входом индикатора, прямой выход триггера подключен к управляющему входу первого ключа, информационный вход которого соединен с первым входом сумматора по модулю два и является вторым входным полюсом модели ветви, вторым выходным полюсом которой является выход первого ключа, соединенный с вторым входом сумматора по модулю два, выход которого подключен к управляющему входу второго ключа, информационный вход которого соединен с средним выводом потенциометра, выход второго ключа подключен к второму выводу масштабного резистора, выводы ключей блока выбора максимального сигнала соединены с единичными входами соответствующих моделей ветвей, шина положительного питающего напряжения через первый и второй кнопочные выключатели подключена соответственно к первым и вторым входным полюсам моделей ветвей. 1411782

Составитель И. Загорбинина

Редактор Н.Лазаренко Техред А.Кравчук Корректор Э.Лончакова

Заказ 3656/46

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4