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

 

Изобретение относится к вычислительной технике, может быть использовано для анализа связности вершин графа и позволяет определить количество ребер и вес связного графа. Устройство содержит матрицу в ВхВ триггеров 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 (Л

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (5è 4 С 06 F 15/2С

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР (21) 4130306/24-24 (22) 04. 10 ° 86 (46) 15. 01. 89. Бюл. № 2 (72) В.ПеНазаров и Е.В.Строганова (53) 681.333(088.8) (56) Авторское свидетельство СССР № 637822, кл. G Об F 15/20, 1978.

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

G F 15/20, 1982. (54) УСТРОЙСТВО ЛЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике, может быть использовано для анализа связности вершин графа и позволяет определить количество ребер и вес связного графа. Устройство содержит матрицу в ВхВ триггеров 1, где  — количество вершин в графе, первую и вторую матрицы из ВхВ элементов И 2 и 3, матрицу из ВхВ цифроимпульсных преобразователей 4, матрицу ВхВ регистров 5, „.SU„1451714 группу из ВхВ элементов 6 задержки,с первой по третью группы из В элементов ИЛИ 7, 8, 9, первый и второй элементы ИЛИ 10, 11, первьй и второй счетчики 12, 13, элемент И 14.

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

1451714

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

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

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

Устройство содержит матрицу из

ВхВ триггеров 1, где  — количество вершин в графе, первую и вторую матрицы из ВхВ элементов И 2 и 3, матрицу из ВхВ цифроимпульсных преобразователей 4,, матрицу из ВхВ регистров

5, группу ВхВ элементов 6 задержки, с первой по третью группы из В элементов ИЛИ 7, 8, 9, первый и второй элементы ИЛИ 10, 11„.первый и второй счетчики 12 13, элемент И 14.

Кроме того, устройство имеет выход 15 признака связности всех вершин графа, вход 16 пуска, вход 17

25 начальной установки, входы 18 признаков наличия ветви из М-й в К-ю вершину графа (К=1, ..., В; M = — 1, ..., В), входы 19 задания веса ветви из N-й в К-ю вершину графа, выход 20 признака окончания работы устройства, выходы 21 количества ветвей, исходящих из М-й вершины графа, выходы 22 суммарного веса ветвей, исходящих из М-й вершины 35

rpaAa, выход 23 суммарного количества ветвей в графе, выход 24 суммарного веса ветвей графа.

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

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

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

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

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

Устройство для анализа параметров графа, содержащее матрицу из ВхВ триггеров, где  — количество вершин в графе, две матрицы из ВхВ элементов И, группу из ВхВ элементов задержки, две группы из В элементов

ИЛИ, элемент И, первый элемент ИЛИ и первый счетчик, причем вход начальной установки устройства подключен к входам установки в "0 1 всех триггеров н 1! матрицы, и к входу установки в 0 первого счетчика, вход признака нали-чия ветви из М-й в К-ю вершину графа (M=1 ..., В; К=1, ..., В) подключен к входу установки в "1" К-го тригге- ра M — é строки матрицы, выход которого подключен к первым входам К-х элементов И М-й строк первой и второй матриц, выход К-го элемента И M-й строки первой группы матрицы подключен к

M-му,,входу К-ro элемента ИЛИ первой группы, выход которого подключен к вторым входам всех элементов И К-й строки первой матрицы и к К-му входу элемента И, выход которого является выходом признака связности всех вершин графа устройства и подключен к входу первого элемента задержки группы, выход ÊõÌ-го элемента задержки группы подключен к входу (КхМ+1)-го элемента задержки группы и к второму входу К-го элемента И М-й строки второй матрицы, выход которого подключен к К-му входу М-го элемента

14517

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

4 шину графа устройства подключен к информационному входу К-ro регистра М-й строки матрицы, выход которого подключен к информационному входу

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

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

1451714

° ° Э

Ф Э Э

° Ф °

Э Э

° Ф °

° Э Ф

Ф Ф Ф

Ф 4 °

ЭФФ

Ф Ф °

) 3!

Э Э °

° 4

Э ° °

Ф Э Ф

Э Ф Ф

Э Ф °

g ° Ф

Ф Ф Ь

Ф Э Ф

Составитель А. Мишин

Редактор И. Рыбченко Техред А.Кравчук Корректор O.Êðàâöoâà

Заказ 7082/48 Тираж 667 Подписное

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

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

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