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

цепи) между двумя вершинами графа с заданным количеством ребер или всех (одного) циклов с заданным количеством ребер. Эти операции необходимы при исследовании надежности систем и решении других задач анализа информационных сетей, отображаемых графами. Поставленная цель достигается тем, что в устройство, содержащее блок перебора сочетаний 4, блок сравнения 6, наборное поле 5, генератор импульсов 1, регистр 7, счетчик П, первый 16 и второй 17 эле15

t

Изобретение относится к вычислиельной технике и может быть испольовано для определения простых цепей циклов графа при исследованиях инормационных сетей, отображаемьгх 5 рафом.

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

На фиго 1 представлена структурная схема устройства; .на фиг. 2 - структурная схема узла сравнения. 25

Устройство содержит (фиг. 1) генератор 1 импульсов, узел 2 сравнения, блок 3 вьщеления единиц, блок 4 перебора сочетаний, блок 5 наборного поля, блок 6 сравнения, регистр 7 зо группу счетчиков 8, группу элементов ИЛИ 9, группу элементов И 10, счетчик 11, первый, второй и третий триггеры 12-14 задания режимов, триггер 15, первый, второй, третий и четвертый элементы И 16-19,-первый, второй, третий и четвертый элементы ШШ 20-23 первый, второй и третий элементы 2420

35

90345

менты И, первый 20 и второй 21 элементы тИ, введены блок выделения единиц 3, узел сравнения 2, группа счетчиков 8, группа элементов ИЛИ 9, группа элементов И 10, первый 12, второй 13, третий 14 триггеры задания режимов, третий 18 и четвертый 19 элементы И, третий 22, четвертый 23 и пятый 27 элементы ШШ, первый 24, второй 25, третий 26 и четвертый 31 элементы задержки, переключатель режимов 28, 2 ило 1 з.п-ф-лы.

15

5

5

о

0

35

26 задержки, пятый элемент ШШ 27, переключатель 28 режимор работы, вход 29 устройства, выход 30 окончания работы устройства, четвертый элемент 31 задержки.

Узел 2 сравнения (фиг. 2) содержит П групп элементов И 32 записи, пгрупп элементов ИЛИ 33 сравнения, группу из п элементов ИЛИ 34 запрета, группу из п-1 элементов И 35 блокировки, группу из п элементов И 36 анализа, выходной элемент ИЛИ 37, информационные входы 38 узла, вход 39 установки регистров в нуль, вход 40 разрешения за- записи кода, выходы 41 узла, группу из п регистров 42.

Генератор 1 импульсов вьщает тактовые сигналы, период следования ко- , торых должен быть не меньше суммарного времени переходных процессов в блоке 3 вьщеления единиц, времени за- держки сигнала на элементе ИЛИ 21 и времени переключения триггера 15

Узел 2 сравнения выполняет функции сравнения и хранения кодов искомьпс простых цепей (циклов) исследуемого графа« записьшаются и хранятся в регистрах 42 узла. В исходное (нулевое) состояние регистры устанавливаются: сигналом с установочного входа. Запись кода, поступившего на информационные входы 38 узла, осуществляются только по сигналу, поступающему на вход 40 разрешения записи ода„ Дл:я этого вход 40 имеет связь с вторыми входами всех элементов И 32,а каждая отдельная шина информационных входов 38 подключена к первым входам всех элементов И 32, относящихся к одному разряду, Разре шение на запись -кода в соответству- юпшй регистр 42 (за исключением пер вого) через соответствующую группу элементов И 32„осуществляются потен циалом с выхода соответствующего элемента И 35, который подключен к входам элементов И 32 соответствующей группыо Разрещающий потенциал на запись кода в первый регистр 42 (на фиг. 2 справа), когда он находится в нулевом состоянии, поступает с инверсного выхода элемента ИЛИ 34 на все элементы И 32 первой группы. Очередные коды последовательно записьтаются в регистры 42 и хранятся в них. Сравнение кодов в узле 2 заключается в проверке факта покрытия единичными разрядами кода, находящегося на информационных входах узла, всех единичных разрядов хотя бы одного из кодов, хранящихся в регистрах 42. Проверка осуществляется следующим образом. С информационных входов узла сравнения на входы элементов ИЛИ 33 подается прямой код .слова. На вторых входах элементов ИЛИ 33 каждой отдельной группы постоянно находятся в инверсном коде сигналы слов, записанных в соответствующих регистрах 42. Если имеет место факт покрытия единичными разрядами входного кода всех единичных разрядов кода, записанного в каком-либо регистре 42, то на выходах элементов ИЛИ 33 соответствующей группы будут находиться единичные сигналы, .которые поступают на входы соответствующего элемента И 36. В этом случае единичный сигнал на выходе элемента И 36 появится лищь при наличии единичного сигнала на прямом вькоде элемента ИЛИ 34, соединенного с входами данного элемента И 36 (это необходимо для исключения из рассмотрения регистров 42, находящихся в нулевом состоянии) Единичный сигнал, по- лу енньй хотя бы на одном из элементов И 36, передается через выходной элемент ШШ 37 на выходы 41 узла 2 сравнения.

