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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ИТВЛЬСТВУ Союз Советских Социалистическик Республик(51)М. Кл. О 06 С 7/122 Государственный комитет сссР по делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ГРАФА НА ДЕРЕВЬЯИзобретение относится к области вычислительной техники и может быть использовано для определения характеристик разложения графа на деревья при исследовании надежности систем, отображаемых вероятностными графами. Известно устройство 1) для поиска прадеревьев направленного графа, содержащее ключевую матрицу, кольцевые коммутаторы, генератор тактовых импульсов, триггеры, схемы И, схемы задержки, блокирующую ячейку, инвертор. Это устройство позволяет 15 сократить число тактовых импульсов, необходимых для поиска всех пра-, деревьев в направленном графе путем исключения частичных графов, в которых повторяются не связанные с кор нем компоненты, содержащиеся в ранее рассмотренных частичных графах. Это устройство характеризуется сле 1- дующими недостатками: отсутствие возможности исследовать ненаправленный граф," отсутствие возможности определения числа деревьев,образованных с участием каждого отдельного ребра графа, отсутствие возможности управ,ления процессом образования деревьев;30 отсутствие возможности определения характеристик разложения графа на деревья.Известно устройство для нахождения деревьев графа 21, содержащее блок индикации, счетчики, диоды, пере-. ключатели, линию задержки, блоки коэффициентов пересчета, счетчики числа деревьев. Этому устройству присущи следующие недостатки: отсутствие возможности определения числа деревьев, образованных с участием каждого отдельного ребра графа; отсутствие возможности управления процессом образования деревьев; отсутствие возможности определения характеристик разложения графа на деревья.Наиболее близким техническим решением к изобретению является устройтво для определения числа деревьев З,содержащее элемент И, входы которого подключены к выходам первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика и к первым входам элементов И первой группы, выходы которых соединеныс .счетными входами других счетчиков, выходы сброса счетчиков и нулевые входы триггеров( й -1) групп подключены к входу сброса устройства, единичные входы триггеров ( М -1) групп соединены с входамизаписи устройства. Кроме того, устройство содержит блок перебора состояний.Недостатками прототипа являются:отсутствие воэможности управленияпроцессом образования деревьев; отсутствие возможности определения характеристик разложения графа надеревья. Характеристиками разложения графа на деревья являются числа подмножеств, в которых деревьяимеют постоянными одно, два и т. д.ребер.Цель изобретения - повышение точности исследования путем реализациидополнительной функции определениячисел подмножеств, в которых деревьяимеют постоянными одно, два и т. д,ребер, и представления возможности 20управления процессом образования деревьев.Цель достигается тем, что в устройство, содержащее элемент И, входы которого подключены к выходам 2первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика и к первым вхЬдам элементов И первой группы, выходы которых соединены с счетными входами других счетчиков, выходы сброса счетчиков и нулевые входы триггеров .( й -1) групп подключены к входу сброса устройства,единичные входы триггеров ( й -1)групп соединены с входами записиустройства, введены элементы задержки, вторая группа элементов И, элементы .запрета, второе и третье наборные поля и ( й -1) распределителей, входы первого распределителясоединены с единичными выходами триггеров первой группы, входы остальных распределителей подключены квыходам элементов запрета, первые 45входы которых соединены с единичными выходами триггеров остальныхгрупп. вторые входы элементов запрета подключены к выходам второгонаборного поля, выходы ( М - 1) распределителей соединены с входамитретьего наборного поля, выходы которого подключены к управляющим входам ключей, управляющий вход (. й -1)-го распределителя соединен "с входомтактовых импульсов устройства и с55одними входами элементов И второйгруппы, другие входы которых подключены к управляющим выходам соответствующих распределителей, выходпервого элемента И второй группй Щсоединен с выходом устройства, выходы остальных элементов И второйгруппы подключены к управляющимвходам соответствующих распределителей и через элементы задержки к вторым входам соответствующих элементов И первой группы, вход считывания первого наборного поля соединенс входом опроса устройства, входывторого наборного поля соединеныс выходами первых й -2 распределителей.Функциональная схема устройствапредставлена на чертеже.Устройство содержит элемент И 1,первое наборное поле 2, ключи 3 -3(ребер), счетчики 4-, 4, элементыИ 5-. 5 ц, первой группы, триггерыби " и-,к-л (ребер), элементы запрета 7 -, 7 н ,д , распределители81 -. 8 й л, втоРое набоРное поле 9,элементы И 10 в . 10 ц.и второй группы,третье наборное поле 11, элементызадержки 12в : .12 4, вход сброса13, вход тактовых импульсов 14,вход опроса 15, выход импульсов останова 1 б,вход записи 17,В триггерахб; ; - номер вершины, ) -номерребра, инцидентного данной вершине.В работе устройства следует выделить два этапа: этап задания структуры графа и этап исследования структуры графа.Рассмотрим этап задания структурыграфа. Основой для задания графа вустройстве является граф, имеющий Йвершин и М ребер, в котором всеэлементы перенумерованы. Элементыустройства упорядочиваются в соответствии с принятой нумерацией, Номера вершин присваиваются распределителям 8 и входам, элемента И 1. Количество распределителей равной -1, количество входов элемента И 1 равноМ . Номера ребер, инцидентных вершинамприсваиваются входным и выходным цепям распределителей 8,Номера возрастают слева направо,На наборном поле 2 входы элемента И 1 и ключи (ребер) 3 в . Зм соединяются в топологическую схему графа. На наборном поле 11 выходы распределителей 8 и входы ключей 3, соответствующие одноименным ребрам графа, соединяются между собой. На наборном поле 9 выходы распределителей 8 и входы элементов запрета 7, соответствующие одноименным ребрам, но инцидентные разным вершинам, соединяются между собой. При этом соблюдается правило: выход распределителя, соответствующего вершине с меньшим номером, должен быть соединен с входом одноименного элемента запрета соответствуюшего вершине с большим номером.В дальнейшем на этапе исследования графа работа устройства протекает по тактам. В первом такте поступает сигнал по входу сброса 13 на нулевые входы триггеров б и стирающие входы счетчиков 4. Триггеры исчетчики устанавливаются в исходноесостояние. Во втором такте в соответствии с матрицей инцидентности поступают сигналы на единичные входы триггеров 5 (ребер) б, которые устанавливаются в состояние "1". С единичных выходов триггеров б (ребер), инцидентных первой вершине, поступают сигналы на входы распределителя первой вершины. 10 С единичных выходов триггеров б (ребер), инцидентных остальным вершинам, сигналы поступают на входы соответствующих распределителей через элементы запрета 7. В каждом распределитеЛе возбуждается один выход, соответствующий возбужденному входу с меньшим номером. Сигналы с выходов распределителей поступают через схему коммутаций наборного поля 9 на входы соответствующих элементов запрета 7, а через схему коммутаций наборного поля 11 на входы соответствующих ключей 3. При этом запрещаются сигналы на одноименных выходах распределителей, соответствующих вершинам со старшими номерами. В результате в каждом распределителе будет возбужден только один выход, причем среди возбужденных выходов не будет одноименных. Возбужденные выходы будут иметь меньшие номера из множества разрешенных номеров.При поступлении сигналов на управляющие входы ключей 3 образуется 35 электрический контакт между их полюсами.В третьем такте поступает сигнал на вход опроса 15, который через схему коммутаций наборного поля 2 40 поступает на входы элемента И 1. Если возбужденные выходы распределителей соответствуют ребрам, образующим дерево, то срабатывает элемент И 1 и с его выхода подается сигнал в пос ледний счетчик 4.В четвертом такте поступает сигнал на вход тактовых импульсов 14, который подается на управляющий вход последнего распределителя 8 и входы элементов И 10. При этом. возбуждается очередной по номеру из разрешенных выходов последнего распределителя 8. Дальнейшая работа устройства протекает путем чередования третьегои четвертого тактов до тех пор, пока не будет возбужден последний из разрешенных выходов последнего распределителя. Тогда-с управляющего выхода распределителя подается сигнал на разрешающий вход соответствую щего элемента И 10. Очередной сигнал, поступающий на вход тактовых импульсов 14, проходит на вход й-го, а через элемент И 10 на вход й-го распределителей и на вход М -го эле-, 65 мента задержки 12. Если выполняются условия образования дерева, то при поступлении сигнала на вход опро"а 15 сработает элемент И 1. В результате поступит сигнал на входы-го и й -1 -го счетчиков. При этом возбуждается очередной разрешенный выход в М -2-м распределителе и возбуждается младший иэ разрешенных (с учетом нового состояния й -2-го распределителя) выходов й -1 - го распределителя. Таким образом, перевод каждого распределителя в новое состояние осуществляется при поступлении сигнала на вход 14, если распределители с высшими номерами находятся в последних из разрешенных состояний.Работа устройства завершается, если все распределители устанавливаются в последние иэ разрешенных состояний. Тогда при поступлении очередного сигнала на вход 14, срабатывают все элементы И 10. Сигналы с выходов элементов И 10 переводят распределители в исходное состояние, а сигнал с выхода первого элемента И 10 является сигналом останова работы устройства. Показание Й -го счетчика 4 соответствует числу деревьев в графе. Показание М -1-го счетчика 4 соответствует числу подмножеств, в которых деревья имеют М -2 постоянных ребер. Показания М -2-го счетчика соответствуют числу подмножеств, в которых деревья имеют й -3 постоянных ребер и т, дТаким образом благодаря введению новых элементов и связей между нимиповысилась точность и глубина исследования разложения графа на деревья,Устройство позволяет определить характеристики разложения графа на деревья. Показания счетчиков характерны для принятой нумерации вершин в графе, Следовательно, имеется возможность управлять процессом образования деревьев, так как с изменением этой нумерации изменяется последовательность образования деревьев. Кроме того, предлагаемое устройство позволяет работать с графами, у которых число вершин и ребер может быть переменньщ..Формула изобретения Устройство для разложения графа на деревья, содержащее элемент И, вхбды которого подключены к выходам первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к ачетному входу одного счетчика и к первым входам элементов И первой группы,выходы которых соединены со счетнымивходами других счетчиков, выходы/7 /7 /7 /7 ИПИ Заказ 4241/37 ираж 751 Подписно 4 МК 4 И 4 н 4. 1Ф 1г. У лиал ПП ате од, ул, Проектная роса счетчиков и нулевые входыф бтриггеров ( Ч -1)групп подключенкнывходу сброса устройства, единич-.соные входы триггеров ( М -1) групиоединены с входами записи устройства, о т л и ч а ю щ е е с я темчтто, с целью повышения точности,5в него введены элементызадержки,вторая группа элементов И, элементызапрета, второе и третье наборныеполя и ( И -1) распределителей,входы первого распределителя соеиеныс единичными выходами триггеровпервой группы, входы остальных распределителей подключены к выходам элементов зв запрета, первые входы которых соединены с единичными выходами триггеров остальных групп, вторые входыэлементов запрета подключены к выМ -1ходам второго наборного поля выхо ыР д( -1) распределителей соединены свходами третьего наборного поля, выходы которого подключены к управляющим входам ключей, управляющий вход( И -1)-го распределителя соединенс входом тактовых импульсов устройства и с одними входами элементов Ивторой группы, другие входы которыхподключены к управляющим выходам соответствующих распределителей, выходпервого элемента И второй группы сое-динен с выходом устройства, выходыостальных элементов И второй группыподключены к управляющим входамсоответствующих распределителей и через элементы задержки к вторым входам соответствующих элементов И первойгруппы, вход считывания первого на-:борного поля соединен с входом опроса устройства, входы второго наборного поля соединены с выхоДами первых 11 -2 распределителей. Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРР 271906, кл. С 06 С 7/48, 1969.2. Авторское свидетельство СССРР 364939, кл, С 06 С 7/48, 1971.3. Авторское свидетельство СССР9 329538, кл. С 06 С 7/48, 1970