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

(54) УСТРОЙСТРОВ СЕТЕЙ АЛИЗА ПАРАМЕТУ 16(57) Излительн СССР1975,ССР1969. етельст С 7/122 ельство С 7/122 польз ас- ей ирен стро ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГННТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидУ 553628, кл. С 06Авторское свидеУ 276538, кл. С 06 бретение относится к выч й технике и может быть и но для анализа путей в с ью изобретения является функциональных возможнос ва за счет определения у1476483 20 мест в пути между начальной и конечной вершинами сети. С этой целью устройство содержит генератор 1 импульсов, распределитель 2 импульсов,группу из Р триггеров 3, где Р -количество ребер в сети, группу иэР элементов И 4, вход 5 разрешенияработы устройства, элемент НЕ 6, мо-дели 7 ребер, элементы 8 индикации,ключи 9, блок 10 определения связных вершин сети и вход 11 пуска устройства, Перед началом работы выходытриггеров 3 соединяют с управляющимивходами ключей 9 в порядке возраста 1Изобретение относится к вычислительной технике и может быть использовано для анализа путей в сетях.Цель изобретения - расширениефункциональных возможностей устрой"ства за счет определения узких меств пути между начальной и конечнойвершинами сети.На чертеже представлена функциональная схема устройства. 10Устройство содержит генератор 1импульсов, распределитель 2 импульсов, группу из Р триггеров 3 (гдеР - количество ребер в сети), группу из Р элементов И 4, вход 5 разрещения работы устройства, элементНЕ 6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 11пуска устройства,Устройство работает следующимобразом,Перед началом работы выходы триггеров 3 соединяют с управляющимивходами ключей 9 в порядке поэрастания весов ребер, а именно выход первого триггера 3 соединяется с управляющим входом ключа 9 той модели 7,соответствующее ребро графа которойимеет наименьший вес, выход второго 30триггера 3 - с управляющим входомключа 9 модели 7 следующего наименьшего по весу ребра и т.д., так чтовыход Р-го триггера 3 соединяется суправляющим входом ключа 9 модели 7 35ребра наибольшего веса. Вход 5 и ния весов ребер сети, Триггеры 3 устанавливают в единичное состояние.На вход 5 устройства подают сигналлогической единицы. После запускагенератора 1 импульсов первый изтриггеров 3, сохранивший до останона генератора 1 свое единичное состояние, укажет узкое место в пути,между начальной и конечной вершинами гофра. Включенные элементы 8 индикации фиксируют путь между указанными вершинами, в котором длина кратчайшей дуги (узкое место) максимальна. 1 ил 2элемент НЕ 6 подключают к начальной и конечной вершинам сети, в пути между которыми требуется найти узкое место, Распределитель 2 обнуляют, все триггеры 3 устанавливаются в единичное состояние, поэтому все ключи 9 открыты и включены все элементы индикации 8.После подачи пускового сигнала на вход 11 генератор 1 начинает выдачу импульсов на тактовый вход распределителя 2, который поочередно выдает сигналы на свои выходы.Дальнейшую работу устройства рассмотрим на примере графа с вершинами А - Д, представленного на чертеже, причем работа (А, Б), (А , В), (Б, В), (Б, Г) (В, Г), (Вр Д) и (Г, Д) имеют веса 6, 4, 1, 3, 7, 2 и 5 соответственно. Импульс с первого выхода распределителя 2 поступает на вход установки в ноль первого триггера 3 и устанавливает его в нулевое состояние. Сигнал с выхода первого триггера 3 поступает на управляющий вход ключа 9 модели 7 и закрывает его, что равносильно исключению ребра (Б, В) из топологии сети. Так как при этом вершины А и Д остаются связанными, первый триггер 3 остается в нулевом состоянии.Далее распределитель 2 выдает импульс по второму, а затем по третьему выходу, обусловливая переход в нулевое состояние второго и третьего триггеров 3, закрытие ключей 9 мо(Г Д), соответствующих номерам 4и 5 триггеров 3 Формула изобретения 10 Составитель А, МишинТехред М.Ходанич Корректор М. Васильева Редактор Л, Пчолийская Заказ 2158/50 Тираж 669 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,101 делей 74 и 7 , и исключение из топологии сети ребер (В, Д), (Б, Г). ПРи выдаче распределителем 2 импульса по четвертому выходу вначале проис 5 ходит переход в нулевое состояние третьего триггера 3, что приводит к закрытию ключа 9 модели 7,1, разрыву цепи протекания тока между вершинами А и Д и исчезновению сигнала уровня "1" на входе элемента б, образовавшийся при этом импульс поступает на вход признака останова генератора 1 и прекращает работу устройства. Кроме того, он проходит через четвертый элемент И 4, открытый по второму входу потенциалом с четвертого выхода распределителя 2, и возвращает в единичное состояние четвертый триггер 3. Номер (4) этого триггера 3, первым сохранившего единичное состояние в группе триг- геров 3, указывает узкое место в пути между вершинами А и Д, так как в графе не осталось ребер меньшего веса. Включенные элементы 8 индикации на моделях 7 д, 7, 74 указывают ребра пути между вершинами А и Д. Если через узкое место проходит несколько путей, то соответствующие элементы индикации 8 указы вают ветви, через которые они проходят. Наличие двух и более узкихмест проверяется пользователем путем сравнения весов ребер, соответствующих триггерам 3 с большими номерами. Например, если в рассмотренном графе вес ребра (Г, Д) был равен 4, а управляющий вход ключа 9 модели 7подключен к выходу пятого триг 40 гера 3, то узкое (второе) место пользователь установил бы путемсравнения весов ребер (А, В) и Устройство для анализа параметров сетей, содержащее группу из Р триггеров (где Р - количество ребер в сети), группу из Р элементов И и блок определения связных вершин сети, причем выход К-го элемента И группы (К = 1,, Р) подключен к входу установки в "1" К-го триггера группы, выход которого подключен к входу признака удаления К-го ребра блока определения связных вершин сети, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет определения узких мест в пути между начальной и конечной вершинами сети, в него введены генератор импульсов, распределитель импульсов и элемент НЕ, причем вход пуска устройства подключен к входу пуска генератора импульсов, выход которого подключен к тактовому входу распределителя импульсов, К-й . выход которого подключен к входу установки в "0" К-го триггера группы и первому входу К-го элемента группы, вход разрешения работы устройства подключен к входу опроса начальной вершины блока определения связных вершин сети, выход признака связности конечной вершины которого подключен к входу элемента НЕ, выход которого является выходом признака окончания работы устройства и подключен к входу признака останова генератора импульсов и вторым входам всех элементов И группы.