Блок 5 наборного поля предназначен для задания графа в виде матрицы инцидентности, строки которой соответствуют ребрам, а столбцы - вершинам графа. Каждая матрица со290345

держит только две 1, расположенные в столбцах, инцидентных данной строке: остальные элементы строки равны О. Единичные элементы матрицы в 5 блоке 5 наборного поля фиксируются

путем замыкания соответствующих контактов. Первые контакты блока 5, относящиеся к отдельным строкам, подключены к отдельным выходам разрядов

О блока 3 вьщеления единиц, а вторые контакты блока 5, относящиеся к отдельным столбцам, подключены к входам отдельных элементов ШШ 9, выходы которых соединены с тактовыми вхо дами соответствующих счетчиков 8.

Блок 4 перебора сочетаний предназначен для формирования кодов совокупностей ребер графа, которые затем проверяются, составляет каждая из них

20 отдельную простило цепь (цикл) или нет. Информационные выходы блока 4 соединены с информационными входами блоков 2 и 3.

25 Блок 3 вьщеления единиц 2 предназначен для выборки каждого отдельного ребра из совокупности, сформированной в блоке 4.

Проверка того, является данная со30 вокупность ребер простой цепью (циклом) или нет, осуществляется на основе использования следующего факта, вы- вытекающего из свойства матрицы инцидентности графа: любая совокупность

35 строк матрицы, образующая простую . цепь между двумя какими-либо верщина- ми графа, содержит в столбцах, соот- ветствующих этим верщинам, ровно по одной 1, а в каждом из других ос40 тавщихся столбцов - либо ровно две 1, либо ни одной (если же эта цепь замкнута, Тое образует цикл, то в ЛЕйбом столбце содержится либо ровно две 1, либо не содержится ни одной).

45 Формально этот факт может иметь место и тогда, когда совокупность ребер образует простую цепь и еще дополнительно один или несколько не пересекающихся между собой циклов (два и

50 более непересекающихся цикла). Эти явления в устройстве определяются узлом 2 сравнения в процессе построения простых цепей (циклов), начиная поиск из минимально возможного или

55 необходимого количества ребер с последующим увеличением этого количества. Выявленные таким образом совокупности ребер в устройстве не фиксируются.

Вершины графа, между которыми отыскиваются простыв цепи, задаются на регистре 7, разрядные выходы которог представляют собой номера вершин.

Блок 6 сравнения необходим для определения факта сравнения кода, записанного в регистре 7, и кода, снимаемого с первых разрядов двухразрядных счетчиков 8, в каждом из которых подсчитывается количество 1 в соответствующем столбце рассматривае- мой совокупности строк.

