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

ел

о а ел

3150645

,f

ти устройства, вход 76 одновременного опроса веса ребер сети устройства, вход 77 установки признаков удаления ребер сети, входы 78 задания веса ребер сети блока 69, информационный выход 79 блока 70, выход 80 признака ; окончания работы устройства,вход 81 опроса пути, выходы 82 признаков принадлежности ребер пути из начальной в JQ конечную вершину сети устройства. Перед началом работы обнуляют блок 71, в блоках 69,72 задают топологию сети, в блоки 74 вьмитания заносят веса соответствующих ребер сети. На первом |с

этапе работы выбирают ребра с максимальным весом и исключают (удаляют) их из топологии графа. Далее циклически определяют ребра, инцидентные начальной вершине графа, выбирают ребро с максимальным весом, добавляют его в топологию соти, формиру€;мую блоком 71,и затем стягивают все ребра, вес которых не меньше веса выбранного ребра Цикл продолжается до тех пор, пока ребро не будет стянуто в конечную вершину сети (сигнал появляется на выходе 80), после этого опрашивают блок 71. 3 ил.

Изобретение относится к вычислительной технике и может быть использовано для определения в сети пути максимальной ширины. С этой целью устройство содержит блок 69 определения инцидентных ребер, блок 70 выбора максимального кода, блок 71 определения пути, блок 72 определения концевых вершин, группу блоков 73 сравнения, группу блоков 74 вычитания, вход 75 опроса начальной вершины сети устройства, вход 76 одновременного опроса веса ребер сети устройства, вход 77 установки признаков удаления ребер сети, входы 78 задания веса ребер сети блока 69, информационный выход 79 блока 70, выход 80 признака окончания работы устройства, вход 81 опроса пути, выходы 82 признаков принадлежности ребер пути из начальной в конечную вершину сети устройства. Перед началом работы обнуляют блок 71, в блоках 69, 72 задают топологию сети, в блоки 74 вычитания заносят веса соответствующих ребер сети. На первом этапе работы выбирают ребра с максимальным весом и исключают (удаляют) их из топологии графа. Далее циклически определяют ребра, инцидентные начальной вершине графа, выбирают ребро с максимальным весом, добавляют его в топологию сети, формируемую блоком 71, и затем стягивают все ребра, вес которых не меньше веса выбранного ребра. Цикл продолжается до тех пор, пока ребро не будет стянуто в конечную вершину сети (сигнал появляется на выходе 80), после этого опрашивают блок 71. 3 ил.

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

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

На.фиг.. представлена функциональная схема моделей ветви, на базе которых рассмотрен пример реализа- . п ции устройства; на фиг.2 - функциональная схема блока управления; на фИг.З - обобщенная структурная схема устройства.

Модели ветви, управляемые бло- ,г ком 2 управления, содержат с первого по семнадцатый элементы И 3-19, первый 20, второй 21, третий 22 и четвертый 23 элементы ИЛИ, пер - вый 24, второй 25, третий 26, чет- Q вертый 27, пятый 28 и шестой 29 триггеры, первый 30 и второй 31 счетчики импульсов, элемент НЕ 32 и схему 33 индикации.

Блок 2 управления содержит с пер- вого по восьмой элементы И 34-41, элемент ИЛИ 42, первый 43, второй 44, третий 45, четвертый 46 и пятый 47 триггеры, элемент НЕ 48, счетчик 49 импульсов и генератор 50 импульсов.

Кроме того, устройство содержит (фиг.2) первый 5Ги второй 52 много- входовые элементы ИЛИ и многовхо- довый элемент И 53. Число входов у каждого многовходового элемента соответствует числу моделей ветвей. Устройство имеет полюсы 54-68, из которых полюсы 54 и 55 у моделей вет- вей служат для коммутации их ме7-ду

55

5

п

г Q

5

5

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

Исходными данными задачи определения пути максимальной ширины между заданными вершинами являются .коммутация моделей ветвей 1 посредством полюсов 54 и 55 между собой в соответствии с конфигурацией модулируемой сети, подключение полюсов 64 и 65 блока 2 управления соответственно к полюсам 54 и 55 тех моделей ветвей, между которыми отыскивается указанный путь, и занесение числа (N-q ; ) импульсов в счетчики 30 всех моделей ветвей, где N - емкость счетчиков 30, 31 и 49.

