Устройство для определения экстремальных путей на ориентированных графах Советский патент 1979 года по МПК G06G7/122 

ча/ второй вход которого поднлючен к выходу блока регистрации, один вхо которого соединен с первым выходом второго триггера, и одним.входом пер вого блока переключения, другие вход блока регистрации соединены с выхода ми первого блока переключения, выход второго ключа подключен кединичному входу второго триггера, нулевой вход которого соединен с первым выходом блока управления, единичный выход второго триггера подключен к управля щему входу третьего ключа, выход которого соединен с первым входом блока управления, второй выход которого подключен к управляющему входу двоич ногб счётчика, третий выход блока управления соединен с,первым входом второго блока переключения и с единичным входом первого триггера, единичный выход которого hoдключeн к управляющему входу первого ключа, третий вход блока управления соединен с выходом первого ключа, четвертый, выход блок управления соединен со входом формирователя импульсов, выход которого подключен ко входу блока задания конфигурации ориентированных Зграфов, первый вход устройства соединен со вторым входом;вто.рого блока переключения, со вторым входом-блокауправления, с единичным входом второго триггера и с нулевым входом первого триггера, второй вход устройства подключен к единичному входу второго триггера, третий вход устройства соединен с информационным входом третьего ключа. Описываемое устройство представле но на чертеже. Оно состоит из блока задания конфигурации ориентированного графа 1, состоящего из формирователей импульсов 2, оптронов 3 и лиНИИ задержки 4, формирователя импуль сов 5, блока управления6 ,: второго блокапереключения-7, переключателя 8, первоготриггера 9.,первого ключа 10, диода- 11, элe 4eнтa ИЛИ 12, двоичного сгетчика 13, первого блока переключения 14, блока р.егистрации 15, второго ключа 16, второго, тригге раl7, третьего, клича 18, -диодов 19, 20, 21. : -:-: Выходн 22 блока задания конфигурации ориентированного: графа 1 соеди нены со входами блока 7, первый которого соединен со входом пере ключателя 8. Первыййыход пёреключателя 8 соединен с .источииком питаНИН, второй его выход - с нулевым входом первого триггера 9; выходы 23 блока задании конфигурации ориентированного графа 1 через эл.емент ИЛИ 12 и ключ 10 соединены со счетным входом двоичного счетчика 13, выходы которого через первый блок переключе ния 14 соединены со.входами блока регистрации 15 Второй выход второго блока переключения 7 соединен с управляющим входом второго,ключа 16, выход блока регистрации 15 через второй ключ 16 и диод 21 соединен с ничным входом второго триггера 17, единичный выход которого соединен с управляющим входом третьего ключа 18. Выход 24 блокауправления 6 соединен с первым В54ОДОМ блока 7 и ничным входом первого триггера 9 единичный выход которого соединен с управляющим входом первого ключа 10, выход которого подключен к третьему входу блока управления, выход 25 блока -управления 6 соединен с управляющим вх одом двоичного счетчика 13; выход 26 блока управления 6 через формирователь импульсов 5 соединен со входом блока задания конфигурации ориентированного графа- 1; выход 27 блока управления 6 через диод 20 соединен нулевым входом второго триггера 17,нулевой выход которого соединен с управляющими входами первого блока переключения 14 и блока регистрации 15. Вход 28 устройства соединен с первым входом блока управления 6, со вторым входом блока 7, а также через диоды 19 и 11 соответственно соединен с нулевыми вводами триггеров 17 и 9; вход 29 устройства соединен с единичным входом триггера 17, вход 30 устройства через третий ключ 18 соединен со вторым входом блока управления. Устройство работает следующим образом. В блоке задания конфигурации ориентированного графа 1 устройства по ориентированному графу формируется модель графа. При этом каждая Х.,- Х; дуга (ветвь) графа набирается из последовательно включенных элементов 2,3,4. Направленность (ориентированность) ветвей определяется светяишм.ся диодом входной цепи оптрона 3. Вершины Х.,,Х2,.. Xf, модели графа подключаются к ооответствунзщим входам 22, выходные цепи оптронов 3 подключаются к соответствующим выходам 23 и вершина Хд (начало проекта) - по входу блока 1. Переключатель 8 устанавливается в положение минус источника питания. Формируется команда Исходное по которой блок управления 6 и блок переключения устанавливаются в исходное положение, триггеры 9 и 17 переводятся в нулевое состояние . ключ 10 и ключ 18 закрываются. По команде Пуск триггер 17 переводится в единичное положение, ключ 16 открывается и первый же импульс частоты f поступает на вход блока управления 6. На выходе 24 блол ка уп5 авления б формируется импульсный сигнал, поступающий на вход бло ка 7, который срабатывает и подключает, например, вершину модели графа Xj через переключатель 8 к. мину:су источника питания. Кроме того, управляющий сигнал переводит тригге 9 в единичное состояние и открывает ключ 1О. Второй импульс частоты f формиру ет импульсный сигнал на выходе 25, который устанавлива ёт двоичный счет чик 13 в исходное положение. Третий импульс частоты :f формиру ет импульсный сигнал на выходе 26, которий возбуждает Iформирователь импульсов 5, в результате .чего последний формирует стандартный импуль опроса. Импульс опроса подается на вершину Хр модели графа. В реэуЪьта те работы элементов дуг модели графа с выходных цепей оптронов 3 (дуг ХоХ1,ХоХу,...Хд,Хз) будут сниматься им пульсы и поступать через элемент ИЛИ 12 и ключ 10на вход двоичного счетчика 13. Поскольку минусовой по тенциал подключен в данный момент к вершине Х модели графа, то на вы ход ньсс цепях оптронов 3 остальных дуг ( Х Х(,, Xg Х, Х Х, Xg Х, X6X,,XjX,X импульсы сниматься не будут. В результате на вход двоичного счетчика 13 придет система импульсов и двоичный счетчик 13 зафиксирует эти импульсы. На. основании информации, поступающей по третьему входу блока управления, блок управления формиру ет импульсный сигнал на выходе 27, триггер 17 переходит в нулевое состо яние и единичным сигналом на выходе открывает блок переключения 14, который подключает к работе блок регистрации 15; ключ 18 при этом за-г кроется. Блок регистрации 15 фиксирует двоичный код на выходе двоичного счетчика 13, отражаюрдий оценку события в вершине графа Х по максимуму и затем, формирует, сигнал, кото Шй переводит триггер 17 в единичное сЬстояниё. Триггер 17 открывает ключ 18. Наэтом заканчивается первый цикл работы. Первый же импулйс частоты f , переводит блок управления б в .исходное положение. Второй и последующие импульсы частоты f начинают выполнять второй цикл работы, КОТО1Ж1Й аналогичен первому циклу. При втором и последующих циклах работы определяются оценки событий по максимуму в остальных вершинах модели графа. Как только блок 7 окажется переведенным на определение оценки События в .последней вершине модели графа, сформируется постоянный сигнал, который закроет ключ 16, в работе устройства после зафиксирования последней оценки события произойдет останрв. Для повторения за--. мера событий в веришнах модели графа по максимуму необходимо последовател но выдать команды Исходное , Пуск . Для оценки событий в вершинах модели графа по минимуму необходимо пе 06 реключатель 8 перевести в положение, при котором к выходу блока 7 подключается нулевой вход триггера 9. Рассматриваемое устройство, благодаря введению новых элементов и связей между ними, обеспечивает возможность определения экстремальных путей по ориентированным графам. Формула изобретения Устройство для определения экстремальных путей на ориентированных графах, содержащее первый ключ, выход которого подключен к счетному входу двоичного счетчика, выходы которого соединены с информационными входами первого блока переключения, триггеры, переключатель, второй и третий ключи, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения экстремальных путей на ориентированных графах, в него введены блок управления, второй блок переключения, формирователь импульсов, блок регистрации, элемент ИЛИ и блок задания конфигурации ориентированных графов, выполненный в виде цепочек, соединенных согласно топологии исследуемого графа, каждая из которых состоит из последовательно соединенных формирователя импульсов, оптрона и линий задержки, причем выходы линий задержки соединены соответственно с группой входов второго блока переключения, первый выход которого через переключатель подключен к нулевому входу первого триггера, вторые выходы оптронов подключены ко входам элемента ИЛИ, выход которого соединен с информационньом входом первого ключа, второй выход второго блока переключения соединен с первым входом второго ключ.а, второй вход которого подключен к выходу блока регистрации, один вход которого соединен с первым выходом второго триггера и одним входом первого блока переключения, другие входы блока регистрации соединены с выходами первого блока.переключения, выход второго ключа.подключен к единичному входу второго триггера, нулевой вход которого соединен с первым выходом блока управления, единичный выход второго триггера подключен к управляющему входу третьего ключа, выход которого соединен с первым входом блока управления, второй выход которого подключен к управляющему входу двоичного счетчика, третий выход блока управления соединен с первым входом второго блока переключения и с единичным входом первого триггера, единичный выход которого подключен к управляющему входу первого клЬзча, третий вход блока управления соединен с выходом

первого ключа, четвертый вьрсод блока управленн соединен со входом формирователя импульсов, ВЕлход которого подключен ко входу блока задания конфигурации ориентированных графов, первый вход устройства соединен со вторым вх;одом второго блока переключения,, со вторым входом блока управления, с единичным входом второго триггера ис нулевым входом первого триггера, второй вход устройства

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

Источники информации, принятые во внимание при экспертизе

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

№ 424152, кЛ. G06 ,F 15/20, 28.02.72.

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

№ 305484, КЛ. G06 G 7/122, 28.09.71.