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

счетчик 8 импульсов, с первого по семнадцатый элементы И 9-25 и с первого по пятый элементы ИЛИ 26-30. Блок 2 управления содержит первый и второй счетчики 31 и 32 импульсов, схему 33 индикации, с первого по шестой триггеры 34-39,элемент ИЛИ 40, с первого по одиннадцатый элементы И 41-51, элемент НЕ 52 и генератор 53 импульсов. Кроме того, устройство содержит первый и второй многовходо- вые элементы ИЛИ 54 и 55,с первого п тринадцатый полюсы 56-68 модели ветви 1, полюсы 69 и 70 блока 2 управле ния, которые соединены с полюсами 56 и 57 тех моделей ветвей сети, между которыми определяется величина максимального потока.

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

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

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

i

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

Эти операции повторяются до тех пор, пока не будет выполняться условие

t 0 Г,

(О,

S и t - соответственно начальная и конечная вершина сети, между которыми определяется величина максимального потока;

- транзитивное отображение вершины S в сети.

А

Г,

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

0

5

0

5

0

5

Р min

К

max

q,jJJ

(2)

(xf, Xj)CK где К - любой (S-t)-разрез (в множестве ветвей); х , и х: - i-тая и j-тая вершины

ветви.

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

Работа устройства начинается с момента установки триггера 35 блока 2 управления в единичное состояние. Единичное состояние триггера 35 выдает разрешение на вход элемента И 42. При этом импульсы генератора 53 проходят через элемент И 42 и поступают на входы элементов И 44, 45 и 47. Через элементы И 44 и 47 импульсы не проходят, так как на других их входах нет разрешения соответственно с триггеров 34 и 37 (они находятся в нулевом состоянии), а через элемент 45 импульсы проходят. С выхода элемента И 45 импульсы поступают на вход элемента ИЛИ 40 и далее с его выхода на вход элемента И 43 и полюс 69 блока 2 управления. Импульсы через элемент И 43 не проходят, так как триггер 36 находится в нулевом положении.

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

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

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

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

С полюса 60 модели ветви 1 разрешение поступает на соответствующий вход 60,...60„ многовходового элемента ИЛИ 54. На входы элемента ИЛИ ь

поступают разрешения только от тех

моделей ветвей, которые своими полюсами 56 и 57 соединены с полюсом 69 блока 2 управления. Единичное состоя0 ние триггеров 3 (или 4) свидетельствует о том, что данная модель ветви 1 принадлежит выбранному (х ,., х ,) разрезу из множества разрезов К. Это соответствует первому шагу в пер15 вой операции решения задачи.

Выполнение второго шага в первой операции решения задачи (выбор ветвей, принадлежащих сформированному разрезу, с наибольшей пропускной способ0 ностью и исключение их из дальнейшего рассмотрения) происходит по разрешению многовходового элемента ИЛИ 54. Это разрешение поступает на вход элементов НЕ 52 и И 41 блока 2

5 управления

В блоке 2 управления это разрешение поступает с выхода элемента И 41 на единичный вход триггера 34 и устанавливает его в единичное состояние,

0 Кроме того, разрешение, поступившее на вход элемента НЕ 52, снимает разрешение с полюсов 63 всех моделей ветвей 1. В результате в моделях ветвей вход элемента И 19 заблокирован.

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

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

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

ступившими на полюсы 56 и 57 модели ветви.

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

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

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

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

Единичное состояние триггера 6 модели ветви выдает разрешение на входы элементов И 9 и II, что обеспе чивает исключение моделей ветвей из дальнейшего рассмотрения на данном шаге и закорачивание полюсов 56 и 57 Таким образом, в моделях ветвей, у который пропускная способность равна или больше пропускной способности выбранной модели, триггеры 5 и 6 установлены в единичное состояни и их полюс 56 закорочен с полюсом 57. Конец этого шага работы устройства определяется моментом появления импульсов переполнения счетчика 31 блока 2 управления. К этому моменту в счетчиках 8 всех моделей ветвей 1

5

0

5 0

з

5

0

0

5

восстанавливается информация о их пропускной способности, т.е. происходит регенерация. Роль регенерацион- ного счетчика для счетчиков 8 всех моделей ветвей 1 выполняет счетчик 31 блока 2 управления. Он начинает свой счет с 0 и его емкость равна N, а счетчики 8 моделей ветвей 1 начинают счет с (N - q ) .

Импульс переполнения счетчика 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

914

и 37 находятся в нулевом состоянии. Этот импульс устанавливает триггер 34 в нулевое состояние, что блокируе вход элемента И 44, и триггер 37 - в единичное. Нулевое состояние триггера 34 запрещает импульсам генератора 53 поступать на полюсы 64 моделей ветвей. Единичное состояние триггера 37,снимает разрешение с полюсов 61 всех моделей ветвей 1 и выдает разрешение на полюс 62 всех моделей ветвей. Съем разрешения с полюса 61 всех моделей ветвей блокирует в них элементы И 13 и 15.

Сигнал, поступивший на полюс 62 всех моделей ветвей 1, устанавливает триггеры 6 в нулевое состояние. Нулевое состояние триггера 6 в модели ветви 1 разрывает закоротку полюсов 56 и 57, что осуществляется за счет снятия разрешения с входов элементов И 9 и 11. Одновременно с этим импульсы генератора 53 поступают на

вход элемента И 42 и далее через эле-25 дение сигналов через элемент И 16.

35

40

менты И 45 и ИЛИ 40 на полюс 69 блока 2 управления. Это происходит потому, что триггеры 35 и 34 находятся соответственно в единичном и нулевом состояниях. С полюса 69 блока 2 30 управления импульсы поступают на полюс 56 или 57 моделей ветвей 1, которые подключены к этому полюсу блока (управления.

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

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

50

55

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

С полюса 57 в модели ветви 1 импульсы через элементы И 16 и ИЛИ 27 поступают на единичный вход триггер 4. По первому импульсу из серии импульсов, поступивших на полюс 57, триггер 4 устанавливается в единичное состояние,которое выдает разрешение на элемент ИЗО. Поэтому остальные импульсы проходят через элемент И 10 и поступают на полюс 56. Это происходит только у тех моделей вет вей, у которых триггер 5 находится в единичном состоянии. Таким образом импульсы распространяются -по сети ч рез модели ветвей с полюса 57 на полюс 56 до тех пор, пока не появятся на полюсе 69 блока 2 управления. При этом модели ветвей 1, у которых триггеры 3 и 4 одновременно находятся в единичном состоянии, принадлежат выделенному пути с наибольшей пропускной способностью. Момент появ ления импульса на полюсе 69 блока управления свидетельствует об окончании выполнения устройством первой операции в процессе решения задачи определения1 величины максимального потока.

О

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

Очередной импульс, поступивший на полюс 70 блока управления, проходит через элементы И 48 и 46, так как триггер 37 находится в единичном состоянии, и устанавливает триггер 36 в единичное состояние. Единичное состояние триггера 36 выдает разрешение на элементы И 43 и 47 и на полюсы 59 всех моделей ветвей. При этом снимается разрешение с элемента И 45 и с полюсов 58 всех моделей ветвей 1 о В моделях ветвей 1 съем разрешения с полюса 58 блокирует элементы И 14, а появление разрешения на полюсе 59 разрешает прохож35

40

30

45

50

5

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

С полюса 57 в модели ветви 1 импульсы через элементы И 16 и ИЛИ 27 поступают на единичный вход триггера 4. По первому импульсу из серии импульсов, поступивших на полюс 57, триггер 4 устанавливается в единичное состояние,которое выдает разрешение на элемент ИЗО. Поэтому остальные импульсы проходят через элемент И 10 и поступают на полюс 56. Это происходит только у тех моделей ветвей, у которых триггер 5 находится в единичном состоянии. Таким образом, импульсы распространяются -по сети через модели ветвей с полюса 57 на полюс 56 до тех пор, пока не появятся на полюсе 69 блока 2 управления. При этом модели ветвей 1, у которых триггеры 3 и 4 одновременно находятся в единичном состоянии, принадлежат выделенному пути с наибольшей пропускной способностью. Момент появления импульса на полюсе 69 блока управления свидетельствует об окончании выполнения устройством первой операции в процессе решения задачи определения1 величины максимального потока.

После этого устройство переходит к выполнению следующей операции - выделение критической ветви в выделенном пути с одновременным уменьшением пропускных способностей всех ветвей выделенного пути на величину пропускной способности критической ветви и удаление этой ветви из дальнейшего рассмотрения. Импульс, поступив- ший на полюс 69 блока 2 управления, проходит через элемент И 43 и поступает на нулевые входы трш геров 35- 37 и на единичный вход триггера 38. При этом триггеры 35-37 установлены в нулевое состояние, а триггер 38 - в единичное. Нулевое состояние триггера 35 снимает разрешение с входа элемента И 42, что запрещает прохождение импульсов генератора 53 через этот элемент. Нулевое состояние триггеров 36 и 37 снимает разрешение соответственно с полюсов 59 и 62 всех моделей ветвей 1. Единичное состояние триггера 38 выдает разрешение на вход элемента И 49, что позволяет импульсам генерафора 53 проходить через этот элемент на вход счетчика 32 и на полюсы 66 всех моделей ветвей 1.

В моделях ветвей 1, которые принадлежат выделенному пути, эти импульсы генератора с полюса 66 поступают на вход элемента И 24 и проходят 35 надлежащих выделенному пути, в счетчерез него, так как на других его входах есть разрешение с единичных выходов триггеров 3 и 4 и с нулевого выхода триггера 7. С выхода элемента И 24 импульсы поступают на вход счетчиков 8. Счетчики 8 моделей ветвей I, которые принадлежат выделенному пути, накапливают эти импульсы. В указанных моделях ветвей I первым переполняется счетчик 8 той, в которой пропускная способность наименьшая. Импульс переполнения счетчика 8 такой модели ветви устанавливает в ней через элемент ИЛИ 29 триггеры 3 и 4 в Нулевое состояние и через элемент И 22 триггер 7 в единичное состояние. Единичное состояние триггера 7 свидетельствует о том, что данная модель ветви является крити40

45

50

чиках 8 уменьшается величина пропускной способности, которая была первоначально представлена числом импульсов (N - q -), на величину пропускной способности критической ветви. В счетчиках 8 таких моделей ветвей пропускная способность равна числу импульсов {N - q ij + q. .fj, , где it w пропускная способность критической ветви.

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

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

ра 7 снимает разрешение с входов элементов И 9-16, 20 и 21.

Одновременно с этим импульс переполнения счетчика 8 модели ветви, которая является критической, появляется на ее полюсе 67 и, следовательно, на соответствующем этой модели входе 67.,... 67 р многовходового элемента ИЛИ 55. С выхода последнего импульс поступает на нулевой вход триггера 38, на единичный вход триггера 39 блока 2 управления и на полюсы 68 всех моделей ветвей I.

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

В блоке 2 управления импульс, поступивший на нулевой вход триггера 39 и единичный вход триггера 39, устанавливает эти триггеры соответственно в нулевое и единичное состояния.

Нулевое состояние триггера 38 снимает разрешение с входа элемента И 49, что прекращает поступление импульсов генератора 53 на вход счетчика 32 и на полюсы 66 всех моделей ветвей I.

При этом в модели, которая соответствует критической ветви, счетчик 8 находится в нулевом состоянии. В остальных моделях ветвей I, при

надлежащих выделенному пути, в счет

чиках 8 уменьшается величина пропускной способности, которая была первоначально представлена числом импульсов (N - q -), на величину пропускной способности критической ветви. В счетчиках 8 таких моделей ветвей пропускная способность равна числу импульсов {N - q ij + q. .fj, , где it w пропускная способность критической ветви.

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

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

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

Исключение такой модели ветви 55 ловия (1).

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

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

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

131

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

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

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

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

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

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

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

10

20

25

|5

§

30

35

40

0

Если импульсы на полюсе 70 блока управления не появляются, это свиде-J тельствует о том, что условие (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) и алгоритма определения критического пути в сети (фиг.8).

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

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

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

потока в сети устройства.

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

ФиМ

Фиг. 2.

tf №n S3

«a

Г

n 5J67, S7n

BlВ..

Фя в Т

L

5 И Is ЯW

Ј/.:

ь

Фиг-В

ttofop ребра с нининальнын (но не нулевым) весон {критическою ребра)

72

1

уваление критическою ребра из топологии tpwpa, накопление веса критических peScp

71,74

L

Уменьшение Весцьебер крити четкого пути на величину Seat критического рвора

V

Опрос (17Jpeffep ny/na с максима - нын потоком (критическою пути)

jnt

I

Путь от начальной к конечной вершине сети omcomcm&jem

«М.дИ,

Нет

Влод

1

исключение (6xot Щ /сел усто- тИленньк признаков стягивания реИер

I

Опрос (Вход 77) весарёбер.имци- дентных начальной вершине сети

1

Выбор ребра с номинальным Весом

№

I

Установка признака тети выбранного ре оеоер критического пути

L

стягивание все рёбер графа,

вес котор Весу выоро)

ix больше или равен

дранного

peipa

i

Стянуто ребро в конечна } вершит/ с

чершину сети

дг

Нет

Опрос (ояод WpeSep критического пути в сети

И

V выход Фие,8