Устройство работает в трех режимах, которые задаются переключателем 28 режимов. Первый режим - определение одной простой цепи (одного цикла с заданным количеством ребер. Второй режим - определение всех простых цепей (циклов) с заданным количеством ребер. Третий режим - определение всех простых цепей (циклов) с количеством ребер, равным или большим заданному. В каждом режиме перед началом работы в блоке 4 перебора сочетаний устанавливаются в 1 первые младпше разряды регистра блока в количестве, равном требуемому исходному количеству ребер. Если определя- .ются простые цепи, то в регистре 7 устройства устанавливаются в 1 два разряда с номерами, равными номерам вершин, между которыми определяются простые цепи. Если определяются циклы, то все разряды регистра 7 должны содержать О. После описанных вьш1е начальных установок устройство в каждом режиме работает следующим образом.

Первый режим. Работа начинается по сигналу, поданному на вход 29 устройства, который устанавливает в нулевое состояние счетчик 11, триггеры 12-14 задания режимов, регистры 42 узла 2 сравнения, поступает на вход элемента ИЛИ 22 я с его выхода устанавливает в нулевое состояние счетчики В, блок 3 выделения единиц, а затем с задержкой на элементе 26 поступает на вход установки в единичное состояние триггера 15 и вход .установки кода блока 3 выделения единиц (элемент 26 задерживает сигнал на время переходных процессов в блоке 5 при установке его в нулевое сост ояние). Этот же сигнал, задержанный на элементе 24, через эамкнутые контакты переключателя 28 устанавливает триггер 12 в единичное

состояние (задержка необходима на время переходных процессов в триггере). Поскольку все регистры 42 узла 2 сравнения находятся в нулевом состоянии, а на информационные входы узла 2 подается некоторый код с выхода блока 4, то сравнения в узле 2 не .происходит. Тогда на прямом выходе узла 2 - О, а на инверсном . В этом случае элемент И 17 закрыт, а элемент И 16 открыт, и сигналы от генератора 1« через элемент И 16 поступают на тактовый вход блока 3. При этом просматривается последовательно вся совокупность строк матрицы инцидентности, сформированная в блоке 4 перебора сочетаний, и на счетчиках 8 подсчитывается количество 1, содержащихся в каждом столбце этой совокупности строк Если в процессе последовательного вьщеления единиц в блоке 3 на каком-либо из счетчиков 8 зафиксируется более двух 1, то на выходе соответствующего элемента И 10 появляется сигнал, который проходит через элементы ИЛИ 23, 21 и устанавливает триггер 15 в нуль, чем обеспечивается прекращение подачи сигналов от генератора 1 на тактовый вход блока 3 выделения единиц. Этот же сигнал с выхода элемента ИЛИ 21 поступает на тактовый вход блока 4 и обеспечивает формирование очередного сочетания, задерживается

на элементе 25 задержки (время задержки определяется переходными процессами в блоке 4 перебора сочетаний) и поступает на вход элемента И 18, который открыт потенциалом с прямого выхода элемента ИЛИ 20, так как триггер 12 находится в единичном состоянии. С выхода элемента И 18 сигнал прохо ит через элемент ИЛИ 22 и выполняет действия, описанные выше.

Если в процессе последовательного выделения единиц блоком 3 переполнения счетчиков 8 не происходит, то после завершения работы блока 3 выполняется сравнение содержимого регистра 7 и кода, снимаемого с первых разрядов счетчиков 8. При совпадении указанных кодов элемент И 19 потенциалом с выхода блока 6 открывается. В этом случае в следующем такте на

выходе окончания работы 3 появляется сигнал, который проходит от- крытьй элемент И 19 и поступает на вход 40 записи кода узла 2 сравне

ния, чем обеспечивается запись в узле сравнения кода, находящегося на его информационных входах, т.е. записывается код совокупности ребер графа, образующей искомую простун) цепь (цикл). Этот же сигнал увеличивает содержимое счетчика 11 на единицу и через элемент ИЛИ 27 сбрасьгоа ет в,нуль триггер 12, чем обеспечивается выдача с инверсного выхода элемента ИЛИ 20 сигнала окончания работы устройства, а с прямого выхода - запрещающего потенциала на элемент И 18. Сигнал с выхода блока 3 поступает также на элемент ИЛИ 21 и с его выхода сбрасьтает триггер 15 в нуль и прекращает подачу тактовых сигналов с генератора 1. При несовпадении кодов регистра 7 и выходов счетчиков 8 элемент И 19 закрывается В этом случае сигнал с выхода блока 3 через элемент И 19 не проходит, а поступает на вход элемента ИЛИ 21 и с его выхода осуществляет описанны ранее действия, т.е. формирует новое сочетание, которое в дальнейщем проверяется, образует оно простзто цепь (цикл) или нет. Если после проверки всех сочетаний для заданного количества ребер совпадения кодов в блоке 6 не происходит, то сигнал с первого выхода окончания работы блока 4 перебора сочетаний проходит через элемент ИЛИ 27 и устанавливает в нуль триггер 12, чем обеспечивается окон- чание работы устройства. В данном сл случае счетчик 11 устройства, а также все регистры 42 узла 2 сравнения

