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

 

Изобретение относится к вычислительной технике и может быть использовано для определения веса максимального потока в сети. Целью изобретения является расширение функциональных возможностей устройства за счет определения величины максимального потока в сети. С этой целью устройство содержит блок определения ребер критического пути в сети, блок выбора минимального кода, группу накапливающих вычитателей, накапливающий сумматор, выход веса максимального потока в сети, выходы веса остаточной пропускной способности ребер сети, вход опроса пути и вход подготовки. Перед началом работы в блоке определения ребер задают топологию сети, обнуляют сумматор, в накапливающие вычитатели заносят вес соответствующих ребер сети. Опрашивают блок определения ребер и определяют состав вершин первого критического пути (т.е. пути с максимальной пропускной способностью). Выделяют ребро с минимальным весом (критическое ребро) и удаляют его из топологии графа, одновременно вес остальных ребер уменьшают на величину веса критического ребра. Указанные операции продолжаются до тех пор, пока в сети существует путь из начальной в конечную вершину сети. 1 з.п. ф-лы. 8 ил.

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

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

РЕСПУБЛИК

„„80„„1474667 А1 (51)4 С 06 F 15/20

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

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

ПРИ ГКНТ СССР

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

/ (21) 4180381/24-24 (22) 1?.01.87 (46) 23.04.89. Бюл. Р 15 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев, И.A. Табунщик, Е.В.Тонкаль и Н.В.Федотов (53) 681 . 333 (088. 8) (56) Авторское свидетельство СССР.

9 64030?, кл. G 06 F 15/20, 1976.

Авторское свидетельство СССР

Ф 1138806, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ СЕТИ (57) Изобретение относится к вычислительной технике и может быть использовано для определения веса максимального потока в сети. Целью изобретения является расширение функциональных возможностей устройства за счет определения величины максимального потока в сети. С этой целью устройство содержит блок определения ребер

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

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

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

Н ABTOPCHQMY СВИДЕТЕЛЬСТВУ критического пути в сети, блок выбора минимального кода, группу накапливающих вычитателей,накапливающий сумматор, выход веса максимального потока в сети, выходы веса остаточной пропускной способности ребер сети, выход опроса пути и вход подготовки. Перед началом работы в блоке определения ребер задают топологию сети, обнуляют сумматор, в накапливающие вычитатели заносят вес соответствующих ребер сети. Опрашивают блок определения ребер и определяют состав вершин первого критического пути (т,е. пути с максимальной пропускной способностью). Выделяют ребро с мини- с

Ю мальным весом (критическое ребро) H удаляют аго яа тололагия графа, одно- Щ временно вес остальных ребер уменьшают на величину веса критического C ребра. Указанные операции продолжаются до тех пор, пока в сети существует путь из начальной в конечную вершину сети. 1 з.п. ф — лы, 8 ил. 4м

2 С5 функциональная схема модели в е тв и; на фиг.4 — функциональная схема блока.управления; на фиг.5 — обобщенная структурная схема устройства; на фиг.6 — обобщенная структурная схема блока определения критического пути; на фиг.7 — блок-схема алгоритма определения веса максимального потока в сети; на фига8 — блок-схема алгоритма определения критического пути в сети.

Модели ветвей I устройства, управляемые блокбм 2 управления содержат с первого по пятый триггеры 3-7, 1474667 счетчик 8 импульсов, с первого по семнадцатый элементы И 9-25 и с первого по пятый элементы ИЛИ 26-30.

Блок 2 управления содержит первый и второй счетчики 31 и 32 импульсов, схему 33 индикации, с первого по шестой триггеры 34-39,элемент ИЛИ 40, с первого по одиннадцатый элементы

И 41-51, элемент НЕ 52 и генератор

53 импульсов, Кроме того, устройство содержит первый и второй многовходовые элементы ИЛИ 54 и 55,с первого по тринадцатый полюсы 56-68 модели ветви 1, полюсы 69 и 70 блока 2 управле- 15 ния, которые соединены с полюсами 56 и 57 тех моделей ветвей сети, между которыми определяется величина максимального потока.

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

