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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИРЕСПУБЛИК 90 1)4 0 06 Р 15/20 ИСАНИЕ ИЗОБРЕТЕНИ ЕТЕЛЬСТ Н АВТОРСКОМ АРСТВЕННЫЙ КОМИТЕТ СССРЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Авторское свидетельство СССРР 1056206, кл. О 06 Р 15/31, 1983.Авторское свидетельство СССРУ 987616, кл. О 06 Р 5/02, 1983.Авторское свидетельство СССРВ 271906, кл. О 06 Р 7/48, 1974.Авторское свидетельсгво СССРВ 888128, кл. С 06 Г 15/20, 1981.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для определения простых цепей и циклов графа приисследованиях информационных сетей, отображаемых графом. Целью изобретения является расширение функциональныхвоэможностей путем реализации функций определения всех простых цепей,соединяющих две заданные вершиныграфа или всех циклов графа, а также всех простых цепей (одной12903 цепи) между двумя вершинами графа с заданным количеством ребер или всех (одного) циклов с заданным количеством ребер. Эти операции необходимы при исследовании надежности систем и решении других задач анализа информационных сетей, отображаемых графами. Поставленная цель достигается тем, что в устройство, содержащее блок перебора сочетаний 4, блок сравнения 6, наборное поле 5, генератор импульсов 1, регистр 7, счетчик 11, первый 16 и второй 17 эле 45менты И, первый 20 и второй 21 элементы ИЛИ, введены блок выделенияединиц 3, узел сравнения 2, группасчетчиков 8, группа элементов ИЛИ 9,группа элементов И 10, первый 12,второй 13, третий 14 триггеры задания режимов, третий 18 и четвертый19 элементы И, третий 22, четвертый23 и пятый 27 элементы ИЛИ, первый24, второй 25, третий 26 и четвертый31 элементы задержки, переключательрежимов 28, 2 ил.1 з.п-ф-лы.Изобретение относится к вычислительной технике и может быть использовано для определения простых цепей и циклов графа при исследованиях информационных сетей, отображаемых 5 графом.Целью изобретения является расши-, рение функциональных возможностей за счет определения циклов путем реализации функций определения всех простых цепей, соединяющих две заданные вершины графа или всех циклов графа, а также. всех простых цепей (одной цепи) между двумя вершинами графа с заданным количеством ребер или всех (одного) циклов с заданным количест- . вом ребер. Эти операции необходимы при исследовании надежности систем и решения других задач анализа информационных сетей, отображаемых гра, фами.На фиг. 1 представлена структурная схема устройства; .на фиг. 2 - структурная схема узла сравнения. 25Устройство содержит (фиг. 1) генератор 1 импульсов, узел 2 сравнения, блок 3 выделения единиц, блок 4 перебора сочетаний, блок 5 наборного поля, блок 6 сравнения, регистр 7, 30 группу счетчиков 8, группу элементов ИЛИ 9, группу элементов И 10, счетчик 11, первый, второй и третий триггеры 12-14 задания режимов, триггер 15, первый, второй, третий и четвертый элементы И 16-19,.первый, второй, третий и четвертый элементы ИЛИ 20-23 первый, второй и третий элементы 2426 задержки, пятый элемент ИЛИ 27, переключатель 28 режимов работы, вход 29 устройства, выход 30 окончания работы устройства, четвертый элемент 31 задержки.Узел 2 сравнения (фиг. 2) содержит и групп элементов И 32 записи, и групп элементов ИЛИ 33 сравнения, группу из и элементов ИЛИ 34 запрета, группу из иэлементов И 35 блокировки, группу из и элементов И 36 анализа, выходной элемент ИЛИ 37, информационные входы 38 узла, вход 39 установки регистров в нуль, вход 40 разрешения зазаписи кода, выходы 41 узла, группу из и регистров 42.Генератор 1 импульсов выдает тактовые сигналы, период следования ко, торых должен быть не меньше суммарного времени переходных процессов в блоке 3 выделения единиц, времени за держки сигнала на элементе ИЛИ 21 и времени переключения триггера 15,Узел 2 сравнения выполняет функции сравнения и хранения кодов искомых простых цепей (циклов) исследуемого графа. Коды записываются и хранятся в регистрах 42 узла. В исходное (нулевое) состояние регистры устанавливаются сигналом с установочного входа. Запись кода, поступившего на информационные входы 38 узла, осуществляются только по сигналу, поступающему на вход 40 разрешения записи кода. Для этого вход 40 имеет связь с вторыми входами всех элементов И 32 а каждая отдельная шина инфор 3 1мационных входов 38 подключена кпервым входам всех элементов И 32,относящихся к одному разряду. Разрешение на запись .кода в соответствующий регистр 42 (за исключением первого) через соответствующую группуэлементов И 32,.осуществляются потенциалом с выхода соответствующегоэлемента И 35, который подключен квходам элементов И 32 соответствующей группы. Разрешающий потенциална запись кода в первый регистр 42(на фиг. 2 справа), когда он находится в нулевом состоянии, поступает с инверсного выхода элемента ИЛИ 34 на все элементы И 32 первойгруппь 1. Очередные коды последовательно записываются в регистры 42 и хранятся в них. Сравнение кодов в узле 2 заключается в проверке фактапокрытия единичными разрядами кода, находящегося на информационных входах узла, всех единичных разрядов хотя бы одного из кодов, хранящихся в регистрах 42. Проверка осущест,вляется следующим образом, С информационных входов узла сравнения на входы элементов ИЛИ 33 подается прямой код .слова. На вторых входах элементов ИЛИ 33 каждой отдельной группы постоянно находятся в инверсном коде сигналы слов, записанных в соответствующих регистрах 42. Если имеет место факт покрытия единичными разрядами входного кода всех единичных разрядов кода, записанного в каком-либо регистре 42, то на выходах элементов ИЛИ 33 соответствующей группы будут находиться единичные сигналыкоторые поступают на входы соответствующего элемента И 36. В этом случае единичный . сигнал на выходе элемента И 36 появится лишь при наличии единичного сигнала на прямом выходе элемента ИЛИ 34, соединенного с входами данного элемента И 36 (это необходимо для исключения из рассмотрения регистров 42, находящихся в нулевом состоянии). Единичный сигнал, полученный хотя бы на одном из элементов И 36, передается через выходной элемент ИЛИ 37 на выходы 41 узла 2 сравнения.Блок 5 наборного поля предназначен для задания графа в виде матрицы инцидентности, строки которой соответствуют ребрам, а столбцы - вершинам графа. Каждая матрица со 290345 4 25 30 35 40 45 50 55 необходимого количества ребер с по 5 10 15 20 держит только две 1 , расположенные в столбцах, инцидентных данной строке: остальные элементы строки равны "О", Единичные элементы матрицы в блоке 5 наборного поля фиксируются путем замыкания соответствующих контактов. Первые контакты блока 5, относящиеся к отдельным строкам, подключены к отдельным выходам разрядов блока 3 выделения единиц, а вторые контакты блока 5, относящиеся к отдельным столбцам, подключены к входам отдельных элементов ИЛИ 9, выходы которых соединены с тактовыми входами соответствующих счетчиков 8,Блок 4 перебора сочетаний предназначен для формирования кодов совокупностей ребер графа, которые затем проверяются, составляет каждая из них отдельную простую цепь (цикл) или нет. Информационные выходы блока 4 соединены с информационными входами блоков 2 и 3. Блок 3 выделения единиц 12", предназначен для выборки каждого отдельного ребра из совокупности, сформированной в блоке 4.Проверка того, является данная совокупность ребер простой цепью (циклом) или нет, осуществляется на основе использования следующего факта, вывытекающего из свойства матрицы инцидентности графа: любая совокупность строк матрицы, образующая простую,цепь между двумя какими-.либо вершинами графа, содержит в столбцах, соответствующих этим вершинам, ровно поодной "1", а в каждом из других оставшихся столбцов - либо ровно две"1", либо ни одной (если же эта цепьзамкнута, т.е. образует цикл, то влЫбом столбце содержится либо ровнодве "1", либо не содержится ни одной).Формально этот факт может иметь место и тогда, когда совокупность ребер образует простую цепь и еще дополнительно один или несколько не пересекающихся между собой циклов (два и более непересекающихся цикла). Эти явления в устройстве определяютсяузлом 2 сравнения в процессе построения простых цепей (циклов), начинаяпоиск иэ минимально возможного или следующим увеличением этого количества, Выявленные таким образом совокупности ребер в устройстве не фиксируются.Вершины графа, между которыми отыскиваются простые цепи, задаются нарегистре 7, разрядные выходы которогопредставляют собой номера вершин,Блок 6 сравнения необходим дляопределения факта сравнения кода, записанного в регистре 7, и кода, снимаемого с первых разрядов двухразрядных счетчиков 8, в каждом из которыхподсчитывается количество "1" в соответствующем столбце рассматриваемой совокупности строк,Устройство работает в трех режимах, которые задаются переключателем28 режимов. Первый режим - определение одной простой цепи (одного цикла)сзаданным количеством ребер. Второйрежим - определение всех простых цепей (циклов) с заданным количествомребер. Третий режим - определениевсех простых цепей (циклов) с количеством ребер, равным или большимзаданному. В каждом режиме перед началом работы в блоке 4 перебора сочетаний устанавливаются в "1" первыемладшие разряды регистра блока в количестве, равном требуемому исходному количеству ребер. Если определя.ются простые цепи, то в регистре 7устройства устанавливаются в "1"два разряда с номерами, равными номерам вершин, между которыми определяются простые цепи. Если определяютсяциклы, .то все разряды регистра 7должны содержать "0". После описанных вьппе начальных установок устройство в каждом режиме работает следу-.ющим образом.Первый режим. Работа начинаетсяпо сигналу, поданному на вход 29 устройства, который устанавливает в нулевое состояние счетчик 11, триггеры12-14 задания режимов, регистры 42узла 2 сравнения, поступает на входэлемента ИЛИ 22 и с его выхода устанавливает в нулевое состояние счетчики 8 блок 3 выделения единиц, азатем с задержкой на элементе 26поступает на вход установки в единичное состояние триггера 15 и вход,установки кода блока 3 выделенияединиц (элемент 26 задерживает сигнал на время переходных процессовв блоке 3 при установке его внулевое состояние). Этот же сигнал,задержанный на элементе 24, череззамкнутые контакты переключателя 28устанавливает триггер 12 в единичноесостояние (задержка необходима навремя переходных процессов в триггере). Поскольку все регистры 42 узла 2 сравнения находятся в нулевом состоянии, а на информационные входы узла 2 подается некоторый код с выхода блока 4, то сравнения в узле 2 не .происходит, Тогда на прямом выходе узла 2 - "0", а на инверсном -налы от генератора 1 через элементИ 16 поступают на тактовый вход бло" ка 3. При этом просматривается последовательно вся совокупность строк матрицы инцидентности, сформированная в блоке 4 перебора сочетаний, и на счетчиках 8 подсчитывается количест 1во 1 , содержащихся в каждом столбце этой сов окупно сти строк , Если в процессе последовательного выделения единиц в блоке 3 на каком-либо из счетчиков 8 з афик сируется более двух " 1 " , то на выходе соответствующего элемента И 1 0 появляется сигнал , который проходит через элементы ИЛИ 232 1 и устанавливает триггер 1 5 в нуль , чем об еспечив ается прекращение подачи сигналов от генератора 1 на тактовый вход блока 3 выделения единиц . Этот же сигнал с выхода элемента ИЛИ 2 1 поступает на тактовый вход блока 4 и обеспечивает формирование очередного сочетания , задерживается на элементе 2 5 задержки ( в ремя з а" держки определяется переходными процессами в блоке 4 перебора сочетаний) и поступает на вход элемента И 1 8 , который открыт потенциалом с прямого выхода. элемента ИЛИ 20 , так как триггер 1 2 находится в единичном состоянии . С выхода элемента И 1 8 сигнал проходит через элемент ИЛИ 2 2 и выполня е т действия , описанные выше .Если в процессе последовательного выделения единиц блоком 3 пе реполнення счетчиков 8 не происходит , то по сле завершения работы блока 3 выполняе тся сравнение содержимого регистр а 7 и кода , снимаемого с первых разрядов счетчиков 8При совпадении указанных кодов элемент И 1 9 потенциалом с выхода блока 6 открывается . В э том случае в следующем такте на выходе окончания работы блока 3 по 3 является сигнал, который проходит открытый элемент И 19 и поступает на вход 40 записи кода узла 2 сравне 15 20 25 30 35 40 45 50 55 1 О "1", В этом случае элемент И 17 закрыт, а элемент И 16 открыт, и сиг 7 12903 ния, чем обеспечивается запись в узле сравнения кода, находящегося на его информационных входах, т.е. записывается код совокупности ребер графа, образующей искомую простую 5 цепь (цикл), Зтот же сигнал увеличивает содержимое счетчика 11 на единицу и через элемент ИЛИ 27 сбрасывает в,нуль триггер 12, чем обеспечивается выдача с инверсного выхода элемента ИЛИ 20 сигнала окончания работы устройства, а с прямого выхода - запрещающего потенциала на элемент И 18. Сигнал с выхода блока 3 поступает также на элемент ИЛИ 21 и с его выхода сбрасывает триггер 15 в нуль и прекращает подачу тактовых сигналов с генератора 1. При несовпадении кодов регистра 7 и выходов счетчиков 8 элемент И 19 закрывается. 2 В этом случае сигнал с выхода блока3 через элемент И 19 не проходит, а .поступает на вход элемента ИЛИ 21 и с его выхода осуществляет описанные 25 ранее действия, т.е. формирует новое сочетание, которое в дальнейшем проверяется, образует оно простую цепь (цикл) или нет. Если после проверки всех сочетаний для заданного количества ребер совпадения кодов в блоке 6 не происходит, то сигнал с первого выхода окончания работы блока 4 перебора сочетаний проходит через элемент ИЛИ 27 и устанавливает в нуль триггер 12, чем обеспечивается окончание работы устройства. В данном слуслучае счетчик 11 устройства, а также все регистры 42 узла 2 сравнения находятся в нулевом состоянии.40 Второй режим работы устройства отличается тем, что сигналом с входа 29 устройства через элемент 24 задержки и замкнутые контакты переключателя 28 устанавливается в единичное состояние триггер 13. Кроме того, окончание работы устройства происходит только по сигналу с первого выхода окончания работы блока 4, который сбрасывает триггер 13 в нуль, т.е. после того, как будут проанализированы все сочетания с заданным количеством ребер. При этом число простых цепей с заданным количеством ребер графа фиксируется в счетчике 11, а сами коды найденных совокупностей ребер записываются в регистры 42 узла 2 сравнения. 45 8В третьем режиме работа устройства отличается тем, что сигнал начала работы с входа 29 устанавливает вединичное состояние триггер 14, который сбрасывается только сигналомс второго выхода окончания работыблока 4 перебора сочетаний, т.е, после того, как будут сформированы ипроверены все возможные сочетанияребер, начиная с заданного количестваНа счетчике 11 фиксируется количество всех простых цепей (циклов),а их коды записываются в регистры 42узла 2 сравнения,Формула изобретения1. Устройство для исследования графов, содержащее блок перебора сочетаний, блок сравнения, наборное поле, генератор импульсов, регистр, счетчик, первый и второй элементы И, первый и второй элементы ИЛИ, о т - л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения циклов, в него введены блок выделения единиц, узел сравнения, группа счетчиков, группа элементов ИЛИ, группа элементов И, первый, второй и третий триггеры задания режимов, третий и четвертый элементы И, третий, четвертый и пятый элементы ИЛИ, первый, второй, третий и четвертый элементы задержки, триггер и переключатель режимов работы, причем вход первого элемента задержки является входом устройства, выход первого элемента задержки подключен к подвижному контакту переключателя режимов работы, первые входы установки в нуль первого, второго и третьего триггеров задания режима объединены между собой, соединены с входом установки в нуль счетчика, с установочным входом узла сравнения, с первым входом третьего элемента ИЛИ и с входом первого элемента задержки, выход третьего элемента ИЛИ подключен к входу установки в нуль блока выделения единиц, к входу третьего элемента задержки, к входам установки в нуль счетчиков группы, выход первого разряда каждого -го счетчика группы подключен к -му входу первой группы входов блока сравнения и подключен к первому входу х-го элемента И группыи), выход второго разряда1290345 каждого -го счетчика группы подключен к второму входу -го элемента И группы, выход каждого х-го элемента И группы подключен к, -му входу четвертого элемента ИЛИ, выход которого подключен к первому входу второго .элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, третий вход второго элемента ИЛИ подключен к выходу четвертого злемен О та задержки, выход второго элемента ИЛИ подключен к тактовому входу блока перебора сочетаний, к . входу установки в нуль триггера и к входу второго элемента задержки, выход которого подключен к первому входу третьего элемента И, второй вход которого подключен к прямому выходу первого элемента ИЛИ, инверсный выход которого является выходом окончания работы устройства, выход третьего элемента И подключен к второму входу третьего элемента ИЛИ, каждый вход первого элемента ИЛИ подключен к прямому вы 25 ходу одноименного триггера задания режима, первый, второй и третий неподвижные контакты переключателя режимов работы соединены с входами установки в единицу соответственно первого, второго и третьего триггеров задания режимов работы, выход третьего элемента задержки подключен к входу установки в единицу триггера и к входу установки кода блока выделения единиц, выход окончания работы ко торого подключен к входу четвертого элемента задержки и к первому входу четвертого элемента И, выход каждого -го разряда регистра подключен к х-му входу второй группы входов блока сравнения, выход которого подклю.чен к второму входу четвертого элемента И, выход четвертого элемента И подключен к первому входу пятого элемента ИЛИ, к счетному входу счетчика и к входу разрешения записи кода узла сравнения, прямой выход которого подключен к первому входу второго элемента И, а инверсный выход узла сравнения подключен к первому входу первого элемента И, вторые входы первого и второго элементов И объединены и подключены к прямому выходу триггера, третьи входы первого , и второго элементов И объединены и подключены к выходу генератора импуль сов, выход окончания перебора всех возможных сочетаний блока перебора 10сочетаний подключен к второму входу пятого элемента ИЛИ и к второму входу установки в нуль второго триггера задания режима работы, выход пятого элемента ИЛИ соединен с вторым входом установки в нуль первого триггера задания режима, выход окончания перебора части сочетаний, блока перебора сочетаний подключен к второму входу установки в нуль первого триггера задания режима, группа информационных выходов блока перебора сочетаний подключена соответственно к группе информационных входов блока выделения единиц и к группе информационных входов узла сравнения, выход каждого -го разряда блока выделения единиц подключен к -й горизонтальной шине наборного поля, соответствующей -й строке матрицы инцидентности исследуемого графа, а 1-й вход каждого -го элемента. ИЛИ группы (где= 1, и;1, г,.) подключен к )-й вертикальной шине -й группы вертикальных шин наборного поля, соответствующим столбцам матрицы инцидентности исследуемого графа, выход каждого -го элемента ИЛИ группы подключен к счетному входу -го счетчика группы, выход первого элемента И соединен с такто- вым входом блока выбора единиц.2. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что узел сравнения содержит группу из п регистров, и групп элементов И записи, п групп элементов ИЛИ сравнения, группу из и элементов ИЛИ запрета, группу из иэлементов И блокировки, группу из и элементов И анализа, выходной элемент ИЛИ, причем первые входы одноименных элементов И записи всех групп обьединены и являются соответствующим входом группы информационных входов узла, первые входы одноименных элементов ИЛИ сравнения всехгрупп обьединены между собой и объединены с первыми входами одноименных элементов И записи групп, выходкаждого х-го элемента И записи каждой,)-й группы (где= Г; и.;= Г; и;ш - число разрядов в регистре; ивколичество регистров в группе) подключен к входу х-го разряда -горегистра группы, нулевой выход -го разряда 1-го регистра подключен к .второму входу х-го элемента ИЛИ сравнения 1-Й группы, выход которого подключен к -му входу -го элемента ИРедактор И. Рйбче орректор А. Тяс аказ 7904/48 Тираж 673 НИИПИ Государств по делам изобр 035, Москва, Ж-ЗПодписноеомитета СССР ног ени Ра и открытийшская наб., д. 4 оизводственно"полиграфическое предприятие, г. Ужгород,оектная, 4 11 29034 анализа группы, выход 1-го элемента анализа группы подключен.к )-му входу выходного элемента ИЛИ, прямой выход которого является прямым выходом узла, а инверсный выход выходного эле 5 мента,ИЛИ является инверсным выходом узла, единичный выход каждого -го разряда,)-го регистра группы подключен к -му входу -го элемента ИЛИ запрета группы, прямой выход которого 10 подключен к (ш+1)-му входу 1-го элемента И анализа группы, а инверсный выход каждого -го элемента ИЛИ запрета группы, кроме первого, подключен к первому входу 1-го (1 =2 , и) 15 элемента И блокировки группы, второй 5 12вход которого подключен к прямому выходу (3-1)-го элемента ИЛИ запретагруппы, вторые входы всех элементовИ записи всех групп объединены и являются входом разрешения записи кодаузла, входы установки в нуль всехрегистров группы объединены и являются установочным входом узла, третьивходы всех элементов И записи каждой,)-го элемента И блокировки группы,объединенные третьи входы элементовИ записи первой группы подключены кинверсному выходу первого элементаИЛИ запрета группы.