находятся в нулевом состоянии.

(

Второй режим .работы устройства отличается тем, что сигналом с входа 29 устройства через элемент 24 задержки и замкнутые контакты переключателя 28 устанавливается в единичное состояние триггер 13. Кроме того, окончание работы устройства происходит только по сигналу с первого выхода окончания работы блока 4, ко- торый сбрасывает триггер 13 в нуль, т,е. после того, как будут проанализированы все сочетания с заданным количеством ребер. При этом число простых цепей с заданным количеством рэбер графа фиксируется в счетчике 11, а сами коды найденных совокупностей ребер записьшаются в регистры 42 узла 2 сравнения.

5

0

0

В третьем режиме работа устройства отличается тем, что сигнал начала работы с входа 29 устанавливает в единичное состояние триггер 14, который сбрасывается только сигналом с второго выхода окончания работы блока 4 перебора сочетаний, т.е. после того, как будут сформированы и проверены все возможные сочетания ребер, начиная с заданного количества. .На счетчике 11 фиксируется количество всех простых цепей (циклов), а их коды записываются в регистры 42 узла 2 сравнения.

Формула изобретения

1, Устройство для исследования графов, содержащее блок перебора сочетаний, блок сравнения, наборное поле, генератор импульсов, регистр, счетчик, первый и второй элементы И, первый и второй элементы ИЛИ, о т - лича -ющееся тем, что, с целью расширения функциональных возмож- ностей устройства за счет определения циклов, в него введены блок выделения единиц, узел сравнения, группа счетчиков, группа элементов ИЛИ, группа элементов И, первый, второй и третий триггеры задания режимов, третий и четвертый элементы И, третий, четвертый и пятый элементы ИЛИ, первый, второй, третий и четвертый элементы задержки, триггер и переключатель режимов работы, причем вход первого элемента задержки является входом устройства, выход первого элемента задержки подключен к подвижному контакту переключателя режимов работы, первые входы установки в нуль первого, второго и третьего триггеров задания режима объединены между собой, соединены с входом установки в нуль счетчика, с установочным входом узла сравнения, с первым входом третьего элемента ИЛИ и с входом первого элемента задержки, выход третьего элемента ИЛИ подключен к входу установки в нуль блока выделения единиц, к входу третьего элемента задержки, к входам установки в нуль счетчиков группы, выход первого разряда каждого 1-го счетчика группы подключен к i-му входу первой группы входов блока сравнения и подключен к первому входу i-ro элемента И группы fi 1, п), выход второго разряда

каждого 1-го -счетчика группы подключен к второму входу i-ro элемента И группы, выход каждого i-ro элемента И группы подключен к, 1-му входу четвертого элемента ИЛИ, выход которого подключен к первому входу второго :элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, тре тий вход второго элемента ИЛИ подключен к выходу четвертого элемен та задержки, выход второго элемента ИЛИ подключен к тактовому входу блока перебора сочетаний, к . входу установки в нуль триггера и к входу второго элемента задержки, выход которого подключен к первому входу третьего элемента И, второй вход которого подключен к прямому выходу первого элемента ИЛИ, инверсный выход которого является выходом окончания работы устройства, выход третьего элемента И подключен к второму входу третьего элемента ИЛИ, каждый вход первого элемента ИЛИ подключен к прямому выходу одноименного триггера задания режима, первый, второй и третий неподвижные контакты переключателя режимов работы соединены с входами установки в единицу соотв.етственно первого, второго и третьего триггеров задания режимов работы, выход третьего элемента задержки подключен к входу установки в единицу триггера и k входу установки кода блока вьщеления единиц, выход окончания работы которого подключен к входу четвертого элемента задержки и к первому входу четвертого элемента И, выход каждого 1-го разряда регистра подключен к i-му входу второй группы входов блока сравнения, выход которого подклю, чен к второму входу четвертого элемента И, выход четвертого элемента И подключен к первому входу пятого элемента ИЛИ, к счетному входу счетчика и к входу разрешения записи кода узла сравнения, прямой выход которого подключен к первому входу второго элемента И, а инверсный выход узла сравнения подключен к первому входу первого элемента И, вторые входы первого и второго элементов И объединены и подключены к прямому выходу триггера, третьи входы первого

