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

 

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

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

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

РЕСПУБЛИК (. )1 4 G 06 F 15/20

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

80

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (2)) 4213206/24-24 (22) 19.03.87 (46) 07.09.89. Бюл. Р 33 (7I) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев, И,А.Табунщик, Е.В.Тонкаль и Н.В.Федотов (53) 68).333(088.8) (56) Авторское свидетельство СССР

У 1138806, кл. G 06 F 15/20, 1983.

Авторское свидетельство СССР по заявке )I 418038)/24-24, кл. С 06 F 15/20, 1987.

„„SU„, 1506451 А 1

2 (54) УСТРОЙСТВО ДЛЯ АНАПИЗА ПАРАМЕТFOB СЕТИ (57) Изобретение относится к вычисли-. тельной технике и может быть использовано для определения в сети пути максимальной ширины. С этой целью устройство содержит блок 69 определения инцидентных ребер, блок 70 выбора максимального кода, блок 71 определения пути, блок 72 определения концевых вершин, группу блоков 73 сравнения, группу блоков 74 вычитания, вход 75 опроса начал. ьой вершины ее3 150645 ти устройства, вход 76 одновременного опроса веса ребер сети устройства, вход 77 установки признаков удаления ребер сети, входы 78 задания веса ре5 бер сети блока 69, информационный выход 79 блока 70, выход 80 признака; окончания работы устройства, вход 81 опроса пути, выходы 82 признаков при" надлежности ребер пути иэ начальной в lO конечную вершину сети устройства.

Перед началом работы обнуляют блок 71, в блоках 69,72 задают топологию сети, в блоки 74 вычитания заносят веса соответствующих ребер сети. На первом 15 этапе работы выбирают ребра с максимальным весом и исключают (удаляют) их иэ топологии графа. Далее циклически определяют ребра, инцидентные начальной вершине графа, выбирают ребро с максимальным весом, добавляют его в топологию сети, формируемую блоком 71,и затем стягивают все ребра, вес которых не меньше веса выбранного ребра. Цикл продолжается до тех пор, пока ребро не будет стянуто в конечную вершину сети (сигнал появляется

1 на выходе 80), после этого опрашивают блок 71. 3 ил.

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

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

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

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

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

Кроме того, устройство содержит (фиг.2) первый 51.и второй 52 многовходовые элементы ИЛИ и многовходовый элемент И 53. Число входов у каждого многовходового элемента со

55 ответствует числу моделей ветвей.

Устройство имеет полюсы 54-68, из которых полюсы 54 и 55 у моделей ветвей служат для коммутации их меуду собой согласно конфигурации моделируемой сети. Остальные полюсы моделей ветвей служат для подключения их к блоку управления, что обеспечивает их синхронную работу.

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

Суть решения задачи определения пути максимальной ширины заключается в выполнении устройством двух этапов работы. Первый этап включает преобразование исходной сети в новую сеть, которая содержит ветви исходной сети с пропускными способностями, равными (ц „— q;> ), (1) где q, — наибольшая существующая

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

Кроме того, новая сеть не содержит ветвей с пропускной способностью, равной Ч;,, т.е. такие ветви исключаются иэ рассмотрения.

Второй этап представляет собой решение задачи определения пути с наибольшей пропускной способностью.в но5 1 50645 6 вои сети и включает циклически понто- является сигнал, так как триггер 29 ряюшие<ч операции нахождения (x x ) находится в нулевом состоянии. Этот разрезл из множества р зрезон К, нь<де- сигнлл поступает на полюс 59 и ",алее

1 ленил нстни разреза (х:; ) с max(a ° — на соответствующий этой модепи ветви

q. ), исключения з длньней<пего р-с- »ход 59< -59д многовходового элем нсмотреиин нет»с.й, у которых пропуск- тл И 53. Дальнейшее поступление имная способность больше или ранна про- пульсов генератора 50 блока 2 уппусной способности выделенной ветви. -.лвления на полюс 62 всех моделей

