Устройство для определения характеристик кратчайших путей на графе

СОЮЗ ОжтсНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 6 С 7/122 Т СССРТНРЫТЮ АНИЕ ИЗОБРЕТЕН О ВТОРСКОМУ СВИДЕТЕЛЬСТВУ ко о СССР 1978.СССР 1975. ГОСУДАРСТВЕННЫЙ КОМ ПО ДЕЛАМ ИЗОБРЕТЕНИИ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для автоматизации управления потоками информации в сложноразветвленных .информационных сетях,управления структурой сети, исследования отдельных свойств сложных графов. Целью изобретения является повышение быстродействияэа счет автоматизации процесса выдачи полученныхданных о кратчайшем пути. Устройстводля определения характеристик кратчайших путей содержит модели основныхветвей исследуемого графа, состоящиеиз переменных резисторов, пороговогоэлемента, модели вспомогательных ветвей исследуемого графа, состоящие изблоков индикации, источник напряжения, источник тока, индикатор тока,аналогово-цифровой преобразователь,группа элементов И-НЕ, и групп иэ шэлементов И и группа регистров памяти, 1 ил.1277 1Изобретение относится к вычислительной технике и может быть использовано для автоматизации управленияпотоками в сложноразветвленных информационных сетях, управления структурой сети, исследования отдельныхсвойств сложных графов.Целью изобретения является повышение быстродействия.Функциональная схема предлагаемо Ого устройства для определения характеристик кратчайших путей представлена на чертеже.Устройство для определения характеристик кратчайших путей содержит 15модели основных ветвей исследуемогографа 1, состоящие из переменных резисторов 1 и порогового элемента,выполненного на реле 3, модели вспомогательных ветвей исследуемого графа 4, состоящие из блоков 5 индикации, нормально разомкнутые контактыреле 6, источник 7 напряжения, ис,точник 8 тока, индикатор 9 тока.,25аналогово-цифровой преобразователь 1 О,группа элементов И-НЕ 11, и групп изш элементов И 12, группа регистров 13памяти, выход 14 устройства.Устройство для определения характеристик кратчайших путей работаетследующим образом.Значения сопротивлений переменныхрезисторов 2, соответствующие весовым коэффициентам ветвей, установлены в начальный момент времени (например, автоматически), В начальный Аи конечный В узлы исследуемого путиподключают регулируемый источник 7Ф 1напряжения. В точки А и В, соответствующие узлам А и В основного гра- ффа, на индикационном графе подключают последовательно соединенные источник 8 тока и индикатор 9 тока. Приначальном напряжении регулируемогоисточника 7 напряжения, подключенныйк нему параллельно аналого-цифровойпреобразователь 10 вырабатывает код,соответствующий началу отсчета.При линейном увеличении напряжения источника 7 токи в ветвях увеличиваются пропорционально сопротивлениям ветвей (весу ветви),В отдельных ветвях основного графа ток достигает значения, при котором срабатывает пороговый элемент 3, замыкающий свой контакт 6 в соответствующей ему индикаторной цепи, В этот момент блок 5 индикации этой 4 О 2цепи вырабатывает и с первого выхода подает на вторые входы элементовИ 12 группы соответствующей сработавшей ветви одиночный импульс разрешения записи текущего значения свыходов аналого-цифрового преобразователя 1 О в регистр 13 памяти, соответствующий сработавшей ветви.Этот процесс продолжается до техпор, пока из блоков 5 индикации иконтактов 6 пороговых элементов 3 небудет создана электрическая цепь дляисточника 8 тока, В результате токисточника 8 протечет не по всем ветвям, отмеченным пороговыми элементами 3, а только по тем из них, которые создапи замкнутый путь для источника 8 тока.В момент протекания тока черезблоки 5 индикации, составляющие кратчайший .путь, они вырабатывают и выдают с второго выхода на первый входсоответствукицих элементов И-НЕ 11 постоянный единичный потенциал, Индикатор 9 тока в этот момент выдаетодиночный импульс, который, поступаяна вторые входы элементов И-НЕ 11,проходит только через те из них, напервые входы которых не подан постоянный единичный потенциал, т.е, черезте элементы И-НЕ, соответствующие ко.торым ветви не входят в состав кратчайшего пути. Импульс индикатора 9 тока, пройдя через отдельные элементыИ-НЕ 11, поступает на входы установки в нуль соответствующих регистров13 памяти. В результате в регистрах13 памяти остается информация толькос ветвях, составляющих кратчайшийпуть, Номера ветвей, составляющихкратчайший путь, определяются исходяиз номеров регистров 13 памяти, в которых не произошло стирание информации,После считывания полученных данных из регистров 13 памяти выполняется кратковременное снятие общегонапряжения питания (для разблокировки), устройство возвращается в исходное состояние и готово к следующимизмерениям,Формула из обре тения Устройство для определения характеристик кратчайших. путей на графе, содержащее источник напряжения, источник тока, индикатор тока, модели основных ветвей, соединенные между3 12771 собой в соответствии с топологией исследуемого графа, и модели вспомогательных ветвей, соединенные между собой в соответствии с топологией исследуемого графа, каждая модель основной ветви содержит параллельно соединенные переменный резистор и пороговый элемент, выполненный в виде реле, а каждая модель вспомогательной ветви содержит последовательно 10 соединенные блок индикации и первый нормально разомкнутый контакт реле одноименной модели основной ветви, причем источник напряжения включен между начальным и конечным узлами ис следуемого графа, а последовательно соединенные индикатор тока и источник тока включены между вспомогательным начальным и вспомогательным конечным узлами исследуемого графа, 20 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены аналого-цифровой преобразователь, и групп по шэлементов И, группа регистров памяти, группа элементов И-НЕ, входы аналого-цифрового преобразователя подключены к выхо 40 4дам источника напряжения, каждый -й вЫход аналого-цифрового преобразователя подключен к первому входу -го элемента И каждой из групп ( = 1, 2 ш), вторые входы элементов И каждой 1-й группы (где ) = 1, 2 п) объединены и через второй нормально разомкнутый контакт реле -й модели основной ветви исследуемого графа подключены к ервому информационному выходу блока индикации 1-й модели вспомогательной ветви, выходы каждого х-го элемента И каждой 1-й группы подключены к входу х-го разряда -го регистра памяти группы, выходы регистров памяти группы являются группой выходов устройства, второй информационный выход блока индикации 1-й модели вспомогательной ветви подключен к первому входу 1-го элемента И-НЕ группы, выход которого подключен к (ш+1)-му разряду )-го регистра памяти блока памяти, вторые входы всех элементов И-НЕ группы объединены и подключены к выходу индикатора тока, выход индикатора тока подключен к входам установки в "0" регистров памяти группы.1277140 Составитель Т,Сапуноведактор А.Маковская Техред Л.Олейник ктор О.Лугова Заказ 55 писное Производственно-полиграфическое предприятие, г.ужгород, у ектная,ВНИИПИ Госу по делам 3035 МосквТираж 671 рственного ко зобретений и Ж, Раушск тета СССРкрытийнаб., д,