УСТРОЙСТВО для ПОИСКА ПРАДЕРЕВЬЕВ НАПРАВЛЕННОГОГРАФА Советский патент 1970 года по МПК G06G7/48 

Данное изобретение относится к области вычислительной техники.

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

Предложенное устройство дополнительно содержит соответствующие каждому кольцевому коммутатору схему задержки, логическую схему «И, логическую схему «ИЛИ, блокирующую ячейку, разделительный диод и инвертор, иричем вьЕХОд последнего триггера каждого кольцевого коммутатора соединен со входом первого триггера этого коммутатора через схему задержки и логическую схему «И. Первый вход логической схемы «ИЛИ, соответствующей первому кольцевому ко ммутатору, п-рисоеди.нен че|рез первую общую для в;сего устройства схему «И ко входу блока пуска и выходу триггера конца поиска, а аналогичные входы схем «ИЛИ, соответствующих другим кольцевым ком1мутаторам,-«выходам схем «И, соответствующих предыдущи.м кольцевым коммутаторам. Вторые входы всех схе.м «ИЛИ подключены к первым выходам блокирующнх ячеек, принадлежащих соответствующим кольцевым коммутаторам. Первый вход блокирующей ячейки первого кольцевого коммутатора соединен через вторую общую для

всего устройства схему «И с выхода.ми генератора тактовых импульсов, схемы «НЕ-И и триггера конца поиска, а первые входы всех последующих блокирующих ячеек - со вторыми выходами предыдущих блокирующих

ячеек. Вторые входы всех блокирующих ячеек присоединены к соответствующим парам шин ключевой матрицы и входам логической схемы «НЕ-И. Входы установки начального состояния триггеров кольцевых коммутаторов и

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

к выходам последних триггеров соответствующих кольцевых коммутаторов, а вторые их входы-к выходам инверторов. Кроме того, в этом устройстве первый вход триггера конца ионска через ключ сброса присоединен к блоку питасхемы «И последнего кольцевого коммутатора.

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

На фиг. 1 изображена фуикциональная схема устройства; на фиг. 2 - блок-схема блокирующей ячейки.

Основными узлами устройства являются: система шин 1, унравляемые кл;очн 2, кольцевые коммутаторы, состоящие из триггеров 3, генератор 4 тактовых импульсов, блок пуска 5, логическая схема «НЕ-И 6, ключ сброса 7, триггер 8 конца поиека., логические схемы «PI 9 И- 10, схемы задержки 11, логические схемы «И 12, «ИЛГ1 13, блокируюид,ие ячейки 14, разделительные диоды 15 и инверторы «НЕ 16.

Блоки //-16 ставятся в соответствие каждому отдельному кольцевому коммутатору, при этом выход иоследнего триггера каждого кольцевого коммутатора соединен со входом первого триггера ьтого коммутатора через схему задерлски 11 и логическую схему «И 12. Первый вход логической схемы «ИЛИ 13, соответствующей первому кольцевому коммутатору, присоединен через схему «И 9 ко входу блока пуска 5 и выходу триггера конца поиска 8, а аналогичные входы остальных схем «ИЛИ 13 - к выходам схем «И /2, соответствующих предыдущим кольцевым коммутаторам. Вторые входы всех схем «ИЛИ 13 подключены к первым выходам блокирующих ячеек 14, принадлежащих к соответствующим кольцевым коммутаторам.

Первый вход. блокирующей ячейки 14 первого кольцевого коммутатора соединен через схему «И 10 с выходами генератора 4 периодических тактовых имнульсов, а также схемы «НЕ-И 6 и триггера 8 конца поиска, а первые входы всех последующих блокирующих ячеек -со вторыми выходами предыдущих. Вторые входы всех блокирующих ячеек присоедииены к соответствующнм парам щнн и входам логической схемы «НЕ-И 6.

Входы установки начального состояния триггеров, образующих отдельные кольцевые коммутаторы, н входы соответствующих этим коммутаторам инверторов «НЕ 16 нодключены непосредственно ко вторым выходам блокирующих ячеек, соответствующих этим коммутаторам, а через разделительные диоды 15 н ключ сброса 7 - к блоку нигания, указанному на фиг. 1. Входы для тактовых импульсов триггеров, образующих отдельный кольцевой коммутатор, присоединены к выходу соответствующей логической схемы «ИЛИ 13. Первые входы логической схемы «И 12 присоединены через схемы задержки 11 к выходам последних триггеров соответствующих кольцевых коммутаторов, а вторые их входы - к выходам инверторов 16.

Первый вход триггера конца ионска через ключ сброса 7 нрнсоединен к блоку питания, а второй его вход - к выходу логической схемы «И 12, принадлежащей к носледнел у

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

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

