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

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

Известно устройство для моделирования сетей, которое позволяет определить путь С наибольшей пропускной способностью в неориентированной сети, Решающими элементами такого устройства служат модели ветвей, число которых соответствует числу ветвей исследуемой сети. Каждая модель ветви осуществляет формирование величины пропускной способности соответствующей ветви моделируемой сети и выполнена на базе элементов И, ИЛИ, триггеров.

счетчика импульсов и схемы индикации, включенных в соответствующую схему. Синхронность работы всех моделей ветвей обеспечивают блок управления и генератор импульсов, выполненные по определенной схеме на базе элементов И, ИЛИ, НЕ, триггеров и счетчика импульсов.

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

Наиболее близким по технической сущности к предлагаемому является устройство для анализа параметров сети, содержащее модели ветвей, число которых соответствует числу ветвей моделируемой сети и которые первым и вторым полюсами соединены между собой согласно конфигурации сети, многовходовый элемент ИЛИ, блок управлени я, причем каждая модель ветви содержит с первого по восьмой элементы И, первый и второй элементы ИЛИ первый счетчик импульсов, первый-пятый триггеры. Единичньн1 вход последнего соединен с выходом восьмого элемента И, а единичные выходы первого и второго триггеров, нулевые входы которых объединены, соединены соответственно с первым и вторым входами первого элемента ИЛИ, выход которого соединен с первым входом пятого элемента И, выход которого является третьим полюсом модели ветви, первым полюсом которой является первый вход третьего элемента И и выход первого элемента И, первый вход которого объединен с первым входом второго элемента И, выход которого соединен с первым входом четвертого элемента И и является вторым полюсом модели ветви, четвертым полюсом которой является первый вход седьмого элемента 1/1, выход которого соединен с единичным входом четвертого Tpyirrepa, причем выход третьего триггера соединен с первым входом шестого элемента И. Кроме того, блок управления содержит первый и второй счетчики импульсов, генератор импульсов, схему индикации, с первого по седьмой элементы И, с первого по пятый триггеры, единичный выход последнего иэ которых соединен с первым входом седьмого элемента И, выход которого соединен с единичным входом ВТОРОГО триггера, нулевой выход которого соединен с первым входом шестого элемента И, а единичный выход второго триггера - с первым входом четвертого элемента 1/1, у которого второй вход является первым полюсом блока управления, а выход этого элемента И соединен,с единичным входом четвертого триггера, единичный выход которого соединен с первым входом третьего элемента И, Выход последнего соеди нен с входом второго счетчика импульсов, разрядные выходы которого соединены с входами схемы индикации, и является вторым полюсом блока управления . Выход генератора импульсов соединен с первыми входами второго и пятого элементов И, второй вход последнего из которых соединен с единичным выходом третьего триггера, а единичный вход первого триггера блока управления соединен с выходом первого элемента И, первый вход которого соединён с выходом многовходового элемента ИЛИ, каждый вход которого соединен с третьим полюсом соответствующей ему модели ветви. Четвертый-восьмой полкзсы всех моделей ветвей подключаются к одноименным полюсам блока,управления, который первым и девятым полюсами подключается соответственно к первому и второму полюсам моделей ветвей, между которыми оп эеделяется величина максимального потока.

Это устройство определяет величину

максимального потока между заданными вершинами сети. однако не позволяет определять ветви, которые принадлежат минимальному правильному разрезу. Под

0 минимальным разрезом сети понимают такой разрез, мощность которого равна величине максимального потока. Минимальный разрез называют правильным, если удаление ветвей этого разреза приводит к тому,

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

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

Поставленная цель достигается тем, что в каждую модель ветви введены схема индикации, второй счетчик импульсов, первый и. второй элементы НЕ, Третий элемент ИЛИ, девятый, десятый и одиннадцатый элементы И, последний из которых первым входом и выходом соответственно соединен с единичным ВЫХОДОМ;четвертого и единичным входом третьего триггеров, последний из которых нулевым входом подключен к нулевым входам первого и четвертого триггеров, единичный выход которого соединен

