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

(51) М, Кл,(22) Заявлено 01.0277 (21) 2447952/18-24 6 06 ц 7/122 с присоединением заявкиГосударствеиицй иомитет ссср ио аелам изобретеиий и открытий(23) Приоритет. Опубликовао 25.01.79 Боллетень3 Лата опубликования описания 2501,79(73) заявитель 54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕЙИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ОРИЕНТИРОВАННЫХ ГРАФАХаэанного устройства.ие возможности авто Изобретение относится к областицифровой вычислительной техники иможет быть применено при расчетах.транспортной сети, сетевых графиков,электрических сетей, тестов контролярелейных структур и т.п,Известно устройство тестовогоконтроля и , содержащее двоичныйсчетчик, реле, соединенные с наборнымполем, кольцевой счетчик, ключи, 10регистратор, логический элемент И, .триггеры,Недостатком устройства являетсяего относительная сложность и невозможность применения для анализа последовательностей импульсов, выражающих минимальное и максимальное числодуг между заданными вершинами ориенти.рованных графов.Наиболее близким по технической . фсущности к рассматриваемому являетсяустройство, содержащее первый ключ,выход которого подключен к счетномувходу двоичного счетчика, выходы ко.торого соединены с информационнымивходами первого блока переключения,триггеры, переключатель, второй итретий ключи 12.Недостатком укявляется отсутств матического анализа величин экстремальных путей на ориентированных графах.Целью изобретения является расши" рение функциональных возможностей устройства за счет определения экстремальных путей на ориентированных графах.Поставленная цель достигается тем, что в устройство введены блок управления, второй блок переключения, фбрмирователь импульсов, блок регистрации, элемент ИЛИ и блок задания конфигурации ориентированных графов, выполненный в виде цепочек, соединенных согласно топологии исследуемого графа, каждая иэ которых состоит из последовательно соединенных формирователя импульсов, оптрона и линий задержки, причем выходы линий задержки соединены соответственно с группой входов второго блока переключения, первый выход которого через переключатель подключен к нулевому входу первого триггера, вторые выходы оптронов подключены ко входам элемента ИЛИ, выход которого соединен с информационным входом первого ключа, второй выход второго блока переключения соединен с первым входом второго клю900 40 8 643 ча, второй вход которого подключен к выходу блока регистрации, один вход которого соединен с первым выходом второго триггера, и одним, входом первого блока переключения, другие входы блока регистрации соединены с выходами первого блока переключения, выход 5 второго ключа подключен к единичному входу второго триггера, нулевой вход которого соединен с первым выходом блока управления, единичный выход второго триггера подключен к управляющему входу третьего ключа, выход которого соединен с первым входом блока управления, второй выход которого подключен к управляющему входу двоичного счетчика, третий выход блока )5 управления соединен с первым входом второго блока переключения и с единичным входом первого триггера, единичный выход которого подключен к управляющему входу первого ключа, третий вход блока управления соединен с выходом первого ключа, четвертый выход блока управления соединен со входом формирователя импульсов, выход которого подключен ко входу блока задания конфигурации ориентированных графов, первый вход устройства соединен со вторым входомвто.рого блока переключения, со вторым входом блока управления, с единичным входомвторого триггера и с нулевым входом первого триггера, второй вход устройства пэдключен к единичному входу второго триггера, третий вход устройства соединен с информационным входом третьего ключа.35Описываемое устройство представле. но на чертеже. Оно состоит из блоказадания конфигурации ориентированного графа 1, состоящего иэ формирователей импульсов 2, оптронов 3 и линий задержки 4, формирователя импульсов 5, блока управления 6,:второгоблока переключения 7, Переключателя8, первого .триггера 9 первого ключа 10, диода 11, элемента ИЛИ 12,двоичного с.етчика 13, первого блока переключения 14, блока регистрации 15, второго клюЧа 16 второго триггера 17, третьего. клЮча 18,. диодов 19, 20, 21, " . .50Выходы 22 блока задания конфигурации ориентированного: графа 1 соедииены со вхоДами блока 7,. первый вы 4 од которого соединен со входомпере"ключателя 8, Первый выход переключателя 8 соединен с источником питания, второй его выход - с нулевым входом первого триггера 9; выходы 23блока задания конфигурации ориенти-рованного граФа 1 через элемент ИЛИ12 и ключ 10 соединены со счетным входом двоичного счетчика 13, выходыкоторого через первый блок переключения 14 соединены со входами блока регистрации 15. Второй выкод второгоблока переключения 7 соединен с управляющим входом второго, ключа 16, выход блока регистрации 15 через второй ключ 16 и диод 21 соединен с еди ничным входом второго триггера 17, единичный выход которого соединен с управляющим входом третьего ключа 18. Выход 24 блока управления 6 соединен с первым входом блока 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.Вершины Х,Х , Хп модели графа подключаются к соответствующим входам 22, выходные. цепи оптронов 3 подключаются к соответствующим выходам 23 и вершина Хо (начало проекта) по входу блока 1.Переключатель 8 устанавливается в положение минус источника питания.Формируется команда Исходное по которой блок управления 6 и блок переключения устанавливаются в ис" ходное положение, триггеры 9 и 17 переводятся в нулевое состояние ключ 10 и ключ 18 закрываются.По команде Пуск триггер 17 переводится в единичное положейие, ключ 18 открывается и первый же импульс частотыпоступает на вход блока управления 6. Яа выходе 24 бло ка управления 6 Формируется импульсный сигнал, поступающий на вход бло ка 7, который срабатывает и подключает, например, вершину модели графа Х через переключатель 8 к мину:су источника питания. Кроме того,управляющий сигнал переводит триггер9 в единичное состояние и открываетключ 10.Второй импульс частоты 1 формирует импульсный сигнал на выходе 25,который устанавливает двоичный счетчик 13 в исходное йоложение.Третий импульс частоты 1 формирует импульсный сигнал на выходе 26,который возбуждаетформировательимпульсов 5, в результате,чего пос-ледний формирует стандартный импульсопроса. Импульс опроса подается навершину Хо модели графа. В результате работы элементов дуг модели графа с выходных цепей оптронов 3 (дугХХ,ХоХ,ХХ) будУт сниматься импульсы и поступать через элементИЛИ 12 и ключ 10 на вход двоичногосчетчика 13Поскольку минусовой потенциал подключен в данный моментк вершине Х модели графа, то на выходных цепях оптронов 3 остальныхдуГ ( Х 1 Х)е Х ХЬз Хд ХЬф Х Х ХЬХ 4,ХХ 4,ХдХ 4импульсы сниматься не будут. В результате на вход двоичного счетчика13 придет система импульсов и двоичный счетчик 13 зафиксирует эти импульсы, На основании информации,поступающей по третьему входу блокауправления, блок управления формиру-:ет импульсный сигнал на выходе 27,триггер 17 переходит в нулевое состо-.яние и единичным сигналом на выходеоткрывает блок переключения 14, который подключает к работе блок регистрации 15 ключ 18 при этом за-.кроется. Блок регистрации 15 фиксйрует двоичный код на выходе двоичного счетчика 13, отражающий оценкусобытия в вершине графа Хз по максимуму и затем Формирует сигнал, который переводит триггер 17 в единичноесостояние. Триггер 17 открывает ключ18. На этом заканчивается первыйцикл работы. Первый же импульс частотыпереводит блок управления 6в исходное положение. Второй и последующие импульсы частоты т начинают выполнять второй цикл работы,который аналогичен первому циклу,При втором и последующих циклах работы определяются оценки событий помаксимуму в остальных вершинахмодели графа. Как только блок 7 окажется переведенным на определениеоценки События в .последней вершинемодели графа, сформируется постоянный сигнал, который закроет ключ 16,в работе устройства"после зафикснрования последней оценки события произойдет останов, Для повторения замера событий в вершинах модели графапо максимуму необходимо последовательно выдать команды Исходное,фПускф,Для оценки событий в вершинах модели графа по минимум необходимо переключатель 8 перевести в положение, при котором к выходу блока 7 подключается нулевой вход триггера 9.Рассматриваемое устройство, благодаря введению новых элементов и связей между ними, обеспечивает воэможность определения экстремальных путей по ориентированным графам.Формула изобретенияУстройство для определения экстремальных путей на ориентированных графах, содержащее первый ключ, выходкоторого подключен к счетному входудвоичного счетчика, выходы которогосоединены с информационными входамипервого блока переключения, триггеры,переключатель, второй и третий ключи, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей за счет определенияэкстремальных путей на ориентированных графах, в него введены блок управления, второй блок переключения,формирователь импульсов, блок регистрации, элемент ИЛИ и блок заданияконфигурации ориентированных графов,выполненный в виде цепочек, соединенных согласно топологии исследуемого графа, каждая из которых состоитиз последовательно соединенных фор мирователя импульсов, оптрона и линийзадержки, причем выходы линий задержки соединены соответственно с группой входов второго блока переключения, первый выход которого через 35 переключатель подключен к нулевомувходу первого триггера, вторые выходы оптронов подключены ко входамэлемента ИЛИ, выход которого соеди-нен с информационным входом первого 40 ключа, второй выход второго блокапереключения соединен с первым входом второго ключа, второй вход которого подключен к выходу блока регистрации, один вход которого соединенс первым выходом второго триггера иодним входом первого блока переклю чения, другие вхоДы блока регистрации соединены с выходами первогоблока, переключения, выход второгоключа подключен к единичному входувторого триггера, нулевой вход кото рого соединен с первым выходом блокауправления,единичный выход второготриггера подключен к управляющемувходу третьего ключа, выход которогосоединен с первым входом блока управ ления, второй выход которого подклю-чен к управляющему входу двоичногосчетчика, третий выход блока управления соединен с первым входом второго блока переключения и с единичнымвходом первого триггера, единичныйвыход которого подключен к управляющему входу первого ключа, третий вход 85 блока управления соединен с выходомб 4 3900 Составитель А,КолчинТехред Э. Чужик Коррект Редактор Д.Мепурншвили трушева Заказ 8026/4 б Подпимитета СССРоткрытийнаб., д. 4/5 тираж 779 ИПИ Государственного по делам изобретений Москва, Ж, Раушска оно 1303 Филиал ППП Патент, г.ужгород, ул,Проектная,первого ключа, четвертый выход блокауправления соединен со входом формирователя импульсов, выход которогоподключен ко входу блока задания конфигурации ориентированных графов,первый вход устройства соединен совторым входом втброго блока переключения, со вторым входом блока управления, с единичным входом второготриггера и с нулевым входом первбготриггера, второй вход устройства подключен к единичному входу второготриггера, третий вход устройства со"единеи с информационным входом третьего ключа. Источникиинформации, принятые во 8 внимание при экспертизе1. Авторское свидетельство СССР Р 424152, кл, 6 06 .Р 15/20, 28. 02. 72. 2. Авторское свидетельство СССР 9 305484, кл. 806 б 7/122, 28.09.71,