и второго элементов И объединены и подключены к выходу генератора импуль сов, выход окончания перебора всех возможных сочетаний блока перебора

- 10

f5

20

25

1290345 0

сочетаний подключен к второму входу пятого элемента ИЛИ и к второму входу установки в нуль второго триггера задания режима работы, выход пятого элемента ИЛИ соединен с вторым входом установки в нуль первого триггера задания режима, выход окончания перебора части сочетаний .блока перебора сочетаний подключен к второму входу установки в нуль первого триггера задания режима, группа информационных выходов блока перебора сочетаний подключена соответственно к группе информационных входов блока выделения единиц и к группе информационных входов узла сравнения, выход каждого i-ro разряда блока выделения единиц подключен к i-й горизонтальной шине наборного поля, соответствующей i-й строке матрицы инцидентности исследуемого графа, а j-й вход каждого i-ro элемента. ИЛИ группы (где i Г, п; j 1, п) подключен к j-й вертикальной шине i-й группы вертикальных шин наборного поля, соответствующим столбцам матрицы инцидентности исследуемого графа, выход каждого i-ro элемента ИЛИ группы подключен к счетному входу i-ro счетчика группы, выход первого элемента И соединен с тактот. вьм входом блока выбора единиц. ;. 2. Устройство по п, , отличающееся тем, что узел сравнения содержит группу из п регистров, 35 п групп элементов И записи, п групп элементов ИЛИ сравнения, группу из п элементов ИЛИ запрета, группу из п-1 элементов И блокировки, группу из п элементов И анализа, выходной элемент ИЛИ, причем первые входы оД7 поименных элементов И записи всех групп объединены и являются соответ- ствзтощим входом группы информационных входов узла, первые входы одноименных элементов ИЛИ сравнения всех групп объединены между собой и объ- единецы с первыми входами одноименных элементов И записи групп, выход каждого i-ro элемента И записи каждой j-й группы (где i Г7 ш; j 1 , п ; m - число разрядов в регистре; п - количество регистров в группе) подключен к входу 1-го разряда J-ro регистра группы, нулевой выход i-ro разряда.j-ro регистра подключен к- второму входу i-ro элемента ИЛИ .сравнения j-й группы, выход которого подключен к i-му входу j-ro элемента И

30

40

45

50

10

;. 35

анализа группы, выход j-ro элемента анализа группы подключен.к j-му входу выходного элемента ИЛИ, прямой выход которого является прямым выходом уз ла, а инверсный выход выходного эле- мента.ИЛИ является инверсным выходом узла, единичный выход каждого i-ro разряда J-ro регистра группы подключен к i-му входу j-ro элемента ИЛИ запрета группы, прямой выход которого подключен к (т+1)-му входу J-ro элемента И анализа группы, а инверсный выход каждого j-ro элемента ИЛИ запрета группы, кроме первого, подклю- чен к первому входу J-ro (j 2 , п) элемента И блокировки группы, второй

вход которого подключен к прямому выходу (j-l)-ro элемента ИЛИ запрета группы, вторые входы всех элементов И записи всех групп объединены и являются входом разрешения записи кода узла, входы установки в нуль всех регистров группы объединены и являются установочным входом узла, третьи входы всех элементов И записи каждой J-й группы, кроме первой группы, объединены и подключены к выходу j-ro элемента И блокировки группы, объединенные третьи входы элементов И записи первой группы подключены к инверсному выходу первого элемента ИЛИ запрета группы.

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

Составитель Т. Сапунова Редактор И. Рыбченко Техред Л.Сердюкова Корректор А. Тяско

Заказ 7904/48

Тираж 673Подписное

ВНШШИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г Ужгород, ул. Проектная, 4