В исходном состоянии перед решением задачи на устройство модели ветви 1 посредством полюсов 56 и 57 коммутируются между собой в соответствии с конфигурацией моделируемой сети. Полюсами 69 и 70 блок 2 управления подключается соответственно к полюсам 56 и 57 тех моделей, между которыми определяется величина макси мального потока, и в счетчики 8 все моделей ветвей заносится число импульсов (11 — q. ),где М вЂ” емкость счетчика; q - величина проФ

35 пускной способности ветви между х;-1 и х,-, †.й вершинами сети. Емкости счетчика 8 модели ветви 1 и счетчика 31

-e блока 2 управления одинаковы. Триггеры всех моделей ветвей 1, все тригге-„ ры и счетчики 31 и 32 импульсов блока 2 управления устанавливаются в нулевое состояние (установочные шины на фиг.3 и 4 не показаны), 1

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

Эти операции повторяются до тех пор, пока не будет выполняться условие ф Г, (1), где S u t — соответственно начальная и конечная вершина сети, между которыми определяется величина максимального потока; транзитивное отображение вершины S в сети, А

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

Под путем с наибольшей пропускной способностью понимают такой путь, пропускная способность которого удовлетворяет условию (q;,)) (г

К (х;, х )ЕК

J где К вЂ” любой (S-t)-разрез (в множестве ветвей); х и х — i-ram u j-тая вершины

1 J ветви.

Операция определения пути с наибольшей пропускной способностью между заданными вершинами сети состоит из циклически повторяющихся шагов: нахождение (х„, х ) разреза нз множества К, выделение ветви разреза (х;, х ) с max q; и исключение ветвей, у которых пропускная способность больше или равна пропускной способности выбранной ветви. Эти шаги повторяются до тех пор, пока не будет выделен требуемый путь. Об этом свидетельствует совпадение вершин, между которыми отыскивается указаннный путь. Совпадение вершин происходит в результате закорачивания полюсов выбранных ветвей с целью исключения их из. дальнейшего рассмотрения. Выполнение шагов первой операции свидетельствует о том, что задача определения пути с наибольшей пропускной способностью, решаемая на известном устройстве, входит как подзадача в задачу определения вели1474667

30 чины максимального потока, которая решается на предлагаемом устройстве.

Работа устройства начинается с момента установки триггера 35 блока 2 управления в единичное состояние ° Еди- ничное состояние триггера 35 выдает разрешение на вход элемента И 42.

При этом импульсы генератора 53 проходят через элемент И 42 и поступают на входы элементов И 44, 45 и 47.

Через элементы И 44 и 47 импульсы не проходят, так как на других их входах нет разрешения соответственно с триггеров 34 и 37 (они находятся в нулевом состоянии), а через элемент И 45 импульсы проходят. С выхода элемента И 45 импульсы поступают на вход элемента ИЛИ 40 и далее с

его выхода на вход элемента И 43 и полюс 69 блока 2 управления. Импуль"ы через элемент И 43 не проходят, так как триггер 36 находится в нулевом положении, Импульсы с полюса 69 блока 2 25 управления поступают на полюсы 56 (или 57) тех моделей ветвей 1, которые в результате коммутации этими полюсами между собой образуют начальную S-вершину сети.

В уаазанных моделях ветвей 1 импульсы с полюса 56 поступают на входы элементов И 11-14 и 21. Элементы

И 11, 12, 14 и 21 заблокированы, и через эти элементы импульсы не проходят. На всех входах элемента И 13 есть разрешение, и поэтому импульсы проходят через этот элемент, С выхо, да элемента И 13 импульсы поступают на вход элемента ИЛИ 26 и, пройдя 40 его, на единичный вход триггера 3.

По первому импульсу из всей серии импульсов, поступивших в модель ветви 1 на полюс 56, триггер 3 устанавливается в единичное состояние, Все последующие импульсы подтверждают это состояние триггера 3.

Аналогично, если импульсы поступают на полюс 57 модели, ветви, они проходят через элементы И 15 и ИЛИ 27 50 и устанавливают триггер 4 в единичное состояние.

Единичное состояние триггера 3 или 4 выдает разрешение на вход элемента И 17 через элемент ИЛИ 28, поступающее на полюс 60 модели ветви

1, так как на другом входе элемента

И 17 есть разрешение, снимаемое с нулевого выхода триггера 5.

С полюса 60 модели ветви 1 разрешение поступает на соответствующий вход 60,...60„многовходового элемента ИЛИ 54. На входы элемента ИЛИ поступают разрешения только от тех моделей ветвей, которые своими полюсами 56 и 57 соединены с полюсом 69 блоха 2 управления. Единичное состояние триггеров 3 (или 4) свидетельствует о том, что данная модель ветви

1 принадлежит выбранному (х;, х ) разрезу из множества разрезов К, Это соответствует первому шагу в первой операции решения задачи, Выполнение второго шага в первой операции решения задачи (выбор ветвей, принадлежащих сформированному разрезу, с наибольшей пропускной способностью и исключение их из дальнейшего рассмотрения) происходит по разрешению многовходового элемента

ИЛИ 54. Это разрешение поступает на вход элементов НЕ 52 и И 41 блока 2 управления.

В блоке 2 управления это разрешение поступает с выхода элемечта И 41 на единичный вход триггера 34 и устанавливает его в единичное состояние, Кроме того, разрешение, поступившее на вход элемента НЕ 52, снимает разрешение с полюсов 63 всех моделей ветвей 1. В результате в моделях ветвей вход элемента И 19 заблокирован, Единичное состояние триггера 34 запрещает прохождение импульсов генератора 53 через элементы И 45 и

ИЛИ 40 на полюс 69 блока управления и разрешает прохождение этих импульсов через элемент И 44 на вход счетчика 31 и на полюсы 64 всех моделей ветвей.

В моделях ветвей 1 импульсы с полюса 64 поступают на вход счетчика

8 импульсов через элемент И 23, так как на другом его входе есть разрешение, снимаемое с нулевого выхода триггера 7, Импульсы на вход счетчика 8 поступают до тех пор, пока не происходит его переполнение. Импульс переполнения счетчика 8 в модели ветви 1 поступает через элемент ИЛИ .29 на нулевые входы триггеров 3 и 4 и на единичный вход триггера 5, который устанавливается в единичное состояние. В результате триггеры 3 и 4 устанавливаются в нулевое состояние, если ранее они были установлены в единичное состояние импульсами, по1474667 ступившими на полюсы 56 и 57 модели ветви.

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

5 счетчика 8, устанавливается через элемент ИЛИ 30 в нулевое состояние очередным импульсом, который поступает на полюс 64 модели ветви. Это происходит потому, что триггер 6 находится в нулевом состоянии и есть разрешение на элемент И 18.

Установка в нулевое состояние триггера 3 или 4 импульсом перепол- 15 кения счетчика 8 производит выбор модели ветви, у которой наибольшая пропускная способность среди всех выделенных ветвей. Это происходит. в результате того, что триггеры сни- 20 мают в соответствующих моделях ветвей разрешения с полюсов 60 и, следовательно, с входод 60,...60 „ многовходового элемента ИЛИ 54.

В момент, когда будет снято по- 25 следнее разрешение с входов 60„...60 элемента ИЛИ 54, блок 2 управления выдает разрешение на полюсы 63 всех моделей ветвей, Это разрешение поступает в моделях ветвей на вход элемен- 30 та И 19. При этом в модели .ветви с

i наибольшей пропускной способностью из выбранного разреза триггер 6 устанавливается в единичное состояние разрешением, снимаемым с единичного выхода триггера 5.

В этом случае триггер 5 остается в единичном состоянии, так как единичное состояние триггера 6 запрещает прохождение очередного импульса с 40 полюса 64 через элемент И 1 8 на нулевой вход триггера"5.

Единичное, состояние триггера 6 модели ветви выдает разрешение на входы элементов И 9 и 11, что обеспе- 45 чивает исключение моделей ветвей из дальнейшего рассмотрения на данном шаге и закорачивание полюсов 56 и 57.

Таким образом, в моделях ветвей, у которых пропускная способность равна или больше пропускной способности выбранной модели, триггеры 5 и 6 установлены в единичное состояние и их полюс 56 закорочен с полюсом

57 ° Конец этОГО mara работы устрой- 55 ства определяется моментом появления импульсов переполнения счетчика 31 блока 2 управления. К этому моменту в счетчиках 8 всех моделей ветвей 1 восстанавливается информация о их пропускной способности, т.е. происходит регенерация. Роль регенерационного счетчика для счетчиков 8 всех моделей ветвей 1 выполняет счетчик

31 блока 2 управления. Он начинает свой счет с 0 и его емкость равна

N, а счетчики 8 моделей ветвей 1 начинают счет с (N — q ° ).

1 )

