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

оо со ьо

ел

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

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

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

Устройство содержит матричную .модель 1 графа, блок 2 управления и блок 3 регистрации.

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

Блок 2 управления предназначен для задания режима работы устройства и ун- равления работой его элементов в процессе определения .матрицы расстояний графа. Блок 2 содержит Р-входовый элемент И 16, светодиоды 17, 18, ключ 19, ключ 20, элементы 21, 22 задержки, триггер 23, ключ 24 с Р информационными цепями, Р-ка- нальный распределитель 25 уровней, кнопочный выключатель 26, выключатель 27, кнопочный выключатель 28, выходные полюсы 29, 30.К и входные полюсы 31.К. Распределитель уровней .может быть выполнен на основе кольцевых сдвигающих схем, регистровых или многоустойчивых схем и имеет входы А, В и выходы (каналы) СК. При поступлении на вход В первого импульса вход А соединяется с выходом С1, при поступлении на вход В второго импульса вход А соединяется с С2 и далее - аналогично. При поступлении на вход В (P-f-l)- го импульса схема возвращается в исходное состояние.

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

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

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

Предлагаемое устройство обеспечивает

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

0 выключателя 27, замыкающие контакты которого готовят цепь подачи сигнала высокого уровня на вход установки в единицу триггера 23 от щины питания через информационные входы ключей 19, 20 и при кратковременном нажатии кнопочного выключателя 26. При этом импульс от шины питания через замыкающие контакты кнопочного выключателя 26 поступает на вход установки в единицу триггера 23. Триггер 23 переходит в единичное состояние и сигQ нал высокого уровня с его прямого выхода поступает на элементы 21, 22 задержки. Через время задержки Т1 сигнал с выхода элемента 21 задержки поступает через выходной полюс 29 блока 2 на входной полюс 13 блока 1. С полюса 13 сигнал по5 ступает на входы установки в исходное состояние интеграторов 7 и установки в нулевое состояние триггеров 11 всех моделей дуг 5.МК. Через Т2 Т1 сигнал высокого уровня поступает на управляющий вход В распределителя уровней 25 и вход установки в

нуль триггера 23. Триггер 23 переходит в нулевое состояние, снимается сигнал высокого уровня с входов элементов задержки, сигнал уровня логической единицы с инверсного выхода триггера 23 поступает на уп5 равляющий вход ключа 24. Распределитель уровней переходит в первое состояние и соединяет вход А с выходом С1. При &том напряжение от шины питания через вход А распределителя уровней поступает на его выход С1 и далее - через соответствующую

0 информационную цепь ключа 24 - на выходной полюс 30.1 блока 2. С полюса 30.1 сигнал поступает на входные полюсы 14.1 и 38.1 блоков 1 и 3 соответственно. С полюса 14.1 сигнал поступает через элемент ИЛИ 4.1 на информационные входы ключей 6 моделей

5 дуг 5.1 К, т.е. всех моделей дуг, соответствующих дугам, которые могут исходить из первой вершины исследуемого графа. С информационных выходов ключей 6 моделей дуг

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

