Устройство для определения оптимального дерева графа Советский патент 1986 года по МПК G06F15/173 

модули 1 всчтвей г рафа (на чертеже показан случай наличия у графа четырех ветвей), коммутатор 2, б-пок 3 управления, генератор 4 импульсов, формирователь 5 импульсов. Каждйя модель ветви графа содержит коммутатор 6. сумматор 7 по модулю два, счет

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

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

Функциональная схема устройства для определения оптимального дерева графа приведена на чертеже.

Устройство содержит модели 1 ветвей графа налример четыре , коммутатор 2, блок 3 управления, генератор 4 импульсов и формирователь 5 импульсов. Каждая модель 1 ветви графа содержит коммутатор 6, сумматор 7 по модулю два, счетчик 8, формирователь 9 импульсов, ключ 10 и элемент 11 индикации. Блок 3 управления содержит регистр 12 сдвига, дешифратор 13, счетчик 14 и элемент ИЛИ 15. Входные и выходные полюса каждой модели ветви обозначены цифрами 16-21.

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

Первоначально обнуляются сумматор 7 и регистр 12, в счетчик 14 заносится количество импульсов К-С+1, где К - емкость счетчика; С - число вершин графа (в котором дерево образует С-1 ветрей); в каждый счетчик 8 заносится количество импульсов, равное К-В; (В; - вес i-й ветви) при определении минимального дерева и равное Bj при определении дерева максимального веса.

«

При поступлении пускового сигна- ла на вход устройства генератор 4 нчинает выдавать импульсы, которые через второй выход коммутатора 2 и

чик 8, формирователь 9 импульсов, ключ 105, элемент 11 индикации. Блок управления содержит регистр 12 сдвига, дешифратор 13, счетчик 14, элемент 1ШИ 15, Входные и выходные полю, са каждой модели ветви обоз начены цифрами 16-21 соответственно. 1 ил.

5

5

0

0

