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

 

СООЗ СОВЕТСНИХ . СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) А1 (Sn4 G 06 F 15?0

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

P: А Б ГОРСКОМ У СВИДЕТЕЛЬСТВУ

I (»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4254592/24-24 (22) 02.06.8! (46) 30.11.88. Бюл. У 44 (72) Е.И, Бороденко, Л.Г. Подзубанов, В.A. Синица и В.В. Верияскин (53) 681.325(088.8) (56) An горское снидетельство СССР

Р 637822,, кл. G 06 F 15/20, 1978.

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

11 896630, кл. С 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАИКТРОВ 1 РАФОВ (57) Изобретение nòíîñèòñÿ к обЛасти вычисли-:ельной техники и может быть использовано для определения связ» ности графов, в том числе ориентированных графов, являшщихся математическими моделями сетей связи, нычислительных сетей. Цель изобретения расширение функциональных возможно— стей за счет оценки связности сильно и слабо связньгх ориентированных графов — достига.=тся тем, что в устройство, содержащее матрипь триггеров и элементов И, группу элементов ИЛИ и элемент И, дополнительно вгедены матрица элементов ИЛИ, с второй по четверту|п группы элементов ИЛИ,груп-: па элементов И, первый и второй эле— менты задержки, с первого по третий элементы ИЕ с второго по шестой элементы И. 2 ил.

1441415

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

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

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

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

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

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

Предварительно происходит устанав- 4 ка в нулевое состояние всех триггеров

i матрицы подачей сигнала на вход 21 начальной установки устройства. Затем на установочные входы 22 триггеров матрицы передаются двоичные сигналы (нуль или единица), определяемые значениями соответствующих элементов матрицы смежности исследуемого графа.

После этого подается потенциал на вход 23 пуска устройства, который попадает на вход первого элемента ИЛИ

5 второй группы и вход первого элемента 9 задержки. На выходе первого элемента ИЛИ 5 первой группы появляется сигнал, который попадает на первые входы элементов ИЛИ 3 первой

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

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

Если гра > является сильно связным, то в результате таких переключений на всех входах первого элемента И 8 имеется сигна", "!", в npo-,èâHoì случае на всех входах хотя бы одного элемента ИЛИ 4 первой группы или элемента ИЛИ 6 третьей группы отсутствуют сигналы и элемент И 8 не срабатывает ° Сигнал с элемента И 8 ..поступает на первый вход элемента И !5.

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

Если граф не сильно связен и на выходе элемента И 8 нет сигнала, то на выходе первого элемента НЕ 1! сигнал есть, поэтому при появлении сигнала на выходе первого элемента 9 задержки срабатывает второй элемент

И 14, сигнал с которого попадает на управляющие входы группы элементов

И 7. Сигнал с выхода элемента И 14 попадает на вход первого элемента

1441415

ИЛИ 5 и с его выхода попадает на первые входы элементов ИЛИ 3 первой сгроки матрицы и через первый элеме« г И 7 группы — на вторые входы элементов ИЛИ 3 первого столбца мат— рицы элементов ИЛИ и далее на вторые

,входы элементов И 2 первой строки и первого с-.:îëáöà матрицы элементов

И. Если первая вершина слабо связана хотя бы с одной вершиной, то соответственно триггер I, первой строки или гервого столбца находится в единичном состоянии. В противном случае все триггеры i первой строки и 15 первого "òîëáöà находятся в нулевом состоянии, граф является не связньм. на всех входах первого элемента ИЛИ

4 и рвой группы и первого элемента

1.11И 6 третьей группы — нули, на 20 в:".одах первого элемента ИЛИ 19 четвертой группы — нули.

Если К-й триггер 1 первой строки находится в единичном состоянии, то си>-нал с егс выхода поступает через соответс-.Bóþöèé элемент И 2 на первый вход К-го элемента ИЛИ 4 первой группы, на К-й вход первого элемента

ИХ .И э третьей группы, сигнал с выхода

i,-гс элемен,а ИЛ 1 4 попадает на пер- 30 вый вход К-го элемента ИЛИ 19 и через К-й э.",."-.мент ИЛИ 5 — на первые входы эле:.ентов ИЛИ 3 К-й строки, а через К-ii элемент И 7 — на вторые входы элементов ИЛИ 3 К-ro столбца ма-..рицы и да.".ее на вторые входы элементов И 2 К-й строки и К-го столбца матрицы элементов И, сигнал с выхода первого элемента ИЛИ 6 попадает на второй вход первого элемента ИЛИ 19. 40 переключEIIF\A для определения слабой связности графа. Поэтому при появлении сигнала на выходе элемента 10 задержки и отсутствии сигнала на выходе элемента И 20 на выходе элемент HE 13 сигнал есть, срабатывает элемент И 17, выход которого подключен к третьему входу блока 18.

Формула изобретения ется сигнал, в противном случае íà 4> выходе хотя бы одного элемента ИЛИ

19 четвертой группы отсутствует сигнал и элемент И 20 не срабатывает.

Сигнал с элемента И 20 поступает на второй вход элемента И 16 и вход элеэлемента НЕ 13.

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

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

10 задержки подобрано с учетом всех устройство для исследования параметров графов, содержащее матрицу триггеров„ матрицу элементов И (размерность матриц равна РхР, где Р количество узлов в исследуемом графе), первый элемент И к первую группу элементов ИЛИ, выходы которых соединены с соответствующими входами с первого по P — и первого элемента И. выход элемента И К-й строки и М-го столбца матрицы соединены с К-м входом М-го элемента ИЛИ первой группы (где К,М=1,...,P), прямой выход триггера К-й строки и M-го столбца мат" рицы соединен с первым входом элемента И К-й строки и М-ro столбца матрицы, установочные входы триггеров матрицы являются установочньми входами устройства, входы сброса триггеров матрицы соединены между собой и являются входом начальной установки устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет оценки связности сильно и слабо связных ориентированных графов, в него введены матрицы элементов ИПИ, вторая, третья и четвертая группы элементов ИЛИ, группы элементов И, первый и второй элементы задержки, первый, второй и -ретий элементы НЕ, с второго по шестой элементы И, выход второго элемента И соединен с первьм входом четвертого элемента

И и первьми входами элементов И группы, вторые входы которых соединены с выходами соответствующих элементов

ИЛИ второй группы и с первьми входами всех элементов ИЛИ соответствующей строки матрицы, выход элемента

ИЛИ К-й строки и М-го столбца матрицы соединен с BTopbftf входом элемента M К-й строки M-го столбца матрицы, вторые входы элементов ИЛИ

M Io столбца матрицы соединены с выходом М-го элемента И группы, К-й вход M-го элемента ИПИ третьей группы соединен с M-м входом К-rn элемента

1441415

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

И являются соответственно, первым, вторым и третьим выходами уСтройства.!

441415

Фиг. 2

Составитель О. Гречухина

Техред М.Дидык

Корректор Э. Лончакова

Редактор И. Рыб енко

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

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

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

Заказ 6290/53

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

r Ужго од ул. Проектная, 4