Устройство для определения оптимального дерева связности графа Советский патент 1988 года по МПК G06G7/122 

(О CZ

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

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

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

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

Устройство содер/юит блок 1 заедания исходного веса ветвей, блок 2 выбора максимального сигнала, блок 3 моделей ветвей, кнопочные выключатели 4, и 4j и ключи 5, - 54. Блок 1 содер кит потенциометры 6,-6, Блок 2 содержит операционные усилители , первуЕО и вторую группы разделительных диодов и, 9f-9 соответственно, резисторы обратной связи, масштаб- ные резисторы . и ключи , Блок 3 содержит модели ветвей 13-5 каждая из KOtopbix включает триггер 14, сумматор 15 по модулю два, ключ 16 и индикатор 17. Работа устройства основана на определении из ветвей множестваэ соответствующего данному шагу решения, Э6ТВИ с экстремальным BecoMj необра I ззпощей циклов с ветвями, включенными I в оптимальньй подграф на предшествующих шагах решения, i Перед решением потенциометрами I 6,-6 задаются напряжения, пропорцио- нальные весам ветвей моделируемого графа при определении дерева связное- .ти максимального веса или пропорциональные величинам, обратным весам ветвей, при определении дерева связности минимального веса. , Решение начинается нажатием кнопоч ного выключателя 4, При этом напря- .жение от шины питания поступает на вторые входы моделей ветвей 13 и - 13j, инцидентных первой вершине графа, а далее на первые входы сумматоров 15 по модулю два этих моделей :ветвей. С выходов сумматоров сигналы уровня логической единицы поступают :на управляющие входы ключей 5, и 5 соответственно. Напряжения с потен циометров 6,62 через информационную депь ключей 5 , 5 поступают на масштабные резисторы 11,, llj операционных усилителей 7, , 7 , ив блоке 2 (Осуществляется выбор максимального Мз этих сигналов. Такэ.если определя- (тся дерево связности максимального

0

веса (веса ветвей приведены в скобках рядом с цифрами, обозначающими номера ветвей, на фиг.1), замыкается ин- .J формационная цепь ключа 12„ и напряжение от шины питания поступает через нее на единичный вход триггера 14 модели ветви 13, Триггер переходит в единичное состояние. Снимается

10 сигнал уровня логической единицы с входа индикатора5 погасание которого сигнализирует о включении первой ветви в решение „ С прямого выхода, триггера сигнал поступает на управляющий

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

Дальнейшая работа устройства аналогична ранее рассмотренному первому шагу и по окончании решения отпуска0 ется кнопочный выключатель, В блоке 3 при этом не горят индикаторы моделей ветвей, соответствующих ветвям, образующим максимальное дерево связности графа,

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

0 входы триггеров 14 всех моделей ветвей, обеспечивая возврат в нулевое состояние тех триггеров, которые перешли в единичное состояние в процессе решения. О возврате схемы в исход5 ное состояние сигнализируют индикаторы моделей ветвей.

Таким образом, устройство обеспечивает эа (п-1) шагов определение Оптимальных деревьев связности линейных неориентированных графов (п - количество вершин моделируемого графа), Время ка кдого шага решения + -ftp ,где t - время срабатывания ключей, t - время переключения тригге-

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

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

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

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

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

3(7)

.™К

с4-з

Фиг. 2