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

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

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

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

Модель 1 ветви (фиг. 1) содержит с первого по шестой триггеры 3-8, первый 9 и второй 10 счетчики импульсов, схему 11 индикации, с первого по четырнадцатый элементы и 12-25, с первого по пятый элементы ИЛИ 26- 30.

ел

о

CD 4i

СП to

Блок 2 управления (фиг. 2) содержит с первого по девятый триггеры 31-39, первый АО и второй А1 счетчики импульсов, с первого по четыр- надцатьиЧ элементы И 42-55, элемент НЕ 56, с первого по четвертый элементы ИЛИ 57-60, генератор 61 импульсов.

Кроме того, устройство содержит первый 62 и второй 63 многовходовые элементы ИЛИ (фиг, 2), Число входов многовходовых элементов ИЛИ 62 и 63 соответствует числу моделей ветвей. Устройство имеет полюсы 64-78, из которых полюсы 64 и 65 у модели 1 ветви служат для коммутации их между собой согласно конфигурации моделируемой сети. Полюсы 66 и 67 блока 2 управления служат соответственно для подключения этого блока к полюсам 64 и 65 тех моделей 1 ветвей между которыми отыскивается указанный путь. Летальные полюсы каждой модели ветви служат для подключения их к блоку управления, что обеспечивает синхронную работу всего устройства . I

Исходными данными задачи оптимизации двух взаимосвязанных потоков является коммутация моделей 1 ветвей полюсами 64 и 65 между собой согласно конфигурации моделируемой сети, подключение полюсов 66 и 67 блока 2 управления к полюсам тех моделей ветвей, между которыми отыскивается требуемый путь. Кроме того в счетчики 9 и 10 моделей ветвей соответственно заносят число импульсов, равное N-q. . и N-b-- , а в Счетчик 41 блока управления заносят число импульсов, равное N-b, где N - емкость счетчиков 9 и 10 импульсов моделей 1 ветвей и счетчиков 40 и 4 блока 2 управления.

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

Г minP max(q jj) 1 к I х,х,е К MJ

b..,.

bod) S5

Этот этап включает циклическ вторяющиеся операции: нахождение (х--Х;) разреза из множества раз К , выбор ветви разреза (х,.-х-) с или max q ,-;| (зависит о выбранного условия (1) или (2)); деление ветвей сети, у которых п пускная способность меньше или р пропускной способности выбранной ви разреза (согласно условиям (1 и (3)) или больше или равна проп ной спвсобности выбранной ветви реза (согласно условиям (2) и (4 Вторая и третья операции вьтолня устройством одновременно. После каждого цикла выполнения операци первого этапа число проверяемых вей сети уменьшается за счет за чивания между собой полюсов 64 и моделей, которые удовлетворяют за ному условию. Выполнение операций первого этапа повторяется до тех пока полюсы, между которыми отыск

,, , . лл .A)«n/4,uj у i l /iy-s jr i W 1 DiV.

p I Г ) b;. , b;j bgf2) вается путь, не будут закорочены К . К j MJ(т.е, не совпадут).

Ъ..- Ь, величина

по

заданная

вторичного потока

ветви (х; X .) ;

минимальная допус 4

тимая величина вторичного потока каждой ветви сети; величина первичного потока

по ветви (хjX .).

Согласно этим условиям процесс решения задачи на данном устройстве /можно представить в виде трех этапов.

Первый этап состоит в выделении из всего множества ветвей сети таких ветвей, пропускная способность первичного потока которых удовлетворяет следующим условиям в зависимости от того, какое условие,(1) или (2) является основным для оптимизации:

p

p

mm К

Г max(q - )1 Ix.x-e К )

inf min(q - )| I к )

mm К

(3)

(4)

0

5

0

5

Q

5

x их

q,r

где К - любой (S-t) разрез (на множестве ветвей), где S и t - соответственно начальная и конечная вершинь сети, меткду которыми определяется путь; i-я и j-я вершины сети; пропускная способность ветви между х;-й и X .-и верпшнами.

Этот этап включает циклически повторяющиеся операции: нахождение (х--Х;) разреза из множества разрезов К , выбор ветви разреза (х,.-х-) с или max q ,-;| (зависит от выбранного условия (1) или (2)); выделение ветвей сети, у которых пропускная способность меньше или равна пропускной способности выбранной ветви разреза (согласно условиям (1) и (3)) или больше или равна пропускной спвсобности выбранной ветви разреза (согласно условиям (2) и (4)). Вторая и третья операции вьтолняются устройством одновременно. После каждого цикла выполнения операций первого этапа число проверяемых ветвей сети уменьшается за счет закорачивания между собой полюсов 64 и 65 моделей, которые удовлетворяют заданному условию. Выполнение операций пер- первого этапа повторяется до тех пор, пока полюсы, между которыми отыски1л л лл .A)«n/4,uj у i l /iy-s jr i W 1 DiV.

