Устройство для анализа параметров сетей
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в сетях. Целью изобретения является расширение функциональных возможностей устройства за счет определения узких мест в пути между начальной и конечной вершинами сети. С этой целью устройство содержит генератор 1 импульсов, распределитель 2 импульсов, группу из Р триггеров 3, где Р - количество ребер в сети, группу из Р элементов И4, вход 5 разрешения работы устройства, элемент НЕ6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 11 пуска уа. Перед началом работы выходы триггеров 3 соединяют с управляющими входами ключей 9 в порядке возрастания весов ребер сети. Триггеры 3 устанавливают в единичное состояние. На вход 5 устройства подают сигнал уровня логической единицы. После запуска генератора 1 импульсов первый из триггеров 3, сохранивший до останова генератора 1 свое единичное состояние, укажет "узкое" место в пути между начальной и конечной вершинами графа. Включенные элементы 8 индикации фиксируют путь между указанными вершинами, в котором длина кратчайшей дуги/"узкое" место/ максимальна. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК
ÄÄSUÄÄ 1476483 А1 (51)4 С 06 F 15/20, G 06 G 7/122
ОпНСАННЕ ИЗОБРЕТЕНИЯ
К ABTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И OTHPblTHRM
ПРИ ГННТ СССР (21) 4207818/24-24 (22) 09.03.87 (46) 30.04.89. Бюл. У 16 (72) Г.С.Колесник (53) 681.333(088.8) (56) Авторское свидетельство СССР
У 553628, кл. G 06 G 7/122, 1975.
Авторское свидетельство СССР
У 276538, кл. G 06 G 7/122, 1969. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТ-
РОВ СЕТЕЙ (57) Изобретение относится к вычислительной технике и может быть использовано для анализа путей в сетях. Целью изобретения является расширение функциональных возможностей устройства за счет определения узких
1476483
20 мест в пути между начальной и конечной вершинами сети. С этой целью устройство содержит генератор 1 импульсов, распределитель 2 импульсов, группу из P триггеров 3, где Р— количество ребер в сети, группу иэ
P элементов И 4, вход 5 разрешения работы устройства, элемент НЕ 6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 11 пуска устройства. Перед началом работы выходы триггеров 3 соединяют с управляющими входами ключей 9 в порядке возраста1
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в сетях.
Цель изобретения — расширение функциональных возможностей устрой" ства за счет определения узких мест в пути между начальной и конечной вершинами сети.
На чертеже представлена функциональная схема устройства. 10
Устройство содержит генератор 1 импульсов, распределитель 2 импульсов, группу из P триггеров 3 (где
Р— количество ребер в сети), группу из P элементов И 4, вход 5 разре- 15 шения работы устройства, элемент
НЕ 6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 11 пуска устройства.
Устройство работает следующим образом, Перед началом работы выходы триггеров 3 соединяют с управляющими входами ключей 9 в порядке поэрастания весов ребер, а именно выход первого триггера 3 соединяется с управляющим входом ключа 9 той модели 7, соответствующее ребро графа которой имеет наименьший вес, выход второго ®0 триггера 3 — с управляющим входом ключа 9 модели 7 следующего наименьшего по весу ребра и т.д., так что выход P-го триггера 3 соединяется с управляющим входом ключа 9 модели 7 ребра наибольшего веса. Вход 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 мо1476483 (1, Д), соответствующих номерам 4 и 5 триггеров 3.
Фо рм ул а и з о б р е т е н и я
Составитель А. Мишин
Техред M.Õoäàíè÷ Корректор M. Васильева
Редактор Л. Пчолийская
Заказ 2158/50 Тираж 669 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", r.Óærîðoä, ул. Гагарина,101 делей 7 4 и 7, и исключение из топологии сети ребер (В, Д), (Б, Г) . При выдаче распределителем 2 импульса по четвертому выходу вначале проис5 ходит переход в нулевое состояние третьего триггера 3, что приводит к закрытию ключа 9 модели 7,18, разрыву цепи протекания тока между вершинами А и Д и исчезновению сигнала уровня "1" на входе элемента 6, образовавшийся при этом импульс поступает на вход признака останова генератора 1 и прекращает работу устройства. Кроме того, он проходит через четвертый элемент И 4, открытый по второму входу потенциалом с четвертого выхода распределителя 2, и возвращает в единичное состояние четвертый триггер 3. Номер (4) этого триггера 3, первым сохранившего единичное состояние в группе триг- геров 3, указывает узкое место в пути между вершинами А и Д, так как в графе не осталось ребер меньшего веса. Включенные элементы 8 индикации на моделях 7, 7, 7 указывают ребра пути между вершинами
А и Д. Если через узкое место проходит несколько путей, то соответствующие элементы индикации 8 указы вают ветви, через которые они проходят. Наличие двух и более узких мест .проверяется пользователем путем сравнения весов ребер, соответствующих триггерам 3 с большими номерами. Например, если в рассмотренном графе вес ребра (Г, Д) был равен 4, а управляющий вход ключа 9 модели
7 подключен к выходу пятого тригГ
40 гера 3, то узкое (второе) место пользователь установил бы путем сравнения весов ребер (А, В) и
Устройство для анализа параметров сетей, содержащее группу из P триггеров (где Р— количество ребер в сети), группу из P элементов И и блок определения связных вершин сети, причем выход К-го элемента
И группы (К = I, P) подключен к входу установки в "1" К-ro триггера группы, выход которого подключен к входу признака удаления К-го ребра блока определения связных вершин сети, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет определения узких мест в пути между начальной и конечной вершинами сети, в него введены генератор импульсов, распределитель импульсов и элемент НЕ, причем вход пуска устройства подключен к входу пуска генератора импульсов, выход которого подключен к тактовому входу распределителя импульсов, К-й . выход которого подключен к входу установки в "0" К-го триггера группы и первому входу К-ro элемента группы, вход разрешения работы устройства подключен к входу опроса начальной вершины блока определения связных вершин сети, выход признака связности конечной вершины которого подключен к входу элемента
НЕ, выход которого является выходом признака окончания работы устройства и подключен к входу признака останова генератора импульсов и вторым входам всех элементов И группы.
