Устройство для исследования графа Советский патент 1985 года по МПК G06F15/173 

t Изобретение отноЬится к вычислительной технике и может быть исполь зовано для решения различных прикладных задач, которые формулируются в терминах теории графов, в ча стности для перечисления деревьев графа и выделения из них совокупности независимых деревьев. Известно устройство для определения числа деревьев в графе, содер жащее два блока регистров, блок перебора сочетаний, два коммутатора, группу ключей, два элемента И, регистр, наборное поле, генератор импульсов, счетчик, два элемента ИЛ и элемент запрета, причем первая группа выходов блока перебора сочет НИИ подключена к группе информацион ных входов регистров первого блока регистров, выходы которого подключе ны к входам ключей первой группы, выходы которых подключены к входам наборного поля, выходы которого под ключены к входам первого элемента И второй выход блока перебора сочетаний к первому входу регистра, первая группа выходов регистра - к первой группе входов блока перебора сочета ний, третий выход блока перебора сочетаний - к первому входу генератора импульсов, второй вход которог является выходом устройства Oj . Недостатком устройства является невозможность определения числа независимых деревьев графа и их кодов Наиболее близким по технической сущности к изобретению является устройство для определения числа деревь ев графа, содержащее блок перебора сочетаний, запоминающие триггеры, подключенные своими входами к блоку перебора сочетаний, управляемые ключевые схемы, которые входами управления соединены с единичными выхо дами запоминающих триггеров и соединены между собой в схему, отображающую граф, элемент И, входы которого соединены с другими входами управляе мых ключевых схем, щину проверки проводимости,-подключенную к входу одной из управляемых ключевых схем, элемент НЕ, ключи и счетчики, причем единичный вьпсод каждого запоминающего триггера подключен к первому входу соответствующего ключа, выход элемента И - через элемент НЕ к вторым входам всех ключей, а выход 072 каждого ключа - к входу соответствующего счетчика Zj , Однако известное устройство также не позволяет выделять независимые деревья графа, фиксировать коды последних и определять их общее число, что существенно ограничивает облает его применения при решении прикладных задач оптимизации сетей ЭВМ. Цель изобретения - расширение функциональных возможностей устройства путем реализации дополнительной функции выделения независимых деревьев в графе, фиксации кодов независимых деревьев и определения их общего числа в процессе перечисления деревьев графа, что позволит, например, получить более точные оценки структурной надежности сетей ЭВМ и выбирать оптимальные маршруты передачи данных в них. Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, блок перебора сочетаний, группу ключей, управляющие входы которых соединены с соответствующими выходами блока перебора сочетаний, первый элемент И, входы которого соединены с первыми выходами ключей группы, триггеры, элемент НЕ, счетчик, первую группу элементов И, первые входы которых соединены с единичными выходами соответствующих триггеров, вторые выходы ключей группы соединены в соответствии с топологией графа, введены распределитель импульсов, блок памяти, вторая группа элементов И, элемент ИЛИ, в-торой элемент И и линия задержки, причем вход распределителя импульсов подключен к выходу генератора импульсов, первый и третий выходы распределителя импульсов соединены соответственно с первым и третьим входами блока перебора сочетаний, второй вход которого подключен к выходу первого элемента И и первому входу второго элемента И, второй выход распределителя импульсов - к первому выходу ключа группы, соответствующего корневой вершине выделяемых деревьев, выходы блока перебора сочетаний соединены с информационными входами блока памяти, первыми входами элементов И второй группы и вторыми входами элементов И первой группы, выходы которых соединены с входами элемента ИЛИ, выход которого через элемент НЕ соединен с вторым входом второгоэлемента И, выход которого подключен к входу счетчика, управляющему входу блока памяти и через линию задержки - к объединенным вторым входам элементов И второй группы, выходы которых соединены с единичными входами соот ветствующих триггеров. Введение указанных элементов с учетом связей между ними позволяет в процессе перечисления деревьев графа выделить двоичные коды незави симых деревьев, а также рпределить их число. Это исключает необходимос разработки специализированных устройств, например, для моделирования и оптимизации надежности сетей ЭВМ повышает качество и точность модели рования. Известно, что оценка надежности сети типа с.,( дает хорошее приближение только при , поэтому для получения оценок структурной надежности для сетей целесообразно использовать выражение типа Р (GbfP --CiP -Uqp - се . D -.,.+ (-1) pi(n-i) где Р (G) - вероятность связности стохастического графа С(т1,т,р) с п вершинам та ребрами, которые им ют вес Р (вероятность присутствия ребра в .г Фе) ; А. - число деревьев графа; f - число независимых дер вьев графа. На фиг. 1 приведена блок-схема устройства для определения независи мых деревьев графа; на фиг. 2 - при мер коммутации выходов ключей для графа с четьфьмя вершинами и четырь мя ребрами. Предлагаемое устройство содержит генератор 1 импульсов, распределитель 2 импульсов, блок 3 перебора сочетаний, блок А памяти, первую группу элементов И 5, триггеры 6, вторую группу элементов И 7, группу ключей 8 по числу ребер исследуемого графа, элемент ИЛИ 9, элемент И 10 проверки связности графа, линию 11 задержки, элемент НЕ 12, счетчик 13 и элемент И 14. Выходы ключей коммутируются согласно топологии графа. При наличии разсешающего сигнала.на управляющем входе ключа его выходы соединяются электрически. При использовании контактных элементов такая функция реализуется на реле с нормально разомкнутым контактом, на бесконтактных элементах управления ключ представляет собой, например, симметричный тиристор типа 2У208А или КУ208. Подготовка устройства к работе требует обнуления блока 4 памяти, счетчика 13, счетчиков и триггеровблока 3 перебора сочетаний, введения уставок п и m в последний, коммутации выходов ключей 8 согласно топологии графа, записи единицы в первый разр5Й; распределителя 2, записи кода эталонного дерева в триггеры 6 или их обнуления. Цепи подготовки, а также цепи питания (в том числе и импульсного) на фиг. 1 не показаны. Устройство работает следующим образом. С приходом разрешающего сигнала на вход 15 генератора 1 импульсов последний генерирует прямоугольные импульсы, которые управляют работой распределителя 2. Тактовые импульсы первого выхода распределителя 2 вызывают появление комбинаций сигналов на выходах блока 3 перебора сочетаний, соответствующих определенному набору (n-l)-ro из m ребер графа. Данными сигналами отпирается (т-1) из m ключей В, между выходами которых образуется электрический контакт. Сигнал проверки связности подграфа из (п-t)-ro ребра со второго выхода распределителя 2 подается на один из выходов какого-либо ключа 8. Если данный подграф связан, то он вызовет появление на всех входах элементов И 10 проверки связности единичных сигналов (фиг. 2). При этом на выходе элемента И 10 фиксируется единичный сигнал Есть дерево, который подается на соответствующий вход блока 3 перебора сочетаний и на первый вход элемента И 1А. В блоке перебора сочетаний увеличивается на единицу содержимое счетчика числа деревьев и блокируется цепь подачи тактовых импульсов. На выходе элемента И 14 единичный сигнал Независимое дерево может по явиться только в случае наличия сигнала Есть дерево и единичного сигнала на выходе элемента НЕ 12„ Последнее возможно лишь при отсутствии совпадений в любом из разрядов еди- ничных сигналов с выходов триггеров 6 и единичных сигналов блока 3 перебора сочетаний. Единичный сигнал Независимое дерево с выхода элемента И 14 увели- чивает на единицу содержимое счетчика 13 независимых деревьев,.разрешает запись кода независимого дерева в блок 4 памяти5 затем через время t, снимает нулевой сигнал с вторых входов элементов И 5, обеспечивая запись кода сформированного независимого дерева в триггеры 6. Если во время подготовки устройства к работе не был записан код эталонного дереBEs то в триггеры 6 аналогично рассмотренному запишется код первого сформированного дерева« Сигнал с третьего выхода распределителя 2 разблокирует цепи подачи тактовых импульсов на первый вход блока 3 перебора сочетаний и подготавл ивает устройство к анализу ново(ГО подграфао Если же набор из (п-1)-го ребра не образует связанного подграфа, то хотя бы на одном из- входов элемента И 10 отсутствует единичный сигнал при наличии опросного сигнала на втором выходе распределителя 2 (фиг. 2). Сигналы Есть дерево и Независимое дерево не формируются. Устройство Переходит к анализу нового подграфа. После анализа всех возможных подграфов с (п-1)-м ребром в блоке 3 перебора сочетаний формируется сигнал Конец. По этому сигналу снимается питание с генератора 1 импульсов (вход 15), и устройство прекращает работу. Двоичные коды независимых деревьев хранятся в блоке 4 памяти, число независимых деревьев определяется содерлшмым счетчика 13, общее хшсло деревьев графа фиксируется счетчиком блока 3 перебора сочетаний. Предлагаемое устройство в отличие от известных позволяет определять наряду с числом деревьев и совокупность попарно независимых деревьев графа, В результате расширяются функциональные возможности устройства, отпадает необходимость в разработке специализированных устройств для моделирования и решения ряда прикладных задач, формулируемых в терминах теории графов.

L

i

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