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

 

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФА, содержащее генератор импульсов , блок перебора сочетаний, группу ключей, управляющие входы которых соединены с соответствующими выходами блока перебора сочетаний, первый элемент И, входы которого соединены с первыми выходами ключей группы, триггеры, элемент НЕ, счетчик, первую группу элементов И, первые входы которых соединены с единичными выходами соответствующих триггеров, вторые выходы ключей группы соединены в соответствии с топологией графа , отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения возможности выделения независимых деревьев в графе, в устройство дополнительно введены распределитель импульсов, блок памяти, вторая группа элементов И, элемент ИЛИ, второй элемент И и линия задержки , причем вход распределителя импульсов подключен к выходу генератора импульсов, первый и третий выходы распределителя импульсов соединены соответственно с первым и треть- , им входами блока перебора сочетаний , второй вход которого подключен к выходу первого элемента И и первому входу второго ,элемента И, второй выход распределителя импульсов подключен к первому выходу ключа группы, соответствующего корневой вершине выделяемых деревьев, выходы блока перебора сочетаний соединены (Л с информационными входами блока памяти , первыми входами элементов И второй группы и вторыми входами элементов И первой группы, выходы кот.орых соединены с входами элемента ИЛИ, выход которого через элемент НЕ соединен с вторым входом второго элемента И, выход которого подключен к входу счетчика, управляющему вхосо ду блока памяти и через Jtинию за00 00 держки - к объединенным вторым входам элементов И второй группы, выходы которых сое5а;инЙ1Ы с единичными входами соответствующих триггеров.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (! 9) (1)) ((5() G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГП4Й (21) 3664346/24-24 (22) 21.11.83 (46) 07.02.85. Бюл. ¹- 5 (72) П.К. Павнитьев (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР № 888128, кл. G 06 F 15/20, 1980.

2. Авторское свидетельство СССР

¹ 329538, кл, С 06 F 15/20, 1972 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФА, содержащее генератор импульсов, блок перебора сочетаний, группу ключей, управляющие входы которых соединены с соответствующими выходами блока перебора сочетайий, первый элемент И, входы которого соединены с первыми выходами ключей группы, триггеры, элемент НЕ, счетчик, первую группу элементов И, первые вхо ды которых соединены с единичными выходами соответствующих триггеров, вторые выходы ключей группы соединены в соответствии с топологией графа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем обеспечения возможности выделения независимых деревьев в графе, в устройство дополнительно введены pQcпределитель импульсов, блок памяти, вторая группа элементов И, элемент

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

1138807

Изобретение относится к вычислительной технике и может быть использовано для решения различных прикладных задач, которые формулируются в терминах теории графов, в частности для перечисления деревьев графа и выделения из них совокупности независимых деревьев, Известно устройство для определения числа деревьев в графе, содержащее два блока регистров, блок перебора сочетаний, два коммутатора, группу ключей, два элемента И, регистр, наборное поле, генератор импульсов, счетчик, два элемента ИЛИ и элемент запрета, причем первая группа выходов блока перебора сочетаний подключена к группе информационных входов регистров первого блока регистров, выходы которого подключены к входам ключей первой группы, выходы которых подключены к входам наборного поля, выходы которого подключены к входам первого элемента И, второй выход блока перебора сочетаний к первому входу регистра, первая группа выходов регистра — к первой группе входов блока перебора сочетаний, третий выход блока перебора сочетаний — к первому входу генера30 тора импульсов, второй вход которого является выходом устройства Ц . !

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

Наиболее близким по технической сущности к изобретению является устройство для определения числа деревьев графа, содержащее блок перебора сочетаний, запоминающие триггеры, подключенные своими входами к блоку перебора сочетаний, управляемые ключевые схемы, которые входами управления соединены с единичными выхо-45 дами запоминающих триггеров и соединены между собой в схему, отображающую граф, элемент И, входы которого соединены с другими входами управляемых ключевых схем, шину проверки 50 проводимости, подключенную к входу одной из управляемых ключевых схем, элемент HE ключи и счетчики, причем единичный выход каждого запоминающего триггера подключен к первому 55 входу соответствующего ключа, выход элемента И вЂ” через элемент НЕ к вторым входам всех ключей, а выход каждого ключа — к входу соответствующего счетчика (2) .

Однако известное устройство также не позволяет выделять независимые деревья графа, фиксировать коды последних и определять их общее число, что существенно ограничйвает область его применения при решении прикладных задач оптимизации сетей ЗВМ.

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

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

3 1138807 4 которого через элемент HE соединен с вторым входом второго элемента И, выход которого подключен к входу счетчика, управляющему входу блока памяти и через линию задержки — к объединенным вторым входам элементов И второй группы, выходы которых соединены с единичными входами соответствующих триггеров.

Введение указанных элементов с учетом связей между ними позволяет в процессе перечисления деревьев графа выделить двоичные коды незавиI симых деревьев, а также определить их число. Это исключает необходимость разработки специализированных устройств, например, для моделирования и оптимизации надежности сетей ЭВМ, повышает качество и точность модели-, 5

25 рования.

Известно, что сети типа оценка надежности

P (С) А P (1 Р) 30

Р (С) Р 1 С2 PZ(n-1) +Сз РЗ(и-1) се

+ (1) 1 Рk(n i) 35 дает хорошее приближение только при

Р О поэтому для получения оценок структурной надежности для сетей

0<Р(1 целесообразно испольэовать выражение типа где P (С) — вероятность связности с стохастического граба

G(n,m,р) с и вершинами, m ребрами, которые имеют вес Р (вероятность 40 присутствия ребра в .гра-. фе);

Ад „ — число деревьев графа;

f — число независимых деревьев графа. 45

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

Предлагаемое устройство содержит генератор 1 импульсов, распредели- 55 тель 2 импульсов, блок 3 перебора сочетаний, блок 4 памяти, первую группу элементов И 5, триггеры 6, 1 вторую группу элементов И 7, группу ключей 8 по числу ребер исследуемого графа, элемент ИЛИ 9, элемент И 10 проверки связности графа, линию 11 задержки, элемент НЕ 12, счетчик 13 и элемент И 14.

Выходы ключей коммутируются согласно топологии графа. При наличии разоешающего сигнала на управляющем входе ключа его выходы соединяются электрически. При использовании контактных элементов такая функция реализуется на реле с нормально разомкнутым контактом, на бесконтактных элементах управления ключ представляет собой, например, симметрич-. ный тиристор типа 2У208А или КУ208.

Подготовка устройства к работе требует обнуления блока 4 памяти, счетчика 13, счетчиков и триггеров. блока 3 перебора сочетаний, введения уставок п и m в последний, коммутации выходов ключей 8 согласно топологии графа, записи единицы в первый разряд распределителя 2, записи кода. эталонного дерева в триггеры 6 или их обнуления ° Цепи подготовки, а также цепи питания (в том числе и импульсного) на фиг. 1 не показаны.

Устройство работает следующим образом.

С приходом разрешающего сигнала на вход 15 генератора l импульсов последний генерирует прямоугольные импульсы, которые управляют работой распределителя 2. Тактовые импульсы первого выхода распределителя 2 вызывают появление комбинаций сигналов на выходах блока 3 перебора сочетаний, соответствующих определенному набору (и-1)-го из ш ребер графа.

Данными сигналами отпирается (ш-1) из ш ключей 8, между выходами которых образуется электрический контакт.

Сигнал проверки связности подграфа из (n-1)-го ребра со второго выхода распределителя 2 подается на один из выходов какого-либо ключа 8. Если данный подграф связан, то он вызовет появление на всех входах элементов И 10 проверки связности единичных сигналов (фиг. 2). При этом на выходе элемента И 10 фиксируется единичный сигнал "Есть дерево", который подается на соответствующий вход блока 3 перебора сочетаний и на первый вход элемента И 14. В блоке пере бора сочетаний увеличивается на еди1 t 38807 ницу содержимое счетчика числа дере вьев и блокируется цепь подачи тактовых импульсов.

На выходе элемента И 14 единичный сигнал "Независимое дерево" может по- 5 явиться только в случае наличия сигнала "Есть дерево" и единичного сигнала на выходе элемента НЕ 12. Пос- леднее возможно лишь при отсутствии совпадений в любом из разрядов единичных сигналов с выходов триггеров

6 и единичных сигналов блока 3 перебора сочетаний.

Единичный сигнал "Независимое дерево" с выхода элемента И 14 увели- 15 чивает на единицу содержимое счетчика 13 независимых деревьев,, разрешает запись кода независжюго дерева в блок 4 памяти, затем через время снимает нулевой сигнал с вторых 20 входов элементов И 5, обеспечивая запись кода сформированного независимого дерева в триггеры б. Если во время подготовки устройства к работе не был записан код эталонного дерева, то в триггеры б аналогично рассмотренному запишется код первого сформированного дерева.

Сигнал с третьего выхода распределителя 2 разблокирует цепи подачи 30 тактовых импульсов на первый вход блока 3 перебора сочетаний и подготавливает устройство к анализу ново го подграфа.

Если же набор из (n-1) -ro ребра не образует связанного подграфа, то хотя бы на одном из- входов элемента И 10 отсутствует единичный сигнал при наличии опросного сигнала на втором выходе распределителя

2 (фиг. 2). Сигналы "Есть дерево" и "Независимое дерево" не формируются, Устройство переходит к анализу нового подграфа.

После анализа всех возможных подграфов с (n-1)-м ребром в блоке 3 перебора сочетаний формируется сигнал "Конец". По этому сигналу снимается питание с генератора 1 импульсов (вход 15), и устройство прекращает работу. Двоичные коды независимых деревьев хранятся в блоке 4 па"мяти, число независимых деревьев определяется содержимым счетчика 13, общее число деревьев графа фиксируется счетчиком блока 3 перебора сочетаний, Предлагаемое устройство в отличие от известных позволяет определять наряду с числом деревьев и совокупность попарно независимых деревьев графа. В результате расширяются функциональные возможности устройства, отпадает необходимость в разработке специализированных устройств для моделирования и решения ряда прикладных задач, формулируемых в терминах теории графов.

1138807

Фиг.1

1138807

Sf

Код юа ЮгоРох д: И1О оФ м бюдах 10: 1И1

Кад на отде N : 1

Составитель С. Назаров

Редактор В. Данко Техред А.Бабииец Корректор Г. Огар

Заказ 10690/38 Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, .4