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

(21)4254592/24-24

(22)02.06.87

(А6) 30.11.88. Бюл. № 44

(72) Е.И. Бороденко, Л.Г. Подзубанов,

В.А. Синица и В.В. Верияскин

(53)681.325(088,8)

(56)Авторское свидетельство СССР fS 637822,, кл. G 06 F 15/20, 1978.

Авто.рское свидетельство СССР № 896630, кл. G 06 F 15/20, 1982.

(54)УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФОВ

(57)Изобретение относится к области вычислительной техники и может быть использовано для определения связ-

ности графов, в том числе ориентированных графов, являющихся математи- ческ1-тми моделями сетей CBHSVI, вычислительных сетей. Цель изобретения - расширение функциональных возможностей за счет оценки связности сильно и слабо связных ориентированных графов - достига.;тся тем, что в устройство, содержащее матрицы триггеров и элементов И, группу элементов ИЛИ и элемент И, дополнительно введены матрица элементов ИЛИ, с второй по 4eTBeptyio группы элементов ИЛИ, группа элементов И, первый и второй элементы задержки, с первого по третий элементы НЕ, с второго по шестой элементы И, 2 ил.

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

Цель изобретения - расширение функциональных возможностей устрой- ства за счет оценки связности сильно и слабо связных ориентированных графов.

Функциональная схема устройства показана на фиг. 1 и 2.

Устройство содержит матрицы триггеров 1, матрицу элементов И 2, матрицу элементов ИЛИ 3, первую группу элементов ИЛИ 4, вторую группу элементов ИЛИ 5, третью группу эле- ментов ИЛИ 6, группу элементов И 7, парвый элемент И 8, первый 9 и второй 10 элементы задержки, первый П и второй 25третий 13 элементы НЕ, второй 14, третий 15, четвертьш 16, пятый 17 элементы И, блок 18 индикации, четвертую группу элементов И 19 шестой элемент И 20, вход 21 начальной установки устройства, установочные входы 22 триггеров 1 матрицы, вход 23 пуска устройства.

Блок 17 содержит три индикатора, соответствующие трем входам: первый сигнализует о сильной связности гра- фа, второй о слабой связности гра- фа, третий - граф не связен.

Устройство работает следу1 1цим образом.

Предварительно происходит установ ка в нулевое состояние всех триггеро 1 матрицы подачей сигнала на вход 2 начальной установки устройства. За тем на установочные входы 22 триггеров матрицы передаются двоичные сиг- налы (нуль или единица), определяемы значениями соответствующих элементов матрицы смежности исследуемого графа После этого подается потенциал на вход 23 пуска устройства, который попадает на вход первого элемента ИЛИ 5 второй группы и вход первого элемента 9 задержки. На выходе первого

.элемента ИЛИ 5 первой группы появляется сигнал, который попадает на первые входы элементов ИЛИ 3 первой строки матрицы элементов ИЛИ и далее на вторые входы элементов И 2 певой строки матрицы элементов И.Если

0 5 0

5

0

5

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

Если К-й триггер 1 первой строки находится в единичном состоянии, то сигнал с его выхода поступает через соответствующий элемент И 2 на первый вход К-гд элемента ИЛИ 4 первой группы и на К-й вход первого элемента ИЛИ 6 третьей группы, сигнал с выхода К-го элемента ИЛИ 4 попадает на вход первого элемента И 8 и через К-й элемент ИЛИ 5 - на первые входы элементов ИЛИ 3 К-й строки матрицы элементов ИЛИ и далее на вторые входы элементов И 2 К-й строки матрицы элементов И, сигнал с выхода первого элемента ИЛИ 6 попадает на вход первого элемента И 8.

Если является сильно связным, то в результате таких переключений на всех входах первого элемента И 8 имеется сигнал 1, в противном случае на всех входах хотя бы одного элемента ИЛИ 4 первой группы или элемента ИЛИ 6 третьей группы отсутствуют сигналы и элемент И 8 не срабатывает. Сигнал с элемента И 8поступает на перв)1Й вход элемента И 15.

Время задержки первого элемента 9 задержки подобрано с учетом всех переключений для определения сильной связности графа. Поэтому сигнал с выхода элемента И 8 поступает до появления сигнала с выхода элемента 9 задержки, значит, на выходе элемента НЕ 12 сигнал есть и срабатьюает элемент И 5, выход которого подклю- чен к первому входу блока 18, г.игна- лизиру10,;1его о С льной связности графа.

Если граф не сильно связен и на выходе элемента И 8 нет сигнала, то на выходе первого элемента НЕ I сигнал есть, поэтому при появлении сигнала на выходе первого элемента 9 задержки срабатывает второй элемент И 14, сигнал с которого попадает на управляющие входы группы элементов И 7. Сигнал с выхода элемента Н 4 попадает на вход первого элемента