вается путь, не будут закорочены (т.е, не совпадут).

Второй этап состоит в проверке выполнения условия (1) или (2) по пропускной способности вторичнсч о потока ветвей, которые выбраны на первом этапе и проверке существовани пути между заданными вершинами, состоящего из ветвеГ, пропускные способности которых удовлетворяют условию (1) или (2). Если пропускные способности по вторичному потоку всех выбранных на первом этапе ветвей удовлетворяют заданному условию (Ь ( t o ° устройство производит вьщеление ветвей пути между заданными вершинами сети. Выделение ветвей искомого пути является третьим этапом работы устройства.

В противном случае, если н;) втором этапе будут наГщены ветви, пропускная способность по вторичному потоку которых не удовлетворяет заданному условию, то эти ветви исключаются из дальнейшего процесса решения задачи. Исключение ветвей осуществляется за счет разрыва цепей прохождения каких-либо сигналов от полюса 64 на полюс 65, и наобор(т, что осуществляется блокировкой ихода и выхода в модели ветви. После удаления ветвей устройство проверяет наличие пути между заданными Bopurmia ми сети, который проходит только по ветвям, удовлетворяющим условию (1) или (2), Если такого пути нет, го устройство переходит опять к выполнению шагов первого этапа. При этом в качестве исходной сети выступает сеть, в которой исключены ветви на втором этапе. Вьшолнение операций первого и второго этапов устройство .производит до тех пор, пока не будет найден путь, пропускные способности ветвей по первичному и вторичному потокам которого на будут удовлетворять условию (1) или (2).

Выбор условия оптимизации (1) или (2) определяется состоянием триггера 31 блока 2 управлсник (фиг. 2). Если триггер 31 находится в нулевом состоянии, то основным условием оптимизации двух взаимосвязанных потоков в сети является условие (1). Если триггер 31 находится в единичном состоянии, то основным условием выступает условие (2) .

Перед началом работы устройства триггеры 3-8 всех моделей 1 ветвей и триггеры 32-39 и счетчик 40 нмпуль0

0

5

(41D блока 2 управления устанавлива- мтся в нулевое состояние (шины занесения исходных данных и установоч- }1ые ишны не показаны) .

Рассмотрим работу устройства, когда основным условием оптимизации двух взаимосвязанных потоков является условие (2). В этом случае триггер 31 блока 2 управления установлен п единичном состоянии.

Рабоаа устройства начинается с момента установки триггера 32 в единичное состояние. Единичное сос- 5 тояние триггера 32 блока управления (фиг. 2) вьщает разрешение на вход элемента И 45, на другой вход которого поступает разрешение с нулевого выхода триггера 37. В результате импульсы от генератора 61 проходят через элемент И 45. С выхода элемента Р1 45 эти импульсы поступают на вход элементен И 47, 49 и 50. Через элементы И 47 и 50 импульсы не проходят, так как нет разрешения на входы этих элементов с триггеров 33 и 34 (они находятся в нулевом состоянии), через элемен 1 И49 амттульсы ге- нератора проходят и чер:-- тлемент ИЛИ 5в поступают на полюс блока 2 управления. Одновременно с этим первый импульс из всей серии, которая поступает через элемент ИЛИ 58, устанавливает триггер j6 в ( состояние,. Единичнор состояние триггера 36 вьщает разрешение на вход элемента И 43, на другой ьхоц которого поступает разрешение с е;и1ничного выхода триггера 31 (этот триггер находится в единичном спстоянии, так как основное условие оптимизации - условие (2)).В результате на выходе элемента И 43 появляется :игнал, который через элемент Н,ГП1 57 поступает на полюс 71 блока 2 управления.

С полюса 71 блока 2 управления сигнал поступает на вход элемента И 22 всех моделей 1 ветвей, что обеспечивает прохождение сигналов через этот элемент.

Импульсы с полюса 66 блока 2 управления поступают на полюсы 64 или 65 ;oдeлeй 1 ветвей, которые в результате коммутации этих полюсов между собой образуют вершину сети, из которой отыскивается путь, удовлетворяющий условию (2).

В указанных моделях 1 ветвей (фиг. 1) импульсы с полюса 64 посту0

5

0

5

0

5

пают ил вход элемелтов И 13 н 13-17. Через элементы И 13, 15 и 17 импульсы не проходят, так как на других входах у них нет разрешения. На всех входах элемента И 16 есть разрешение, поэтому с выхода этого элемента импульсы через элемент ИЛИ 28 поступают на единичный вход триггера 3. По первому импульсу из всей серии импульсов, поступивших в модель 1 ветЕИ на полюЬ 64, триггер 3 устанавливается в единичное состояние. Все последующие импульсы подтверждают это состояние триггера 3. Аналогич- но, если импульсы поступают на полюс 65 модели 1 ветви, они проходят только через элементы И 18 и ИЛИ 27 и устанавливают триггер 4 в единичное состояние.

Единичное состояние триггера 3 или 4 выдает разрешение па вход элемента И 20 через элемент ИЛИ 26 и свидетельствует о том, что данная модель 1 ветви принадлежит выбранно- му разрезу (х;- х) из множества разрезов К. Это соответствует первой операции первого этапа решения задачи.

Разрешение с выхода элемента И 20 поступает на полюс 70 модели 1 ветви Это возможно потому, что на другом входе элемента И 20 ть разрешение, снимаемое с нулевого выхода триггера 5.

С полюса 70 модели 1 ветви разрешение поступает на соотвстствуюш 1Й вход 70 многовходового элемента ИЛИ 62 (фиг. 2). Причем на входы 70 мно- говходового элемента ИЛИ 62 доступа- ют разрешения только от тех моделей 1 ветвей, триггеры 3 или 4 которых находятся в единичном состоянии,

Выбор модели ветви, принадлежащей сформированному разрезу, с пропускно способностью первичного потока, равного mintq;j , а также моделей ветвей, пропускная способность первичного потока которых меньше или равна пропускной способности выбранной ветви, происходит по разрешению, которо появляется на выходе многовходового элемента ИЛИ 62. Это разрешение поступает на вход элементов НЕ 56 и И 44.

На выходе элемента НЕ 56 исчезает разрешение, которое поступает на вход элемента И 42. Однако другой вход элемента И 42 заблокирован еди

Q 0

5

О

«

г

5

0

5

ничцым состоянием триггера 31 и, следовательно, изменение сигнала на полюсе 71 блока 2 управления не происходит. Через элемент И 44 разрешение проходит, так как на другом его входе есть разрешение с нулевого выхода триггера 35, и поступает на единичный вход триггера 33. В результате триггер 33 устанавливается в единичное состояние. Единичное состояние триггера 33 запрещает прохождение импульсов через элементы И 49 и ИЛИ 58 на полюс 66 блока 2 управления и разрешает прохождение импульса генератора 61 с выхода элемента И 45 через элемент И 47. Единичное состояние триггера 33 свидетельствует о том, что устройство начинает выполнять вторую и третью опе- радаи первого этапа. С выхода элемента И 47 импульсы генератора 61 поступают на полюс 69 и через элемент ИЛИ 59 на вход счетчика 40 импульсов до его переполнения.

В каждой модели 1 ветви импульсы с полюса 69 поступают на вход элемента И 21 и счетчика 9 импульсов до егс5 ереполнения. Импульс переполнения счетчика 9 модели ветви устанавливает триггер 5 в единичное состояние. Одновременно этот импульс через элемент И 23 поступает на полюс 76 тех моделей 1 ветвей, которые принадлежат выбранному разрезу. Кроме того, этот импульс через элемент ИЛИ 29 поступает на нулевые входы триггеров 3 и 4.

Единичное состояние триггера 5 через элемент И 22 устанавливает триггер 6 в единичное состояние. В этом случае триггер 5 остается в единичном состоянии, так как единичное состояние триггера 6 запрещает прохождение очередного импульса с полюса 69 через элемент И 21 на нулевой вход триггера 5.

Импульс, поступивший на нулевые входы триггеров 3 и 4 с выхода счетчика 6 импульсов, устанавливает их в нулевое состояние, если один из них ранее был установлен в единичное состояние импульсами, которые поступили на полюс 64 или 65 модели ветви. В результате установки триггеров 3 или 4 л нулевое состояние снимаются все сигналы с полюсов 70 многовходового элемента ИЛИ 62 и, следовательно.

снимается сигнал с выхода этого эле мента.

С полюса 76 модели 1 ветви импул поступает на соответствующий этой модели ветви вход 76 многовходово- го элемента ИЛИ 63 и, пройдя этот многовходовый элемент, поступает на нулевой вход триггера 36. В результате триггер 36 устанавливается в нлевое состояние. Первый импульс, по явивошйся на одном из входов 76 мно говходового элемента ИЛИ 63, определяет модель ветви, у которой наименьшая пропускная способность по первичному потоку J и котора принадлежит выбранному разрезу (Х(- X;). Нулевое состояние триггера 36

снимает разрешение с входа элемента И 43 и, соответственно, через элемент ИЛИ 57 с полюса 71 всех моделей 1 ветви.

Единичное состояние триггера 6 вдает разрешение на входы элементов И 12 и 13, что обеспечивает закорачи вание полюсов 64 и 65 модели ветви. Закорачивание полюсов 64 и 65 модели ветви исключает ветвь из дальнейших проверок, которые выполняются на первом этапе. Таким образом, в моделях 1 ветвей сети, у которых пропускная способность меньше или равна пропускной способности модели ветви разреза, триггеры 5 и 6 устанавливаются в единичное состояние, триггеры 3 и 4 - в нулевое и их полюсы 64 и 65 закорачиваются. Это происходит потому, что в моделях 1 ветвей, у которых импульс переполнения счетчика 9, появившийся после того, как будет снято разрешение с полюса 71 и входа элемента И 22, триггер 5 устанавливается в единичное состояние, а затем этот триггер устанавливается в нулевое состояние очередным импульсом, поступившим на полюс 69. Это происходит в результате того, что единичное состояние триггера 5 вьдает сигнал на вход элемента И 22, Через этот элемент сигнал не проходит, и триггер 6 остается в нулевом состоянии, что позволяет проходить через элемент И 21 очередному импульсу, которьш поступает на полюс 69 из блока 2 управления от генератора 61 импульсов.

Импульс переполнения счетчика 40 блока 2 управления поступает через элемент ИЛИ 58 на полюс 66. Далее

0

0

0

5

этот импульс поступает на полюс 64 или 65 моделей ветвей и весь процесс работы устройства повторяется аналогично описанному выше, т.е. устройство повторяет операции первого этапа.

Такие процессы повторяются до тех пор, пока очередной импульс переполнения счетчика 40 блока 2 управления, поступающий на полюс 66, не появится на полюсе 67. Это происходит потому, что импульс с полюса 66 поступает на полюс 64 или 65 моделей 1 ветвей и, 5 проходя соответственно элементы И 13 и 12, появляется на полюсе 65 или 64 соответственно модели 1 ветви.

Момент появления импульса на полюсе 67 блока 2 управления свидетельствует об окончании вьшолнения устройства второй и третьей операций первого этапа. К этому моменту все множество ветвей моделируемой сети разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность по первичному потоку q..

5

0

5

0

5

которых удовлетворяет условию (4), и в соответствующих им моделях 1 ветвей триггера 5 и 6 находятся в единичном состояниу. Другое подмножество содержит ветви с пропускными способностями, которые не удовлетворяют условию (4), и их триггеры 5 и 6 находятся в нулевом состоянии. Эти модели в процессе выполнения следующего этапа работы устройства не участвуют. Кроме того, к этому моменту в счетчиках 9 всех моделей 1 ветвей восстанавливается информация об их пропускной способности по первичному потоку, т.е. происходит регенерация. Роль регенерационного счетчика для счетчиков 9 всех моделей 1 ветвей выполняет счетчик 40 импульсов блока 2 управления, который начинает счет с О и его емкость равна N. Счетчики 9 всех моделей 1 ветвей начинают счет с N-q; i .

Импульс с полюса 67 в блоке 2 управления поступает на вход элементов И 54 и 55. Через элемент И 55 этот импульс не проходит, так как триггер 38 находится в нулевом состоянии, а через элемент И 54 импульс проходит на единичный вход триггера 37. В результате этот триггер устанавливается в единичное состояние. Единичное состояние триггера 37 выдает разрешение на вход элементов И 51 и 53 и

снммаот ра чкчпенис с нхоцл элемента И А 5. F.UHnn4ii e состояние триггера 37 сви;;етельстпует о том, что устр(5Йстно начинает выполнять опера- lyivf второго этапа. При этом импульсы генератора 61 проходят через элемент И 51 . Далее они поступают на полюс 75 и черен элемент ЮТ1 59 на вход счетчика 40. С полюса 75 эти импульсы поступают в каждой модели 1 ветви на вход элемента И 25. Кроме того, импульсы с выхода элемента И 51 поступают па вход счетчика 41.

В каждой модели 1 ветви импульсы проходят через элемент И 25 только в тех моделях ветвей, триггер 6 которых находится в единичном состоянии, и далее поступают на вход счетчика 10 импульсов до его переполнения. Импульс переполнения счетчика 10 поступает на вход элемента И 24. Через этот элемент импульс переполнения счетчика 10 может пройти в том случае, если триггер 8 находится в ьгулавом состоянии. Состояние триггеров 8 всех моделей ветвей определяется работой счетчика 41 импульсов блока 2 управления. Импульс переполнения счетчика 41 поступает на полюс 73 всех моделей 1 ветвей и устанавливает триггер 8 в единичное состояние, что запрещает прохождение импульсов переполнения счетчика 10 через элемент И 24.

Единичное состояние триггера 7 в моделях ветвей свидетельствует о том, что пропускная способность по вторичному потоку в данных моделях не удовлетворяет условию (2), т.е. bj: Ьд. Такие модели ветвей и, следовательно, соответствующие им ветви моделируемой сети из дальнейшего процесса решения задачи исключаются. Исключение моделей ветвей из дальнейшего процесса решения задачи осуществляется за счет съема разрешения с входов элементов И 12- 19 в модели ветви, что запрещает прохождение сигналов с полюса 64 на полюс 65, и наоборот, через модель ветви.

Выполнение второго этапа работы устройства продолжается до момента появления импульса переполнения счетчика 40 импульсов блока 2 управления (фиг. 2), К этому моменту все подмножество ветвей, которое выбран на первом этапе и пропускная способ

0

5

ность по иерничному потоку которых удовлетворяет условию (4), еще разбивается на два подмножества. Одно подмножество содержит ветви моделируемой сети, которые полностью удовлетворяют условию (2), т.е. их пропускные способности по первичному потоку и по вторичному соответствуют требованиям, которые предъявляются к искомому пути. В соответствующих этим ветвям моделях триггеры 5 и 6 должны находиться в единичном состоянии, а триггер 7 - в нулевом. Для другого подмножества пропускные способности ветвей по первичному потоку удовлетворяют условию (4).и, следовательно, условию (2), а по вторичному потоку их пропускные способности не удовлетворяют условию (2), т.е. условие (2) полностью не выполняется. В соответствующих этим ветвям моделях триггеры 5 и 6 находятся в единичном состоянии, а также в единичном состоянии находится триггер 7.

Проверка существования пути в сети между заданными вершинами, сос- тоящет о из ветвей, которые удовлетворяют полностью условию (2), устройство пр(;изводит следующим образом. Импульс переполнения счетчика 40 иьтульсов через элемент ИЛИ 58 поступает на полюс 66 блока управле- шя. К этому моменту в счетчике 10 всех моделей 1 ветвей и в счетчике 41 импульсов блока 2 управления восстанавливается информация о bj и, соответственно, о Ь, . Роль регенера- дионного счетчика в этом случае, так же как и в предыдущем, выполняет счетчик 40 импульсов блока 2 управления, который начинает счет с О и его емкость равна N. Счетчики 10 всех моделей ветвей и счетчик 41 блока управления начинают счет соответственно с N-b;j И N-boКроме того, этот импульс переполнения счетчика 40 поступает на вход генератора 61 импульсов и, соответственно, на единичный вход триггера 38 через элемент И 53 и на нулевой вход триггера 37. В результате триггер 38 устанавливается в единичное состояние, а триггер 37 - в нулевое.

Нулевое состояние триггера 37 снимает разрешение с выхода элемента И 51, что прекращает поступление импульсов генератора 61 на полюсы 69

0

0

5

0

5

и 75 и пходы сче гчикч в 40 и 41 блока 2 управления.

Еди}1ичиос состояние тршч-ера 38 выдает разрешение на вход элементов И 52 и 55, что обеспечивает прохождение сигналов через эти элементы. Одновременно с этим импульс переполнения счетчика 40, постунивший на полю 66 блока управления, опять поступает на полюс 64 или 65 моделей I ветвей, который в результате коммутащ1и этих полюсов между собой образует вершину сети, из которой отыскивается путь, удовлетворяющий пол}1остью условию (2) . В моделях ветвей .-этот импульс с полюса 64 поступает через элемент И 13 на полюс 65. Аналогично, если это импульс поступает на полюс 65, то он проходит через элемент И 12 на по- люс 64 .

Таким образом, распространяясь по сети с полюса 6Д на полюс 65 или с полюса 65 на полюс 64 от модели к модели, этот импульс появляется на полюсе 67 блока управления. Распространение импульсов переполнении счетчика 40 на втором этапе возможно только по тем моделям ветвей, триггеры 5 и 6 которых находятся в единично состоянии, а триггер 7 - в нулевом.

Появление импульса на полюсе 67 блока 2 управления свидетельствует о том, что путь, пропускная способность ветвей которого полностью удовлетворяет условию (2), найден и устрой- ство в этом случае переходит к выполнению заключительного этапа работы - выделению ветвей искомого пути. В противном случае, если импульс на по- люсе 67 не появляется, что свидетельствует об отсутствии искомого пути, устройство переходит опять к вьшол- нению операций первого этапа, и весь процесс работы устройства повторится аналогично описанному выше.

Переход устройства к выполнению операций первого этапа происходит следующим образом.

По импульсу переполнения счетчи- ка 40 блока 2 управления, который поступает на вход генератора 61 импульсов в конце второго этапа работы устройства, генератор импульсов выдает импульс, сдвинутый относительно входного, на вход элемента И 52. Этот импульс проходит через элемент И 52 и поступает на нулевой вход триггера 38, на вход элемента ИЛИ 60

4Q 20

5 эп

.

Q

5

5

и на полюс 74 всех моделей 1 ветвей При этом в каждой модели ветви импульс с полюса 74 поступает на нулевой вход триггера 8 и через элементы 1ШИ 30 и 29 на нулевые входы триггеров 6, 3 и 4, устанавливая эти триггеры в нулевое состояние. Одно- нроменно с этим устанавливается в нулевое состояние триггер 38, что запрещает прохождение дальнейших сигналов через элементы И 52 и 55, и в нулевое состояние триггер 33. Нулевое сос7ояш1е триггера 33 разрешает прохождение импульсов генератора 61 через 3jieMeHTbi И 49 и ИЛИ 58 на полюс 66 блока 2 управления. Это приводит к тому, что весь описанный выше продесс повторяется. То есть устройство перейдет к выполнению опера- Д11Й первого и второго этапов. При этом из моделируемой сети исключаются ветви, которые не удовлетворяют условию (2). В соответствующих этим ветвям моделях триггер 7 находится в единичном состоянии, чем обеспечивается исключение таких моделей из дальнейшего процесса решения задачи.

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

Импульс, поступивший на полюс 67 блока 2 управления, поступает на вход элементов И 54 и 55. Через элемент И 54 импульс не проходит, так как триггер 38 в этом случае находится в единичном состоянии, а через элемент И 55 он проходит на единичный вход триггера 35 и через элемент ИЛИ 60 на нулевой вход триггера 33. В результате триггеры 35 и 33 соответственно устанавливаются в единичное и нулевое состояния. Кроме того, этот импульс устанавливает триггер 39 в единичное состояние, что блокирует Еход элемента И 52.

Единичное состояние триггера 35 снимает разрешение с полюсов 68 всех моделей 1 ветвей и вьщает разрешение на полюсы 72. В результате в каждой модели ветви блокируются элементы И 16 и 18, а на входе элемента ИЛИ 30 появляется сигнал, который устанавливает триггер 6 в нулевое состоя- н ие. Нулевое состояние триггера 6 снимает разрешение с входов элементов И 12 и 13, чем блокирует входы

прохо15

этих элементов и не позволяет дить сигналам через них.

Одновременно с этим, нулевое состояние триггера 33 разрешает прохождение импульсов генератора 61 через элементы И 49 и ИЛИ 58 на полюс 66 блока 2 управления. Эти импульсы генератора 61 с полюса 66 поступают на полюсы 64 моделей ветвей, которые этим полюсом подключены к полюсу 66 блока управления и образуют вершину, из которой отыскивается необходимый путь,

В модели ветви импульсы с полюса 64 через элементы И 17 и ИЛИ 28 поступают на единичный вход триггера 3. По первому импульсу из всей этой серии импульсов триггер 3 устанавливается в единичное состояние. Единичное состояние триггера 3 выдает разрешение на вход элемента И 15, чем обеспечивается прохождение остальных импульсов этой серии с полюса 64 через элемент И 15 на полюс 65 модели ветви (фиг. 1). Таким образом, импульсы, распространяясь по сети от модели к модели, устанавливают триггеры 3 в единичное состояние и появляются на полюсе 67 блока 2 управления. Причем эти импульсы распространяются топько по тем моделям ветвей, у которых триггер 5 находится в единичном состоянии, а триггер 7 - в нулевом. Эти модели соответствуют ветвям исследуемой сети, пропускные способности каждой из которых полностью удовлетворяют условию (2).

По первому импульсу, появившемуся на полюсе 67 блока 2 управления, триггер 34 устанавливается в единичное состояние, так как этот импульс проходит через элементы И 55 и 48 на единичный вход триггера 34 (в это момент триггеры 38 и 35 находятся в единичном состоянии).-Единичное состояние триггера 34 снимает разрешение с входа элемента И 49 и полюса 78. В результате прекращается поступление импульсов генератора 61 через элемент И 49 на полюс 66, а во всех моделях 1 ветвей снимается разрешение с входа элемента И 17. Кроме того, единичное состояние триггера 34 выдает разрешение на вход элементов И 46 и 50 и полюсы 77 всех моделей 1 ветвей.

452

16

В результате импульсы генератора 61 с выхода элемента И 45 через элемент И 50 и начинают поступать на полюс 67 блока управления и далее на полюсы 65 тех моделей ветвей, которые полюсом 65 подключены к полюсу 67 блока 2 управления. В моделях ветвей импульсы с полюса 65 через менты И 19 и ИЛИ 27 поступают на

единичный вход триггера 4. По первому импульсу из всей этой серии им- рульсов триггер 4 устанавливается в единичное состояние, что обеспе 5 чивает прохождение остальных импульсов этой серии с полюса 65 через элемент И 14 на полюс 64 модели ветви. Таким образом, импульсы, распространяясь по сети с полюса 65 на по20 люс 64 от модели к модели, устанавливают триггер 4 в единичное состояние и появляются на полюсе 66 блока 2 управления. Следует заметить, что распространение импульсов с полюса 67

25 блока управления через модели ветвей на полюс 66 происходит только по тем моделям ветвей, у которых триггеры 5 и 7 находятся соответственно в единичном и нулевом состоянии. Эти моде30 ли соответству.от ветвям, пропускные способности которых полностью удовлетворяют условию (2).

5

0

5

0

5

Появление первого импульса этой серии на полюсе 66 блока 2 управления приводит к тому, что триггер 32 устанавливается в нулевое состояние. Это происходит в результате того, что импульс с полюса 66 проходит через элемент И 46 на нулевой вход триггера 32. Нулевое состояние триггера 32 Свидетельствует о том, что искомый путь найден и его ветви индицируются схемой 11 индикации. В этих моделях триггеры 3-5 одновременно находятся в единичном состоянии, а остальные триггеры - в нулевом. Индицируемый путь полностью удовлетворяет условию (2), т.е. пропускная способность каждой ветви такого пути по первичному потоку удовлетворяет пути с наименьшей пропускной способностью, а пропускная способность по вторичному потоку этих ветвей больше или равна некоторой минимальной допустимой величине.

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

Отличие заключается только в том, что среди ветвей разреза Х;- х- выбирается ветвь, у которой max q ,; } С величиной пропускной способности этой ветви сравнивают пропускные способности остальных ветвей оси. Таким образом, по окончании второго этапа все множество ветвей исследуемой сет разбивается на два подмножества. Первое подмножество ветвей содержит ветви, пропускные способности которых по первичному потоку удовлетворяют условию (3). Это обеспечивается тем, что триггеры 5 и 6 в моделях, соот- ветствую1цих этим ветвям, устанавливаются в единичное состояние. Достигается это с помощью сигнала, которы появляется на полюсе 71 блока 2 управления. Сигнал формируется тогда, когда снимается последний сигнал с многовходового элемента ИЛИ 62, что происходит в момент переполнения последнего счетчика 9 импульсов из моделей ветвей разреза, В результате появляется сигнал на выходе элемента НЕ 56, который через элементы И 42 и ИЛИ 57 поступает на полюс 71, Прохождение сигнала через элемент И 42 обеспечивает нулевое состояние триггера 31, При решении этой задачи триггер 31 должен находиться в нулевом состоянии .

Появление сигнала на полюсе 71 всех моделей ветвей разрешает проходить сигналам через элемент И 22 и устанавливает триггер 6 в единичное состояние.

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

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

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

5

0

5

0

5

0

5

0

5

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

DTOpO19

та И и входом установки в го триггера, выход установки в О, третьего триггера соединен с выходом десятого элемента И, первый и второй входы которого соеди11ел(ы соответственно со счетным входом первого счетчика импульсов и инверсным выходом четвертого триггера, прямой выход которого соединен с вторыми входами первого и второго элементов Н, вход установки в 1 четвертого тригтера соединен с выходом одиннадцатого элемента И, второй вход которого соединен с третьим входом модели ветви, вьгход девятого элемента И является вторым выходом модели ветви, третий вход всех моделей ветвей соединен с третьим выходом блока управления, в блоке управления третьим выходом является выход первого элемента HJM, первый и второй входы которого соединены соответственно с выходами первого и второго элементов И, первый вход второго элемента И соединен с прямым входом шестого триггера, вход установки в О которого соединен с выходом второго MHCji OBxouoEoro элемента Р1ЛИ, вход ус;аионки в единицу шестого триггера соединен г выходом второго элемента ИЛИ и первым Р ходом п,5того элемента И, выход которого соединен с входом установки в О второго триггера, прямой выход которого соединен с первым ВУ.ОДОМ четвертого элемента И, второй вход и выход которого соединены соответственн с первым выходом генератора импульсов и первыми входами шестого, восьмого, девятог о элементов И, второй вход шестого элемента И соединен с прямым выходом триггера, инверсный выход которого соединен с вторым входом восьмого элемента И, выход которого соединен с первым входом второго элемента ИЛИ,второйвхоа которого соединен с Быхолом переполнения первого счетчика импульсов, вход установки в 1 третьего триггера соединен с выходом третьего элемента И, первый вход которого соединен с выходом второго элемента ИЛИ и входом элемента НЕ, оыход которого соединен с первым входом первого элемента И, второй вход которого соединен с инверсным выходом первого триггера, прямой вьгход которого соединен с вторым входом второго элемента И, выход седьмого элемента И соединен с

5

0

20

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

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

0

5

0

5

сов и инверсным выходом шестого триг- рера, входы установки в 1 и О которого являются пятым и шестым входами модели ветви, причем последний соединен с первыми входами четвертого и пятого элементов ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом двенадцатого элемента И, выход которого является первым выходом модели ветви, выход четвертого элемента ИЛИ соединен с входом установки в О второго триггера, инверсный выход третьего триггера соединен с вторым входом девятого элемента И, выход которого является вторьим выходом модели ветви, вторые входы пятого элемента ИЛИ и одиннадцатого элемента И являются соответственно четвертым и третьим выходами модели ветви, выход пятого элемента ИЛИ соединен с входом установки в О четвертого триггера, прямой выход которого соединен с вторыми входами первого и четырнадцатого элементов И, счетный вход второго счетчика соединен с выходом четырнадцатого элемента И, первый вход которого является седьмым входом модели ветви, с третьего по седьмой входы всех моделей ветвей соединены с соответствующими выходами блока управления, в который дополнительно введены с седьмого по девятый триггеры, второй счетчик импульсов, с девятого по четьфнадцатый элементы ИЛИ, второй выход генератора импульсов соединен с первым входом одиннадцатого элемента И, второй и третий входы и выход которого соединены соответственно с прямым и инверсным выходом восьмого и девятого триггера и первым входом четвертого элемента ИЛИ, второй вход которого соединен с прямыми входами пятого и выходом де0

5

0

5

0

5

0

вятого триггеров и выходом четьфнад- цатого элемента И, первый и второй входы которого соединены соответственно с прямым выходом восьмого триггера и выходом девятого элемента И, второй вход и выход которого соединены соответственно с инверсным выходом восьмого триггера и входом установки в 1 седьмого триггера, вход установки в О которого соединен с выходом переполнения первого счетчика импульсов, входом генератора импульсов и первым входом двенад- цатого элемента И, второй вход которого соединен с входом десятого элемента II и прямим выходом седьмого триггера, инверсный выход которого соединен с третьими входами второго и четвертого элементов И, первый выход генератора импульсов соединен с вторым входом десятого элемента И, выход которого является седьмым выходом блока управления и соединен с первым входом третьего элемента ПТИ и счетным входом второго счетчика импульсов, выход переполнения которого является пятым выходом блока управления, второй вход и выход третьего элемента ИЛli соединены соответственно с выходом шестого элемента И и счетным входом первого счетчика импульсов, входы установки в 1 и О третьего триггера соединены соответственно с выходами третьего элемента И и четвертого элемента ИЛИ, входы установки в 1 и О восьмого триггера соединены соответственно с выходами двенадцатого и одиннадцатого элементов И, причем выход последнего является шестым выходом блока управления, прямые выходы пятого и четвертого триггеров являются четвертым и восьмым выходами блока управления.

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

66 77 W 57 П ба Фаг. г

Составитель О. Гречухнна

Техред М.Моргентал Корректор В. Кабаций

3TS

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