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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК И 4 С 06 Р 15/ ПИСАНИЕ ИЗОБРЕТ 1 ц,СЛЕДОВАН осится к цифр ехнике и моие васницкии ри исследованиио-логических изобретен(56) Авторское св У 637822, кл, 6 ОАвторское свид У 89663.0, кл. С 0 детельство СССР Р 15/20, 1978, тельство СССР Р 15/201 1982,ункциональных воз а за счет получезначений приорите этой целью в уст ния количественныхтов вершин графа. ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ К АВТОРСКОМУ СВИДЕТЕ,ПЬСТ(54) УСТРОЙСТВО ДЛЯСВЯЗНОСТИ ГРАФОВ(57) Изобретение овой вычислительнойбыть использованографов информационструктур ЭВМ Цельляется расширениеможностей устройст1280383 ройство, содержащее матрицу формирователей топологии исследуемого графа,каждый формирователь которой содержит триггеры 1, элементы И 2, 6 иэлементы 7 задержки, первую группуэлементов 3 ИЛИ по числу столбцовматрицы, выходной элемент И 4, выходной счетчик 12, формирователь 8 импульса, дополнительно введены втораягруппа элементов ИЛИ 9 по числустрок матрицы, группа счетчиков 10по числу строк матрицы и выходнойИзобретение относится к цифровойвычислительной технике и может бытьиспользовано.при исследовании графовинформационно-логических структурЭВМ,Цель изобретения - расширениефункциональных возвожностей устройства за счет получения количественньм значений приоритетов вершин графа.На чертеже приведена блок-схемаустройства.Устройство содержит триггеры 1,элементы И 2, первую группу элементов ИЛИ 3, выходной элемент И 4, установочный вход устройства 5, элементы И 6, элементы 7 задержки, формирователь 8 импульсов, вторую группуэлементов ИЛИ 9, группу счетчиков 10,выходной элемент ИЛИ 1, выходнойсчетчик 12, выход 13 индикации количества ребер связности устройства,выходы 14 индикации приоритета соответствующей вершины графа, выход 5индикации связности устройства, ин-,формационные входы 16 устройства,триггер 1, элементы И 2 и 6 и элемент7 задержки образуют формировательматриц 17,Устройство для исследования связности графов работает следующим образом.В тактепо входу 5 проходитустановка в нулевое состояние всехтриггеров 1 матрицы 17, выходногосчетчика 12 и счетчиков 1 О. В тактена входы установки в единицу тригегеров 1 матрицы 17 передаются двоичэлемент ИЛИ 11. Введение в устройство второй группы элементов ИЛИ, группы счетчиков и выходного элементаИЛИ позволяет решать задачи сетевого планирования. Количественные значения приоритетов вершин в этом случае являются мерой, характеризующейсрочность выполнения задач планирования. Задачи с более высокими приоритетами должны быть поставлены навыполнение ранее, чем задачи с болеенизкими приоритетами. 1 ил,ные сигналы, определяемые значениями соответствующих элементов матрицы смежности исследуемого графа. Одновременно в такте 1 определяетсяналичие связности первой вершины совсеми остальными. Если первая вершина связана хотя бы с одной вершиной,то соответствующий триггер 1 первойстроки находится в единичном состоянии. В противном случае все триггеры 1 находятся в нулевом состоянии.и, значит, граф состоит из несколькихнесвязанных частей.1Если все триггеры 1 первой строкинаходятся в единичном состояниитона выходах всех элементов ИЛИ 3 имеется сигнал, срабатывает элемент И4, на выходе 15 устройства появляется сигнал, свидетельствующий о том, 20что исследуемый граф является связным, Если не все триггеры первойстроки, а только -й триггер находится в единичном состоянии, тогдасигнал с его выхода поступает насоответствующий элемент ИЛИ 3, сигнал с которого поступает на элементИ 4 и на входы элементов И 2 -йстроки. Если 1-й триггер 1 -й строки находится в единичном состоянии,то сигнал с него поступает черезсоответствующий элемент И 2 на вход;-го элемента ИЛИ 3, через которыйсигнал поступает на элемент И 4 и 35на входы элементов И 2 -й строки.Если граф является связным, то врезультате таких перекючений навсех входах элемента И 4 и на выходе 15 устройства имеется сигнал, В80383 4должна быть поставлена на выполнение раньше, чем задача с более низким приоритетом,противном случае на всех входах хотябы одного элемента ИЛИ 3 отсутствуютсигналы и элемент И 4 не срабатывает: граф не является связным,В случае, если граф связан, сигнал с выхода элемента И 4 в видеступеньки поступает на вход формирователя 8 импульса, с выхода которогосигнал в виде одиночного импульсачерез первый элемент 7 задержки поступает на вход первого элемента И 6,другой вход которого соединен с выходом первого триггера 1 первой строки.Если данный триггер 1 находится вединичном состоянии, то сигнал с выхода элемента И 6 в риде одиночногоимпульса поступает на первый входэлемента ИЛИ 6 первой строки, с выхода которого он попадает на счетныйвход счетчика 10 первой строки ипервый вход элемента ИЛИ 11, С выхода элемента ИЛИ 11 сигнал поступаетна счетный вход счетчика 12.С выхода первого элемента 7 задержки сигнал поступает также навход следующего элемента 7 задержки,далее аналогичным образом опрашивается содержимое всех следующих триггеров. При этом последовательно вработу включаются соответствующиеэлементы ИЛИ 9 и счетчики 10 соответ 10 15 г 0 25 30 35 Э 40 45 50 55 ствующих строк матрицы.В результате полного цикла опроса содержимое счетчика 12 соответствует количеству единиц в матрице смежности (количеству ребер связного графа) а содержимое счетчиков 10 соответствует количеству единиц в соответст. - вующих строках матрицы смежности (приоритету соответствующих вершин графа). Получение количественной оценки приоритетов вершин графа необходимо учитывать при решении ряда задач сетевого планирования, а также при параллельном решении наборов задач на нескольких процессорах (в целях сокращения общего времени решения). Количественные значения приоритетов в этом случае являются мерой, характеризующей срочность выполнения данных задач, так как значение приоритета равно количеству информационных связей данной задачи с задачами-приемниками, то задержка задачи с более высоким приоритетом приводит к зат держке большего. количества задач- преемников. Поэтому такая задача формула изобретенияСоставитель Т, СапуноваТехред Л.Олейник Корректор М. Пожо Редактор Л. Пчелинская Заказ 7051/42 Тирад 671 ПодписноеВНИИПИ Государственного комитета СССР.по делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 5 1 ледующего формирователя, выход рлемента задержки последнего формирователя каждой нечетной строки матрицы подключен к входу элемента задержки последнего, формирователя последующей строки матрицы, выход элемента задержки первого формирователя каждой четкой строки матрицы подключен к входу элемента задержки первого формирователя последующей строки матрицы, выход выходного счетчика является выходом индикации количества ребер связности устройства, о т л и 1ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет получения количественного значения приоритета вершин графа, в устройство введены вторая группа элементов ИЛИ по числу строк матрицы формирователей топологии исследу 280383 6емого графа, группа счетчиков И, выходной элемент ИЛИ, выход первогоэлемента И каждого К-го формирователя каждой -й строки матрицыподключен к К-му входу 1-го элемента ИЛИ второй группы (где Е =1,и;,1=1,ь), выход кажжого-го элемента ИЛИ второй группы подключенк 1 -му входу выходного элемента 10 ИЛИ и подключен к счетному входу1-го счетчика группы, входы установки в "0" счетчиков группы объединены между собой и входом установкинуля выходного счетчика, счетныйвход которого подключен к выходу выходного элемента ИЛИ, выход каждогосчетчика труппы является выходом индикации приоритета соответствующей вершины графа.20