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

сд

4

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

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

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

Устройство содержит матрицу из ВхВ триггеров 1, где В - количество вершик в графе, первую и вторую мат- рицы из ВхВ элементов И 2 и 3, мат- рицу из ВхВ цифроимпульсных преобразователей. AS матрицу из ВхВ регистро 5, группу БкВ элементов 6 задержки, первой по третью группы из В элементов ИЛИ 7, 8, 9, первый и второй элементы ИЛИ 10, 11,,,первьш и второ счетчики 12, 13, элемент И 14.

Кроме того, устройство имеет выход 15 признака связности всех вершин графа, вход 16 пуска, вход 17 начальной установки, входы 18 признаков наличия ветви из М-й в К-ю вершину графа (, ..., В; М 1, .,..5 В), входы 19 задания веса ветви из в К-ю вершину графа, выход 20 признака окончания работы устройства, выходы 21 количества ветвей, исходяш 1х из М-й вершины графа, выходы 22 суммарного веса ветвей, исходящих из вершины , графа, выход 23 суммарного количества ветвей в графе, выход 24 суммарного веса ветвей графа. I

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

Перед началом работы на входы 1 устройства подают коды чисел, равны весу ветвей, соединяющих М-ю и К-ю вершины графа. На вход 16 пуска уст ройства подают импульсный сигнал единичного уровня. Лри этом устанавливаются в ноль все триггеры 1 и счетчики 12 и 13,. веса соответствующих дуг заносятся в регистры 5 На входы 18 признаков наличия ветв из М-й в К-ю вершину графа устройст подт,ают импульсные сигналы единичног уровня, npti этом в триггеры 1 заносится информация о топологии графа в соответствии с его матрицей смежности. Если граф является связным, на выходе элемента И 14 появляется потенциал высокого уровня, который.

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

5

0 5

Q

д

0

5

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

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

314

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

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

f4 fj

Изобретение относится к вычислительной технике, может быть использовано для анализа связности вершин графа и позволяет определить количество ребер и вес связного графа. Устройство содержит матрицу в ВхВ триггеров 1, где В - количество вершин в графе, первую и вторую матрицы из ВхВ элементов И 2 и 3, матрицу из ВхБ цифроимпульсньгх преобразователей 4, матрицу ВхВ регистров 5, группу из ВхВ элементов 6 задержки,с первой по третью группы из В элементов ИЛИ 7, 8, 9, первый и второй элементы ИЛИ 10, 11, первьш и второй счетчики 12, 13, элемент И 14. Перед началом работы установкой в единицу триггеров 1 задают топологию графа в соответствии с его матрицей сложности. В регистры 5 заносят вес соответствующих ребер графа. В том случае, если все вершины графа связаны, на выходе элемента И 14 появляется импульс единичного уровня, который, проходя последовательно через элементы 6 задержки, позволяет подсчитать количество вершин в графе (на счетчике 12) и его вес (на счетчике 13). литeJ ьнocть задержки в каждом элементе 6 выбрана из условия, чтобы перед запуском очередного преобразователя 4 предыдущий успел закончить выдачу веса соответствующего ребра графа. 1 ил. С S (Л