Суть решения задачи определения пути максимальной ширины заключается п выполнении устройством двух этапов работы. Первый этап включает преобразование исходной сети в новую сеть, которая содержит ветви исходной сети с пропускными способностями, равными

(q;j - q;j), (1) где п ,. - наибольшая существующая

у какой-либо ветви в исходной сепи пропускная способность.

Кроме того, новая сеть не содержит ветвей с пропускной способностью, равной q-: , т.е такие ветви исключаются из рассмотрения.

Второй этап представляет собой решение задачи определения пути с наибольшей пропускной способностью.в ноЬ150

вой сети и включает циклически повторяющиеся операции нахождения (xj,X ) разре чл из множества рпзреяов К, выле ления ветви ряяреза (х;:;:) с max(q.-- Ч-,; ) исключения гз дальнейшего pic смотрения ветвей, у Koropr ix пропускная способность больше или равна про- пусной способности выделенной ветви. Исключение этих ветвей происходит за- корачинлнием по;гюсов 5А и 55. Эти циклически повторяющиеся операции выполняются до тех пор, пок,-; полюсы, между которыми отыскивается путь, не будут закорочены (т.е. не совпадут). После этого производят формирование сймого пути в новой сети. Ветви, принадлежа- 1цие этому пути в новой сети. Совпадают в исходной сети с ветвями, которые: формируют путь максимальной Ш4грит1.

Перед началом работы устройства триггеры 24-29 всех моделей ветвей 1 и триггеры 43-47 блока 2 управления, а также счетчики 31 импульсов всех моделей ветвей и счетчик 49 блока управления устанавливаются в иулсвое состояние (установочные ти№ не показаны).

Работа устройства начинается с момента установки триггера 47 блока 2 управлеция в единичное состояние, что соответствует началу выполнения устройством первого этаг1л. Единичное состояние триггера 47 выдает разрешение на вход элемента И 41. При этом импульсы генератора 50, поступающие на второй вход элемента И 41, проходит через этот элемент на noj ioc 62 всех моделей 1 ветвей. В модели ветви эти импульсы генераторя поступают на вход счетчика 30 и через элементы И 17 и ИЛИ 23 на вход счетчика 34. Это происходит потому, что на втором входе элемента И I7 есть разрешение с нулевого выхода триггера 29..

После поступления числа qj: импульсов в счетчик 30 каждой модели ветви на его выходе появляется импульс переполнения, который поступает на единичный вход триггера 28. Этот импульс устанавливает триггер 28 в единичное состояние, которое выдает разрешение на вход элемента И 16-и, кроме того, снимает разрегаениэ с входа элемента И 17. В результате импульсы генератор; , не проходят через элемент И 17 и ИЛИ 23 на вход счетчика 3. Однако на выходе элемента И 16 по-

5

0

5

0

5

0

5

0

5

0

5

51 6

является сигнал, так как триггер 29 находится в нулевом состоянии. Этот сигнал поступает на полюс 59 и далее на соответствующий этой модели ветви вход 59ч-39 многовходового элемента И 53. Дальнейшее поступление импульсов генератора 50 блока 2 управления на полюс 62 всех моделей ветвей приводит к тому, что все модели выдают сигнал на свои полюсы 59 и, следовательно, на все входы , многовходового элемента И 53. К этому моменту в счетчики 31 импульсов модели ветви поступает число импульсов, равное пропускной способности - q; . В модели ветви, которая имела наибольшую пропускную способность - qJ , счетчик 30 обнуляется, В остальных моделях ветвей в счетчик 30 заносится число импульсов, ранное (N - q . )

При появлении импульса на входах )9 59п многовходового элемента И 53 от всех моделей 1 ветвей на его выходе появляется сигнал, который поступает на полюс 60 всех моделей.

В каждой модели I ветви сигнал с 60 поступает на вход г пемен- iC3 НЕ 32, И 15 и 18. В результате элемент НЕ 32 снимает разрешение с входа элемента И 14. Импульсы гене- p.iTopa 50, поступающие на полюс 62, проходят через элементы И 18 и IL 111 23 на вход счетчика 31,

Дальнейшее поступление импульсов генератора 50 блока 2 управления на полюс 62 приводит к тому, что у всех моделей I ветвей первым переполняется счетчик 31 тот, в который было занесено наибольшее число импульсов. Такой моделью 1 ветви является модель, у которой наибольшая пропускная способность. Импульс переполнения счетчика 31 устанавливает в модели триггер 29 в единичное состояние и появляется через полюс 6 на соответствующем этой модели входе 614-61„ многовходового элемента ИЛИ 52.