Исключение этих ветвей происходит эл- !р ветвей приводит к тому что все моде 1 корачи»линем по»юсов 54 и 55. Эти цик- пи выдают сигнал на свои полюсы 59 и., лически повторяющиеся операции выпол- следовательно, на все входы 59<-59я няются до тех пор, пока полюсы, между многовходового элемента И 53, К этокоторыми отыскивается путь, ис будут му моменту в счетчики 31 импульсов закорочены (т.е. не совпа (. . овпадут). После !5 к.лживой модели ветви поступает число этого производят формиронание самого импульсов, равное пропускной способпу " и. Ветви, принадлежа- и< сти — q; . В модели ветви, которая пути в новой сети щие этому пути н ноной сети, сонпада- имела наибольшую пропускную способют н исходной сети с ветвями, которы<. ность — с!,, счетчик 30 обнуляется нуляется. формируют путь максимальной ширин»<, ?p В остальны!с моделях ветвей в счетчик 30 заносится число импульсов, Перед началом работы у Tpor:ñòâл рлиисе (N — q, ). тригге ы 24-29 всех мо р р оделей нетнеи При появлении импульса на входах и триггеры 43-47 блока 2 управления, 9 -59с1 многонходового элемента И 53 а также счетчики 31 имиульсон Pãåê ?5 от Pñåê моделей ветвей на его выхомоделей ветвей и счетчик 49 блока уп- де появляется сигнал который постуЭ ранления устанавливаются н и1-ясное пает на полюс 60 всех моделей. состояние (устлноночныс шины не В каждой модели ветви сигнал с показаны). и< лю =а 60 посгупает на вход "-,леменРлбота устройства нлчиилется с мо- „-p < н HF. 32, И 15 и 18. В результате мента устанонки триггера 47 блока 2 "лемент НЕ .32 снимает разрешение с управления н единичное состояние, »хода элемента И 14. импульсы генечто соответствует илчллу ньи|олнечия р.r r ора 50, поступающие на полюс 6", устроис тном пери огir эт<иr л . Единичное проходят через элементы И 18 и состояние триггера 47 ныдает разреше- I - III 23 иа вход счетчика 31.

35 ние на вход элемента И 41, При этом Дальнейшее поступление импульсов импульсы геиер".тора 50, поступающие генератора 50 блока 2 управления на на второй »ход элемента И 41, прохо- по..юс 62 приводит к тому, что у всех дйт через этот элемент нл поспюс 62 моделей ветвей первым переполняетвсех моделей ветвей. В моделя нст- 4р ся счетчик 31 тот, в который было ни эти импульсы генератора поступают злиесено наибольшее число импульсов, на вход счетчика 30 и через элементы Такой моделью ветви является модель, И 17 и ИЛИ 23

ИЛ 23 на »ход . четчика 34.

r у которой наибольшая пропускная споЭто происходит пот«му, что на втором собность. Импульс переполнения счетвходе элемента И 17 есть разрешение 45 чика 3! устанавливает в модели тригс нулевого выхода триггера 29. гер 29 в единичное состояние и появПосле поступления числа q, им- ляет-.я через полюс 61 на соответстпульсон н счетчик 30 каждой модели »ующем этой модели входе 61 -61 мно1 и мно ветви на его выходе появляется им- гонходоного элемента ИПИ 52. пульс переполнения, который поступа- 50 С вьгхода многовходового элемента ет на единичный вход триггера 28. ИЛИ 52 импульс переполнения поступает

Этот импульс устанавливает триггер 28 ыл единичный вход триггера 43 и нуи единичное состояние.. которое выдает леной вход триггера 47, что устанавразрешение на вход элемента И !6.и, линяет их н соответствующее состояние. кроме того, снимлет разрешение с нхо- 55 Нулевое состояние триггера 47 запреда элемента И I . В результате импуль- ш: ет дальнейшее прохождение импульсы генерлт<>рл не проходят через эле- . н генератора 50 через элемент И 41 мент И 17 и ИЛИ 23 на вход счетчика 3 . нл полюс 62 всех моделей ветвей. К

Однако нл ннхсде элемента И 16 по- этому моменту счетчики 31 импульсов каждой модели ветви, у которой н этот счетчик было занесено число им> пульсов, равное q,! с >якие модели соотнетств ую1 Ветвям с наибольшей пропускной спосoáIIoñтью), обнуляется.

