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

 

Изобретение относится к цифро вой вычислительной технике и может быть использовано при исследовании графов информационно-логических структур ЭВМ. Целью изобретения является расширение функциональных возможностей устройства за счет получения количественных значений приоритетов вершин графа. С этой целью в уст (Л ю 00 о со с 00

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

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

РЕСПУБЛИК

„„80„„12 0

yg 4 С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

4СР ..

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, . 3 (56) Авторское свидетельство СССР

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

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

У 89663.0, кл. G 06 F 15/20, 1982.

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3937398/24-24 (22) 29.07.85 (46) 30.12.86. Бюл. У 48 (72) В,Н, Кустов, M.Â. Квасницкий и В.В. Красавцев (53) 681.333 (088.8) (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СВЯЗНОСТИ ГРАФОВ (57) Изобретение относится к цифро» вой вычислительной технике и может быть использовано при исследовании графов информационно-логических структур ЭВИ. Целью изобретения является расширение функциональных возможностей устройства за счет получения количественных значений приоритетов вершин графа. С этой целью в уст1280383

Ф

2 ройство, содержащее матрицу формирователей топологии исследуемого графа, каждый формирователь которой содержит триггеры 1, элементы И 2, 6 и элементы 7 задержки, первую группу элементов 3 ИЛИ по числу столбцов матрицы, выходной элемент И 4, выходной счетчик 12, формирователь 8 импульса, дополнительно введены вторая группа элементов ИЛИ 9 по числу; строк матрицы, группа счетчиков 10 по числу строк матрицы и выходной!

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

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

На чертеже приведена блок-схема устройства.

Устройство содержит триггеры I, элементы И 2, первую группу элементов ИЛИ 3, выходной элемент И 4, установочный вход устройства 5, элементы И 6, элементы 7 задержки, формирователь 8 импульсов, вторую группу элементов ИЛИ 9, группу счетчиков 10, выходной элемент ИЛИ !1, выходной счетчик 12, выход 13 индикации количества ребер связности устройства, выходы 14 индикации приоритета соответствующей вершины графа, выход 15 индикации связности устройства, ин-, формационные входы 16 устройства, триггер 1, элементы И 2 и 6 и элемент

7 задержки образуют формирователь матриц 17.

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

В такте t„ IIo входу 5 проходит установка в нулевое состояние всех триггеров 1 матрицы 17, выходного счетчика 12 и счетчиков 10. В такте на входы установки в единицу триго геров 1 матрицы 17 передаются двоичэлемент ИЛИ 11. Введение в устройство второй группы элементов ИЛИ, группы счетчиков и выходного элемента

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

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

Если все триггеры 1 первой строки находятся в единичном состоянии,,то на выходах всех элементов ИЛИ 3 имеется сигнал, срабатывает элемент И

4, на выходе 15 устройства появляется сигнал, свидетельствующий о том, 20 что исследуемый граф является связным. Если не все триггеры первой строки, а только i — и триггер находится в единичном состоянии, тогда сигнал с его выхода поступает на соответствующий элемент ИЛИ 3, сигнал с которого поступает на элемент

И 4 и на входы элементов И 2 i-й строки. Если j-й триггер 1 i-й строки находится в единичном состоянии, то сигнал с него поступает через соответствующий элемент И 2 на вход

g-го элемента ИЛИ 3, через который сигнал поступает на элемент И 4 и

35 на входы элементов И 2 -й строки.

Если граф является связным, то в результате таких перек::ючений на всех входах элемента И 4 и на выходе 15 устройства имеется сигнал. В

80383 4 должна быть поставлена на выполнение раньше, чем задача с более низким приоритетом.

12 противном случае на всех входах хотя бы одного элемента ИЛИ 3 отсутствуют сигналы и элемент И 4 не срабатывает: граф не является связным.

В случае, если граф связан, сигнал с выхода элемента И 4 в виде ступеньки поступает на вход формирователя 8 импульса, с выхода которого сигнал в виде одиночного импульса через первый элемент 7 задержки поступает на вход первого элемента И 6, другой вход которого соединен с выходом первого триггера 1 первой строки.

Если данный триггер I находится в единичном состоянии, то сигнал с выхода элемента И 6 в риде одиночного импульса поступает на первый вход элемента ИЛИ 6 первой строки, с выхода которого он попадает на счетный вход счетчика 10 первой строки и первый вход элемента ИЛИ 11. С выхода элемента ИЛИ 11 сигнал поступает на счетный вход счетчика 12.

С выхода первого элемента 7 задержки сигнал поступает также на вход следующего элемента 7 задержки, далее аналогичным образом опрашивается содержимое всех следующих триггеров. При этом последовательно в работу включаются соответствующие элементы ИЛИ 9 и счетчики 10 соответ10

Э

55 ствующих строк матрицы.

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

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

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

И, вход установки в "1" триггера каждого формирователя матрицы является соответствующим входом группы информационных входов устройства; входы установки нуля триггеров всех формирователей матрицы объединены между собой, объединены с входом установки нуля выходного счетчика и являются установочным входом устройства, выход второго элемента И каждого

i-го формирователя каждого g-ro столбца матрицы (где i =2,3,..., 1,2,3...п ) подключен к i-му входу J-ro элемента ИЛИ первой группы, выход которого подключен к 1-му входу выходного элемента И и первым входам первых элементов И всех формирователей ()+1) и строки матрицы, второй вход второго элемента И каждого формирователя матрицы подключен к выходу триггера этого;ке формирователя матрицы, выход триггера каждого формирователя матрицы подключен к первому входу первого элемента И того же формирователя матрицы, второй вход которого подключен к выходу элемента задержки того же формирователя матрицы, выход выходного элемента И подключен к входу формирователя импульсов и является выходом индикации связности графа, выход формирователя импульсов подключен к входу элемента задержки первого формирователя первой строки матрицы формирователей топологии исследуемого графа, в каждой строке которой выход элемента задержки предыдущего формирователя подключен к входу элемента задержки каждого посСоставитель Т. Сапунова

Техред Л.Олейник Корректор M. Пожо

Редактор Л. Пчелинская

Заказ 7051/42

Тирая 671 Подписное

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

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

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

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

10 ИЛИ и подключен к счетному входу

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