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

 

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

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

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

РЕСПУБЛИК (51)4 G 06 F 15/20

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3940682/24-24 (22) 06.08.85 (46) 15.02.87. Бюл. И 6 (72) В. N. Полищук, Н. И. Крылов и В. В. Соколов (53) 681.335(088.8) (56) Авторское свидетельство СССР

Р 1056206, кл. G 06 Г 15/31, 1983.

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

И 987616, кл. G 06 F 5/02, 1983.

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

11 271906, кл. G 06 7 7/48, 1974.

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

Р 888128, кл. G 06 F 15/20, 1981.

„„ЯЦ„„1290345 А ) (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, 0 группу счетчиков 8, группу элементов

ИЛИ 9, группу элементов И 10, счетчик

11, первый, второй и третий триггеры 12-14 задания режимов, триггер 15, первый, второй, третий и четвертый элементы И 16-19,-первый, второй, третий и четвертый элементы ИЛИ 20-23 первый, второй и третий элементы 2426 задержки, пятый элемент ИЛИ 27, переключатель 28 режимов работы, вход 29 устройства, выход 30 окончания работы устройства, четвертый эле мент 31 задержки.

Узел 2 сравнения (фиг. 2) содержит п групп элементов И 32 записи, и групп элементов ИЛИ 33 сравнения, группу из п э л еeмMеetнтов ИЛИ 34 запрета, группу из и-1 элементов И 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 первой группы. Очередные коды последовательно записываются в регистры 42 и хранятся в них. Сравнение кодов в узле 2 заключается в проверке факта покрытия единичными разрядами кода, находящегося на информационных входах узла, всех единичных разрядов хотя бы одного из кодов, хранящихся в регистрах 42. Проверка осущест,вляется следующим образом. С информационных входов узла сравнения на входы элементов ИЛИ 33 подается прямой код слова. На вторых входах элементов ИЛИ 33 каждой отдельной группы постоянно находятся в инверсном коде сигналы слов, записанных в соответствующих регистрах 42. Если имеет место факт покрытия единичными разрядами входного кода всех единичных разрядов кода, записанного в каком-либо регистре 42, то на выходах элементов ИЛИ 33 соответствующей группы будут находиться единичные сигналы,,которые поступают на входы соответствующего элемента И 36. В этом случае единичный сигнал на выходе элемента И 36 появится лишь при наличии единичного сигнала на прямом выходе элемента

ИЛИ 34, соединенного с входами данного элемента И 36 (это необходимо для исключения из рассмотрения регистров 42, находящихся в нулевом состоянии). Единичный сигнал, полученный хотя бы на одном из элементов И 36, передается через выходной элемент ИЛИ 37 на выходы 41 узла 2 сравнения.

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

50

55 необходимого количества ребер с по5

1О

20 держит только две !, расположенные в столбцах, инцидентных данной строке: остальные элементы строки равны

"О". Единичные элементы матрицы в блоке 5 наборного поля фиксируются путем замыкания соответствующих контактов. Первые контакты блока 5, относящиеся к отдельным строкам, подключены к отдельным выходам разрядов блока 3 выделения единиц, а вторые контакты блока 5, относящиеся к отдельным столбцам, подключены к входам отдельных элементов ИЛИ 9, выходы которых соединены с тактовыми входами соответствующих счетчиков 8.

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

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

Проверка того, является данная совокупность ребер простой цепью (циклом) или нет, осуществляется на основе использования следующего факта, вывытекающего из свойства матрицы инцидентности графа: любая совокупность строк матрицы, образующая простую . цепь между двумя какими-.либо вершинами графа, содержит в столбцах, соответствующих этим вершинам, ровно по одной "1", а в каждом из других оставшихся столбцов — либо ровно две

"I", либо ни одной (если же эта цепь замкнута, т.е. образует цикл, то в лЫбом столбце содержится либо ровно две "1", либо не содержится ни одной).

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

1290345 6

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

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

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

Первый режим. Работа начинается по сигналу, поданному на вход 29 устройства, который устанавливает в нулевое состояние счетчик ll, триггеры

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

2 сравнения находятся в нулевом состоянии, а на информационные входы узла 2 подается некоторый код с выхода блока 4, то сравнения в узле 2 не происходит, Тогда на прямом выходе узла 2 — "0", а на инверсном—

1О "1". В этом случае элемент И 17 закрыт, а элемент И 16 открыт, и сигналы от генератора 1 через элемент

И 16 поступают на тактовый вход бло15

55 ка 3. При этом просматривается последовательно вся совокупность строк

I матрицы инцидентности, сформированная в блоке 4 перебора сочетаний, и на счетчиках 8 подсчитывается количестIt 1t во 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 по3 является сигнал, который проходит открытый элемент И 19 и поступает на вход 40 записи кода узла 2 сравне7 12903 ния, чем обеспечивается запись в узле сравнения кода, находящегося на его информационных входах, т.е.. записывается код совокупности ребер графа, образующей искомую простую цепь (цикл). Зтот же сигнал увеличивает содержимое счетчика 11 на единицу и через элемент ИЛИ 27 сбрасывает в.нуль триггер 12, чем обеспечивается выдача с инверсного выхода элемента ИЛИ 20 сигнала окончания работы устройства, а с прямого выхода — запрещающего потенциала на элемент И 18. Сигнал с выхода блока 3 поступает также на элемент ИЛИ 21 и с его выхода сбрасывает триггер 15 в нуль и прекращает подачу тактовых сигналов с генератора 1. При несовпадении кодов регистра 7 и выходов счетчиков 8 элемент И 19 закрывается. 2

В этом случае сигнал с выхода блока

3 через элемент И 19 не проходит, а . поступает на вход элемента ИЛИ 21 и с его выхода осуществляет описанные 2 ранее действия, т.е. формирует новое сочетание, которое в дальнейшем проверяется, образует оно простую цепь (цикл) или нет. Если после проверки всех сочетаний для заданного количества ребер совпадения кодов в блоке

6 не происходит, то сигнал с первого выхода окончания работы блока 4 перебора сочетаний проходит через элемент ИЛИ 27 и устанавливает в нуль триггер 12, чем обеспечивается окончание работы устройства. В данном слуслучае счетчик ll устройства, а также все регистры 42 узла 2 сравнения находятся в нулевом состоянии.

Второй режим работы устройства отличается тем, что сигналом с входа

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

11, а сами коды найденных совокупностей ребер записываются в регистры

42 узла 2 сравнения.

45 8

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

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

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

1, n), выход второго разряда