Блокирующая ячейка, нредставленная на фиг. 2, состоит из логических схем «И 17 и 18 и инвертора «НЕ 19, при этом нервые входы схем «И 17 и 18 совмещены с первым входом блокирующей ячейки, второй вход логической

схемы «И 17 непосредственно, а второй вход логической схемы «И 18 через инвертор «НЕ 19 - со вторым ее входом. Первый и второй выходы блокирующей ячейки совмещаются соответственно с выходами схем «И 17 и 18.

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

управляемый ключ, причем один из его контактов присоединяет к вертикальной шине, соответствующей вершине - началу дуги, а второй- к горизонтальной шине, соответствующей вершине - концу дуги. Триггеры, управляющие ключами, контакты которых присоединены к одной и той же горизонтальной шине, соединяются вместе со схемой задержки 11 и логической схемой «И 12 в кольцевой коммутатор.

Работа устройства начинается с установки его в нсходное положение сигналом, подаваемым от блока питания через ключ сброса 7 и разделительпые диоды. Поиск прадеревьев начииается с момента отпускания этого ключа. Если частичный, граф, образованный дугами, соответствуюшимн замкнутым на любом этане работы устройства ключам (в том числе и при установке его в исходное положение), представляет собой прадерево, то на всех входах логической схемы «НЕ-И появляется сигнал. Вследствие этого путь тактовым имнульсам от генератора периодических тактовых имнульсов во все кольцевые коммутаторы закрыт

В этом случае состояние устройства может быть изменено только подачей единичного тактового импульса от блока пуска на первый кольцевой коммутатор. Если этот импульс (или сигнал сброса при установке устройства в исходное положение) приведет к замыканиЕо ключей, соответствующих дугам, не образующих прадерева, то вследствие отсутствия сигнала хотя бы на одном из входов логической схемы «НЕ-И 6 открывается путь сигнала от генератора периодических тактовых импульсов. Первый из этих сигналов попадает через блокируюп;ие ячейки- и соответствующую логическую схему «ИЛИ 13 на первый по очереди кольцевой коммутатор, соответствующий горизонтальной шине, на которой отсутствует сигнал. В расположенных выше кольцевых коммутаторах этот же тактовый импульс попадает на входы схемы начального состояния триггеров, устанавливая коммутаторы схемы в исходное состояние, характеризующееся замыканием первых ключей управляемых триггерами этих коммутаторов.

Схема задержки // вместе с логическими схемами «НЕ 16 и «И 12 препятствует (в случае переключения последнего триггера в соответствующем кольцевом коммутаторе)- подаче тактового импульса в последующий кольцевой коммутатор, если на этот коммутатор подается такой импульс от генератора периодических тактовых импульсов.

Подача тактовых импульсов в кольцевые коммутаторы как от генератора периодических тактовых импульсов, так и от блока пуска становится вообще невозможной после окончания поиска, т. е. срабатывания триггера конца поиска, так как исчезновение сигнала на его выходе приводит к закрытию путей для сигнала через логические схемы «И 9 и 10.

Предмет изобретения

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

0 первый вход логической схемы «ИЛИ, соответствующей первому кольцевому коммутатору, присоединен через первую общую для всего устройства схему «И ко входу блока пуска и выходу триггера конца поиска, а аналогичные входы схем «ИЛИ, соответствующих другим кольцевым коммутаторам,- к выходам схем «И, соответствуюцих предыдущим кольцевым коммутаторам; вторые входы всех схем «ИЛИ подключены к первым выходам

0 блокирующих ячеек, принадлежащих соответствующим кольцевым коммутаторам; первый вход блокирующей ячейки первого кольцевого коммутатора соединен через вторую общую для всего устройства схему «И с выходами

5 генератора тактовых импульсов, схемы «НЕ-И и триггера конца поиска, а перовые входы всех последующих блокирующих ячеек-ico вторыми выходами предыдущих блокирующих ячеек; вторые входы всех блокирующих ячее-к присоединены к соответствующим парам шин ключевой матрицы и входам логической схемы «НЕ-И ; входы установки начального состояния триггеров кольцевых коммутаторов и входы соответствующих этим коммутаторам инверторов подключены непосредственно ко вторым вы.чодам блокирующих ячеек, соответствующих тем же ком1мутаторам, а через разделительные диоды и ключ сброса - к блоку питания; входы тактовых импульсов

0 триггеров, образующих один кольцевой коммутатор, присоединены к ,выходу соответствующей логической схемы первые входы логических схем «И присоединены через схемы задержки к выходам последних триггеров соответствующих кольцевых коммутаторов, а вторые их входы-к выходам инверторов; цервый в.ход триггера конца поиска через ключ сброса присоединен к блоку питания, а второй вход - к выходу логической схемы

0 «И последнего кольцевого ком,мутатора.

А

19 У

. выx

Риг.г