Устройство для анализа параметров сетей Советский патент 1989 года по МПК G06G7/122 

1

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

Цель изобретения - расширение функциональных возможностей устройства за счет определения узких мест в пути между начальной и конечной вершинами сети

На чертеже представлена функциональная схема устройства„

Устройство содержит генератор импульсов, распределитель 2 импульсов, группу из Р триггеров 3 (где Р - количество ребер в сети), группу из Р элементов И 4, вход 5 разрешения работы устройства, элемент НЕ 6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 1J пуска устройствас

Устройство работает следующим образом,,

Перед началом работы выходы триггеров 3 соединяют с управляющими входами ключей 9 в порядке поэраста- ния весов ребер, а именно выход первого триггера 3 соединяется с управляющим входом ключа 9 той модели 7, соответствующее ребро графа которой имеет наименьший вес, выход второго триггера 3-е управляющим входом ключа 9 модели 7 следующего наименьшего по весу ребра и т„д„, так что выход Р-го триггера 3 соединяется с управляющим входом ключа 9 модели 7 ребра наибольшего веса„ Вход 5 и

элемент НЕ 6 подключают к начальной и конечной вершинам сети, в пути между которыми требуется найти узкое место. Распределитель 2 обнуляют, все триггеры 3 устанавливаются в единичное состояние, поэтому все ключи 9 открыты и включены все элементы индикации 8 о

После подачи пускового сигнала

O на вход 11 генератор 1 начинает выдачу импульсов на тактовый вход распределителя 2, который поочередно выдает сигналы на свои выходы0

Дальнейшую работу устройства рас5 смотрим на примере графа с вершинами А - Д, представленного на чертеже, причем работа (А, Б), (А , В), (Б, В), (Б, Г), (В, Г), (В, Д) и (Г, Д) имеют веса 6, 4, 1, 3, 7, 2

0 и 5 соответственно Импульс с первого выхода распределителя 2 поступает на вход установки в ноль первого триггера 3 и устанавливает его в нулевое состояние о Сигнал с выхода

первого триггера 3 поступает на управляющий вход ключа 9 модели 7 и закрывает его, что равносильно исключению ребра (Б, В) из топологии сетио Так как при этом вершины А и Д

0 остаются связанными, первый триггер 3 остается в нулевом состоянии

Далее распределитель 2 выдает импульс по второму, а затем по третьему выходу, обусловливая переход в ну5 левое состояние второго и третьего триггеров 3, закрытие ключей 9 моделей 7 g и 7 рг и исключение из топологии сети ребер (В, Д), (Б, Г). При выдаче распределителем 2 импульса по четвертому выходу вначале происходит переход в нулевое состояние третьего триггера 3, что приводит к закрытию ключа 9 модели 7д8, разрыву цепи протекания тока между вершинами А и Д и исчезновению сигнала уровня 1 на входе элемента 6, образовавшийся при этом импульс поступает на вход признака останова генератора 1 и прекращает работу устройства. Кроме того, он проходит через четвертый элемент И 4, открытый по второму входу потенциалом с четвертого выхода распределителя 2, и возвращает в единичное состояние четвертый триггер 30 Номер (4) этого триггера 3, первым сохранившего единичное состояние в группе триг- - геров 3, указывает узкое место в пути между вершинами А и Д, так как в графе не осталось ребер меньшего веса. Включенные элементы 8 индикации на моделях , 78г, 7ГА указывают ребра пути между вершинами А и Д. Если через узкое место проходит несколько путей, то соответствующие элементы индикации 8 указывают ветви, через которые они проходят Наличие двух и более узких мест -проверяется пользователем путем сравнения весов ребер, соответствующих триггерам 3 с большими номерами. Например, если в рассмотренном графе вес ребра (Г, Д) был равен 4, а управляющий Вход ключа 9 модели 7ГД подключен к выходу пятого триг- гера 3 , то узкое (второе) место пользователь установил бы путем сравнения весов ребер (А, В) и

0

5

0

5

0

5

0

(Г, Д), соответствующих номерам 4 ., и 5 триггеров 3„

Формула изобретения

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

, выход которого подключен к входу установки в О К-го триггера группы и первому входу К-го элемента группы, вход разрешения работы устройства подключен к входу опроса начальной вершины блока определения связных вершин сети, выход признака связности конечной вершины которого подключен к входу элемента НЕ, выход которого является выходом признака окончания работы устройства и подключен к входу признака останова генератора импульсов и вторым

входам всех элементов И группы

Изобретение относится к вычислительной технике и может быть использовано для анализа путей в сетях. Целью изобретения является расширение функциональных возможностей устройства за счет определения узких мест в пути между начальной и конечной вершинами сети. С этой целью устройство содержит генератор 1 импульсов, распределитель 2 импульсов, группу из Р триггеров 3, где Р - количество ребер в сети, группу из Р элементов И4, вход 5 разрешения работы устройства, элемент НЕ6, модели 7 ребер, элементы 8 индикации, ключи 9, блок 10 определения связных вершин сети и вход 11 пуска уа. Перед началом работы выходы триггеров 3 соединяют с управляющими входами ключей 9 в порядке возрастания весов ребер сети. Триггеры 3 устанавливают в единичное состояние. На вход 5 устройства подают сигнал уровня логической единицы. После запуска генератора 1 импульсов первый из триггеров 3, сохранивший до останова генератора 1 свое единичное состояние, укажет "узкое" место в пути между начальной и конечной вершинами графа. Включенные элементы 8 индикации фиксируют путь между указанными вершинами, в котором длина кратчайшей дуги/"узкое" место/ максимальна. 1 ил.