1290345 каждого i-го счетчика группы подключен к второму входу i-го элемента И группы, выход каждого 1-го элемента

И группы подключен к. i-му входу четвертого элемента ИЛИ, выход которого подключен к первому входу второго

:элемента ИЛИ, второй вход которого подключен к выходу второго элемента

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

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

i-го разряда регистра подключен к

i-му входу второй группы входов блока сравнения, выход которого подклю.чен к второму входу четвертого элемента И, выход четвертого элемента

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

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

i-ro разряда блока выделения единиц подключен к i-й горизонтальной шине наборного поля, соответствующей i-й строке матрицы инцидентности исследуемого графа, à j-й вход каждого i-го элемента ИЛИ группы (где i = I, n;

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

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

)й группы (где i = Г, и..; j = Г; и ;

m — - число разрядов в регистре; ив количество регистров в группе) подключен к входу i-ro разряда g-ro регистра группы, нулевой выход i-го разряда,,1-го регистра подключен к . второму входу i-ro элемента ИЛИ сравнения j-Й группы, выход которого подключен к i-му входу j-го элемента И

Фиа2

Составитель Т. Сапунова

Редактор И. Рйбченко Техред 1I.Сердюкова Корректор А. Тяско

Заказ 7904/48

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

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

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

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

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

5 12 вход которого подключен к прямому выходу (j-1)-ro элемента ИЛИ запрета группы, вторые входы всех элементов

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

j-й группы, кроме первой группы, объединены и подключены к выходу

J-го элемента И блокировки группы, объединенные третьи входы элементов

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

ИЛИ запрета группы.