Импульс переполнения счетчика 31 блока 2 управления поступает через элемент ИЛИ 40 на полюс 69, Далее этот импульс поступает на полюсы 56 и 57 моделей ветвей 1, и весь процесс работы устройства на первых двух шагах первой операции повторяется аналогично описанному.. Итерационное выполнение этих шагов устройством повторяется до тех пор, пока импульс переполнения счетчика 31 блока 2 управления, поступивший на полюс 69 не появится на полюсе 70. Это происходит потому, что импульс с полюса

69 поступает на полюс 56 или 57 моделей ветвей 1 и, проходя элементы

И 9 или 11, появляется на полюсе 57 или 56.

В момент появления импульса на полюсе 70 блока 2 управления все множество ветвей моделируемой сети разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность q; которых удовлетворяет условию (2), и в соответствующих им моделях ветвей триггеры 5 и 6 находятся в единичном состоянии, Другое подмножество содержит ветви с пропускными. способностями, которые не удовлетворяют условию (2), и их триггеры 5 и 6 остаются в нулевом состоянии. Эти модели ветвей в выделении пути с наибольшей пропускной способностью не участвуют, так как их триггеры 5 находятся в нулевом состоянии.

Дальнейшая работа устройства состоит в формировании пути с наибольшей пропускной способностью. Для этого в блоке 2 управления импульс, поступивший на полюс 70, проходит через элемент И 48 и поступает на единичный вход триггера 37 и на нулевой вход триггера 34 ° Это происходит потому, что триггер 39 находится в нулевом состоянии и есть разрешение. на другом входе элемента И 48. Через элементы И 51 и 46 импульс с полюса