В счетчик 30 этих моделей заносится число N — q импульсов. В счетчи(J ки 31 импульсов Остальнь1х моделей

> ветвей заносится число N — q,„„ + q, импульсон, В счетчики 30 импульсов этих же неTBcй эаносится число N

q импульс он. Другими словами, исходная информация о пропусной способности всех моделей ветвей .в счетчике 30 импульсов носстанавливается.

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

P реэулы ате выполнения описанных 25 операций устройством исходная сеть преобразуется в нонук сеть, что снидетельс тнует OEI Окончании первого

Эта11а >)а(OTE>f

К вып(х>1н(1нию Втоtoão этап 1 рябо гы уст ро11с гв о псреход11т 11О импульсу > к О тopblй пoянляс тc.я и "(нг!хОдe мнo! ОвхО

poBol элемент,1 И>П! 52 Этот мс>мент

ОПрЕдЕЛяетс-я уотаНОВЛЕНИЕМ трИГГЕра

43 блока 2 управления н единичное ".О"5 стояние. Единичное состояние триггера 43 ныдс(ет разрешение на вход элемента И 34. При этом импульсы генератора 50 проходят чс.реэ элемент И 34 и поступают на Вход элементов И 36, 39 и 40. Через элементы И 36 и 40 импульсы не проходят, так как Они заблокированы ну;1еным состоянием триггеров 44 и 46, а через элеменг И 39 импульсы проходят. С выхода элемента 45

И 39 они поступают на вход элемента

ИЛИ 42 и далее на полюс 64 блока 2 управления. Через элемент И 37 импуль-, сы не проходRI потому, что на другoM

dro входе нет разрешения с единичного, выхода триггера 45.

Импульсы с и(люса 64 блока 2 управления поступях . на полюсы 54 или 55 мопелей Ветвей, которые в

55 результате xo 111утации этими полюсами между собой образуют вершину S сети, иэ которой othlo1 инается путь .. оглас— но услонин>

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

И 9 и ИЛИ 21 и устанавливают триггер 25 в единичное состояние.

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

С полюса 56 модели 1 ветви разреч(ение поступает на соответствующий вход 56(-56 > многовходоного элемента

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

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

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

1506451

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

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

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

Установка в нулевое состояние триггера 24 или 25 импульсом переполнения счетчика 31 производит выбор модели ветви, у которой наибольшая 45 пропускная способность среди всех выделенных ветвей, т.е. пропускная способность этих ветвей новой сети

° равна max(N — q + q," ) . .Это происходит в результате того, что тригге50 ры 24 и 25 снимают s соответствующих моделях ветвей разрешения с полюсов 56 и, следовательно, с входов

56» -56»» многовходового элемента

ИЛИ 51, 55

В тот момент, когда снимается последнее разрешение с входа 56» -56„ элемента ИЛИ 51, блок 2 управления выдает разрешение на полюсы 67 всех моделей I ветвей. Это разрешение в модели ветви поступает на вход элемента И 12. При этом в модели ветви с наибольшей пропускной способностью, которая записана в счетчике 31, из выбранного разреза триггер 27 устанавливается в единичное состояние, так как на другом входе элемента

И 12 есть разрешение с единичного выхода триггера 26.

Единичное состояние триггера 27 модели выдает разрешение на входы элементов И 3 и 5, что обеспечивает исключение моделей ветвей иэ дальнейшего рассмотрения на втором эта,пе работы устройства и закорачивание полюсов 54 и 55 у этих моделей. Таким образом, в моделях ветвей, у которых пропускная способность равна или больше пропускной способности выбранной модели, триггеры 26 и 27 ус ° танавливаются в единичное состояние и их полюсы 54 и 55 оказываются закороченными. Конец этой операции работы устройства определяется моментом появления импульса переполнения счетчика 49 блока 2 управления. К этому моменту в счетчиках 31 всех моделей I ветвей восстанавливается информация об их пропускной спо. »бности в новой сети, т.е. происходит регенерация содержимого счетчиков 31. Роль регенерационного счетчика для счетчи ков 31 всех моделей I ветвей выполняет счетчик 49 блока 2 управления, которьп».начинает свой счет с "0, а счетчики 31 моделей 1 ветвей начина1 ют счет с Н вЂ” q, + q;!

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

Эта операция итерациоино повторяется до тех пор, l»oKa очередной импульс переполнения счетчика 49 блока 2 управления, поступивший на полюс 64, не появится на полюсе 65. Это происходит потому, что импульс с полюса 64 ,:оступает на полюс 54 или 55 моделей ветвей и проходя соответственно элемент И 3 или 5, появляется на полюсе 55 или 54 модели I ветви.

1 150645!

В момент появления импульса на НОлюсе 65 блоь а увр;!Вления Все множество ветвей нсгвс и сети разбивается

H а д еЗ а и О дм н О ж е c . т IE a .

Одно подмножество содержит ветви, пропускная с"uc >бнос Eь которых, за— писанная в счет>!ике 31, удовлетворяет условию (1). Триггеры 26 и 27 таких моделей ветвей находятся в единичном состоянии. Другое пс!дмножество содержит ветви новой сети с пропускными способностями, которые не удовлетворяют условя!о (1), и их триггеры 26 и 27 останутся в нулевом состоянии. 3ти модели не участвуют в формирОвaHEEH EIcкомОгО пути TBK к лк их триггер 26 нахопится в нулевом

15 состоянии.

Дальнейшее Вьпгс>лнение Опер авии

20 второго этапа устройством Состоит в формировали!! пути, ветви которого удонлетвО1>яют условию (1), Для этого в блоке 2 управления EEIEIEyzbc, поступивший на полЮС 65, устанавливает триггер 44 В ну!!евс>е состояние, а триггер 46 — в единичное, Нулевое состояние триггера 44 запрешает прохождение импульсов генератора 50 через элемент И 36 на вход счетчика 49 и на с>с!лн>сь> 63 Вс ех моделей Ветвей.

Ед!!Ничнс!е состоян!!с триггера 46 снимает разрсшение с полюсов 58 и Выдает разрешение па >«и>юсы 68 всех моделей I ветвей.

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

Pазрешение, псявившееся на полюсе 68, устанавливает В 40 моделях ветвей В нулевое состояние.

Нулевое состояние триггера 27 в модели ветви разрываст закоротку полюсов 54 и 55, что происходит в резульТаТр. снятия р3зрешения с ВХОДОВ эле 45 ментов И 3 и 5. Одновременно с этим импульсы генератора 50 начинают опять поступать через элементы И 39 и ИЛИ 42 на полюс 64 блока 2 управления. С полюса 64 бзсока управления импульсы поступают на полюс 54 или 55 моделей 1 Ветвей, к полюсам которых подключен полюс 64 блока 2 управле» ния. при этом на полюс 63 моделей 1 ветвей импульсы поступать не будут, 55 таК КаК НЕТ РазРЕШЕНИЯ На ВХОДЕ ЭЛЕмента И 36 От три! гера 44 блока управления. В указанных моделях 1 ветвей импульсы с. полюса 54 поступают

12

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

В модели 1 ветви импульсы с выхода элемента И 8 через элемент

Ю1И 20 поступают на вход триггера 24, и по первому импульсу из всей серии он устанавливается в единичное состояние. Единичное состояние триггера 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 через элементы И 34 и 40 поступают на полюс 65 и далее на полюсы 55 моделей ветвей, к которым подключен полюсом 65 блок 2 управления.

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

l50645I

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

С полюса 64 блока 2 управления импульсы поступают через элемент И 37 на нулевой вход триггера 43 и первый иэ них устанавливает этот триггер в

1О нулевое состояние. Нулевое состояние триггера 43 сигнализирует о конце решения задачи. При этом модели ветвей, у которых триггеры 24 и 25 находятся одновременно в единичном со.

15 стоянии, принадлежат искомому пути.

Эти модели индицируются схемой 33 индикации.

На обобщенной структурной схеме устройства (фиг.3) обозначены б лок 69 определения инцидентных ре20 бер, блок 70 выбора максимального кода, блок 7! определения пути, блок 72 определения концевых вершин, группа блоков 73 сравнения, группа блоков 74 25 вычитания, вход 75 опроса начальной вершины сети устройства, вход 76 одновременного опроса веса ребер сети устройства, вход 77 установки признаков удаления ребер сети входы 78

1 30 задания веса ребер сети блока 69, информационный выход 79 блока 70, выход 80 признака окончания работы устройства, вход Rl опроса пути устройства, выходы 82 признаков принадлежности ребер пути иэ начальной н конечную вершину сети устройства.

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

45 ребер сети. При помощи блока 70 определяют вес наибольшего иэ ребер сети. Затем удаляют иэ топологии сети .все ребра, вес которых не меньше веса максимального иэ них и одновременно на сумматорах 74 фиксируют новый

50 вес ребер, равный разности веса максимального ребра и К-го ребра сети (K I,...,Р, где P — количество ребер в сети), После этого сним,ют сиг55 нал с входа 76 и разрешают работу блока 71, Далее работа устройства сводится к циклическому повторению следующих операций. Подавая на вход 75 сигнал уровня логической единицы оп=

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

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

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

Р— количество рсбер н сети, блок определения концевых нершин и группу из Р блокон вычитания, причем вход опроса начальной вершины сети устройства подключен к одноименному входу блока определения инцидентных ребер, выход веса К-ro ребра которого (К

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

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

1с0645

16 ра блока определения пути, выход признака принадлежности К-го ребра пути из начальной в коиечную вершину является одноименным выходом устройст- ва, отличающееся тем, что, 5 с целью расширения функциональных возможностей устройства за счет определения s сети пути максимальной ширины, информационный выход блока выбо- 1О ра максимального кода подключен к входам вычитаемого всех блоков вычитания группы, выход К-го блока вычи.тания группы подключен к входу задания веса К-го ребра блока определения инцидентных ребер и к второму информационному входу К-го блока сравнения груПпы, выход признака "I!e меньше" .которого подключен к входам признака удаления К-го ребра сети блока определения инцидентных ребер и блока определения концевых вершин, входы установки признаков удаления ребер которых подключены к одноименному входу устройства, вход одноименного опроса веса ребер сети устройства подключен к одноименному входу блока определения инцидентных ребер, вход опроса пути устройства подключен к одноименному входу блока определения пути.

1506451

Составитель А.Мишин

ТехредА.Кравчук .Корректор С.Черни

Редактор В.Петраш

В

Зак аз 6660 Тирам 668 Подписно одписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1О1