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

 

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

союз сОВетских

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

РБСПУБЛИК

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4773585/24 (22) 25.12,89, (46) 30.01.92. Бюл. № 4 (71) Институт проблем моделирования в энергетике АН УССР (72) А.А, Мирошниченко, И.А. Табунщик, Е.В. Тонкаль и Н;В. Федотов (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 1138806, кл. G 0,6 F 15/20, 1983.

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

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

Известно устройство для моделирования сетей, которое позволяет определить путь с наибольшей пропускной способностью в неориентированной сети, Решающими элементами такого устройства служатмодели ветвей, число которых соответствует числ у ветвей исследуемой сети, Каждая модель ветви осуществляет формирование величины пропускной способности соответствующей ветви моделируемой сети и выполиена на базе элементов И, ИЛИ, триггеров, „„ Ц „„1709347 Al (я)5 G 06 F 15/419 шения задач на сетях. Цель изобретения— расширение функциональных возможностей устройства за счет выделения в сети ветвей минимального правильного разреза. Задача определения минимального правильного разреза решается за счет циклического повторения операций выделения пути с наибольшей пропускной способностью, выделения критической ветви в выделенном пути.с одновременным умен ьш ездием и ропускн ых способностей всех ветвей выделенного пути на величину пропускной способности критической ветви, разметки критических ветвей выделен/ ного пути (присвоения критической ветви номера найденного пути), удаления размеченных ветвей и проверки связности вершин, между которыми определяется минимальный правильный разрез,-2 ил. счетчика импульсов и схемы индикации, включенных в соответствующую схему. Синхронность работы всех моделей ветвей обеспечивают блок управления и генератор импульсов, выполненные по определенной схеме на базе элементов И, ИЛИ, НЕ, триггеров и счетчика импульсов.

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

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

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

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

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

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

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

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

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

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

И и входом второго элемента НЕ, выход которого соединен с вторым входом четвертого элемента И, третий вход которого объединен с третьими входами первого, второго, третьего и шестого элементов И и соединен с нулевым выходом пятого триг- . гера. Первый и второй вход восьмого элемента И соответственно подключены к единичному выходу второго триггера и выходу пятого элемента И, а третий вход восьмого элемента И, четвертый вход которого соединен с единичным выходом четвертого триггера, соединен первым входом первого элемента ИЛИ и первым входом десятого элемента И, второй вход и выход которого соединены соответственно с вто1709347 мента И, третий вход которого соединен с выходом второго элемента И, нулевым входом пятого триггера, вторым входом седь- 35

45

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

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

Второй вход первого элемента И соедийен с первым входом четвертого элемента И, 10

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

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

Модель ветви 1 устройства содержит с первого ао одиннадцатый элементы И 3-13, первый, второй и третий элементы ИЛИ 14—

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

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

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

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

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

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

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

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

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

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

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

6 на единичный вход триггера 19 и установят его в единичное состояние.

Единичное состояние триггеров 19 или

20 выдает соответственно разрешение на элементы И 10 и 12 и через элемент ИЛИ 14— на вход элемента 47, 30

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

22 модели ветви, принадлежащий разрезу

Гз и имеющий максимальный вес среди ветвей разреза.

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

48. Это происходит в момент появления импульса переполнения счетчика 27 блока 2 управления.

Кроме того, счетчик 17 выполняет роль регенерационного счетчика. Он начинает свой счет с "0" и его емкость paaxa N, а счетчики 17 моделей ветвей 1 начинают счет с Mi1.

Импульс переполнения счетчика 27 поступает на полюсы 56 всех моделей ветвей

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

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

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

ИЛИ 16 поступает на вход элемента И 9.

10 Далее импульс переполнения счетчика,17, пройдя через элемент И 9, устанавливает триггер 22 в единичное состояние и поступает на вход элемента И 7. Так как триггер 45 устройства управления находит15 ся в нулевом состоянии, то на полюсе 51 и, соответственно, на втором входе элемента

И 9 моделей ветвей присутствует разрешение. В результате переполнения счетчика

17 одной из моделей ветвей, принадлежа20 щих разрезу Гз,! импульс переполнения с выхода счетчика 17 через элемент ИЛИ 16, И9 и 7 поступает на полюс 50 и через элементы ИЛИ 47 и 35 устройства 2 управления устанавливает триггер 45 в единичное

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

1709347

Единичное состояние триггера 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 тех моделей ветвей, которые в результате коммутации этими полюсами образуют конечную вершину сети (т). В этих моделях импульсы проходят через элементы И 6 и 3 на полюс 48. Такое прохождение импульсов с полюса 48 на полюс 49 возможно только по, тем моделям ветвей, у которых пропускные способности удовлетворяют ограничению (их триггеры 20 и 21 установлены в единичное состояние на первой вычислительной операции). При этом импульсы, распространяясь по сети от модели к модели, устанавливают триггер 19 в единичное состояние и появляются на полюсе 48 моделей ветвей, которые в результате коммутации образуют начальную (S) вершину сети. Далее эти импульсы появляются на полюсе 58 блока 2 управления.

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

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

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

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

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

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

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

45 нег.о.

Единичное состояние триггера 40 блока

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

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

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

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

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

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

46, продолжающие ггроходить через weмент И 31, поступают на полюс 59 и элемент

И 38.

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

Если связность есть, то импульсы с rioлюса 59 блока 2 управления через полюсы

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

Причем единичное состояние триггера 42 возобновляет работу устройства и весь вычислительный процесс повторяется.

В результате решения задачи в счетчике

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

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

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

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

85 тыс.руб./год.

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

Устройство для анализа параметров сети, содержащее модели ветвей, соединенKblx своими первыми и вторыми полюсами в соответствии с топологией сети, элемент

ИЛИ и блок управления, причем каждая модель ветви содержит восемь элементов

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

И той же модели ветви, выход которого под-.

1709347 гера модели ветви, единичный выход пятого триггера модели ветви — к первому входу восьмого элемента И той же модели ветви, единичный выход первого триггера блока управления —.к первому входу первого эле- 5 мента И блока управления, выход первого элемента И блока управления — к единичному входу второго триггера блока управления, нулевой выход второго триггера блока управления — к первому. входу второ- . 10 го элемента И блока управления, единичный- выход второго триггера блока управления — к первому входу третьего элемента И блока управления, второй эход третьего элемента И блока управления — к 15 первому полюсу блока управления, выход третьего элемента И блока управления — к единичному входу третьего триггера блока управления, единичный выход третьего триггера блока управления — к первому вхо- 20 ду элемента И блока управления, выход четвертого элемента И блока управления — к входу первого счетчика блока управления, информационный выход первого счетчика блока управления — к входу элемента инди- 25 кации блока управления и к второму полюсу блока управления, выход генератора импульсов блока управления — к первым входам пятого и шестого элементов И блока управления, единичный выход четвертого 30 триггера блока управления — к второму входу пятого элемента И блока управления, единичный вход пятого триггера блока управления — к выходу седьмого элемента И блока управления, первый вход седьмого 35 элемента И блока управления — к выходу элемента ИЛИ, входы которого соединены с первыми полюсами всех моделей ветвей, с .четвертого по восьмой полюсы всех моделей ветвей подключены к одноименным 40 полюсам блока управления соответственно, первый и девятый полюса блока управления — к первому и второму полюсам моделей ветвей,инцидентных заданной паре вершин соответственно, о т л и ч а ю- 45

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

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

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

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

ИЛИ и первому входу десятого элемента

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

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

1709347

16 выходу пятого элемента И блока управления, входу второго счетчика блока управления, первому входу восьмого элемента И блока. управления и нулевому входу пятого триггера блока управления, нулевой выход пятого триггера блока управления — к второму входу четвертого элемента И блока управления, третий вход четвертого элемента И блока управления — к выходу шестого элемента И блока управления, нулевому входу первого триггера блока управления, второму входу первого элемента И блока управления, первому входу девятого элемента И блока управления и второму полюсу блока управления, шестой полюс которого подключен к объединенным второму входу шестого элемента И блока управления, нулевому входу третьего триггера блока управления и выходу восьмого элемента И блока управления, второй вход восьмого элемента И блока управления подключен к единичному выходу пятого триггера блока управления, второму входу девятого элемента. И блока управления и четвертому полюсу блока управления, треФ тий полюс которого подключен к нулевому выходу шестого триггера блока управления, нулевой вход шестого триггера блока управления подключен к единичному вхо5 ду первого триггера блока управления, выходу второго счетчика блока управления и восьмому полюсу блока управления, единичный вход шестого триггера блока управления — к выходу второго элемента И

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

И блока управления — к первому входу третьего элемента И блока управления, 20 третий вход третьего элемента И блока управления — к нулевому выходу пятого триггера блока управления, единичный вход четвертого триггера блока управления — к выходу девятого. элемента И блока управ25 ления.

1709347

Редактор M. Петрова

Заказ 428 Тираж Подписное

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

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

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

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

Техред М.Моргентал Корректор. О. Кравцова

5О Ь

50<