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

 

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

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

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

РЕСПУБЛИК (sg 4 G 06 F 15 20

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

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

/ фЬг-,.

4 л

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4144104/24-24 (22) 03.11.86 (46) 30.04.88. Бюл. № 16 (72) О. Г. Алексеев, В. И. Большаков, В. М. Крикун и Н. И. Ячкула (53) 68! .333(088.8) (56) Авторское свидетельство СССР № 1134944, кл. G 06 F 15/20, 1983, Авторское свидетельство СССР № 525954, кл. G 06 F 15/20, 1974. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике, может быть использовано для

„„SU„„1392574 А1 решения задач на графах и позволяет определить величины кратчайших расстояний между всеми парами вершин связного графа. С этой целью устройство содержит матрицу времяимпульсных развертывающих преобразователей, позволяющую определить кратчайшие пути из заданной начальной вершины во все другие вершины графа, и средства, обеспечивающие последовательный перебор номеров начальных вершин.

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

1392574

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

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

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

Устройство содержит матричную модель

1 графа, блок 2 управления и блок 3 регистрации.

Матричная модель 1 графа предназначена для моделирования топологии исследуемого графа и длин (весов) его дуг. Он содержит двувходовые элементы ИЛИ 4.К (К= 1,...,Р, где P — количество вершин в графе), модели дуг 5.МК (М=!...P), каждая из которых состоит из ключа 6, интегратора 7, регистра 8, цифроаналогового преобразователя (ЦАП) 9, схемы 10 сравнения, триггера 1 состояния дуги и светодиода

12, входные полюсы 13, 14К и выходные полюсы 15.К.

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

И 16, светодиоды 17, 8, ключ 19, ключ 20, элементы 21, 22 задержки, триггер 23, ключ

24 с P информационными цепями, Р-канальный распределитель 25 уровней, кнопочный выключатель 26, выключатель 27, кнопочный выключатель 28, выходные полюсы

29, ЗО.К и входные полюсы 31.К. Распреде.читель уровней может быть выполнен на основе ко.чьцевых сдвигающих схем, регистровых или многоустойчивых схем и имеет входы А, В и выходы (каналы) СК. При поступлении на вход В первого импульса вход А соединяется с выходом Cl, при поступлении на вход В второго импульса вход А соединяется с С2 и далее — аналогично. При поступлении на вход В (Р+ 1)го импульса схема возвращается в исходное состояние.

Блок 3 регистрации предназначен для фиксирования значений элементов матрицы расстояний и содержит элементы регистрации 32.МК, каждый из которых состоит из ключа 33, ключа 34, интегратора 35, аналогоцифрового преобразователя (АЦП) 36 регистр 37, и входные полюсы 38.К, 39.К.

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

При этом возможны следующие ситуации: если МК-я дуга графа ориентирована, то

40

10 !

55 в регистр 8 модели дуги 5.МК вносится код, соответствующий весу МК-й дуги; если

МК-я дуга графа неориентирована, то код, соответствующий ее весу, вносится в регистры 8 моделей дуг 5.МК и 5.КМ; если МК-й дуги в графе нет, то в регистр 8 модели дуги 5.МК вносится максимально возможный код при М К и код нуля при М=К.

Предлагаемое устройство обеспечивает автоматическое определение матрицы расстояний, последовательное определение кратчайших путей из М-й вершины графа до всех остальных вершин графа с индикацией дуг, входящих в соответствующий данной вершине подграф кратчайших путей: определение кратчайших путей из заданной вершины во все остальные. Наиболее общим режимом работы является режим автоматического определения матрицы расстояний. Работа в этом режиме начинается включением выключателя 27, замыкающие контакты которого готовят цепь подачи сигнала высокого уровня на вход установки в единицу триггера 23 от шины питания через информационные входы ключей 19, 20 и при кратковременном нажатии кнопочного выключателя 26. При этом импульс от шины питания через замыкающие контакты кнопочного выключателя 26 поступает на вход установки в единицу триггера 23. Триггер

23 переходит в единичное состояние и сигнал высокого уровня с его прямого выхода поступает на элементы 21, 22 задержки.

Через время задержки Т! сигнал с выхода элемента 21 задержки поступает через выходной полюс 29 блока 2 на входной полюс 13 блока l. С полюса 13 сигнал поступает на входы установки в исходное состояние интеграторов 7 и установки в нулевое состояние триггеров !1 всех моделей дуг 5.МК. Через Т2 Т! сигнал высокого уровня поступает на управляющий вход В распределителя уровней 25 и вход установки в нуль триггера 23. Триггер 23 переходит в нулевое состояние, снимается сигнал высокого уровня с входов элементов задержки, сигнал уровня логической единицы с инверсного выхода триггера 23 поступает на управляющий вход ключа 24. Распределитель уровней переходит в первое состояние и соединяет вход А с выходом Cl. При этом напряжение от шины питания через вход А распределителя уровней поступает на его выход C l и далее — через соответствующую информационную цепь ключа 24 — на выходной полюс 30.1 блока 2. С полюса 30.1 сигнал поступает на входные полюсы 14.1 и 38.1 блоков 1 и 3 соответственно. С полюса 14.1 сигнал поступает через элемент ИЛИ 4.! на информационные входы ключей 6 моделей дуг 5.1Ê, т.е. всех моделей дуг, соответствующих дугам, которые могут исходить из первой вершины исследуемого графа. С информационных выходов ключей 6 моделей дуг

1392574

5.1К сигнал уровня логической единицы поступает на вход интеграторов 7 этих моделей дуг.

С полюса 38.! сигнал высокого уровня поступает на информационный вход ключа

33 и управляющий вход ключа 34 элементов регистрации 32.К. С информационного выхода ключей 33 сигнал поступает на входы интеграторов 35 элементов регистрации

32.1К. Интеграторы 7 и 35 этих моделей дуг и элементов регистрации начинают вырабатывать линейно возрастающие напряжения с заданным углом наклона. С выходов интегратора 7 напряжение поступает на вход схемы 10 сравнения, на другой вход которой подано напряжение, соответствующее ходу длины (веса) ветви с ЦАП 9 этой модели дуги. 1!ри равенстве напряжений на выходе интегратора 7 и LjAII 9 на выходе схемы 10 сравнения появляется сигнал логической единицы, поступающий на вход установки в единицу триггера 11.

Триггер 11 соответствующей модели дуги

7 переходит в единичное состояние. Если, например, в моделируемом графе минимальна длина 1К-й дуги, то первым перейдет в единичное состояние триггер 11 модели дуги 5.1К. Сигнал уровня логической единицы через светодиод 12 поступает на управляющий вход ключа 6 в этой модели дуги, управляющие входы ключей 6 моделей дуг 5.МК, выходной полюс 15.К блока 1 и вход элемента ИЛИ 4.К. Информационные цепи ключей 6 этих моделей дуг размыкаются, исключая «включение» любой другой модели дуги, входящеи в К-ю вершину. С выхода элемента ИЛИ 4.К сигнал логической единицы поступает через информационные цепи ключей 6 на входы интеграторов 7 моделей дуг 5.МК, моделируя начало работы дуг, которые могут исходить из К-й вершины графа. С выходного полюса 15.К сигнал поступает на входной полюс

3l.Ê и 39.К блоков 2.3 соответственно. С полюса 31.К сигнал поступает на соответствующий вход элемента И 16, а с полюса

39.К на управляющий вход ключа 33 и информационный вход ключа 34 информационных элементов 32.МК. При этом информационные цепи ключей 33 размыкаются, прекращается подача сигнала на вход интегратора 35 элемента 32.1 К регистрации. Одновременно замыкается информационная цепь ключа 34 этого элемента регистрации, через нее сигнал высокого уровня поступает на АЦП 36, и код, соответствующий длине кратчайшего пути из 1-й вершины в К-ю, записывается в регистр 37.

Аналогичным образом моделируется достиже ние всех остальных вершин графа и фиксируется длина кратчайшего пути из 1-й вершины до них. Когда будет смоделировано достижение наиболее удаленной вершины, на всех входах элемента. И 16 присутствует сигнал высокого уровня, «горя10

45 щие» светодиоды 12 «включенных» моделей дуг индицируют дуги подграфа кратчайших расстояний первой вершины, а регистры 37 элементов регистрации 32.1К зафиксирует значения элементов первой строки матрицы расстояний графа. Сигнал высокого уровня с выхода элемента И 16 поступает через светодиод 17 на управляющий вход ключа 19.

«Загорание» светодиода 17 сигнализирует об окончании первого шага работы устройства. Информационная цепь ключа 19 замыкается и напряжение от шины питания через информационные цепи ключей 20 и

l9 и замкнутые контакты выключателя 27 поступает на вход установки в единицу триггера 23. Триггер 23 переходит в единичное состояние. Снимается сигнал высокого уровня с инверсного выхода триггера 23 и далее — с управляющего входа ключа 24.

Информационные цепи ключа 24 размыкаются и разрывают цепь подачи сигнала высокого уровня с выходного полюса 30.1 на входные полюсы 14.1 и 38.1 блоков 1.3 соответственно. С прямого выхода триггера 23 сигнал поступает на входы элементов 21, 22 задержки. Работа устройства на последующих тактах будет аналогична рассмотренной выше. В начале последнего P-го шага решения сигнал высокого уровня с выхода CP распределителя 25 уровней поступает не только на выходной полюс 30.Р, но и через светодиод 18 на управляющий вход ключа 20 «Загорание» светодиода 18 сигнализирует о наличии последнего такта работы, а размыкание информационной цепи ключа 20 исключает начало следующего (Р+1)-го шага решения. По окончании P-го шага решения формируется последняя строка матрицы расстояний и «загорается» светодиод 17, сигнализируя теперь уже об окончании всего процесса решения. Для возврата схемы в исходное положение выключается выключатель 27 и кратковременно нажимается кнопочный выключатель 26, триггер 23 переходит (Р+1)-й раз в единичное состояние. Через время Tl устанавливаются в исходное состояние интеграторы 7 и триггеры !! моделей дуг блоков 1, а через время Т2 устанавливается в исходное состояние распределитель 25 уровней.

При последовательном определении кратчайших путей из К-й вершины во все остальные вершины графа с индикацией соответствующих подграфов кратчайших путей уст ройство работает аналогично, но для того, чтобы обеспечить время, необходимое для анализа подграфа кратчайших путей на каждом шаге решения, выключатель 27 перед работой не включается. Iодграф кратчайших путей из вершины, соответствующий данному такту работы, индицируется включенными светодиодами !2 моделей дуг блока l. Он может быть получен после включения светодиода 17 блока 2, сиг1392574

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

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

Редактор А. Маковская Техред И. Верес Корректор А. Тяско

Заказ )809/54 Тираж 704 Подписное

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

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

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

Для начала последующего шага решения кратковременно нажимается кнопочный выключатель 28 блока управления.

Устройство для исследования параметров графа, содержащее матрицу из Р)(Р времяимпульсных развертывающих преобразователей, где Р— количество вершин в графе, первую группу из P элементов ИЛИ, блок синхронизации в элемент Й, выход которого подключен к тактовому входу блока синхронизации, вход пуска которого является входом пуска устройства, причем выход К-ro времяимпульсного развертывающего преобразователя (К= I,...P) М-й строки матрицы (М=! ...P) подключен к К-му входу М-го элемента ИЛИ первой группы, отличающееся тем, что, с целью расширения функциональных возможностей устрой- 2п ства путем определения кратчайших расстояний между парами всех вершин графа, в него введены вторая группа элементов ИЛИ, матрица из P)<Р времяимпульсных интегрирующих преобразователей и распределитель импульсов, Р-й выход которого подключен к входу блокировки блока синхронизации, первый выход синхронизации которого подключен к тактовому входу распределителя импульсов, К-й выход которого подключен к входам пуска всех времяимпульсных интегрирующих преобразователей

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