5 с первым входом третьего элемента ИЛИ. Выход последнего соединен с первым входом первого элемента И, второй вход которого соединен с единичным входом первого триггера, выходом четвертого элемента 1/1 и входом первого элемента НЕ. Выход последнего соединен с вторым входом третьего элемента И, выход которого соединен с единичным входом второго триггера, вторым входом второго элемента

5 И и входом второго элемента НЕ, выход которого соединен с вторым входом четвертого элемента И, третий вход которого объединен с третьими входами первого, второго, третьего и шестого элементов И и

0 соединен с нулевым выходом пятого триггера. Первый и второй вход восьмого элемента И соответственно подключены к единичному выходу второго триггера и выходу пятого элемента И, а третий вход восьмого элемента И, четвертый вход которого соединен с единичнь1м выходом четвертого триггера, соединен первым входом первого элемента ИЛИ и первым входом десятого элемента И, второй вход и выход которого соединены соотпетственно с вторым входом первого элемента ИЛИ м с вычитающим входом второго счетчика импульсов. Суммирующий вход последнего соединен с выходом щестого элемента И, выходы заема и переноса второго счетчика соединены соответственно с первым и вторым входами четвертого элемента ИЛИ, выход которого соединен с вторым входом седьмого элемента И, а единичный выход пятого триггера - с первым входом девятого элемента И. Выход последнего соединен с входом первого счетчика импульсов, разрядные выходы которого подключены к схеме индикации. Пятым-десятым полюсами модели ветви являются соответственно второй вход третьего элемента ИЛИ, нулевой вход третьего триггера, второй вход девятого элемента И, третий вход щестого элемента И, второй вход одиннадцатого элемента И и третий вход десятого элемента И, посредством которых каждая модель ветви подключена к блоку управления, в который введен шестой триггер, восьмой, девятый элементы И элемент НЕ, выход которого

соединен с вторым входом четвертого элемента И, а вход этого элемента НЕ является восьмым полюсом блока управления и соединен с выходом пятого элемента И, входом первого счетчика, первым входом восьмого элемента И импульсов и нулевым входом первого триггера. Нулевой выход последнего соединен с вторым входом третьего элемента И, третий вход которого соединен с выходом второго Э;лемента И, нулевым входом пятого триггфа, вторым входом седьмого элемента И, первым входом девятого элемента И и является вторым полюсом блока .управления. Шестым полюсом блока управления являются объединенные второй вход второго элемента И, нулевой вход четвертого триггера, единичный вход третьего триггера и выход восьмого элемента И, у которого второй вход соединен с единичным

, выходом первого триггера, с вторым входом девятого элемента И и является пятым полюсом блока управления/четвертым полюсом которого является нулевой выход шестого триггера. Нулевой вход последнего соединен с единичным входом пятого триггера, выходом первого счетчика импульсов и является девятым полюсом блока, а еди;ничный вход шестого триггера соединен с йыходомшестого элемента И, второй вход которого соединен с выходом многовходо. вого элемента ИЛИ и первым входом первого элемента И, выход которого соединен с единичным входом первого триггера и является седьмым полюсом.блока управления. Второй вход первого элемента И соединен с первым входом четвертого элемента И,

третий вход которого соединен с нулевым выходом первого триггера, а нулевой вход третьего триггера - с выходом девятого элемента И.

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

Модель ветви 1 устройства содержит с ;

первого по одиннадцатый элементы И 3-13, первый, второй и третий элементы ИЛИ 1416, первый и второй счетчики 17-18 импульсов, первый-пятый триггеры 19-23, первый и второй элементы НЕ 24-25 и схему 26