70 не проходит, так как триггеры 39

1474667

10 и 37 находятся в нулевом состоянии.

Этот импульс устанавливает триггер

34 в нулевое состояние, что блокирует вход элемента И 44 и триггер 37—

Э

5 н единичное, Нулевое состояние триггера 34 запрещает импульсам генератора 53 поступать на полюсы 64 моделей ветвей. Единичное состояние триггера

37 снимает разрешение с полюсон 61 всех моделей ветвей 1 и вьщает разрешение иа полюс 62 всех моделей ветвей. Съем разрешения с полюса 61 всех моделей ветвей 1 блокирует в них элементы И 13 и 15. 15

Сигнал, поступивший на полюс 62 всех моделей ветвей 1 устанавливает триггеры 6 н нулевое состояние. Нулевое состояние триггера 6 в модели ветви 1 разрывает закоротку полюсов 20

56 и 57, что осуществляется за счет снятия разрешения с входов элементов И 9 и 11 . Одновременно с этим импульсы генератора 53 поступают на вход элемента И 42 и далее через эле- 25 менты И 45 и ИЛИ 40 на полюс 69 блока 2 управления. Это происходит потому, что триггеры 35 и 34 находятся соответственно в единичном и нулевом состояниях. С полюса 69 блока 2 30 управления импульсы поступают на полюс 56 или 57 моделей ветвей 1, которые подключены к этому полюсу блока управления.