Ш1И 5 н с его вы-хода попадает на первые входы элементов ИЛИ 3 первой строки матрицы и через первый элемент И 7 группы - на вторые входы элементов ИЛИ 3 первого столбца матрицы элементов ИЛИ и далее на вторые ,входы элементов И 2 первой строки и первого столбца матрицы элементов И. Если первая вершина слабо связана хотя бы с одной вершиной, то соответственно триггер 1, первой строки или первого столбца находится в единичном состоянии, В противном случае все триггеры первой строки и первого столбца находятся в нулевом состоянии, граф является не связныь, ка всех входах первого элемента ИЛИ 4 первой группы и первого элемента Р.ИИ 6 третьей группы - нули, на входах первого элемента ИЛИ 19 четвертой группы - нули.

Если К-й триггер 1 первой строки находится в единичном состоянии, то

с п нал с его выхода поступает через

соответствующий элемент И 2 на пер- вый вход К-го элемента ИЛИ 4 первой группы, на вход первого элемента ИЛИ 6 третьей группы, сигнал с выхода К-го элемента ИЛ11 4 попадает на пер- вьш вход К-го элемента ИЛИ 19 и через К.-й элемент ИЛИ 5 - на первые входы эле:- ентов liTIH 3 К-й строки, а через К-й элемент И 7 - на вторые входы элементов ИЛИ 3 К-го столбца матрицы и далее на вторые входы элементов И 2 К-й строки и К-го столбца матрицы элементов И, сигнал с выхода первого элемента ИЛИ 6 попадает на }зторой вход первого элемента ИЛИ 19.

Если граф является слабо связным, то в результате таких переключений на всех входах шестого элемента И 8 имеется сигнал, в противном случае на выходе хотя бы одного элемента ИЛИ I9 четвертой группы отсутствует сигнал и элемент И 20 не срабатывает. Сигнал с элемента И 20 поступает на второй вход, элемента И 16 и вход эле- элемента НЕ 13.

При наличии сигнала на выходе элемента И 14 и элемента И 20 срабатывает элемент И 16, выход которого подключен к второму входу блока 18, сиг- нализиругощему о слабой связности гра сра.

Время задержки второго элемента 10 задержки подобрано с учетом всех

5

5

0 5 0

5 Q

g

переключений для определения слабой связности графа. Поэтому при появлении сигнала на выходе элемента 10 задержки и отсутствии сигнала на выходе элемента И 20 на выходе элемент НЕ 13 сигнал есть, срабатьгоает элемент И 17, выход которого подключен к третьему входу блока 18.

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

Устройство для исследования параметров графов, содержащее матрицу триггеров, матрицу элементов И (раз-мерность матриц равна РхР, где F - количество узлов в исследуемом графе) , первый элемент И и первую группу элементов ИЛИ, вь{ходы которых соединены с соответствующими входами с первого по Р-й первого элем ента И. выход элемента И К-й строки и М-го столбца матрицы соединены с К-м входом М-го элемента ИЛИ цервой группы (где К,,...,Р), прямой выход три1- гера К-й строки и М-го столбца матрицы соединен с первым входом элемента И К-й строки и М-го столбца матрицы, установочные входы триггеров матрицы являются установочными входами устройства, входы сброса триггеров матрицы соединены между, собой и являются входом начальной установки устройства, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет оценки связности сильно и слабо связных ориентированных графов, в него введены матрицы элементов ИЛИ, вторая, третья и четвертая группы элементов ИЛИ, группы элементов И, первый и второй элементы задержки, первый, второй и третий элементы НЕ, с второго по шестой элементы И, выход второго элемента И соединен с первым входом четвертого элемеЛа И и первыми входами элементов И группы, вторые входы которых соединены с выходами соответствующих элементов ИЛИ второй группы и с первыми входами всех элементов ИЛИ соответствующей строки матрицы, выход элемента ИЛИ К-й строки и М-го столбца матрицы соединен с вторьм входом элемента М К-й строки М-го столбца матрицы, вторые входы элементов ИЛИ М-го столбца матрицы соелинены с выходом М-го элемента И группы, К-й вход М-го элемента ИЛИ третьей группы соединен с М-м входом К-го элемента

ИЛИ первой группы, выход К-го элемента ИЛИ третьей группы соединен с первым входом К-го элемента ИЛИ второй группы, с первьм входом К-го элемен- та ИЛИ четвертой группы, (Р+К)-м входом первого элемента И, выход которого соединен с первым входом третьего элемента И, и входом первого элемента НЕ, выход KOTOpsoro соединен с первым входом второго элемента И, второй вход которого соединен с выходом первого элемента задержки, входом второго элемента задержки и входом второго элемента НЕ, выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с выходом третьего элемента НЕ, вход которого соединен с втос выходом шестого элемента И, К-й вход которого соединен с выходом К-го элемента ИЛИ четвертой группы, второй вход которого соединен с вторым входом К-го элемента ИЛИ второй группы и выходом К-го элемента ИЛИ первой группы, третий вход первого элемента ИЛИ второй группы соединен с выходом второго элемента И, выход второго элемента НЕ соединен с вторым входом третьего элемента И, четвертый вход первого элемента ИЛИ второй группы и вход первого элемента задержки объединены и являются входом пуска устройства, выходы третьего, четвертого и пятого элементов И являются соответственно, первым, вторым и третьим выходами ус;тройст

рым входом четвертого элемента И и 20 ва.

ЦЗШ.1

Фи2.2