индикации. Блок 2 управления содержит первый и второй счетчики 27 и 28 импульсов, схему 29 индикации, с первого по девятый элементы И 30-38, элемент НЕ 39, с первого по шестой триггеры 40-45, генератор 46 импульсов. Кроме того, устройство содержит многовходовый элемент ИЛИ 47, с первого по десятый полюса 48-57 модели ветви 1 и полюса 58-59 блока 2 управления, которые соединяются с полюсами 48 и 49

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

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

зом.

В исходном состоянии перед решением задачи на устройстве модели ветви 1 посредством полюсов 48 и 49 коммутируются между собой в соответствиии с конфигура-

цией моделируемой сети. Полюсами 58 и 59 блок 2 управления подключается соответственно к полюсам 48 и 49 тех моделей, между которыми определяется правиль- ный разрез, и в счетчики 17 всех моделей

ветви 1 заносится число импульсов (), где (ц - величина пропускной способности ветви между XI-и Xj-вершинами сети. Емкости счетчика 17 модели ветви 1 и счетчика 27 блока 2 управления одинаковы. Триггеры

и счетчики 18 всех моделей ветвей 1, все триггеры и счетчики 27 и 28 блока управления устанавливаются в нулевое состояние (установочные шипы на фиг.1 и фиг,2 не показаны).

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

выделение пути с наибольшей пропускной способностью между заданными вершинами сети;

выделение критической ветви в выдеенном пути с одновременным уМеньшением пропускных способностей всех ветвей выделенного пути на величину пропускной способности критической ветви;

разметка критических ветвей выделенного пути, которая представляет собой присвоение критической ветви номера, равного номеру найденного пути;

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

Решение задачи начинается с момента установки триггера 42 в единичное состояние. После зтого устройство переходит к выполнению вычислительной операции, которая включает в себя выделение подмножества ветвей сети Гз. где S - начальная вершина сети; Гз - ветви, инцидентные начальной вершине; определение в выделенном подмножестве ветви с наибольшей пропускной способностью и сравнение с ней пропускных способностей всех остальных ветвей сети; закорачивание ветвей, пропускные способности которых больше или равны пропускной способности ветви с наибольшей пропускной способностью из подмножества Гз. Этот процесс повторяют до тех пор, пока вершины S и t не совпадут (где t - конечная вершина сети).

Выполнение первой вычислительной опер1ации устройством происходит следующим образом.

Единичное состояние триггера 42 разрешает прохождение импульсам генератора 46 через элементы И 34 и НЕ 39 на полюсы 58,55 и вход счетчика 27 блока 2 управления. С полюса 58 блока 2 управления импульсы поступают на полюс 48 или 49 тех моделей ветвей 1, которые в результате коммутации между собой образуют начальную вершину сети (S).

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

Если импульсы поступят на полюс 49 модели ветви, они пройдут через элемент И 6 на единичный вход триггера 19 и установят его в единичное состояние.

Единичное состояние триггеров 19 или 20 выдает соответственно разрешение на элементы И 10 и 12 и через элемент ИЛИ 14 на вход элемента 47.

Одновременно импульсы с полюса 55 через элементы И 8 моделей ветвей 1 поступают на суммирующие входы счетчиков 17 всех моделей ветвей до их переключения.

Переполнение счетчиков 17 моделей ветвей происходит в порядке убывания значений весов ветвей сети. Импульс переполнения счетчика 17 через элемент ИЛИ 16 поступает на вход элемента И 9.

0 Далее импульс переполнения счетчика f 17, пройдя через элемент И 9. устанавливает триггер 22 в единичное состояние и поступает на вход элемента И 7. Так как триггер 45 устройства управления находится в нулевом состоянии, то на полюсе 51 и, соответственно, на втором входе элемента И 9 моделей ветвей присутствует разрешение. В результате переполнения счетчика 17 одной из моделей ветвей, принадлежащих разрезу Гз, импульс переполнения с выхода счетчика 17 через элемент ИЛИ 16, И9 и 7 поступает на полюс 50 и через элементы ИЛИ 47 и 35 устройства 2 управления устанавливает триггер 45 в единичное

5 состояние, что снимает разрешение с полю-, са 51 и закрепляет прохождение импульсов через элемент И 9. Все последующие переполнения счетчиков 17 других моделей ветвей не вызь1вают установку в единичное

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

5 22 модели ветви, принадлежащий разрезу Гз и имеющий максимальный вес среди ветвей разреза.

Закорачивание ветвей, пропускные способности которых больше или равны

0 пропускной способности ветви с пропускной способностью наибольшей среди ветвей Гз,, осуществляется за счет прямой передачи сигналов с полюса 48 через элементы И 5 и 4 на полюс 49, а наоборот с

5 полюса 49 через элементы И 6 и 3 - на полюс 48. Это происходит в момент появления импульса переполнения счетчика 27 блока 2 управления.

Кроме того, счетчик 17 выполняет роль

0 регенерационного счетчика. Он начинает свой счет с его емкость равна N, а счетчики 17 моделей ветвей 1 начинают счет с Mij.

Импульс переполнения счетчика 27 поступает на полюсы 5(6 всех моделей ветвей 1. В моделях .ветвей, в которых триггер 22 устано§лен в единичное состояние, этот импульс поступает через элемент И 13 на единичный вход триггера 21 и устанавливает его в единичное состояние.

Единичное состояние триггера 21 через элемент ИЛИ 15 выдает разрешение на входы элементов И 3 и 4. Это обеспечивает прохождение импульсов генератора с полюса 48 на полюс 49, а с полюса 49 - на полюс 48.

Одновременно с этим импульс переполнения счетчика 27 блока 2,управления, поступает на нулевой вход триггера 45 и единичный вход триггера 44, что приводит к установке этих триггеров в соответствующее состояние.

Нулевое состояние триггера 45 выдает разрешение на полюс 51, и весь процесс повторяется. Выполнение первой вычислительной операции продолжается до тех пор, пока импульсы генератора 46, поступающие на полюс 58 блока 2 управления и далее на полюсы 48 моделей ветвей 1, которые в результате коммутации образуют начальную вершину сети (S), не появятся на полюсе 59.

Это свидетельствует о переходе устройства к выполнению второй вычислительной операции.

Выполнение второй вычислительной операции происходит следующим образом.

Первый импульс, появившийся на полюсе 59 блока 2 управления, проходит через элемент И 36, так как триггер 44. находится в единичном состоянии. С выхода элемента .И 36 импульс поступает на единичный йход триггера 41 и устанавливает его в единичное состояние. Единичное состояние триггера 41 снимает разрешение с входа элемента И 34 и выдает разрешение на элементы И 30,31 и 33, При этом импульсы генератора 46 проходит через элемент И 31 на полюс 59 и на нулевой вход триггера 44 блока 2 управления. Первый импульс этой серии устанавливает триггер 44 в нулевое состояние, которое запрещает прохождение сигналов через элемент И 36.

С полюса 59 блока 2 управления импульсы генератора 46 поступают на полюсы 49 тех моделей ветвей, которые в результате коммутации этими полюсами образуют конечную вершину сети (t). В этих моделях импульсы проходят Через элементы И 6 и 3 на полюс 48. Такое прохождение импульсов с полюса 48 на полюс 49 возможно только ло тем моделям ветвей, у которых пропускные способности удовлетворяют ограничению (их триггеры 20 и 21 установлены в единичное состояние на первой вычислительной операции). При этом импульсы, распространяясь по сети от модели к модели, устанавливают триггер 19 в единичное состояние и появляются на полюсе48 моделей ветвей, которые в результате коммутации

образуют начальную (S) вершину сети. Далее эти импульсы появляются на полюсе 5В

блока 2 управления.

В блоке 2 управления импульс с полюса

58 поступает через элемент И 33 на единичный вход триггера 43 и устанавливает его в единичное состояние. Единичное состояние триггера 43 свидетельствует о том. что устройство выделило путь с наибольшей пропуск- .

ной способностью и переходит к выполнению следующей вычислительной операции - выделению критической ветви в пути и уменьшению пропускных способностей всех ветвей пути на величину пропускной способности критической ветви. Это происходит следующим образом.

Единичное состояние триггера 43 выдает разрешение на элемент И 32. В результате импульсы генератора 46 начинают

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

12 на вычитающий вход счетчика 17. При переполнении счетчика 17 у одной из модели ветви на выходе заема появляется импульс, который через элементы ИЛИ 16, И 9 и 7 появляется на полюсе 50. Кроме того,

этот импульс в модели ветви поступает через элемент И 10 на вход триггера 23 и . устанавливает его в единичное состояние. Далее этот импульс появляется на соответствующем входе 50 много входового элемента ИЛИ 47. С выхода последнего импульс через элемент И 30 поступает на единичный вход триггера 40 и полюс 54 блока управле- ния. .

с полюса 54 блока 2 управления импульс поступает в каждой модели ветви на вход элемента И 11. В тех моделях, у которых триггер 23 находится в единичном состоянии, импульс с выхода элемента И 11 поступает на вхбд счетчика 18 и заносится в

него.

Единичное состояние триггера 40 блока 2 управления запрещает прохождение импульсов генератора 46 через элемент И 32 на полюс 57 и вход счетчика 28, а также CHJ Iмает разрешение с входа элемента И 33.

В результате выполнения этой операции в счетчике 28 блока управления заносится число импульсов, пропорциональное величине пропускной способности критической ветви.

В модели ветви, которая соответствует критической ветви сети, счетчик 17 обнуля- ется, а в счетчик 18 заносится импульс. Число импульсов, занесенных в счетчик .18 модели критической ветви, определяет номер ветви, принадлежащей минимальному правильному разрезу.

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

Удаление размеченных ветвей, принадлежащих минимальному правильному разрезу, осуществляет триггер 23. Его единичное состо ние снимает разрешение с входов элементов И З-б, что запрещает прохождение сигналов с полюса 48 на полюс 49 и наоборот.

Проверка на связность между начальной (S) и конечной (t) вершинами происходит в результате того, что импульсы генератора 46, продолжающие гфоходить через элемент И 31, поступают на полюс 59 и элемент И 38.

G выхода элемента И 38 первый же прошедший импульс поступает на нулевой вход триггера 42 и устанавливает его в нулевое состояние. В то же время импульсы с полюса 59 поступают на полюсы 49 моделей ветвей 1, которые в результате коммутации образуют вершину t.,

Если связности между начальной (S) и конечной (t) вершинами нет, то триггер 42 блока управления остается в нулевом состоянии, что свидетельствует об окончании решения задачи.

Если связность есть, то импульсы с Нолюса 59 блока 2 управления полюсы 49 моделей ветвей, которые в результате коммутации формируют вершину t, проходят по моделям на полюсы 48 и, распространяясь по сети, появляются на полюсе 58 блока 2 управления. Далее с полюса 58 через элемент И 37 они поступают на нулевые входу триггеров 41 и 43 и единичный вход триггера 42. В результате эти триггеры устанавливаются в соответствующее состояние. Причем единичное состояние триггера 42 возобновляет работу устройства и весь вычислительный процесс повторяется.

В результате решения задачи в счетчике 28 блока управления накапливается число импульсов, которое определяет величину максимального потока. Эта величина индицируется схемой 29 индикации.

В счетчиках 18 моделей ветвей 1, которые соответствуют ветвям, принадлежащим минимальному правильному разрезу, накапливается число импульсов, которое определяет номер ветви разреза. Этот номер индицируется схемой 26 индикации соответствующей модели.

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

элементах НЕ, трех элементах ИЛИ, схеме индикации, и блик управления, который выполнен на двух счетчиках импульсов, генератора импульсов, шести триггерах, элементе НЕ, девяти элементах И, схеме

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

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

прогнозировать реконструкцию проезжей части городской сети и т.д.

Ожидаемый экономический эффект от использования изобретения составляет 85 тыс.руб./год.

Формула изобретения Устройство для анализа параметров сети, содержащее модели ветвей, соединенных своими первыми и вторыми полюсами

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

модели ветви, выход которого подключен

к третьему полюсу той же модели ветви,

первый полюс которой подключен к перво-му входу третьего элемента И модели ветви и к выходу четвертого элемента И той же модели ветви,, первый вход которого подключен к первому входу пятого элемента И той же модели ветви, выход которого

подключен к первому. входу шестого элет мента И той Модели ветви и к ее второму полюсу, четвертый полюс модели ветви подключен к первому входу седьмого элемента И той же модели ветви, выход которого под-чен к единственному входу четвертого тригrepa модели ветви, единичный выход пятого триггера модели .ветви - к первому входу восьмого элемента И той же модели ветви, единичный выход первого триггера блока управления -.к первому входу первого элемента И блока управления, выход первого элемента И блока управления - к единичному входу второго триггера блока управления, нулевой выход второго триггера блока управления - к первому входу второго элемента И блока управления, единичный выход второго триггера блока управления - к первому входу третьего элемента И блока управления, второй вход третьего элемента И блока управления - к первому полк}су блока управления, выход третьего элемента И блока управления - к единичному входу третьего триггера блока управления, единичный выход третьего триггера блока управления - к первому входу элемента И блока управления, выход четвертого элемента И блока управления - к входу первого счетчика блока управления, информационный выход первого счетчика блока управления - к входу элемента индикации блока управления и к втор1ому полюсу блока управления, выход генератора импульсов блока управления - к первым входам пятого и шестого элементов 1/1 блока управления, единичный выход четвертого триггера блока управления - к второму входу пятого элемента И блока управления, единичный вход пятого триггера блока управления - к выходу седьмого элемента И блока управления, первый вход седьмого элемента И блока управления к выходу элемента ИЛИ, входы которого соединены с первыми полюсами всех моделей ветвей с четвертого по восьмой полюсы всех моделей ветвей подключены к одноименным полюсам блока управления соответственно, первый и девятый полюса блока управления - к первому и второму полюсам моделей ветвей,инцидентных заданной паре вершин соответственно, отличаю:1цееся тем, что, /с целью расширения функционаЛьных возможностей устройства эа счет выделения в сети минимального правильного разреза между заданной парой вершин сети, в каждую модель ветви введены элемент индикации, второй счетчик, два элемента НЕ, третий и четвертый элементы ИЛИ и с девятого по одиннадцатый элементы И, а в блок управления - шестой триггер, восьмой и девятый элементы И и элемент НЕ, причем первый вход и выход девятого элемента И модели ветви подключены к единичным выходам четвертого и пятого триггеров той же модели ветви, нулевой вход пятого триггера подключен к нулевым входам первого и четвертого триггеров той же модели ветви, единичный выход пятого триггера - к первому входу второго элемента ИЛИ, выход которого подключен к первому входу четвертого элемента И, второй вход которого подключен к единичному входу первого триггера, выходу шестого элемента И и входу первого элемента НЕ той же модели ветви, выход которого подключен к второму входу третьего элемента И той же модели ветви, выход которого подключен к единичному входу второго триггера, второму входу пятого элемента И и входу второго элемента НЕ той же модели ветви, выход которого подключен к второму входу шестого элемента И той же модели ветви, третий вход которого подключен к третьим входам третьего, четвертого и пятого 5 лемейтов И, к второму входу восьмого элемента И и нулевому входу третьего триггера той же модели ветви, первый и второй входы первого элемента И модели ветви подключены к единичному выходу второго триггера и выходу второго элемента И той же модели ветви, третий вход первого элемента И модели ветви, четвертый вход которого подключен к единичному выходу четвертого, триггера, первому входу первого элемента ИЛИ и первому входу десятого элемента ИЛИ той же модели ветви, второй вход и выход которого подключены к второму входу первого элемента ИЛИ и вычитающему входу второго счетчика той же модели ветви соответственно, суммирующий вход которого подключен к выходу восьмого элемента И той же модели ветви, выходы заема и переноса второго счетчика модели ветви - к первому и второму входам третьего элемента ИЛИ той же модели ветви соответственно, выход третьего элемента ИЛИ модели ветвИ - к второму входу седьмого элемента И той же модели йетви, единичный выход третьего триггера модели ветви - к первому входу одиннадцатого элемента И той же модели ветви, выход которого подключен к входу первого счетчика той же модели ветви, второй вход второго элемента ИЛИ модели,ветви, нулевой вход пятого триггера модели ветви, второй вход одиннадцатого элемента И модели ветви, третий вход восьмого элемента И модели ветви, второй вход девятого элемента И модели ветви и второй вход десятого элемента И модели ветви подключены с пятого по десятый полюсам той же модели ветви соответственно, выход элемента НЕ блока управления подключен к второму . входу треьего элемента И блока управления, седьмЬму полюсу блока управления.

выходу пятого элемента И блока управления, входу второго счетчика блока управления, первому входу восьмого элемента И блока управления и нулевому входу пятого триггера блока управления, нулевой выход пятого триггера блока управления - к второму входу четвертого элемента И блока управления, третий вход четвертого элемента И блока управления - к выходу шестого элемента И блока управления, нулевому входу первого триггера блока управления, второму входу первого элемента И блока управления, первому входу девятого элемента И блока управления и второму полюсу блока управления, шестой полюс которого подключен к объединенным второму входу шестого элемента И блока управления, нулевому входу третьего триггера блока управления и выходу восьмого элемента И блока управления, второй вход восьмого элемента И блока управления подключен к единичному выходу пятого триггера блока управле ния, второму входу девятого элемента И блока управления и четвертому полюсу блока управления, третий полюс которого подключен к нулевому выходу шестого триггера блока управления, нулевой вход шестого триггера блока управления подключен к единичному входу первого триггера блока управления, выходу второго счетчика блока управления и восьмому полюсу блока управления, единичный вход шестого триггера блока управления - к ВЫХОДУ второго элемента И блока управления, второй вход второго элемента И блока управления - к выходу элемента ИЛИ и первому входу седьмого элемента И блока управления, выход седьмого элемента И блока управления - к единичному входу пятого триггера блока управления,и шестому полюсу блока управления, второй вход седьмого элемента И блока управления - к первому входу третьего элемента И блока управления, третий .вход третьего элемента И блока управления - к нулевому выходу пятого триггера блока управления, единичный вход четвертого триггера блока управления - к выходу девятого элемента И блока управления.

Изобретение относится к средствам электронного моделирования и может быть испольэовано при построении специализированных вычислительных устройств для решения задам на сетях. Цель изобретения - расширение функциональных возможностей устройства за счет выделения в сети ветвей минимального правильного разреза. Задача- определения минимального правильного разреза решается за счет циклического повторения операций выделения пути с наибольшей пропускной способностью, выделения критической ветви в выделенном пути с одновременным уменьше'нием пропускных способностей всех ветвей выделенного пути на величину пропускной способности критической ветви, разметки критических ветвей выделенного пути (присвоения критической ветви номера найденного пути), удаления разме'- ченных ветвей и проверки связности вершин, между которыми определяется минимальный правильный разрез. 2 ил.'%f ••«^fe

Ч 57 55 Jf 9 Фиг1

1 I

55 57

Фиг.2