В указанных моделях Ветвей 1 им» 35 пульсы с полюса 56 поступают на вход элемента И 14 тех моделей, триггер ,5 которых находится в единичном состоянии, и проходят через него. Это происходит потому, что на других его 40 входах есть разрешение с единичного выхода триггера 5, с нулевого выхода триггера 7 и через полюс 58 с нулевого выхода триггера 36 блока 2 управления. 45

В модели ветви 1 импульсы поступают через элементы И 14 и ИЛИ 26 на единичный вход триггера 3. По первому импульсу из всей серии импульсов поступинших в модель ветви на 50 полюс 56, триггер 3 устанавливается в единичное состояние. Единичное состояние триггера 3 выдает разрешение на элемент И 12, на другом входе которого есть разрешение с выхода элемента И 17, что соответствует одновременно состоянию триггера 5 и нулевому состоянию триггера 7. Поэтому остальные импульсы их всей серии с полюса 56 через элемент И 12 поступают на полюс 57 модели ветви 1. Таким образом, импульсы распространяются по сети через модели ветвей, триггеры 5 которых находятся в единичном состоянии до тех пор, пока они не появятся на полюсе 70 блока 2 управления.

Очередной импульс, поступивший на полюс 70 блока управления, проходит через элементы И 48 и 46, так как триггер 37 находится в единичном состоянии, и устанавливает триггер 36 в единичное состояние.

Единичное состояние триггера 36 вьщает разрешение на элементы И 43 и 47 и на полюсы 59 всех моделей ветвей.

При этом снимается разрешение с элемента И 45 и с полюсов 58 всех моделей ветвей 1. В моделях ветвей 1 сьем разрешения с полюса 58 блокирует- элементы И 14, а появление разрешения на полюсе 59 разрешает прохождение сигналов через элемент И 16.

Одновременно с этим импульсы генератора 53 через элементы И 42 и 47 поступают на полюс 70 блока 2 управленйя и далее на полюсы 57 моделей ветвей 1, которые этими полюсами подключены к полюсу 70 блока управления.

С полюса 5? в модели ветви 1 импульсы через элементы И 16 и ИЛИ 27 поступают на единичный вход триггера

4. По первому импульсу из серии импульсов, поступивших на полюс 57, тригrер 4 устанавливается в единичное состояние, которое вьщает разрешение на элемент И 10. Поэтому остальные импульсы проходят через элемент

И 10 и поступают на полюс 56, Это происходит только у тех моделей ветвей, у которых триггер 5 находится в единичном состоянии. Таким образом, импульсы распространяются .по сети через модели ветвей с полюса 57 на полюс 56 до тех пор, пока не поянятся на полюсе 69 блока 2 управления.

При этом модели ветвей 1, у которых триггеры 3 и 4 одновременно находятся в единичном состоянии, принадлежат выделенному пути с наибольшей пропускной способностью. Момент поянления импульса на полюсе 69 блока управления свидетельствует об окон— чании выполнения устройством первой операции н процессе решения задачи определения величины максимального потока. 1474667

После этого устройство переходит к выполнению следующей операции — выделение критической ветви в вьделенном пути с одновременным уменьшением. пропускных способностей всех ветвей выделенного пути на величину пропускной способности критической ветви и удаление этой ветви из дальнейшего рассмотрения, Импульс, поступив- 10 ший на полюс 69 блока 2 управления, проходит через элемент И 43 и поступает на нулевые входы триггеров 3537 и на единичный вход триггера 38.

При этом триггеры 35-37 установлены 15 в нулевое состояние, а триггер 38— в единичное. Нулевое состояние триггера 35 снимает разрешение с входа элемента И 42, что запрещает прохождение импульсов генератора 53 через 20 этот элемент. Нулевое состояние триггеров 36 и 37 снимает разрешение соответственно с полюсов 59 и 62 всех моделей ветвей 1. Единичное состояние триггера 38 вьщает разрешение 25 на вход элемента И 49, что позволяет ю пульсам генератора 53 проходить через этот элемент на вход счетчика

32 и на полюсы бб всех моделей ветвей 1. 30

