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

О Il И С А Н И Е 27!906

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства Л

Кл. 42тпт, 7/48

Заявлено 11.Х1.1968 (№ 1281771/18-24) с присоединением заявки №

Приоритет

Опубликовано 26Х.1970. Бюллетень М 18

Дата опубликования описания 9.IX.1970

МПК G 06g 7/48

Комитет по делам изобретений и открытий при Совете Министров

СССР ъ ДК 681.33.157.001 (088.8) 1

Б. И. Блажкевич и Е. Д. Михайлова т

Физико-механический институт АН Украинской1СЙР - :I

I 1

A 13TGP bl изобретения

Заявитель

УСТРОЙСТВО ДЛЯ ПОИСКА ПРАДЕРЕВЬЕВ НАПРАВЛЕННОГО

ГРАФА

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

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

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

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

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

10 ячеек. Вторые входы всех блокирующих ячеек присоединены к соответствую цизт парам шпн ключевой матрицы и входам логической схемы

«HE — И». Входы установки начального состояния триггеров кольцевых коммутаторов и

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

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

271906

65 схемы «И» последнего кольцевого коммутатора.

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

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

Основными узлами устройства являются: система шин 1, управляемые кл.:очи 2, кольцевые коммутаторы, состоящие из триггеров 3, генератор 4 тактовых импульсов, блок пуска 5, логическая схема «Нà — И» 6, ключ сброса 7, триггер 8 конца поиска, логические схемы «И»

9 и- 10, схемы задержки 11, логические схемы

«И» 12, «ИЛИ» 13, блокирующие ячейки 14, разделительные диоды 15 и инверторы

«НЕ» 16.

Блоки 11 — 16 ставятся в соответствие каждому отдельному кольцевому коммутатору, при этом выход последнего триггера каждого кольцевого коммутатора соединен со входом первого триггера этого коммутатора через схему задержки 11 и логическую схему «И» 12.

Первый вход логической схемы «ИЛИ» 13, соответствующей первому кольцевому коммутатору, присоединен через схему «И» 9 ко входу блока пуска 6 и выходу триггера конца поиска 8, а аналогичные входы остальных схем

«ИЛИ» 18 — к выходам схем «И» 12, соответствующих предыдущим кольцевым коммутаторам. Вторые входы всех схем «ИЛИ» 18 подключены к первым выходам блокирующих ячеек 14, принадлежащих к соответствующим кольцевым коммутаторам.

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

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

Вторые входы всех блокирующих ячеек присоединены к соответствующим парам шин ВУодам логической схемы «HE — И» 6.

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

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

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

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

19 — со вторым ее входом. Первый и второй выходы блокирующей ячейки совмещаются соответственно с выходами схем «И» 17 и 18.

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

Работа устройства начинается с установки

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

Если частичный граф, образованный дугами, соответствующими замкнутым на любом этапе работы устройства ключам (в том числе и при установке его в исходное положение), представляет собой прадерево, то на всех входах логической схемы «НŠ— И» появляется сигнал. Вследствие этого путь тактовым импульсам от генератора периодических тактовых импульсов во все кольцевые коммутаторы закрыт логической схемой «И» 10.

271906

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

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

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

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

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

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

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

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

271906

Риг / Рог. 7, Сос1авитель Л. Б. Дмитриева

Редактор М. И. Андреева Техред T. П. Курилко Корректор И. С. Хлыстова

Заказ 2423/9 Тираж 480 Подписное

ЦНИИПИ Комитета пп делам изобретений и открытий прп Совете Министров СССР

Ыыоска, Ж-35, Раугпская наб., д. 4у5

Типография, пр. Сапунова, 2