С полюса 38.1 сигнал высокого уровня поступает на информационный вход ключа 33 и управляющий вход ключа 34 : лемен- тов регистрации 32.К. С информационного выхода ключей 33 сиг нал поступает на входы интеграторов 35 элементов регистрации 32.1 К. Интеграторы 7 и 35 этих моделей дуг и эле.ментов регистрации начинают вырабатывать линейно возрастающие напряжения с заданным углом наклона. С выходов интегратора 7 напряжение поступает на вход схемы 10 сравнения, на другой вход которой подано напряжение, соответствующее ходу длины (веса) ветви с ЦАН 9 этой модели дуги. При равенстве напряжений на выходе интегратора 7 и Ц.ЛП 9 на выходе схемы 10 сравнения появляется сигнал логической единицы, поступающий на вход установки в единицу триггера 11. Триггер 11 соответствующей модели дуги 7 переходит в единичное состояние. Если, например, в моделируемом графе минимальна длина 1К-Й дуги, то первым перейдет в единичное состояние триггер 11 модели дуги 5.1 К. Сигнал уровня логической единицы через светОлТиод 12 поступает на управляющий вход ключа 6 в этой модели дуги, управляющие входы ключей 6 моделей дуг 5.МК, выходной полюс 15.К блока 1 и вход элемента ИЛИ 4.К. Информационные цепи ключей 6 этих моделей дуг размыкаются, исключая «включение любой другой модели дуги, входящей в К-ю верщину. С выхода элемента ИЛИ 4.К сигнал логической единицы поступает через информационные цепи ключей 6 на входы интеграторов 7 моделей дуг 5.МК, моделируя начало работы дуг, которые могут исходить из К-й верщины графа. С выходного полюса 15.К сигнал поступает на входной полюс 31.К и 39.К блоков 2.3 соответственно. С полюса 31.К сигнал поступает на соответствующий вход элемента И 16, а с полюса 39.К - на управляющий вход ключа 33 и информационный вход ключа 34 информационных элементов 32.МК. При этом информационные цепи ключей 33 размыкаются, прекращается подача сигнала на вход интегратора 35 элемента 32.1 К регистрации. Одновременно замыкается информационная цепь ключа 34 этого элемента регистрации, через нее сигнал высокого уровня поступает на АЦП ,36, и код, соответствующий длине кратчайщего пути из 1-й верщины в К-ю, записывается в регистр 37. Аналогичным образом моделируется достиже ние всех остальных вершин графа и фиксируется длина кратчайщего пути из 1-й верщины до них. Когда будет смоделировано достижение наиболее удаленной верщины, на всех входах элемента И 16 присутствует сигнал высокого уровня, «горящие светодиоды 12 «включенных моделей дуг индицируют дуги подграфа кратчайших расстояний первой верщины, а регистры 37 элементов регистрации 32.1 К зафиксирует 5 значения элементов первой строки матрицы расстояний графа. Сигнал высокого уровня с выхода элемента И 16 поступает через све- тодиод 17 на управляющий вход ключа 19. «Загорание светодиода 17 сигнализирует об окончании первого щага работы устройства. Информационная цепь ключа 19 замыкается и напряжение от щины питания через информационные цепи ключей 20 и 19 и замкнутые контакты выключателя 27 поступает на вход установки в единицу

5 триггера 23. Триггер 23 переходит в единичное состояние. Снимается сигнал высокого уровня с инверсного выхода триггера 23 и далее - с управляющего входа ключа 24. Информационные цепи ключа 24 размыкаются и разрывают цепь подачи сигнала вы сокого уровня с выходного полюса 30.1 на входные полюсы 14.1 и 38.1 блоков 1.3 соответственно. С прямого выхода триггера 23 сигнал поступает на входы элементов 21, 22 задержки. Работа устройства на последую5 ших тактах будет аналогична рассмотренной выще. В начале последнего Р-го тага рещения сигнал высокого уровня с выхода СР распределителя 25 уровней поступает не только на выходной полюс 30.Р, но и через светодиод 18 на управляющий вход

0 ключа 20 «Загорание светодиода 18 сигнализирует о наличии последнего такта работы, а размыкание информационной цегж ключа 20 исключает начало следующего (P-(-l)-ro щага рещения. По окончании Р-го щага решения формируется последняя стро5 ка матрицы расстояний и «загорается светодиод 17, сигнализируя теперь уже об окончании всего процесса рещения. Для возврата схемы в исходное положение выключается выключатель 27 и кратковременно

,, нажимается кнопочный выключатель 26, триггер 23 переходит (Р-(-1)-й раз в единичное состояние. Через время Т1 устанавливаются в исходное состояние интеграторы 7 и триггеры II моделей дуг блоков 1, а через время Т2 устанавливается в исходное сос5 тояние распределитель 25 уровней.

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

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

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

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

0

0

5

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

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