Устройство для поиска прадеревьев направленногографа

27 906 ОПИСАНИЕ ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУСоюз Советских Социалистических РеспубликЗависимое от авт. свидетельства ЛЪ Кл, 42 аявлено 11.Х.1968 ( 1281771/18-24)присоединением заявкиПриоритетОпубликовано 26 Х,1970. Бюллетень18Дата опубликования описания 9.1 Х.1970 МПК б 06 д 7/4 Комитет по делам изобретении и сткрыти при Совете Министров ХК 681 ЗЗ 157001Д, Михайлова 1 й СЙР .-Авторызобретения И, Блажкевич зико-механический институт АН Украин аявите УСТРОЙСТВО ДЛЯ ПОИСКА ПРАДЕРЕВЬЕВ НАПРАВЛЕННОГРАФА Данное изобретение числительной техники Известно устройств ревьев направленного чевую матрицу, кольц стоящие из управляю триггеров, генератор блок пуска, логическу сброса, триггер конц схемы И.носится к ооласти выпоиска праде- держащее клю ммутаторы, со. ючами матрицы ых импульсов, НЕ - И, ключ и логические о для рафа, с евые к щих кл такто ю схему поискПредложенное устроиство дополнительно содержит соответствующие каждому кольцевому коммутатору схему задержки, логическую схему И, логическую схему ИЛИ, блокирующую ячейку, разделительный диод и инвертор, причем выход последнего триггера каждого кольцевого коммутатора соединен со входом первого триггера этого коммутатора через схему задержки и логическую схемуИ. Первый вход логической схемы ИЛИ, соот. ветствуюшей первому кольцевому коммутато. ру, присоединены через первую общую для всего устройства схему И ко входу блока пуска и выходу триггера конца поиска, а аналогичные входы схем ИЛИ, соответствующвх другим кольцевым коммутаторам, - ,к выходам схем И, соответствующих предыдущим кольцевым коммутаторам, Вторые входы всех схем ИЛИ подключены к первым выходам блокирующпх ячеек, принадлежащих соответствующим кольцевым коммутаторам. Первый вход блокирующей ячейки первого кольцевого коммутатора соединен через вторую общую для 5 всего устройства схему И с выходами генератора тактовых импульсов, схемы НЕ - И и триггера конца поиска, а первые входы всех последующих блокирующих яеек - со вторыми вь ходами предыдущих блокирующих 10 ячеек. Вторые входы всех блокирующих ячеекприсоединены к соответствующим парам шпн ключевой матрицы и входам логической схемы НЕ - И. Входы установки начального состояния триггеров кольцевых коммутаторов и 15 входы соответствующих этим коммутатораминверторов подключены непосредственно ко вторым выходам блокирующих ячеек, соответствующих тес же коммутаторам, а через разделительные диоды и ключ сброса - к блоку пп тания. Входы тактовых импульсов триггеров,образующих один кольцевои коммутатор, присоединенных к выходу соответствующей логической схемы ИЛИ. Первые входы логических схем И присоединены через схемы задержки 25 к выходам последпх триггеров соответствующих кольцевых коммутаторов, а вторые их входы - к выходам инверторов. Кроме того, в э 1 ом устройстве первый вход триггера конца поиска через ключ сброса присоединен к блоку питаЗ 0 ния, а второй его вход - к выходу логической55 60 65 схемы И последнего кольцевого коммутатора,Это позволяет сократить число тактовых импульсов, необходимых для поиска всех прадеревьев в направленном. графе, в результаге исключения тактовых импульсов, приводящих к выбору сочетаний замкнутых ключей, соответствующих частичным графам, в которых повторяются несвязанные с корнем компоненты, содержащиеся в частичных графах, соответствующих сочетаншо замкнутых ключей, образованных предыдущими тактовыми импульсами.На фиг. 1 изображена функциональная схема устройства; hа фиг. 2 - блок-схема блокирующей ячейки,Основными узлами устройства являются: система шин 1, управляемые кл;очи 2, кольцевые коммутаторы, состоящие из триггеров 3, генератор 4 тактовых импульсов, блок пуска 5, логическая схема НГ - И 6, ключ сброса 7, триггер 8 конца поиска, логические схемы И 9 и. 10, схемы задержки П, логические схемы И 12, ИЛИ 13, блокирующие ячейки 14, разделительные диоды 15 и инверторы НЕ 16.Блоки 11 - 16 ставятся в соответствие каждому отдельному кольцевому коммутатору, при этом выход последнего триггера каждого кольцевого коммутатора соединен со входом первого триггера этого коммутатора через схе. му задержки 11 и логическую схему И 12, Первый вход логической схемы ИЛИ 13, соответствующей первому кольцевому коммутатору, присоединен через схему И 9 ко входу блока пуска 6 и выходу триггера конца поиска 8, а аналогичные входы остальных схем ИЛИ 13 - к выходам схем И 12, соответствующих предыдущим кольцевым коммутаторам. Вторые входы всех схем ИЛИ 13 подключены к первым выходам блокирующих ячеек 14, принадлежащих к соответствующим кольцевым коммутаторам.Первый вход блокирующей ячейки 14 первого кольцевого коммутатора соединен через схему И 10 с выходами генератора 4 периодических тактовых импульсов, а также схемы НЕ- - И 6 и триггера 8 конца поиска, а первые входы всех последующих блокирующих ячеек - со вторыми выходами предыду щих. Вторые входы всех блокирующих ячеек присоединены к соответствующим парам шин и входам логической схемы НЕ - И 6.Входы установки начального состояния триггеров, образующих отдельные кольцевые коммутаторы, и входы соответствующих этим коммутаторам пнверторов НЕ 16 подключены непосредственно ко вторым выходам блокирующих ячеек, соответствующих этим коммутаторам, а через разделительные диоды 16 и ключ сброса 7 - к блоку питания, указанному на фиг. 1. Входы для такговых импульсов триггеров, образующих отдельный кольцевой коммутатор, присоединены к выходу соответствующей логической схемы ИЛИ 13, Пер 5 10 15 20 25 30 35 40 45 50 вые входы логической схемы И 12 присоединены через схемы задержки 11 к выходам последних триггеров соответствующих кольцевых коммутаторов, а вторые их входы - к выходам инверторов 16.Первый вход триггера конца поиска через ключ сброса 7 присоединен к блоку питания, а второй его вход - к выходу логическои схемы И 12, принадлежащей к последнему кольцевому коммутатору. Первая пара шин, соответствующая корню прадеревьев графа, присоединена непосредственно к заземленному зажиму блока питания, Контакты управляемых ключей 1, соответствующих дугам графа, исходящим из одной вершины и заходящим во вторую вершину, присоединены к вертикальным шинам, соответствующим первым вершинам, и горизонтальным шинам, соответствующим вторым вершинам.Блокирующая ячейка, представленная на фиг. 2, состоит из логических схем И 17 и 18 и инвертора 11 Е 19, при этом первые входы схем И 17 и 18 совмещены с первым входом блокирующей ячейки, второй вход логической схемы И 17 непосредственно, а второй вход логической схемы И 18 через инвертор НЕ 19 - со вторым ее входом. Первый и второй выходы блокирующей ячейки совмещаются соответственно с выходами схем И 17 и 18.При подготовке устройства к решению задачи поиска прадеревьев в конкретном графе каждой вершине последнего ставится в соответствие отдельная пара шин, состоящая из соединенных вместе горизонтальной и вертикальной шин, Пара шин, поставленная в соответствие корню прадеревьев, соединяется с одним зажимом источника питания, каждой дуге графа 1 за исключением дуг заходящих в корень) ставится в соответствие отдельный управляемый ключ, причем один из его контактов присоединяет к вертикальной шине, соответствующей вершине - началу дуги, а второй - к горизонтальной шине, соответствующей вершине - концу дуги. Триггеры, управляющие ключами, контакты которых присоединены к одноп и той же горизонтальной шине, соединяются вместе со схемой задержки 11 и логической схемой И 12 в кольцевой ком. мутатор. Работа устройства начинается с установки его в исходное положение сигналом, подаваемым от блока питания через ключ сброса 7 и разделительные диоды. Поиск прадеревьев начинается с момента отпускания этого ключа. Если частичный граф, образованный дугами, соответствующими замкнутым на любом этапе работы устройства ключам (в том числе и при установке его в исходное положение), представляет собой прадерево, то на всех входах логической схемы НЕ - И появляется сигнал. Вследствие этого путь тактовым импульсам от генератора периодических тактовых импульсов во все кольцевые коммутаторы закрыт логической схемой И 10.5В этом случае состояние устройства может быть изменено только подачей единичного тактового импульса от блока пуска на первый кольцевой коммутатор. Если этот импульс (или сигнал сброса при установке устройства в исходное положение) приведет к замыканию ключей, соответствующих дугам, не образующих прадерева, то вследствие отсутствия сигнала хотя бы на одном из входов логической схемы НЕ - И б открывается путь сигнала от генератора периодических тактовых импульсов, Первый из этих сигналов попадает через блокирую п;ие ячейки и соответствующую логическую схему ИЛИ 13 на первый по очереди кольцевой коммутатор, соответствующий горизонтальной шине, на которой отсутствует сигнал. В расположенных выше кольцевых коммутаторах этот же тактовый импульс попадает на входы схемы начального состояния триггеров, устанавливая коммутаторы схемы в исходное состояние, характеризующееся замыканием первых ключей управляемых триггерами этих коммутаторов.Схема задержки 11 вместе с логическими схемами НЕ 16 и И 12 препятствует (в случае переключения последнего триггера в соответствующем кольцевом коммутаторе) подаче тактового импульса в последующий кольцевой коммутатор, если на этот коммутатор подается такой импульс от генератора периодических тактовых импульсов.Подача тактовых импульсов в кольцевые коммутаторы как от генератора периодических тактовых импульсов, так и от блока пуска становится вообще невозможной после окончания поиска, т. е. срабатывания триггера конца поиска, так как исчезновение сигнала на его выходе приводит к закрытию путей для сигнала через логические схемы И 9 и 1 О. Предмет изобретенияУстройство для поиска прадеревьев направленного графа, содержащее ключевую матрицу, кольцевые коммутаторы, состоящие из управляющих ключами матрицы триггеров, генератор тактовых импульсов, блок пуска, логическую схему НЕ - И. ключ сброса, триггер конца поиска и логические схемы И, отличаюиееся тем, что, с целью уменьшения време 5 10 15 20 25 30 35 40 45 50 ни поиска прадеревьев, оно дополнительно содержит соответствующие каждому кольцевому коммутатору схему задержки, логическую схему И, логическую схему ИЛИ, блокирующую ячейку, разделительный диод и инвертор, причем выход последнего триггера каждого кольцевого коммутатора соединен со входом первого триггера этого коммутатора через схему задержки и логическую схему И; первый вход логической схемы ИЛИ, соответствующей первому кольцевому коммутатору, присоединен через первую общую для всего устройства схему И ко входу блока пуска и выходу триггера конца поиска, а аналогичные входы схем ИЛИ, соответствующих другим кольцевым коммутаторам, - к выходам схем И, соответствуюцтих предыдущим кольцевым коммутаторам; вторые входы всех схем ИЛИ подключены к первым выходам блокирующих ячеек, принадлежащих соответствующим кольцевым коммутаторам; первый вход блокирующей ячейки первого кольцевого коммутатора соединен через вторую об;цую для всего устройства схему И с выходами генератора тактовых импульсов, схемы НЕ - И и триггера конца поиска, а первые входы всех последующих блокирующих ячеек со вторыми выходами предыдущих блокирующих ячеек; вторые входы;всех блокирующих ячеек присоединены к соответствующим парам шин ключевой матрицы и входам логи ческой схемы НЕ - И; входы установки начального состояния триггеров кольцевых коммутаторов и входы соответствующих этим коммутаторам инверторов подключены непосредственно ко вторым выходам блокирующих ячеек, соответствующих тем же коммутаторам, а через разделительные диоды и ключ сброса - к блоку питания; входы тактовых импульсов триггеров, образующих один кольцевой коммутатор, присоединены к,выходу соответствующей логической схемы ИЛИ; первые входы логических схем И присоединены через схемы задержки к выходам последних триггеров соответствующих кольцевых коммутаторов, а вторые их входы - к выходам инверторов; первый вход триггера конца поиска через ключ сброса присоединен к блоку питания, а второй вход - к выходу логической схемы И последнего кольцевого коммутатора,271906Рог. РСос 1 авитель Л. Б. Дмитриева Редактор М, И. Андреева Техред Т. П. Курилко Корректор И. С. ХлыстоваЗаказ 2423/9 Тираж 480 Подписное ЦНИИПИ Комитета по делам изобретений и открытий прп Совете Министров СССР Ыыоска, Ж, Раугпская ньб., д. 45пография, пр, Сапунова, 2