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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК О А О 4 С 06 Р 1 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ 1 САН Н АВТОРСКОМУ СВ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО ДЕРЕВА ГРАФА(57) Изобретение относится к области вычислительной техники и можетбыть использовано при решении наизвещенных графах задач нахожденияоптимального дерева, Целью изобретения является повышение быстродействия устройства. Устройство содержит1251100 модули 1 ветвей графа. на чертежепоказан случай наличия у графа четырех ветвей), коммутатор 2, блок 3управления, генератор 4 импульсов,формирователь 5 импульсов. Каждая модель ветви графа содержит коммутаторб, сумматор 7 по модулю два, счетИзобретение относится к вычислительной технике и может быть исполь " зовано при решении на взвешенных графах задач нахождения оптимального дерева. 5Целью изобретения является повышение быстродействия устройства,Функциональная схема устройства для определения оптимального дерева графа приведена на чертеже.10Устройство содержит модели 1 ветвей графа например четыре, коммутатор 2, блок 3 управления, генератор 4 импульсов и формирователь 5 импульсов. Каждая модель 1 ветви5 графа содержит коммутатор 6, сумма" тор 7 по модулю два, счетчик 8, формирователь 9 импульсов, ключ 10 и элемент 11 индикации, Блок 3 управления содержит регистр 12 сдвига, де 20 шифратор 13, счетчик 14 и элемент ИЛИ 15, Входные и выходные полюса каждой модели ветви обозначены цифрами 16-21.Устройство для определения оптимального дерева графа работает следующим образом.Первоначально обнуляются сумматор 7 и регистр 12, в счетчик 14 заносится количество импульсов К-С+1, где К - емкость счетчика; С - число вершин графа (в котором дерево образует Светвей); в каждый счетчик 8 заносится количество импульсов, равное К-В, (В, - вес 35 х-й ветви) при определении минимального дерева и равное В; при определении дерева максимального веса. При поступлении пускового сигна ла на вход устройства генератор 4 начинает выдавать импульсы, которые через второй выход коммутатора 2 и чик 8, формирователь 9 импульсов,ключ 10, элемент 11 индикации, Блокуправления содержит регистр 12 сдвига, дешифратор 13, счетчик 14, элемент ИЛИ 15, Входные и выходные полюса каждой модели ветви обозначеныцифрами 16-21 соответственно. 1 ил. полюса 17 моделей ветвей, инцидентных первой вершине графа, поступаютна первые входы соответствующих сумматоров 7. На вторые входы сумматоров импульсы не поступают, поэтому свыходов сумматоров 7 импульсы проходят на счетный вход счетчика 8, Припереполнении счетчика 8 модели ветви,имеющей наименьший вес (в данном случае рассматривается нахождение дерева минимального веса, в счетчиках 8занесены количества импульсов К-В 1,),сигнал переполнения с его выхода поступает, во-первых, через полюс 18на соответствующий выход устройстваи тем самым идентифицирует ветвь, вошедшую в формируемое минимальное де"рево, во-вторых, на управляющий входкоммутатора б, который соединяет свойинформационный вход с выходом,в-третьих, на входы формирователя 9импульсов, который, в свою очередь,выдает импульс на информационный входключа 1 О и соответствующие входы регистра 12 (который запоминает единицу в ячейке памяти) и дешифратора 13. При наличии на всех входахдешифратора 3 только одного единичного сигнала он выдает сигнал по первому выходу на установочный входрегистра 12, который обнуляетсяина вход. элемента ИЛИ 15. С выхода злеэлемента ИЛИ 15 сигнал поступает насчетный вход счетчика 14, которыйувеличивает свои показания на 1, и наустановочные входы счетчиков 8 всехмоделей ветвей. В результате всесчетчики 8, которые начали счет им"пульсов, сбрасываются в исходное состояние К-В;, за исключением переполнившихся счетчиков 8, которые остаются в состоянии переполнения до концаработы устройства. С выхода счетчи 3 1251ка 14 на управляющие входы ключей 10 поступает нулевой сигнал, позтому выданные формирователями 9 импульсов сигналы на выходы кЛючей 10 не проходят. Интервал следования импуль. сов с выхода генератора 4 выбирается таким, чтобы вышеуказанные процессы, обусловленные переполнением какого-либо счетчика 8 при поступлении 1-го импульса генератора 4, закончились. к моменту поступления (1+1)-го импульса,При дальнейшей работе устройства импульсы с второго выхода коммутатора 2 проходят на первые входы сумма торов 7 не только моделей ветвей, ин цндентных первой вершине, но и Моделей ветвей, полюса 17, которых соединены с вторым выходом коммутатора 2 через коичутаторы 6, соединившие сноиВ информационные входы и выходы при поступлении сигналов на их управляющие входы Коммутатор 6 обеспечиваетдвухстороннее прохождение сигналов не только с информационного входа иа ф 5 выход, но и наоборот тогда выход его становится информационным входом). В ходе работы устройства по иере переполнения счетчиков 8 в Формирующее ся дерево включаются все новые и 30 новые ветви кроме ветвей, образующих циклы так как в таких ветвях импульсы поступают на оба входа сумматора 7 и, следовательно, на вход счетчика 8 не проходят, 33Рслн ветви в дерево включаются по одной, то после отсчета С"1 импуль сов счетчиком 14 он выдает сигнал переполнения, который поступает на вход останона генератора 4 прекращая ра боту устройства, и на управляющие входы ключей 10, которые соединяют свои информационные входы с выходами. В результате импульс, выданный формирователем 9 импульсов модели ветви, включенной в дерево графа последней, проходит на вход элемента 11 индикации, который идентифицирует эту нетвь и одновременно сигнализм" рует об окончании работы устройства Ветви оптимального дерева опрадаля ют по наличию потенциалов парапол" кения счетчиков на сООТВЕтетнувщИМ выходах устройства.В случае переполнения одновремен 1 но двух (или более) ечатчикоэ 8 е вы ходов еоответствующего числа формнро вателей 9 импульсов сигналы доступа" 100 4ют на информационные входы регистра 12, который запоминает соответствующее число единиц в ячейках памяти, и на входы дешифратора 13. При наличии на входах более одного еди- нияного сигнала дешифратор 13 выдает сигнал по второму выходу на вход формирователя 5 импульсов, который вьщаетимпульс на управляющий вход коммутатора 2, и последний переключает свой. информационный вход на первый выход. В результате импульсы генератора 4 проходят на вход сдвига регистра 12, поочередно онрашивают его ячейки и считывают на выход соответствующее число единиц.Единичные сигналы с выхода регист- ра 12 через второй вход элемента ИЛИ 15 проходят, во-первых, на счетный вход счетчика 14, который увели" чивает свои показания на соответствующее число единиц, во-вторвк, йа установочные входы счетчикой 8, кото" рые ло первому сигналу сбраеычаютея в исходное состояние Е-В, за исключением пареполнивщихся счетчиков) . Длительность импульса, выдаваемого Формирователем 5 юаульсов, выби рается такой, чтобы импульсы ганаратора 4 опросили всэ ячайкн регистра 12, По окончании импульса на уп-, равляющем входа коммутатор 2 вновь соединяат свой информационный вход с вторым выходом н работа устройства продолжаатея. Еелн а процесса ечнтыаання адн" ниц нэ регистра 12 лронаовло паралолнанна счетчика 14, то енгнал нарэлол нанна поступаетна управляющие входы ключей 10 н Открывает нм, э раэул тата ю 63 ульеы эеэм фофинфцватэлэй 9 нилулэсоа иодалай ветвей, включен ныж э дерево нь лоелэднеи Вага фабО ты устройства, лромедят череэ кювчн 10 на вмоды элаиэнтов 1 1 ннднма ЦНН) КОТОРЫЭ ННДНЦНРУВТ ЭТН ВЕТВН Н этни Онгмалнэмруат О налнчнн в РРафе двум (нлн 6 Олее иннниальным девевь эв кЩЦОэ нэ моторным Обфаеевайе ватвяин вмлвченавн в дереве де неещ ладмеге щага рабеты уетвейетва 1 н Маадей Одней ветвьв нэ чнеда ветвей включенным на дееледнеи щаге 1 Суииар= Йый вее вптниальнОРО д 1 ева иеФет бить Ояределем еуиинвеваниеи вееев ветвей вейедюнн в де=РЕВО1251100 Составитель Т.СапуноваРедактор И.Рыбченко Техред М.Ходанич Корректор С,Черни Заказ 4413/47 Тираж б 71ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, М 5 Подписное Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4 Формула изобретения Устройство для определения оптимального дерева графа, содержащее группу моделей ветвей графа, соединенных согласно топологии исследуемого графа, генератор импульсов, формирователь импульсов, блок управления, содержащий счетчик, каждая модель ветви графа также содержит счетчик, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены коммутатор, в блок управления введены регистр сдви" 15 га, дешифратор, элемент ИЛИ, в каждую модель ветви графа введены коммутатор, сумматор по модулю два формирователь импульсов, элемент индикации, вход запуска генератора импуль сов является входом запуска устрой- ства, а выход генератора импульсов подключен к информационному входу коммутатора, управляющий вход котоРого подключен к выходу формирова теля импульсов, первый выход коммутатора подключен к входу сдвига регистра сдвига, выход которого подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ и установочный вход регистра сдвига объединеныподключены к входу формирователя импульсов, выход элемента ИЛИ подключен к счетному входу счетчика блока управления и к установочным входам счетчиков моделей ветвей графа, выход счетчика блока управления подключен к входу останова генератора импульсов и к управляющим входам ключей моделей ветвей графа, второй выход коммутатора подключен к первым входам сумматоров по модулю два моде-, лей ветвей графа., инцидентных первой вершине графа, информационный вхсд и выход коммутатора каждой модели ветви графа подключены соответственно к первбму и второму входам сумматора по модулю два, выход которого подключен к счетному входу счетчика модели ветви графа выход счетчика модели ветви графа подключен к управляюще/му входу коммутатора модели ветви графа, к входу формирователя импульсов модели ветви графа и является соответствующим выходом устройства, вы- ход формирователя импульсов модели ветви графа через ключ подключен к входу элемента индикации, информационные входь 1 регистра сдвига соединены с одноименными входами дешифратора и подключены к выходам формирователей импульсов соответствующих моделей ветвей графа.