В моделях ветвей 1, которые принадлежат вьделенному пути, эти импульсы генератора с полюса бб поступают на вход элемента И 24 и проходят 35 через него, так как на других его входах есть разрешение с единичных выходов триггеров 3 и 4 и с нулевого . выхода триггера 7. С выхода элемента

И 24 импульсы поступают.на вход

40 счетчиков 8. Счетчики 8 моделей ветв ей I которые принадлежат в ьделенному пути, накапливают эти импульсы.

В указанных моделях ветвей 1 первым переполняется счетчйк 8 той, в которой пропускная способность наименьшая. Импульс переполнения счетчика 8 такой модели ветви устанавливает в ней. через элемент ИЛИ 29 триггеры

3 и 4 в Нулевое состояние и через элемент И 22 триггер 7 в единичное состояние. Единичное состояние триггера 7 свидетельствует о том, что данная модель ветви является критической. Исключение такой модели ветви 55 из дальнейшего процесса решения задачи определения величины максимального потока происходит в результате того, что единичное состояние триггера 7 снимает разрешение с входов элементов И 9-16, 20 и 21.

Одноврвменно с этим импульс переполнения счетчика 8 модели ветви, которая является критической, появляется íà ее полюсе 6? и, следовательно, на соответствующем этой модели входе

67, ...67„ многовходового элемента

ИЛИ 55. С выхода последнего импульс поступает на нулевой вход триггера

38, на единичный вход триггера 39 блока 2 управления и на полюсы 68 всех моделей ветвей 1.

В моделях ветвей 1 импульс, поступивший на полюс 68, проходит через элементы ИЛИ 30 и 29 и устанавлива ет триггеры 3-5 в нулевое состояние, В блоке 2 управления импульс, поступивший на нулевой вход триггера

39 и единичный вход триггера 39, устанавливает эти триггеры соответственно в нулевое и единичное состояния.

Нулевое состояние триггера 38 снимает разрешение с входа элемента

И 49, что прекращает поступление импульсов генератора 53 на вход счетчика 32 и на полюсы 66 всех моделей ветвей 1.

При этом в модели, которая соответствует критической ветви, счетчик

8 находится в нулевом состоянии.

В остальных моделях ветвей 1, при надлежащих вьделенному пути, в счетчиках 8 уменьшается величина пропускной способности, которая была первоначально представлена числом импульсов (N — q ), на величину пропуск j 1 ной способности критической ветви.

В счетчиках S таких моделей ветвей пропускная способность равна числу импульсов jN — 1; + с1; „, где — пропускная способйость крити11 kp ческой ветви.

При этом число импульсов, которые поступают на вход счетчика 32 блока

2 управления, равно величине пропуск" ной способности критической ветви.

Единичное состояние триггера 39 блока управления вьдает разрешение на вход элементов И 50 и 51. Это свидетельствует о том, что устройство перешло к проверке выполнения уст ловия (1).

Проверка выполнения условия (1) происходит следующим образом. Импульсы генератора 53 проходят через элементы И 50 и ИЛИ 40 и поступают!

474667

14 на полюс 69 блока 2 управления. Далее с полюса 69 эти импульсы поступают на полюсы 56 или 57 тех моделей ветвей 1, которые в результате коммута5 ции этими полюсами между собой образуют начальную Б-вершину сети.

В указанных моделях ветвей 1 импульсы с полюса 56 поступают на вход элементов И 11-14 и 21 ° Элементы

И 11-14 заблокированы, так как все триггеры модели ветви находятся в нулевом состоянии,и через эти элементы импульсы не проходят. На входах элемента И 21 есть разрешение с нуле- 15 вого выхода триггера 7. Эти разрешения поступают с нулевого выхода триггера 7 модели и через полюс 65 с единичного выхода триггера 39 блока

2 управления. С выхода элемента

И 21 импульсы поступают на полюс 57.

Аналогично, если импульсы поступают на полюс 57 модели ветви, они проходят через элемент И 20 и поступают на полюс 56. 25

Таким образом, импульсы распространяются по сети через модели ветвей

