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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН (19) (И) 0 А1 (5ц 4 С 06 С 7/122

Ф)1 г »

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

Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTKPblTVM (21) 3896725/24-24 (22) 17.05.85 (46) 15.12,86. Бюл..9 46 (72) А.М.Кощель, В.А.Кривенко и В.Ф.Шаповалов (53) 681. 333 (088. 8) (56) Авторское свидетельство СССР

М 781830, кл. G 06 G 7/122, 1978.

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

Ф 553628, кл. G 06 С 7/ 122, 1975. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ (57) Изобретение относится к области вычислительной техники и может быть использовано для автоматизации управления потоками информации в сложноразветвленных .информационных сетях, управления структурой сети, исследования отдельных свойств сложных графов. Целью изобретения является повышение быстродействия эа счет автоматизации процесса выдачи полученных данных о кратчайшем пути. Устройство для определения характеристик кратчайших путей содержит модели основных ветвей исследуемого графа, состоящие из переменных резисторов, порогового элемента, модели вспомогательных ветвей исследуемого графа, состоящие из блоков индикации, источник напряжения, источник тока, индикатор тока, аналогово-цифровой преобразователь, группа элементов И-НЕ, и групп иэ m элементов И и группа регистров памяти. 1 ил.! 12 77 l

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

Целью изобретения является повышение быстродействия..

Функциональная схема предлагаемо- !О

ro устройства для определения характеристик кратчайших путей представлена на чертеже.

Устройство для определения характеристик кратчайших путей содержит !5 модели основных ветвей исследуемого графа 1, состоящие из переменных резисторов 1 и порогового элемента, выполненного на реле 3, модели вспомогательных ветвей исследуемого гра- 20 фа 4, состоящие из блоков 5 индикации, нормально разомкнутые контакты реле 6, источник 7 напряжения, ис,точник 8 тока, индикатор 9 тока., 25 аналогово-цифровой преобразователь lU группа элементов И-НЕ 11, и групп из ш элементов И 12, группа регистров 13 памяти, выход 14 устройства.

Устройство для определения характеристик кратчайших путей работает следующим образом.

Значения сопротивлений переменных резисторов 2, соответствующие весовым коэффициентам ветвей, установле- . ны в начальный момент времени (напри- 35 мер, автоматически). В начальный А и конечный В узлы исследуемого пути подключают регулируемый источник 7

Ф 1 напряжения. В точки А и В, соответствующие узлам А и В основного графа, на индикационном графе подключа— ют последовательно соединенные источник 8 тока и индикатор 9 тока. При начальном напряжении регулируемого источника 7 напряжения, подключенный к нему параллельно аналого-цифровой преобразователь 10 вырабатывает код, соответствующий началу отсчета.

При линейном увеличении напряжения источника 7 токи в ветвях увеличиваются пропорционально сопротивлениям ветвей (весу ветви).

В отдельных ветвях основного графа ток достигает значения, при котором срабатывает пороговый элемент 3, замыкающий свой контакт 6 в соответствующей ему индикаторной цепи. В этот момент блок 5 индикации этой

40 2 цепи вырабатывает и с первого выхода подает на вторые входы элементов

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

Этот процесс продолжается до тех пор, пока из блоков 5 индикации и контактов 6 пороговых элементов 3 не будет создана электрическая цепь для источника 8 тока. В результате ток источника 8 протечет не по всем ветвям, отмеченным пороговыми элементами 3, а только по тем из них, которые создапи замкнутый путь для источника 8 тока.

В момент протекания тока через блоки 5 индикации, составляющие кратчайший -путь, они вырабатывают и выдают с второго. выхода на первый вход соответствующих элементов И-НЕ 11 постоянный единичный потенциал, Индикатор 9 тока в этот момент выдает одиночный импульс, который, поступая на вторые входы элементов И-НЕ 11, проходит только через те из них, на первые входы которых не подан постоянный единичный потенциал, т.е. через те элементы И-НЕ, соответствующие которым ветви не входят в состав кратчайшего пути. Импульс индикатора 9 тока, пройдя через отдельные элементы

И-НЕ 11, поступает на входы установки в нуль соответствующих регистров

13 памяти. В результате в регистрах

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

После считывания полученных данных из регистров 13 памяти выполняется кратковременное снятие общего напряжения питания (для разблокировки), устройство возвращается в исходное состояние и готово к следующим измерениям, Формула изобретения

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

3 12771 собой в соответствии с топологией исследуемого графа, и модели вспомогательных ветвей, соединенные между собой в соответствии с топологией исследуемого графа, каждая модель основной ветви содержит параллельно соединенные переменный резистор и пороговый элемент, выполненный в виде реле, а каждая модель вспомогательной ветви содержит последовательно 10 соединенные блок индикации и первый нормально разомкнутый контакт реле одноименной модели основной ветви, причем источник напряжения включен между начальным и конечным узлами ис- 15 следуемого графа, а последовательно соединенные индикатор тока и источник тока включены между вспомогательным начальным и вспомогательным конечным узлами исследуемого графа, 20 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены аналого-цифровой преобразователь, и групп по m ýëåìåíòîâ И, группа регистров яти, группа эле- 25 ментов И-НЕ, входы аналого-цифрового преобразователя подключены к выхо—

40 4 дам источника напряжения, каждый i-й вЫход аналого-цифрового преобразователя подключен к первому входу i-го элемента И каждой из групп (i = 1 2 m) вторые входы элементов И каждой j-й группы (где j = 1, 2...n) объединены и через второй нормально разомкнутый контакт реле j-й модели основной ветви исследуемого графа подключены к

1 ервому информационному выходу блока индикации j-й модели вспомогательной ветви, выходы каждого i-го элемента И каждой j-й группы подключены к входу

i-го разряда j-го регистра памяти группы, выходы регистров памяти группы являются группой выходов устройства, второй информационный выход блока индикации j-й модели вспомогательной ветви подключен к первому входу

j-го элемента И-НЕ группы, выход которого подключен к (m+1)-му разряду

j-го регистра памяти блока памяти, вторые входы всех элементов И-НЕ группы объединены и подключены к выходу индикатора тока, выход индикатора тока подключен к входам установки в

"0" регистров памяти группы.

1277140

Составитель Т.Сапунова

Техред Л.Олейник

Корректор О.Луговая

Редактор А.Маковская

Тираж 671

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

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

Заказ 55

Подписное

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