Устройство для определения экстремальных путей на ориентированных графах

Устройство для определения экстремальных путей на ориентированных графах

Иллюстрации

Показать все

Реферат

 

643900

:cy источника питания. Кроме того, управляющий сигнал переводит триггер

9 в единичное состояние и открывает ключ 10.

Второй импульс частоты f формирует импульсный сигнал на выходе 25, который устанавливает двоичный счетчик 13 в исходное йоложение.

Третий импульс частоты f формирует импульсный сигнал на выходе 26, который возбуждает формирователь импульсов 5, в результате,чего пос- ледний формирует стандартный импульс опроса. Импульс опроса подается на вершину Хо модели графа. В результате работы элементов дуг модели графа с выходных цепей оптронов 3 (дуг

ХоХ1.ХоХ5,."Хб,Х,) будут сниматься импульсы и поступать через элемент

ИЛИ 12 и ключ 10 на вход двоичного счетчика 13 ° Поскольку минусовой потенциал подключен в данный момент к вершине Х> модели графа, то на выходных цепях оптронов 3 остальных

Дуг (X7 Хе, Х Хе, Xz Хе, Хе Х Хе Х4 > Х Х4,XzX4 импульсы сниматься не будут . В результате на вход двоичного счетчика

13 придет система импульсов и двоичный счетчик 13 зафиксирует эти импульсы. На основании .информации, поступающей по третьему входу блока управления, блок управлення формиру-: ет импульсный сигнал на выходе 27, триггер 17 переходит в нулевое состо-. яние и единичным сигналом на выходе открывает блок переключения 14, который подключает к работе блок регистрации 15 ключ 18 при этом за-. кроется. Блок регистрации 15 фиксйрует двоичный код на выходе двоичного счетчика 13, отражающий оценку события в вершине графа Х по максимуму и затем формирует сигнал, который переводит триггер 17 в единичное состояние. Триггер 17 открывает ключ

18. На этом .заканчивается первый цикл работы. Первый же импульс частоты переводит блок управления 6 в исходное положение. Второй и последующие импульсы частоты f начинают выполнять второй цикл работы, который аналогичен первому циклу, При втором и последующих циклах работы определяются оценки событий по максимуму в остальных вершинах модели графа. Как только блок 7 окажется переведенным на определение оценки События в .последней вершине модели графа, сформируется постоянный сигнал, который закроет ключ 16, в работе устройства"после зафикснрования последней оценки события произойдет останов. Для повторения замера событий в вершинах модели графа по максимуму необходимо последовательно выдать команды Исходное, Пуск .

Для оценки событий в вершинах модели графа по минимум необходимо переключатель 8 перевести в положение, при котором к выходу блока 7 подключается нулевой вход триггера 9.

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

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

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

40 ключа, второй выход второго блока переключения соединен с первым входом второго ключа, второй вход которого подключен к выходу блока регистрации, один вход которого соединен с первым выходом второго триггера и одним входом первого блока переклю45 чения, другие входы блока регистрации соединены с выходами первого блока, переключения, выход второго ключа подключен к единичному входу второго триггера, нулевой вход кото50 рого соединен с первым выходом блока управления, единичный выход второго триггера подключен к управляющему входу третьего ключа, выход которого соединен с первым входом блока управ5g. ëåíèè, второй выход которого подклю- чен к управляющему входу двоичного счетчика, третий выход блока управления соединен с первым входом второго блока переключения и с единичным входом первого триггера, единичный выход которого подключен к управляющему входу первого ключа, третий вход

85 блока управления соединен с выходом