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

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

1

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

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

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

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

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

В такте t по входу 5 проходит установка в нулевое состояние всех триггеров 1 матрицы 17, выходного счетчика 12 и счетчиков 10. В такте tg на входы установки в единицу триггеров 1 матрицы 17 передаются двоич

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

5

0

5

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

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

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

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

Б случае, если граф связан, сиг- нал с выхода элемента И 4 в виде ступеньки поступает на вход формирователя 8 импульса, с выхода которого сигнал в виде одиночного импульса через первый Элемент 7 задержки пос- тупает на вход первого элемента И 6, другой вход которого соединен с выходом первого триггера 1 первой строки Если данный триггер 1 находится в единичном состоянии, то сигнал с вы- хода элемента И 6 в иде одиночного импульса поступает на первый вход элемента ИЛИ 6 первой строки, с вы- хода которого он попадает на счетный вход счетчика 10 первой строки и первый вход элемента ИЛИ I1, С выхода элемента ИЛИ 11 сигнал поступает на счетный вход счетчика 12.

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

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

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

0

5

0 5

)

5 0

должна быть поставлена на выполнение раньше, чем задача с более низ КИМ приоритетом.

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

Устройство для исследования связности графа, содержащее матрицу формирователей топологии исследуемого графа, первую группу элементов ШШ по числу столбцов матриць: формирователей топологии исследуемого графа, выходной элемент И, формирователь импульсов и выходной счетчик, каждый формирователь матрицы формирователей топологии исследуемого графа содержит триггер, первый элемент И и эле- ; мент задержки, каждый формирователь матрицы, кроме формирователей первой строки, содержит второй элемент И, вход установки в 1 триггера каждого формирователя матрицы является соответствующим входом группы информационных входов устройства;-входы установки нуля триггеров всех формирователей матрицы объединены между собой, объединены с входом установки нуля выходного счетчика и являются установочным входом устройства, выход второго элемента И каждого i-ro формирователя каждого J-ro столбца матрицы (где i 2,3,... , j 1,2,3...п ) подключен к i-му входу J-ro элемента ИЛИ первой группы, выход которого подключен к J-му входу выходного элемента И И первым входам первых элементов И всех формирователей (j+l)-й строки матрицы, второй вход второго элемента И каждого формирователя матрицы подключен к выходу триггера этого же формирователя матрицы, выход триггера каждого формирователя матрицы подключен к первому входу первого элемента И того же формирователя матрицы, второй вход которого подключен к выходу элемента задержки того же формирователя матрицы, выход выходного элемента И подключен к входу формирователя импульсов и является выходом индикации связности графа, выход формирователя импульсов подключен к входу элемента задержки первого формирователя первой строки матрицы формирователей топологии исследуемого графа, в каждой строке которой выход элемента задержки пре- дьщутдего формирователя подключен к входу элемента задержки каждого последующеШо формирователя, выход элемента задержки последнего формирователя каждой нечетной строки матрицы подключен к входу элемента задержки последнего формирователя последующей строки матрицы, выход элемента задержки первого формирователя каждой четкой строки матрицы подключен к входу элемента задержки первого формирователя последующей строки матри- цы, выход выходного счетчика является выходом индикации количества ребер связности устройства, отличающееся тем, 4to, с цепью расширения функциональных возможное- тей за счет получения количественного значения приоритета вершин графа в устройство введены вторая группа элементов ИЛИ по числу строк матрицы формирователей топологии исследу-

Редактор Л. Пчелинская Заказ 7051/42

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

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

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

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

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

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

емого графа, группа счетчиков И, выходной элемент ИЛИ, выход первого элемента И каждого k-ro формирователя каждой j-й строки матрицы подключен к k-му входу, j-ro элемента ИЛИ второй группы (где k 1,и; ,n), выход кажжого j-го элемента -ИЛИ второй группы подключен к J -му входу выходного элемента ИЛИ и подключен к счетному входу J-ro счетчика группы, входы установки в О счетчиков группы объединены между собой и входом установки нуля выходного счетчика, счетный вход которого подключен к выходу выходного элемента ИЛИ, выход каждого счетчика труппы является выходом индикации приоритета соответствующей вершины графа.

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