С вьгхода многовходового элемента ИЛИ 52 импульс переполнения поступает на единичный вход триггера 43 и ну- лепой аход триггера 47, что устанав- ливлет их в соответствующее состояние. Нулевое состояние триггера 47 запре- дальнейшее прохождение импуль- . .в генератора 50 через элемент И 41 на полюс 62 всех моделей ветвей. К этому моменту счетчики 31 импульсов

каждой модели ветви, у которой в этот счетчик было занесено число импульсов, рапное q,j (такие модели соотпетстп ветвям с наибольшей прпускной способностью), обнуляется. В счетчик 30 птях моделей з.эносится число N - q;. импульсов. В счетчики 31 импульсгш остальных моделей ветвей заносится число N - q; + q;: импульсов, В счетчики 30 импульсов этих ж:е ветвсш заносится число N -- - q; импульсов. Другими словами, исходная информация о пропусной способности всех моделей ветвей .в счет- чике 30 импульсов восстанавливается.

Единичное состояние триггера 29 моделей 1 н тией, ггропускная способность которых равна , исключает эти ветви из дальнейшего рассмотре- ния. Это происходит в результате того, что единичное состояние триггера 29 снимает разрешение с входов элментов И 3-10.

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

К вып1)лнониго второго этапа работы ycTpoiicTBo переходит по импульсу, ко торЬ1Й появляется на выходе многовхо- дового элемента HUH 52. Этот момент определяется установлением 43 блока 2 управления в единичное со стояние. Единичное состояние триггера 43 выдает разрешение на вход элемента И 34, При этом импульсы генератора 50 проходят чс;рс з элемент И 34 и поступают на вход элементов И 36, 39 И 40. Через элементы И 36 и 40 импульсы не проходят, так как они заблокированы 1гулевым состоянием триггеров 44 и 46, а через элемент И 39 импульсы проходят. С выхода элемента И 39 они поступают на вход элемента ИЛИ 42 и далее на полюс 64 блока 2 управления., Через элемент И 37 импул сы не проходят потог-гу, что на друго его входе нет разрешения с единичног выхода триггера 45.