1 до тех пор, пока не появятся на полюсе 70 блока 2 управления, Если импульсы появляются на полю- 30 се 70 блока 2 управления, это свидетельствует о том, что условие (1) не выполняется, и устройство повторяет описанный процесс выполнения операций. Повторное выполнение операций устройство начинает по импульсу, который поступает на полюс 70. Этот импульс проходит через элемент И 51 так как триггер 39 находится в единичном состоянии, и устанавливает триг- щ

rep 39 в нулевое состояние, а триггер

35 — в единичное, Момент установки триггера 35 является началом выполнения очередного цикла описанных операций. При этом из моделируемой сети исключается модель, которая соответствует критической ветви, и в некоторых моделях изменяется пропускная способность.

С каждым циклом повторения описанных операций в счетчике 32 накапливаются импульсы генератора 53, Общее число накопленных импульсов огреде-. ляет величину максимального потока, которая равна сумме пропускных способностей критических ветвей и определяет величину максимального потока. Величина максимального потока индицируется схемой 33 индикации.

Если импульсы на полюсе 70 блока управления не появляются, это свиде тельствует о том, что условие (1) выполняется, и повторного запуска устройства не происходит.

Таким образом, структура устройства, обеспечивающая решение задачи определения веса максимального потока в сети, должна включать блок 71 определения ребер критического пути в сети, блок 72 выбора минимального кода, группу накапливающих вычитателей

73 и накапливающий сумматор 74, причем выход сумматора 74 является выходом 75 веса максимального потока в сети, выходы вычитателей 73 являются выходами 76 веса остаточной пропускной способности ребер сети, входы опроса пути и повготовки блока 71 определения ребер критического пути в сети являются входами 77 и 78 устройства.

Блок 71 определения ребер критического пути в сети включает в себя узел 79 определения инцидентных ребер графа, узел 80 выбора максимального кода, узел 81 определения пути в сети, группу узлов 82 сравнения и узел 83 определения концевых вершин ребер сети, выход признака совпаден.. я концевой вершины ребра с конечной вершиной сети является одноименным выходом 84 блока 71, выходы веса ребер сети блока 81 являются одноименными выходами 85 блока 71 входы 86 установки признаков удаления ребер сети подключены к одноименньм входам узлов 79 и 83.

Перед началом работы в блоке 71 (79, 81, 83) задают топологию графа.

Блоки устройства синхронизируют в соответствии с алгоритмами определения веса максимального потока (фиг,7) и алгоритма определения критического пути в сети (фиг.З), Формула и з о б р е т е н и я

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

Р накапливающих вычитателей, где

1474667

30

2.устройство по п.1, о т л ич ающе е с я тем, что блок определения ребер критического пути в сети содержит узел определения инцидентных ребер вершин сети, удел выбора максимального кода, узел определения пути в сети, группу из К узлов сравнения и узел определения концевых вершин ребер сети, причем вход 40 опроса блока подключен к входу опроP — количество ребер в сети, и накапливающий сумматор, причем вход

1 опроса устройства подключен к одноименному входу блока определения ребер критического пути в сети, выход веса K-го ребра пути (К=1,...P) подключен к К-му информационному входу блока выбора минимального кода, К-й выход позиции минимального кода .)р которого подключен к входу установки признака исключения К-го ребра сети блока определения ребер критического пути в сети и к входу разрешения счета К-го накапливающего вычитателя 15 группы, выход разности которого является выходом веса остаточной пропускной способности К-го ребра сети устройства и подключен к входу задания веса К-го ребра сети блока определе- 20 ния ребер критического пути в сети, вход подготовки которого является одноименным входом устройства, информационный выход блока выбора минимального кода подключен к входам вычитае- 2 мого всех накапливающих вычитателей группы и к входу слагаемого накапливающего сумматора, выход которого является выходом веса максимального потока в сети устройства.

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

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

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

1474667

1474667

1474667 ие.

Фиг.6

1474667

Ялом

79 л" л р

Фие. 7

Фи@8

Составитель А,Иишин

Техред Л.Сердюкова Корректор Л.Пилипенко

Редактор О.Юрковецкая

Заказ 1896/48 Тираж 667 Подписное

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

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

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