Устройство для определения числа деревьев в графе
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Номер патента: 888128
Автор: Червяцов
Текст
(5 )М. Кл. О 06 Р 15/20 Государственный комитет пв делам наабретеннй и открытий(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ДЕРЕВЬЕВ В ГРАФЕИзобретение относится к вычислительной технике и может быть использовано для определения числа независимых деревьев графа при исследовании надежности систем, отображаемых графами.5 Известно устройство для поиска прадеревьев направленного графа 11 ,содержащее ключевую матрицу, кольцевые коммутаторы, генератор тактовых импульсов,1 О триггеры, логические схемы И, схемы задержки, блокирующую ячейку, инвертор, Это устройство позволяет сократить число тактовых импульсов, необходимых для поиска всех прадеревьев в направленном1 графе путем исключения частичных графов, в которых повторяются несвязанные с корнем компоненты, содержащиеся в ранее рассмотренных частичных графах.К недостаткам данного устройства относятся: отсутствие возможности исследовать ненаправленный граф и определять число деревьев, образованных с участием каждого отдельного ребра графа, отсут 2ствие возможности определять число независимых деревьев графа.Известно устройство для определения числа деревьев графа (2, содержащее регистры, блок перебора сочетаний, коммутатор, ключи, элемент И, наборное поле, генератор импульсов и счетчик.Недостатком данного устройства является то, что в нем отсутствует возможность определения числа независимых деревьев графа. Цель изобретения - расширение функциональных возможностей путем реализации дополнительной функции определения числа независимых деревьев графа.Поставленная цель достигается тем, что в известное устройство, содержащее первый блок регистров, блок перебора сочетаний, первый коммутатор, первую группу ключей, первый элемент И, регистр, наборное поле, генератор импульсов и счетчик,причем первая группа выходов блока перебора сочетаний подключена к8881 28 51 О 15 группе информационных входов первогоблока регистров соответственно, выходыкоторого подключены к входам ключейпервой группы, выходы которых подключены к входам наборного поля, выходыкоторого подключены к входам первого эле-мента И, второй выход блока перебора сочетаний подключен к первому входу регистра,первая группа выходов регистра подключенак перв ой группе входов бл ока перебора с очетаний соответственно, третий выходблока перебора сочетаний подключен кпервому входу генератора импульсов, второй вход которого является входом устройства, выход генератора импульсов подклю-,чен к первому входу первого коммутатора, первый выход которого подключен квторому входу блока перебора сочетаний,второй выход первого коммутатора подключен к управляющему входу первогоблока регистров, введены второй блокрегистров, второй коммутатор, ключ, триггер, блок сравнения, второй элемент И,два элемента ИЛИ и элемент запрета,причем второй выход регистра подключенк первым входам элемента ИЛИ, второгоэлемента И, ключа и к инверсному входуэлемента запрета, второй выход первогоблока регистров подключен к второмувходу ключа и прямому выходу элементазапрета, выход которого подключен квторому входу регистра, выход ключаподключен к входу второго коммутатора,первая группа выходов которого подключена к входам второго блока регистровсоответственно, выходы которой подключены к первым входам блока сравнения соответственно, второй выход второго коммутатора подключен к вторым входам второгоэлемента ИЛИ и второго элемента И, выходкоторого подключен к входу счетчика,первая группа выходов первой группырегистров подключена к второму входублока сравнения, первый выход которогоподключен к второму входу первого элемента ИЛИ и третьему входу второгоэлемента ИЛИ, выход которого подключен к второму входу первого коммутатора, третий выход которого подключен ктретьему входу блока сравнения, второйвыход которого подключен к третьемувходу первого коммутатора и третьемувходу первого элемента ИЛИ, выход которого подключен к инверсному входу триггера, выход первого элемента И подключен к прямому входу триггера, выходкоторого подключен к четвертому входублока сравнения и четвертому входу первого коммутатора,25 30 35 40 45 50 55 4 На чертеже представлена блок-схема устройства для определения числа деревь ев в графе.Устройство содержит блок 1 перебора сочетаний, первый блок регистров 2 1 22 , , регистр 3, .второй блок регистров 4,1, 44, первый 5, второй 6 коммутаторы, первую группу ключей 7,1, 7 д7 р, первый элемент И 8, ключ 9, второй элемент И 10, первый и второй элементы ИЛИ 11, 12, элемент 13 запрета, наборное поле 14, триггер15, блок 16 сравнения, генератор 17 импульсов и счетчик 1 8. Топография графа задается на наборномполе 14 путем коммутации выходов поля,соответствующих в вершинам графа, и входов поля, соответствующих М ребрамграфа,Устройство для определения деревьевграфа работает следующим образом. При поступлении сигнала на вход генератора 17 генератор запускается и вырабатывает тактовые импульсы, которые поступают через коммутатор 5 на вход блока 1, На каждом такте блока перебора сочетаний возбуждает Ввыход из М по программе С, (программа П 1), Сигналы с выходов блока 1 поступают на входы регистров 2 и запоминаются. С выходов блока регистров 2 сигналы поступают на входы группы ключей ребер 7, между выходами ключей при этом устанавливается электрический контакт, Если данный набор В ребер из М образует первое дерево, срабатывает элемент И 8 и переводит триггер 15 в единичное состояние. С единичного выхода триггера 15 сигнал Сравнение поступает на четвертый вход коммутатора 5 и на четвертый вход блока 16, коммутатор 5 подключает выход генератора 17 к третьему входу блока 16. Блок 16 осуществляет -сравнение-набора, записанного в первой группе регистров 2, с наборами, записанными во второй группе блока регистров 4, Поскольку все регистры 4 пока свободны, на выходе блока 16 вырабатывается сигнал фНет сравнения, который поступает через элемент ИЛИ 11 на инверсный вход триггера 15 и на вход коммутатора 5. При этом триггер устанавливается в нулевое состояние и снимает сигнал Сравнение с входа блока сравнения, а коммутатор 5 подключает выход генератора к входу первой группы регистров 2. Под действием сигналов, поступающих с выхода гесводится к определению всех деревьев в графе, а затем сравнение деревьев между собой, такой алгоритм требует больших затрат времени.В данном устройстве временные затра-. ты значительно меньше. Сокращение времени достигается за счет последовательного применения двух программ, По первой программе отыскивается дерево путем выбора Вребер из М. После отыскания первого дерева независимые с ним деревья отыскиваются путем выбора В ребер из М-В+ 1, при этом число выборов резко сокращается.Для того, чтобы исключить появление одинаковых наборов, полученных при обра.щении к первой и второй программам, в устройстве предусмотрена специальная проверка набора в блоке сравнения. Это в свою очередь сокращает количество тактов работы устройства для полного решения задачи,изобретения ,Устройство для опредепения числа деревьев в графе, содержащее первый блок регистров, блок перебора сочетаний, перпервый элемент И, регистр, наборное поле, генератор импульсов и счетчик, причем первая группа выходов блока перебора сочетаний подключена к группе информационных входов регистров первого блока регистров соответственно, выходы которого подключены к входам клюЧей первой группы, выходы которых подключенык входам наборного поля, выходы которогоподключены к входам первого элемента И,второй выход блока перебора сочетанийподключен к первому входу регистра, первая группа выходов регистра подключенак первой группе входов блока перебора 45сочетаний соответственно, третий выходблока перебора сочетаний подключены кпервому входу генератора импульсов, второй вход которого является входом устройства, выход генератора импульсов подключен к первому входу первого коммутатара, первый выход которого подключенк второму входу блока перебора сочетаний, второй выход первого коммутатораподключен к управляющему входу первогоблока регистров, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей путем реализации дополнительной функции определениягчисла независимых деревьев графа, в не 5 888128нератора 17 через коммутатор 5 па входы блока регистров 2, содержимое блокарегистров 2 через элемент 13 переписывается в регистр 3. По окончании записи в регистр 3 на его выходе формируется сигнал Занят", а на рабочих выходахформируются сигналы запрета, поступающие в блок 1.Блок перебора сочетаний переключается на работу по программе С (проВ грамма П 2). Сигнал "Занят" поступаетна вход элемента 13, ключа 9, элемента И 10 и через элемент ИЛИ 12 навторой вход коммутатора 5, Под действием сигнала Занят" выходы блока регистров 2 отключаются от входа регистра 3 и подключаются через ключ 9 икоммутатор 6 к входу блока регистров4; выход генератора 17 через коммутатор 5 подключается к входу блока 1. При 20поступлении сигналов от генератора блок1 на каждом такте возбуждает Ввыход из М-В + 1, Очередной набор Всигналов проверяется на условие образования дерева. Если набор сигналов абра- н ф о р м у л а зует дерево, то в отличие от рассмотренфного выше данный набор записываетсячерез ключ 9 и коммутатор 6 в блок 4.По окончании записи набора в регистр 4с выхода коммутатора 6 выдается сигнал 5 вый коммутатор, первую группу ключей, фЗанятф на вход элемента И 10 и черезэлемент ИЛИ 12 на второй вход коммутатора 5. При этом в счетчик 18 записывается единица, а блок перебора сочетаний продолжает работу по программеП 2.При завершении работы по программеП 2 с выхода блока 1 в регистр 3 выдается сигнал фКонец П 2", который сбрасывает регистр в исходное состояние, в результате чего блок перебора сочетанийпереходит на работу по программе П 1.По окончании программы П 1 с выхс- да блока перебора сочетаний в генераторвыдается сигнал фКонец П 1 ф, которыйостанавливает генератор. На этом работаустройства завершается. Содержимоесчетчика 18 указывает число попарно независимых деревьев.В известных устройствах анализ графаограничивается либо определением числадеревьев, либо определением числа деревьев, образованных с участием каждого отдельного ребра. В данном устройстве реализована возможность определения числапар независимых деревьев в графе, чтоповышает полноту и точность анализа.Алгоритм отыскания независимых деревьев в графе с помощью известных устройств4) го введены блок регистров, второй коммутатор, ключ, триггер, блок сравнения, второй элемент И, два элемента ИЛИ и элемент запрета, причем второй выход регистра подключен к первым входам элементов ИЛИ, второго элемента И, ключа и к инверсному входу элемента запрета, второй выход первого блока регистров подключен к второму входу ключа и прямому входу элемента запрета, выход которого подключен к второму входу регистра, выход ключа подключен к входу второ го коммутатора, первая группа выходов которого подключена к входам второго блока регистров соответственно, выходы которой подключены к первой группе входов блока сравнения соответственно, второй выход второго коммутатора подключен к вторым входам второго элемента ИЛИ и второго элемента И, выход которого подключен к входу счетчика, первая группа выходов первого блока регистров подключе:18на к второму входу б)нка сравнения, первыйвыход которого подключен и второму входу первого элемента ИЛИ и к третьемувходу второго элемента ИЛИ, выход которого подключен к второму входу первогокоммутатора, третий выход которого подключен к третьему входу блока сравнения,второй выход которого подключен к третьему входу первого коммутатора и третьему входу первого элемента ИЛИ, выходкоторого подключен к инверсному входутриггера, выход первого элемента И под 1ключец к прямому входу триггера, выходкоторого подключен к четвертому входублока сравнения и четвертому входу первого коммутатора.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРНо 271906, кл. (:1 06 б 7/48, 1974.2, Авторское свидетельство СССР
СмотретьЗаявка
2901578, 31.03.1980
РОСТОВСКОЕ ВЫСШЕЕ ВОЕННОЕ КОМАНДНОЕ УЧИЛИЩЕ ИМ. ГЛАВНОГО МАРШАЛА АРТИЛЛЕРИИ НЕДЕЛИНА М. И
ЧЕРВЯЦОВ ВИКТОР НИКОЛАЕВИЧ
МПК / Метки
МПК: G06F 15/173
Опубликовано: 07.12.1981
Код ссылки
<a href="https://patents.su/4-888128-ustrojjstvo-dlya-opredeleniya-chisla-derevev-v-grafe.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для определения числа деревьев в графе</a>
Предыдущий патент: Устройство для контроля логических узлов
Следующий патент: Устройство для сбора, обработки и отображения информации
Случайный патент: Устройство для настройки гармонических