Импульсы с полюса 64 блока 2 управления поступают на полюсы 54 или 55 моделеГ; 1 ветвей, которые в результате коммутации этими полюсами между собой образуют вершину S сети, из которой от(,|сь:ивпется путь гогласНО УСЛОВИИ .

,

Q Q с

0

В указанных, моделях 1 ветвей liM- пульсы с полюса 54 поступят на вход элементов И 5-8. Элементы И 6-8 заблокированы, и через эти элементы импульсы проходить не будут. На всех выходах элемента И 5 есть разрешения, и поэтому импульсы проходят через этот элемент. С выхода элемента И 5 импульсы через элемент ИЛИ 20 поступ ают на единичный вход триггера 24. По первому импульсу из всей серии импульсов, поступивших в модель 1 ветви на по- пюс 54, триггер 24 устанавливается в единичное состояние. Все последующие импульсы подтверждают это состояние триг гера 24, Аналогично, если импульсы поступают на полюс 55 модели 1 ветви, они проходят через элементы И 9 и 1ПИ 21 и устанавливают триг- 1 ер 25 в единичное состояние.

Единичное состояние триггега 24 или 25 вьщает разрешение на вход элемента И 13 через элемент КПИ 22, В результате на полюсе 56 модели ветви появляется разрешение, так как на другом входе элемента И 13 есть разрешение с нулевого выхода триггера 26.

С полиса 56 модели ветви разрешение поступает на соответствующий вход 56(-56 многовходового элемента Ш1И 51. На входы элемента ИЛИ 51 поступают разрешения только от тех моделей ветвей, которые своим полюсом 54 или 55 соединены с полюсом 64 блока 2 управления. Единичное состояние триггеров 24 или 25 свидетельствует о том, что данная модель ветви принадлежит разрезу () из множества разрезов К, Это соответствует первой операции второго этапа работы устройства,

Выбор модели ветви, принадлежащей сформированному разрезу, с наибольшей пропускной способностью и исключение из дальнейшего рассмотрения моделей ветвей, пропускные способности которых больше или равны пропускной способности ветви, принадлежащей разрезу, происходят по разрешению многовходового элемента ИЛИ 51. Это разрешение поступает в блок 2 управления на вход элементов НЕ 48 и И 35.

В результате элемент НЕ 48 снимает разрешение с полюсов 67 всех моделей I ветвей, что блокирует вход элемента И 21 в моделях.

С выхода элемента И 35 разрешение поступает на единичный вход триггера А4 и устанавливает его в единичное состояние. Единичное состояние триггера 44 запрещает прохождение импульсов генератора 50 через элементы И 39 и ИЛИ 42 на полюс 64 блока 2 управления и разрешает прохождение импульсов через элемент И 36 на вход счетчика 49 импульсов и на полюс 63 всех моделей 1 ветвей.

В моделях 1 ветвей импульсы с полюса 63 через элемент И 19 поступают на вход счетчика 31 до его переполнения. Это происходит только у тех моделей,у которых триггер 29 находится в нулевом состоянии, т.е. у моделей, которые принадлежат новой сети. Импульс переполнения счетчика 3 модели ветви поступает через элемент И 14 на нулевые входы триггеров 24 и 25 и единичный вход триггера 26. В результате триггеры 24 и 25 устанавливаются в нулевое состояние, если они ранее были установлены в единичное состояние импульсами, поступившими на полюс 54 или 55 модели ветви. Им- пульс переполнения счетчика 31 через элемент И 15 не проходит, так как нет разрешения на полюсе 60.

Триггер 26, установленный в единичное состояние поступившим на его

единичный вход импульсом переполнения ков 31 всех моделей 1 ветвей выполняет счетчик 49 блока 2 управления.

счетчика 31, устанавливается в нулевое состояние очередньгм импульсом, поступившим на полюс 63. Это происходит потому, что триггер 27 находится в нулевом состоянии и есть разрешение на вход элемента И 11.

Установка в нулевое состояние триггера 24 или 25 импульсом переполнения счетчика 31 производит выбор модели ветви, у которой наибольшая пропускная способность среди всех выделенных ветвей, т.е. пропускная способность этих ветвей новой сети равна max(N Ч ,; Ч , j ) Это происходит в результате того, что триггеры 24 и 25 снимают в соответствующих моделях ветвей разрешения с полюсов 56 и, следовательно, с входов 56t -56п многовходового элемента ИЛИ 51.

В тот момент, когда снимается последнее разрешение с входа 56, -56, элемента ИЛИ 51, блок 2 управления выдает разрешение на полюсы 67 всех

который, начинает свой счет с О , а счетчики 31 моделей 1 ветвей начинают счет с N qii

м

40

Импульс переполнения счетчика 49 блока 2 управления поступает через элемент ИЛИ 42 на полюс 64. Далее этот импульс с полюса 64 поступает 45 на полюсы 54 или 55 моделей 1 ветвей, с которыми соединен полюс 64 блока управления, и весь процесс выполнения этой операции второго этапа повторяется аналогично описанному выпе. Эта операция итерационно/ повторяется до тех пор, пока очередной импульс переполнения счетчика 49 блока 2 управления, поступивший на полюс 64, не появится на полюсе 65. Это происходит потому, что импульс с полюса 64 iiucTynaeT на полюс 54 или 55 моделей 1 ветвей и проходя соответственно элемент И 3 или 5, появляется на полюсе 55 или 54 модели I ветви.

50

55

o

5

моделей I ветвей. Это разрешение в модели ветви поступает на вход элемента И 12. При этом в модели 1 ветви с наибольшей пропускной способностью, которая записана в счетчике 31, из выбранного разреза триггер 27 устанавливается в единичное состояние, так как на другом входе элемента И 12 есть разрешение с единичного выхода триггера 26,

Единичное состояние триггера 27 модели выдает разрешение на входы элементов И 3 и 5, что обеспечивает иск лючение моделей ветвей из дальнейшего рассмотрения на втором эта- ,пе работы устройства и закорачивание полюсов 54 и 55 у этих моделей. Таким образом, в моделях ветвей, у которых пропускная способность равна или больше пропускной способности выбранной модели, триггеры 26 и 27 ус- танавливаются в единичное состояние и их полюсы 54 и 55 оказьшаются закоро- 5 ченными. Конец этой операции работы устройства определяется моментом появления импульса переполнения счетчика 49 блока 2 управления. К этому моменту в счетчиках 31 всех моделей I ветвей восстанавливается информация об их пропускной cnoi обности в новой сети, т.е. происходит регенерация содержимого счетчиков 31. Роль реге- нерационного счетчика для счетчиг0

0

который, начинает свой счет с О , а счетчики 31 моделей 1 ветвей начинают счет с N qii

м

Импульс переполнения счетчика 49 блока 2 управления поступает через элемент ИЛИ 42 на полюс 64. Далее этот импульс с полюса 64 поступает на полюсы 54 или 55 моделей 1 ветвей, с которыми соединен полюс 64 блока управления, и весь процесс выполнения этой операции второго этапа повторяется аналогично описанному выпе. Эта операция итерационно/ повторяется до тех пор, пока очередной импульс переполнения счетчика 49 блока 2 управления, поступивший на полюс 64, не появится на полюсе 65. Это происходит потому, что импульс с полюса 64 iiucTynaeT на полюс 54 или 55 моделей 1 ветвей и проходя соответственно элемент И 3 или 5, появляется на полюсе 55 или 54 модели I ветви.

R момент пояи.пония импульса на гто люсе 65 блока 2 управления все мно- жестио ветней }{овой сети разбивается на два подмножес:тва ,

Одно подмножестно содержит ветви, пропускная спс1собнос 1 ь которых, за- писанняя в счетчике 31, удовлетворяет условщо (1). Триггеры 26 и 27 таких моделей ветвей находятся в единичном состоянии. Другое подмножество содержит новой сети с пропукными способностями, которые не удовлетворяют условию (1), и их триггеры 26 и 27 останутся в нулевом состоянии. Эти модели не участвуют в формировании искомого пути, так как их триггер 26 находится в нулевом состоянии,,

Дальнейшее выполнение оиерапли второго этапа устройством состоит в формировании пути, ветви которого удовлетво1 яют услорпио (I). Для этого В блоке 2 yпpaIзлeftия импульс, поступивший па полч; С 65, устанавл1даает триггер 44 в нулевое состояние, а триггер 46 - в единичное. Нулевое состояние триггера 44 запрещает прохождение импульсов генератора 50 через элемент И 36 на вход счетчика 49 и на ПОЛК1СЫ 63 всех моделей ветвей. Единичное состояние триггера 46 снимает разрешение с полисов 58 и выдает разрешение fta |1олюсы 68 всех моделей 1 ветвей..

Съем разрси1е11ия с полюсов 58 в моделях ветвей блокирует в них элементы И 7 и 9.

Разрешение, появившееся на полюсе 68, устанавливает триггеры 27 в моделях ветвей в нулевое состояние. Нулевое состоя1тие триггера 27 в модели ветви разрывает закоротку полюсов ЗА и 55. что происходит п результате снятия разрешения с входов элементов И 3 и 5. Одновременно с этим импульсы г енератора 50 начинают опять поступать через элементы И 39 и ИЛИ 42 на полюс 6А блока 2 управле гия. С полюса 64 блока управления импульсы поступают на полюс 54 кли 55 моделей 1 ветвей, к полюсам которых подключен полюс 64 блока 2 управле-- ния. При Э1ом на полюс 63 моделей I ветвей импульсы поступать не будут, так как нет рачрешения на входе элемента И 36 от Tpiirrepa 44 блока управления. В указанных моделях 1 ветвей импульси с полюса 54 поступают

0

5

0

5

0

5

0

5

на вход элемента И 8 тех моделей, триггер 26 которых находится в единичном состоянии, и проходят через него. При этом на другом входе элемента И 8 есть разрешение, поступающее через полюс 57 с нулевого выхода триггера 45 блока 2 управления.

В модели 1 ветви импульсы с выхода элемента И 8 через элемент Ш1И 20 поступают на вход триггера 2А, и по первому импульсу из всей серии он устанавливается в единичное состояние. Единичное состояние триггера 24 выдает разрешение на элемент И 6, Поэтому остальные импульсы из всей серии с полюса 54 через элемент И 6 поступают на полюс 55 модели 1 ветви. Это происходит у тех моделей, триггеры 26 которых находятся в единичном состоянии. Таким образом, импульсы распространяются по новой сети через модели ветвей, у которых триггеры 26 находятся в единичном состоянии до тех-пор,, пока они не появятся на полюсе 65 блока 2 управления ,

Поступивший на полюс 65 блока 2 управления импульс проходит через элемент И 38, так как триггер 46 находится в единичном состоянии, и ус-, танавливает триггер 45 в единичное состояние. Единичное состояние триггера 45 выдает разрешение на полюсе 66 всех моделей ветвей и снимает разрешение с их полюса 57, выдает разрешение на элементы И 37 и 40 и снимает разрешение с элемента И 39, При этом с полюсов 57 съем разрешения блокирует элемент И 8 в модели ветви, а появление разрешения на полюсе 66 открывает элемент И 10. Одновременно импульсы генератора 50 через элементы И ЗА и 40 поступают на по.тос 65 и далее на полюсы 55 моделей ветвей, к которым подключен полюсом 65 блок 2 управления,

С полюса 55 в модели 1 ветви нм- пульсы через элементы И 10 и ИЛИ 21 постуТ1ают на единичный вход триггера 25, По первому импульсу из серии импульсов, поступивших на по.люс 55, триггер 25 устанавливается в единичное состояние, которое вьщает разрешение на элемент И А. Поэтому остальные импульсы проходят через этот элемент и поступают на полюс 5А. Это происходит только у тех моделей, у которых триггер 26 находится в единич

1315

ном состоянии. Таким образом, импульсы распространяются по сети через модели ветвей с полюса 55 на полюс 5Д до тех пор, пока не появятся на полюсе 64 блока 2 управления,

С полюса 6Д блока 2 управления импульсы поступают через элемент И 37 на нулевой вход триггера 43 и первый из них устанавливает этот триггер в нулевое состояние. Нулевое состояние триггера 43 сигнализирует о конце решения задачи. При этом модели 1 ветвей, у которых триггеры 24 и 25 находятся одновременно в единичном с стоянии, принадлежат искомому путн„ Эти модели индицируются схемой 33 индикации.

На обобщенной структурной схеме устройства (фиг.З) обозначены блок 69 определения инцидентных ребер, блок 70 выбора максимального кода, блок 71 определения пути, блок 72 определения концевых вершин, группа блоков 73 сравнения, группа блоков 74 вычитания, вход 75 опроса начальной вершины сети устройства, вход 76 одновременного опроса веса ребер сети устройства, вход 77 установки признаков удаления ребер сети, входы 78 задания веса ребер сети блока 69, информационный выход 79 блока 70, выход 80 признака окончания работы устройства, вход 81 опроса пути устройства, выходы 82 признаков принадлежности ребер пути из начальной в конечную вершину сети устройства.

Перед началом работы обнуляют блок 71, в ближах 69 и 72 (в общем случае этот может быть один блок для операций над сетью) задают топологию сети, в блоки 74 вычитания заносят веса соответствующих ребер сети. Подав на вход 76 сигнал уровня логической единигу), опрашивают вес ребер сети. При помощи блока 70 определяют вес наибольшего из ребер сети. Затем удаляют и топологии сети лее ребра, вес которых не меньше веса максимального из них и одновременно на сумматорах 74 фиксируют новый вес ребер, равньгй разности веса максимального ребра и К-го ребра сети (К 1,,...,Р, где Р - количество ребер в сети). Досле этого снимают сигнал с входа 76 и разрешают работу блока 71. Далее работа устройства сводится к циклическому повторению следующих операций. Подавая на вход 75

0

5

0

5

5

0

5

0

5

0

I14

сигнал уровня логической единицы, оп-г ределяют ребра, инцидентные начальной вершине графа.Определяют вес максимального ребра и в соответствии с ним устанавливают в блоке 71 призлгк принадлежности К-го ребра дереву искомого пути (добавляют ребро в текущую топологию блока 71). После этого стягивают все ребра сети, вес которых превьш1ает вес максимального ребра из первого разреза. Далее работа уст-рой- ства повторяется до тех пор, пока на выходе 80 блока 72 не появится сиг- н.гп уровня логической единицы - признак того, что стянуто ребро, инцидентное конечное вершине пути,, В этом случае опросы блока 69 и связанные с этим операции прекращают, производят опрос блока 71, который выбирает из множества добавленных ребер те из них, которые составляют непрерывный путь из начальной в конечную вершину графа, и выдает их на выходе 82 устройства. Выполнение указанного алгоритма обеспечивает средства синхронизации (не показаны). Формула изобретения

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

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

45

,д г

6

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

59

Фиг.1

SSn

66

fS 50 56

Фиг. 2