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

(5 ц 4 б 06 Г 15 20 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ 4ЛфОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР134944, кл. б 06 Г 15/20, 1983,Авторское свидетельство СССР525954, кл. 6 06 Г 15/20, 1974, (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике, может быть использовано для ц.801392574 А 1 решения задач на графах и позволяет определить величины кратчайших расстояний между всеми парами вершин связного графа, С этой целью устройство содержит матрицу времяимпульсных развертывающих преобразователей, позволяющую определить кратчайшие пути из заданной начальной вершины во все другие вершины графа, и средства, обеспечивающие последовательный перебор номеров начальных вершин. Результаты определения величин кратчайших путей запоминаются в матрице время- импульсных интегрирующих преобразователей. 1 ил.расстояний графа.Целью изобретения является расширениефункциональных возможностей устройствапутем определения кратчайших путей меж.ду всеми парами вершин графа.На чертеже представлен пример функцио 30 40 50 Изобретение относится к вычислительной технике, может быть использовано при создании устройств для решения задач на графах и позволяет определить матрицу нальной схемы устройства.Устройство содержит матричную модель 1 графа, блок 2 управления и блок 3 регистрации.Матричная модель 1 графа предназначена для моделирования топологии исследуемого графа и длин (весов) его дуг. Он содержит двувходовые элементы ИЛИ 4.К (К= 1Р, где Р - количество вершин в графе), модели дуг 5.МК (М=Р), каж. дая из которых состоит из ключа 6, интегратора 7, регистра 8, цифроаналогового преобразователя (ЦАП) 9, схемы 10 сравнения, триггера1 состояния дуги и светодиода 12, входные полюсы 13, 14 К и выходные полюсы 15.К.Блок 2 управления предназначен для задания режима работы устройства и управления работой его элементов в процессе определения матрицы расстояний графа. Блок 2 содержит Р-входовый элемент И 16, светодиоды 17,8, ключ 19, ключ 20, элементы 21, 22 задержки, триггер 23, ключ 24 с Р информационными цепями, Р-канальный распределитель 25 уровней, кнопочный выключатель 26, выключатель 27, кнопочный выключатель 28, выходные полюсы 29, ЗО.К и входные полюсы 31.К. Распреде. литель уровней может оыть выполнен на основе кольцевых сдвигающих схем, регистровых или многоустойчивых схем и имеет входы А, В и выходы (каналы) СК. При поступлении на вход В первого импульса вход А соединяется с выходом С 1, при поступлении на вход В второго импульса вход А соединяется с С 2 и далее - аналогично. При поступлении на вход В (Р+ 1)- го импульса схема возвращается в исходное состояние.Блок 3 регистрации предназначен для фиксирования значений элементов матрицы расстояний и содержит элементы регистрации 32,МК, каждый из которых состоит из ключа 33, ключа 34, интегратора 35, аналогоцифрового преобразователя (АЦП) 36 регистр 37, и входные полюсы 38.К, 39.К.Перед работой, учитывая, что количество моделей дуг в матричной модели графа позволяет исследовать ориентированные, неориентированные и смешанные связные графы любой топологии, задается топология исследуемого графа внесением соответствующих кодов в регистры 8 моделей дуг. При этом возможны следующие ситуации: если МК-я дуга графа ориентирована, то 10 15 20 25 35 45 55 в регистр 8 модели дуги 5.МК вносится код, соответствующий весу МК-й дуги; если МК-я дуга графа неориентирована, то код, соответствующий ее весу, вносится в регистры 8 моделей дуг 5.МК и 5.КМ; если МК-й дуги в графе нет, то в регистр 8 модели дуги 5.МК вносится максимально возможный код при М К и код нуля при М=К. Предлагаемое устройство обеспечивает автоматическое определение матрицы расстояний, последовательное определение кратчайших путей из М-й вершины графа до всех остальных вершин графа с индикацией дуг, входящих в соответствующий данной вершине подграф кратчайших путей: определение кратчайших путей из заданной вершины во все остальные. Наиболее общим режимом работы является режим автоматического определения матрицы расстояний. Работа в этом режиме начинается включением выключателя 27, замыкающие контакты которого готовят цепь подачи сигнала высокого уровня на вход установки в единицу триггера 23 от шины питания через информационные входы ключей 19, 20 и при кратковременном нажатии кнопочного выключателя 26. При этом импульс от шины питания через замыкающие контакты кнопочного выключателя 26 поступает на вход установки в единицу триггера 23. Триггер 23 переходит в единичное состояние и сигнал высокого уровня с его прямого выхода поступает на элементы 21, 22 задержки. Через время задержки Т сигнал с выхода элемента 21 задержки поступает через выходной полюс 29 блока 2 на входной полюс 13 блока 1. С полюса 13 сигнал поступает на входы установки в исходное состояние интеграторов 7 и установки в нулевое состояние триггеров 1 всех моделей дуг 5,МК. Через Т 2 Т сигнал высокого уровня поступает на управляющий вход В распределителя уровней 25 и вход установки в нуль триггера 23. Триггер 23 переходит в нулевое состояние, снимается сигнал высокого уровня с входов элементов задержки, сигнал уровня логической единицы с инверсного выхода триггера 23 поступает на управляющий вход ключа 24. Распределитель уровней переходит в первое состояние и соединяет вход А с выходом С 1. При этом напряжение от шины питания через вход А распределителя уровней поступает на его выход С и далее - через соответствующую информационную цепь ключа 24 - на выходной полюс 30.1 блока 2. С полюса 30.1 сигнал поступает на входные полюсы 14.1 и 38.1 блоков 1 и 3 соответственно. С полюса 14.1 сигнал поступает через элемент ИЛИ 4. на информационные входы ключей 6 моделей дуг 5.1 К, т.е. всех моделей дуг, соответствующих дугам, которые могут исходить из первой вершины исследуемого графа. С информационных выходов ключей 6 моделей дуг50 55 5.1 К сигнал уровня логической единицы поступает на вход интеграторов 7 этих моделей дуг.С полюса 38. сигнал высокого уровня поступает на информационный вход ключа 33 и управляюгций вход ключа 34 элементов регистрации 32.К. С информационного выхода ключей 33 сигнал поступает на входы интеграторов 35 элементов регистрации 32.1 К. Интеграторы 7 и 35 этих моделей дуг и элементов регистрации начинают вырабатывать линейно возрастающие напряжения с заданным углом наклона. С выходов интегратора 7 напряжение поступает на вход схемы 1 О сравнения, на другой вход которой подано напряжение, соответствуюгцее ходу длины (веса) ветви с ЦАП 9 этой модели дуги. Гри равенстве напряжений на выходе интегратора 7 и ЦАГ 9 на выходе схемы 10 сравнения появляется сигнал логической единицы, поступающий на вход установки в единицу триггера1. Триггер 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-й вершины до них. Когда будет смоделировано достижение наиболее удаленной вершины, на всех входах элемента И 6 присутствует сигнал высокого уровня, горяО 15 го 25 30 35 40 45 щие светодиоды 12 включенных моделей дуг индицируют дуги подграфа кратчайших расстояний первой вершины, а регистры 37 элементов регистрации 32.1 К зафиксирует значения элементов первой строки матрицы расстояний графа. Сигнал высокого уровня с выхода элемента И 16 поступает через светодиод 17 на управляющий вход ключа 19. Загорание светодиода 17 сигнализирует об окончании первого шага работы устройства. Информационная цепь ключа 19 замыкается и напряжение от шины питания через информационные цепи ключей 20 и 19 и замкнутые контакты выключателя 27 поступает на вход установки в единицу триггера 23. Триггер 23 переходит в единичное состояние. Снимается сигнал высокого уровня с инверсного выхода триггера 23 и далее - с управляющего входа ключа 24. Информационные цепи ключа 24 размыкаются и разрывают цепь подачи сигнала высокого уровня с выходного полюса 30.1 на входные полюсы 14.1 и 38.1 блоков 1.3 соот. ветственно. С прямого выхода триггера 23 сигнал поступает на входы элементов 21, 22 задержки. Работа устройства на последуюших тактах будет аналогична рассмотренной выше. В начале последнего Р-го шага решения сигнал высокого уровня с выхода СР распределителя 25 уровней поступает не только на выходной полюс 30.Р, но и через светодиод 18 на управляющий вход ключа 20 Загорание светодиода 18 сигнализирует о наличии последнего такта работы, а размыкание информационной цепи ключа 20 исключает начало следуюгцего (Р+1) -го шага решения. По окончании Р-го шага решения формируется последняя строка матрицы расстояний и загорается светодиод 17, сигнализируя теперь уже об окончании всего процесса решения. Для возврата схемы в исходное положение выключается выключатель 27 и кратковременно нажимается кнопочный выключатель 26, триггер 23 переходит (Р+ 1)-й раз в единичное состояние. Через время Т устанавливаются в исходное состояние интеграторы 7 и триггерымоделей дуг блоков 1, а через время Т 2 устанавливается в исходное состояние распределитель 25 уровней. При последовательном определении крат. чайших путей из К-й вершины во все остальные вершины графа с индикацией соответствующих подграфов кратчайших путей уст ройство работает аналогично, но для того, чтобы обеспечить время, необходимое для анализа подграфа кратчайших путей на каждом шаге решения, выключатель 27 перед работой не включается. Г 1 одграф кратчай царях путей из вершины, соответствуюгций данному такту работы, индицируется включенными светодиодами 2 моделей дуг блока 1. Он может быть получен после включения светодиода 17 блока 2, сиг1392574 формула изобретения Составитель А. МишинРедактор А. Маковская Техред И. Верес Корректор А. ТяскоЗаказ 1809/54 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж - 35, Раушская наб д. 45Производственно-полиграфическое предприятие, г. Ужгород, ул Проектная, 4 нализирующего об окончании такта работы.Для начала последующего шага решениякратковременно нажимается кнопочный вы.ключатель 28 блока управления,Устройство для исследования параметров графа, содержащее матрицу из РК Р время- импульсных развертывающих преобразователей, где Р - количество вершин в графе, первую группу из Р элементов ИЛИ, блок синхронизации в элемент Й, выход которого подключен к тактовому входу блока синхронизации, вход пуска которого является входом пуска устройства, причем выход К-го времяимпульсного развертывающего преобразователя (К= 1,Р) М-й строки матрицы (М= Р) подключен к К-му входу М-го элемента ИЛИ первой группы, отличающееся тем, что, с целью расширения функциональных возможностей устрой О ства путем определения кратчайших расстояний между парами всех вершин графа, в него введены вторая группа элементов ИЛИ, матрица из Р)(Р времяимпульсных интегрирующих преобразователей и распределитель импульсов, Р-й выход которого подключен к входу блокировки блока синхронизации, первый выход синхронизации которого подключен к тактовому входу распределителя импульсов, К-й выход которого подключен к входам пуска всех времяимпульсных интегрирующих преобразователей М-й строки матрицы и первому входу К-го элемента ИЛИ второй группы, выход которого подключен к входу пуска всех время- импульсных развертывающих преобразователей, К-й строки матрицы, выход М-го элемента ИЛИ первой группы подключен к входам останова времяимпульсных интегрирующих преобразователей М-го столбца матрицы, к М-му входу элемента И, второму входу М-го элемента ИЛИ второй группы, второй выход синхронизации блока синхронизации подключен к входам установки всех времяимпульсных развертывающих преобразователей матрицы.