полюса 17 моделей ветвей, инцидентных перйой вершине графа,, поступают на первые входы соответствующих сумматоров 7. На вторые входы сумматоров импульсы не поступают, поэтому с . выходов сумматоров 7 импульсы проходят на счетньй вход счетчика 8 При переполнении счетчика В модели ветви, имеющей наименьший вес (в данном случае рассматривается Нахождение дерева минимального веса, в счетчиках 8 занесены колич;ества импульсов K-Bj,) , сигнал переполнения с его выходи поступает, во-первых, через полюс 18 на соответствующий выход устройства и тем самым идентифицирует ветвь, вошедшую в формируемое минимальное-дерево, во-вторых, на управляющий вход коммутатора 6, который соединяет свой информационный вход с выходом, 8-третьюс, на входы формирователя 9 импульсов , который, в свою очередь-, выдает импульс на информационный вход ключа 10 и соответствующие входы регистра 12 (который запоминает единицу в ячейке памяти и деш1141рато- ра 13.- При наличии на всех входах дешифратора 13 то-лько одного единичного сигнала он выдает сигнал по первому выходу на установочный вход регистра 12, .который обнуляется,,и на вход.элемента ИЛИ 15. С выхода эле- элемента ИЛИ 15 сигнал поступает на счетный вход счетчика 14, который увеличивает свои показания на 1, и на установочные входы счетчиков.8 всех ноделей ветвей. В результате все счетчики 8, которые начали счет импульсов, сбрасываются в исходное состояние К-В(, за исключением переполнившихся счетчиков 8, которые остаются в состоянии переполнения до конца работы устройства. С выхода счетчи3125

ка 14 на управляющие входгл ключей 10 поступает нулевой сигнал, поэтому выданные формирователями 9 импульсов , сигналы на выходы ключей 10 не проходят. Интервал следования импуль- 5 сов с выхода генератора 4 выбирается таким, чтобы вьппеуказанные процессы, обусловленные переполнением какого-либо счетчика 8 при постзтленни j-ro импульса генератора А, закончи- Ю лись.к моменту поступления (j+l)-ro импульса.

При дальнейшей работе устройства импульсы с второго выхода коммутатора 2 проходят на первые входы сумма- 5 торов 7 не только моделей ветвей, ин- цидентных первой вершине, но и Моделей ветвей, полюса 17 которых соединены с вторым выходом коммутатора 2 через коммутаторы б, соединившие свои20 информационные входы и выходы при поступлении сигналов на их управляющие входы.. Коммутатор 6 обеспеш вает „ двухстороннее прохождение сигналов не только с информационного входа на 25 выход, но и наоборот (тогда выход его становится информационным входом), Б ходе работы устройства по мере переполнения счетчиков 8 в формирующееся дерево включаются все новые и 30 новые ветви, кроме ветвей, образующих циклы,, так как в таких ветвях импульсы поступают на оба входа сумматора,

7и, следовательно, на вход счетчика

8не проходят. 33

Если ветви в дерево включаются по одаой, то после отсчета С-1 юетуль сов счетчиком 14 он выдает сигнал переполнения, который поступает на зход рстанова генератора 4,.прекращая ра- 40 боту устройства, и яа управляюнрив входы кjnoчeй 10, которые соединяют свои информационные входы с выходами. В результате импульс, выданный формирователем 9 импульсов модели ,, ветви, включенной в дерево графа последней, прбходит ка цход элементе П индикации, которьй идентифицирует эту ветвь и одновременно снгналнан- рует об окончании работы устройства Ветви оптимального дереяа, опредалл- ют по наличию потенциалов первпоя- нения счетчиков на соответствующих выходах устройства.

В случае переполнения одноярем§1Н- §1 но двух (или более) ечетчикеш 8 е 1Ы- ходов еоответствующего числа формирв нагелей 9 импу/ibcoii енгнапы пеетупё1004

ют на информационные входы регистра 12, который запоминает соответствующее число единиц в ячейках памяти, и на входы дешифратора 13. При наличии на входах более одного еди- нияного сигнала дешифратор 13 выдает сигнал по второму выходу на вход формирователя 5 импульсов, который выдает 1импульс на управляющий вход Коммутатора 2, и последний переключает свой информационный вход на первый выход. В результате импульсы генератора 4 проходят на вход сдвига регистра 12, поочередно опрашивают его ячейки и считывают на выход соответствующее число единиц. Единичные сигналы с выхода регист- ра 12 через второй вход элемента ИЛИ 15 проходят, во-первых, на счетный вход счетчика 14, который увеличивает свои показания на соответствующее число единиц, во-вторых, на установочные входы счетчико ё 8, которые по первому сигналу сбрасываются в исходное состояние К-В; (эа исклю- чеиием переполнившихся счатчюсов), Длительность импульса, выдаваемого формирователем 5 импульсов, выбирается такой, чтобы импульсы генератора 4 опросили все ячейки регистра I2. По окончании и fflyльca не управляющем входе коммутатор 2 вновь соединяет свой информационной вход с вторым выходом и работа устройства продолжается.

Если процессе считывания едк- ниц И1 регистра 12 произошло переполнение счетчика U, те сигнал перепел иеиия поступает на управляющие вхеды ключей 10 и ИХ| В тате и тульсы всех форйир ватвлей 9 импульсев неделей ветвейi включенных в дерево на поелвдаем шаге рав§- ты устрейства преходят че𧧠кяв чн 10 на ахеда §ленентв8 П цнН| кетерые нндкцнруют 9ти вепн и 9Т1М еигналиэнруют е налнчни i графе двух (lutH белее) мшнмальшх дер@1Ь еВ| iiiaji ee т к§терых еЗрааенанв вет1ямН| вклкченмши i дереше да п@@« ледаегв вага раЗзты уетр§й ва} и Валдай вда@й ветеш т чн@ла i@T8@ft) вкпвчен1кв1 на пзелеккем 1дг@ 6у1«4ар №й §ве зп г1тальм@г@ gepeia изже быть еирёвелем еушнрзшаниём lefii i i@Eiit№ii i pesit

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

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

Редактор И.Рыбченко

Составитель Т.Сапунова .

Техред М.ХодашгчКорректор С.Черни .

Заказ 4413/47 Тираж 671Лодписное

ВНИИПИ Государственного ко митета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д, 4/5

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

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

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

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

Изобретение относится к области вычислительной техники и может быть использовано при решении на извешенных графах задач нахождения оптимального дерева. Целью изобретения является повышение быстродействия устройства. Устройство содержит ,fB -т... j2L,i е i (Л