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

 

Изобретение относится к вычислительной технике и может быть использовано для исследования потоков в сетях. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи оптимизации двух взаимосвязанных потоков между заданной парой вершин сети. Устройство содержит блок 1 сравнения, блок 2 задания матрицы инцидентности, блок 3 определения концевых вершин ребер, блок 4 определения маршрута, блок 5 выбора ребер с оптимальной пропускной способностью, блок 6 синхронизации, входы 7 задания веса ребер по первичному потоку устройства, входы 8 задания веса ребер по вторичному потоку устройства, вход 9 задания критического веса по вторичному потоку устройства, вход 10 пуска устройства, выходы 11, 12 блока 6 синхронизации, выходы 13 признаков принадлежности дуг маршруту устройства. После подачи сигнала уровня логической единицы на вход 10 пуска устройства блок 6 синхронизации формирует последовательность сигналов уровня единицы на выходах 11, 12, предусмотренную временной диаграммой его работы. При этом на выходах 13 устройства формируется множество ребер в пути между начальной и конечной вершинами сети, у которого пропускная способность по первичному потоку максимальна, а пропускная способность по вторичному потоку не больше максимально допустимой величины, 1 з.п. ф-лы, 7 ил.

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

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

РЕСПУБЛИН щ) О 06 F 15/20

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 13>

13ф

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

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

ПРИ ГКНТ СССР

1 (21) 4250142/24-24 (22) 27.05.87 (46) 23.08,90. Бюл. В 31 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев, И.А.Табунщик, .Е .В.Тонкаль и Н.В.Федотов (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 1138805, кл. G 06 F 15/20, 1983.

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

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

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

4 определения маршрута, блок 5 выбора ребер с оптимальной пропускной способностью, блок 6 синхронизации, входы 7 задания веса ребер по первичному потоку устройства, входы 8 задания веса ребер по вторичному потоку устройства, вход 9 задания т критического веса по вторичному потоку устройства вход 10 пуска устройства, выходы 11, 12 блока 6 синхронизации, выходы 13 признаков принадлежности дуг маршруту устройства.

После подачи сигнала уровня логической единицы на вход 10 пуска устройства блок 6 синхронизации форми1587533 при Ь,. (b

О1 рует последовательность сигналов уровня единицы на выходах 11, 12, предусмотренную временной диаграммой его работы. При этом на выходах 13 устройства формируется множество ребер в пути между начальной и коИзобретение относится к вычислительной технике и может быть использовано для исследования потоков в 15 сетях.

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

I между заданной парой вершин сети.

Г

На фиг.1 представлена функциональная схема устройства; на фиг.2 — временная диаграмма работы блока синхронизации; на фиг.3 — функциональная 2$ схема блока выбора ребер с оптимальной пропускной способностью;на фиг.4 -,, временная диаграмма работы его узла синхронизации; на фиг.5 — пример модульной реализации устройства; на фиг.6 — ; на фиг ° 7 иллюстративный пример решения задачи оптимизации двух взаимосвязанных потоков

Устройство содержит (фиг. 1) блок

1 сравнения, блок 2 задания матри35 цы инцидентности, блок 3 определения концевых вершин ребер, блок 4 определения. маршрута, блок 5 выбора ребер с оптимальной пропускной спо- „ собностью, блок 6 синхронизации, входы

7 задания веса ребер по первичному потоку устройства, входы 8 задания веса ребер по вторичному потоку устройства, вход 9 задания критическо- 45 го веса по вторичному потоку устройства, вход 10 пуска устройства, выходы 11 и 12 блока 6 синхронизации, выходы 13 признаков принадлежности дуг маршруту устройства .

Блок 5 выбора ребер с оптимальной пропускной способностью содержит узел 14 стягивания ребер, узел

15 определения иницидентных ребер, узел 16 выбора максимума, накапливающий узел 17 сравнения, регистр 18, 55 узел 19 синхронизации, тактовый

Вход 20 блока 5, входы 21 задания ееса ребер, входы 22 признаков иннечной вершинами сети, у которого пропускная способность по первичному потоку максимальна, а пропускная спосОбность пО втОричнОму потОку не больше максимально допустимой величины. 1 з.п. ф-лы, 7 ил. цидентности ребер вершинам сети блока 5, вход 23 начальной установки блока 5, с первого по третий выходы

24-26 узла 19 синхронизации и выходы 27 признаков принадлежности ребер множеству оптимальных.

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

Задача оптимизации двух взаимосвязанных потоков .является задачей определения пути между заданной парой вершин сети, у которого пропускная способность П по первичному потоку удовлетворяет условию пути с наибольшей пропускной способностью, а пропускная способность по вторичному потоку не превосходит или, в крайнем случае, равна максимальной допустимой величине. Пропускная способность такого пути удовлетворяет условию (min (max (q;;), b..) где Ь. — величина в,торичного по1J тока по ребру (х;,xf);

Ъ вЂ” "-аданная максимальйая допустимая величина вторичного потока для каждого ребра сети; — величина первичного потоIf . ка по ребру (х,, х ), k — любой (S-t) разрез в мноj Ф жестве сети;

S u t — соответственно начальная и конечная вершины сети.

Перед началом работы в блок 2 задания матрицы инцидентности заносят информацию о топологии сети. На вхо- . ды 7 и 8 устройства подают информацию о весе (пропускной способности) реб е р по перв ич ному и в торичному потоку соответственно. На вход 9 подают информацию о максимально допустимой (критической) величине вторич7533 6

5 158 ного 1.:. . При этом блок 2 исключает из тг.-.;логии графа все ребра, вес которых по вторичному потоку превышает допустимую (критиче скую) величину.

На вход 10 пуска устройства пода- ят импульс уровня логической едини- цы. При этом блок 6 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы. Сигнал уровня логической единицы появляется на первом выходе 11 блока 6. При этом блок

5 выбора ребер с оптимальной пропускной способностью накапливает на своих выходах 27 состав ребер, вес которых не меньше веса ребер с максимальной пропускнбй способностью среди всех ребер инцидентных начальной вершине, и стягивает эти ребра. Через в ремя, до с тато чное для о к он чан ия ук азанных процессов, блок 6 синхронизации снимает сигнал уровня логической единицы с выхода 11 и формиру-ет сигнал уровня логической единицы на выходе 12. При этом блок 3 опре-. деления концевых вершин ребер проверяет принадлежность конечной вершины составу концевых (т.е, производит проверку наличия пути из начальной в конечную вершину сети по "оптимальным" ребрам). В том случае, если путь из начальной в конечную вершину отсутствует, работа устройства повторяется. В противном случае на выходе признака принадлежности конечной вершины массиву концевых блока 3 появляется импульс уровня логической единицы. При этом останавливается блок

6 синхронизации, а блок 4 выдает на выходы 13 устройства множество ребер, принадлежащих оптимальному маршруту.

Блок выбора ребер с оптимальной пропускной способностью работает следующим образом.

Перед началом работы обнуляют накапливающий узел 17 сравнения. На входы 20 подают информацию о весе ребер сети, на входы 22 информацию о ее топологии. На вход 20 пуска подают сигнал уровня логической единицы.

При этом узел 19 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы (фиг.4). Сигнал уровня логической единицы появляется на выходе 26 узла 19. При этом узел

15 формирует на своих выходах массив ребер, инцидентных начальной вершине сети, а узел 16 выбора максимума выбирает вес максимального из них и выдает его (вес) на свой информа- . ционный выход. Через время, достаточное для определения веса максимального из ребер, на выходе 25 узла 19 появляется, сигнал уровня логической единицы. При этом информация с выхода узла 16 заносится в регистр 18. Через время, достаточное для записи, узел 19 снимает сигналы уровня логической единицы с выходов 25 и 26 и формирует сигнал уровня логической единицы на выходе 24. При этом узел

17 сравнивает веса ребер сети с весом, записанным в регистр 18, H накапливает (по ИП1) результаты срав нения ("не меньше") для каждого информационного направления. При этом узел -14 стягивает все ребра, вес которых превосходит значение, записанное в регистре 18. Через время, достаточное для окончания операции. сравнения, узел 19 снимает сигнал уровня логической единицы с выхода

24 ° При поступлении на вход 20 очередного тактового импульса работа блока 5 повторяется.

Устройство может быть выполнено в виде моделей 28 ребер (фиг.5) и блока 29 управления (фиг.6).

Модель 28 ребра содержит элементы И 30-44, элементы ИЛИ 45-50, триггеры 51-56, счетчики 57 и 58, элемент HE 59 и элемент 60 индикации.

Блок 29 управления содержит счетчики 61 и 62, элементы И 63-74, элементы HJIH 75-78, элемент HE 79,триггеры 80-85, генератор 86 импульсов, элемент ИЛИ 87. Устройство имеет полюса 88-101, среди которых 88 и 89 у моделей 28 ребер служат для коммутации их между собой, согласно конфигурации моделируемой сети. Полюса

90-99 в моделях 28 ребер служат для подключения к блоку управления, что обеспечивает их синхронную работу.

Полюсами 100 и 101 блок 29. управления подключается соответственно к полюсам 88 и 89 тех моделей ребер, между которыми отыскивается оптимальный путь.

Задание исходных данных задачи оптимизации двух взаимосвязанных потоков осуществляется с помощью коммутации моделей 28 ребер посредст1587533

50

Перед началом работы устройства триггеры 51-56 всех моделей 28 и

55 триггеры 80-85 и счетчик 61 блока 29 управления устанавливаются в нулевое состояние. Цепи установки н занеoeния исходных данных не показаны. вом полюсов 88 и 89 между собой в соответствии с конфигурацией моделируемой сети, подключением полюсом 100 и 101 блока 29 управления к полюсам тех моделей 28 ребер, между которы5 ми отыскивается путь, занесения (N—

q..), (М вЂ” b; ) и (М - Ъ ) числа импульсов соответственно в счетчики

57, 68 моделей 28 ребер и счетчик

6? блока 29 управления,где N — емкость счетчиков °

Процесс нахождения пути можно представить в виде трех этапов.

Первый этап содержит циклически повторяющиеся шаги: нахождение разреза х -, х ) из множества разрезов К;

1 Э выделение ребра разреза (х;, х ) с

max q; выбор ребер, у которйх величина первичных потоков больше или равна величине первичного потока выбранного ребра разреза. Второй и третий шаги первого этапа выполняются устройством одновременно. Выполнение третьего шага состоит в зако- 25 рачивании полюсов 88 и 89 моделей 28, что приводит к исключению их из дальнейшего рассмотрения на этом этапе.

Второй этап заключается в проверке выполнения ограничений на вели-чину вторичного потока b; для каждого ребра, выбранного на первом этапе, с заданной максимальной допустимой вепичиной bo. В результате проверки может оказаться, что ребра удовлетворяют или не удовлетворяют ограничению. В этом случае эти ребра исключаются из процесса решения задачи, Исключение ребер представляет собой блокирование в модели 28 це- 40 пи прохождения сигнала от полюса 88 к полюсу 89, и наоборот. Кроме того, на этом этапе одновременно производится проверка наличия пути между заданными веРшинами, пРоходящего по 45 ребрам. Если такого пути нет, устройI ство переходит к выполнению операций первого этапа, при наличии пути — к выполнению третьего этапа.

Третий этап .заключается в выделении ребер этого пути и его индик ации.

Работа устройства начинается с момента установки триггера 80 в единичное состояние. Единичное состояние триггера 80 выдает разрешение на вход элемента И 64. При этом импульсы генератора 86 проходят через элемент И 64 и поступают на входы элементов И 66 и 67. Через элемент

И 67 импульсы поступают на вход элемента ИЛИ 75 и далее на полюс 100 блока 29 управления.

Импульсы с полюса 100 блока 29 управления поступают на полюса 88 или

89 моделей 28, которые в результате коммутации этими полюсами между собой образуют вершину сети, из которой отыскивается путь. В укаэанных моделях 28 импульсы с полюса 88 поступают на вход элементов 32-35. На всех входах элемента И 34 есть раз-. решения и поэтому импульсы пройдут через него и поступят на единичный вход триггера 51. По первому импульсу из всей серии импульсов, поступивших в модель 28 на полюс 88,триггер 51 установится в единичное состояние. Все последующие импульсы подтверждают это состояние триггера 51.

Аналогично, если импульсы поступят на полюс 89 модели 28, они пройдут через элемент И 36 и установят триггер 52 в единичное состояние.

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

51 или 52 выдает разрешение на вход элемента И 38. Разрешение поступает на полюс 95 модели 28.

С полюса 95 модели 28 разрешение поступает на соответствующий .этой модели вход многовходового элемента

ИЛИ 87. На входы элемента ИЛИ 87 поступают разрешения только от тех моделей 28, которые своим полюсом 88 или 89 связаны с полюсом 100 блока

29 управления. Единичное состояние триггеров 51 или 52 свидетельствует о том, что данная модель 28 принадлежит выбранному разрезу (х °, х ) из множества разрезов К. Это соответствует первому шагу первого этапа решения задачи.

Выбор ветви Разреза (х,, х;) с

max q, и выбор ребер сети, величи1J на первичных потоков через которые больше или равна величине потока выбранного ребра разреза, что соответствует выполнению второго и третьего шагов первого этапа, происходит следующим образом. Разрешение с выхода многовходового элемента

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

НЕ 79 и одновременно, через элемент

И 65 на единичный вход триггера 81.

В результате элемент НЕ 79 снимет разрешение с полюса 94 блока 29 управления и, следовательно, с полюсов . 94 всех моделей 28, что блокирует вход элемента И 39 в каждой модели 28.

Разрешение, поступившее на единичный вход триггера 81, устанавливает его в единичное состояние, что запретит прохождение импульсов генератора 86 на полюс 100 блока 29 управления и разрешит прохождение импульсов на вход счетчика 61 и полюс 90. Единичное состояние триг- 20 гера 81 свидетельствует о том, что устройство начинает выполнять второй и третий шаги первого этапа.

В моделях 28 импульсы с полюса 90 поступают через элемент И 43 на 25 вход счетчика 57 до его переполнения.

Импульс переполнения счетчика 57 модели 28 поступает на единичный вход триггера 53 и одновременно через 30 элемент ИЛИ 43 на нулевые входы триггеров 51 и 52. В результате триггеры 51 и 52 установятся в нулевое состояние, если ранее они были установлены в единичное состояние импульсами, поступившими на полюса 88 и

89 моделей 28, Триггер 53, установленный в единичное состояние поступившим на его вход импульсом -переполнения счетчи- 4р ка 57, установится в нулевое состояние очередным импульсом, который поступит на полюс 90. Это происходит потому, что триггер 54 находится в нулевом состоянии и он выдает разре- 45 шение на вход элемента И 39. В результате очередной импульс, который поступает на полюс 90, пройдет через элементы И 39 и ИЛИ 48 на нулевой вход триггера 53.

В результате установки триггеров

51 и 52 в модели 28 происходит снятие разрешения с полюса 95 и, следовательно, с соответствующего входа многовходового элемента ИЛИ 87, В тот момент, когда будет снято последнее разрешение с полюса 95 многовходового элемента ИЛИ 87, блок 29 управления выдаст разрешение на по1587533 !О люс 94 моделей 28. При этом в модели 28 выбранного разреза с наибольшей пропускной способностью по первичному потоку триггер 54 установится в единичное состояние. Единичное состояние триггера 54 запретит установку триггера 53 в нулевое состояние очередным импульсом, который поступит на полюс 90 модели 28. Это происходит потому, что на нулевом выходе триггера 54 будет снято pasрешение, которое заблокирует элемент

И 39 и очередной импульс с полюса 90 не пройдет через элементъ1- И 39 и

ИЛИ 48.на нулевой вход триггера 53 °

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

53 и 54 в единичное состояние у тех моделей, у которых величина первичного потока равна или больше величины первичного потока выбранното ребра разреза. Единичное состояние триггеров 53 и 54 свидетельствует о том, что пропускная способность этих моделей по первичному потоку удовлетво; ряет условию. Кроме того, единичное состояние триггера 54 в каждой модели 28 выдает, разрешение на входы элементов И 30 и 32, что обеспечивает закорачивание полюсов 88 и 89 и исключение таких моделей 28 из дальнейшего рассмотрения на первом этапе.

Конец выполнения второго и третьего шагов первого этапа устройством определяется моментом появления импульса переполнения счетчика 61 блока 29 управления. К этому моменту в счетчиках 57 всех моделей 28 вос- . становится ш формация о величинах их первичных потоков, т,е. произойдет регенерация, Роль регенерационного счетчика для счетчиков 57 всех мо- делей 28 выполняет счетчик 6! блока

29 управления. Он начинает свой счет с 1 0 и его емкость равна N, а счетчики 57 моделей 28 начинают счет с (N — q;. ) .

Импульс пе ре полнения сче тчика 61 блока 29 управления поступает через элемент ИЛИ 75 на полюс !00. Кроме того, импульс переполнения счетчика 61 поступает на вход генератора 86, который по этому импульсу выдает на вход элемента И 71 импульс,который сдвинут относительно входного, Через элемент И 71 этот импульс не

1587533

12 пройдет, так как нет разрешения с единичного выхода триггера 85.

Далее этот импульс с полюса 100 блока 29 управления поступает на полюс 88 или 89 тех моделей 28, которые в результате коммутации этими полюсами между собой образуют верши«у сети, из которой отыскивается п ть, и весь процесс выполнения шагов первого этапа повторяется аналогично описанному. Итерационное выполнение шагов первого этапа повторяется до тех пор, пока очередной импульс переполнения счетчика 61 блока 29 управления, который поступаеТ через элемент ИЛИ 75 на полюс

100, не появится на полюсе 101. Появление импульса на полюсе 101 происходит в результате распространения импульса переполнения счетчика 61 по тем моделям 28, триггеры 53 и 54 которьгх находятся в единичном состоянии. В таких моделях импульс с полюса 88 через элемент И 32 поступает на полюс 89 или с полюса 89 через элемент И 30 на полюс 88.

Момент появления импульса на полюсе 101 блока 29 управления свидетельствует о том, что первый этап работы устройства окончен и все множество ребер сети разбито на два подмно, жества. Одно подмножество содержит ребра, величины первичных потоков через которые удовлетворяют условию, и в соответствующих им моделях 28 триггеры 53 и 54 находятся в единичном состоянии. Другое подмножество содержит ребра с величинами первичных потоков, которые не удовлетворяют указ анному условию, и их триггеры 53 и 54 будут в нулевом состоянии. Это подмножество ребер при вы— полнении последующих этапов работы устройства не участвует в решении задачи.

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

Импульс, который появился на полюсе 101 блока 29 управления, поступит на вход элементов И 72-74. Через элемент И 72 импульс пройдет, так как есть разрешение с нулевого выхода

3S

S0

55 триггера 85. С выхода элемента И 72 этот импульс поступает на единичный вход триггера 84 и установит его в единичное состояние. Единичное состояние этого триггера 85 снимает разрешение с входов элементов 64, 67 и 74 и выдает разрешение на элементы И 70, 71, 73 и полюс 94 блока

29 управления. В результате импульсы генератора 86 пройдут через элемент

И 70 поступят на вход счетчика 62.

Одновременно эти импульсы начнут поступать через элемент ИЛИ 76 на вход счетчика 61 и на полюс 90 блока 29 управления.

В моделях 28 разрешение с полюса

91 поступит на входы элементов НЕ 59 и И 44. В результате на выходе элемента НЕ 59 исчезнет сигнал и элемент И 43 будет заблокирован. Одновременно с этим импульсы, которые поступают на полюс 90, будут проходить через элемент И 44 на вход счетчика 58 до его переполнения. Следует заметить, что дпя моделей 28, у которых выполняется условие b < Ь счетчики 58 переполнятся раньше или одновременно со счетчиком 62 блока

29 управления. В этих моделях 28 импульс переполнения сетчика 58 не пройдет через элемент И 41, так как триггер 56 находится в нулевом состоянии. Следовательно, триггер 55 у таких моделей 28 останется в нулевом состоянии, а триггеры 53 и 54 — в единичном, В моделях 28, у которых не выполняется условие b; b, счетчики

58 переполнятся позже, чем счетчик

62 блока 29 управления. В таких моделях 28 триггер 55 устанавливается в единичное состояние, а триггеры

53 и 54 — в нулевое. Это происходит следующим образом.

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

28. В моделях 28 он, поступает на единичный вход триггера 56 и устанавливает его в единичное состояние.

Единичное состояние триггера 56 выдает разрешение на вход элемента

И 41, что обеспечивает прохождение импульсов переполнения счетчика 58 в модели 28 через этот элемент. Импульс переполнения счетчика 58, пройдя через элемент И 41 на единичный вход триггера 55, установит его в единичное состояние. Единичное состо13 158 якие триггера 55 выдает разрешение на вход элемента И 42 и снимает разрешение с входов элементов И 30-37, что запрещает прохождение сигналов от плюса 88 модели 28 к полюсу

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

Очередной импульс переполнения счетчика 6 1 блока 29 управления поступает на вход элемента ИЛИ 75 и на вход генератора 86. По этому импульсу генератор 86 импульсов выдает импульс, который сдвинут относительно входного, на вход элемента И 71.

Через элемент И 71 импульс пройдет, так как на входе этого элемента есть разрешение с единичного вьмода триггера 85 и нулевого выхода триггера

84. С выхода элемента И 7 1 импульс поступает на полюса 93 всех моделей

28. В моделях 28 этот импульс поступает на нулевой вхогг триггера 56 и через элемент И 42 на нулевой вход триггера

54 и устанавливает их в нулевое состояние. Кроме того, этот кгпульс поступает на нулевые входы триггеров 53, 5 1 и 52. В результате они устанавливаются в нулевое состояние.

К моменту появления импульса переполнения на выходе счетчика 61 информация в счетчиках 58 моделей 28 и в счетчике 62 блока 29 управления восстановлена, т.е. происходит регенерация. Роль регенерационного счетчика, также как и на первом этапе,для этих счетчиков выполняет счетчик 61 блока 29 управления. Он начинает счет с нуля, а счетчики 58 моделей 28 и счетчик 62 блока 29 управления начинает соответственно свой счет с (N — Ь ° ) и (N — Ъ ), lJ о

С выхода элемента ИЛИ 75 импульс переполнения счетчика 61 блока 29 управления поступает иа полюс 100 и далее на полюса 88 или 89 моделей 28, которые подключены к полюсу 100. В моделях 28 этот импульс с полюса 88 через элемент И 32 поступает на полюс 89. Аналогично этот импульс с полюса 89 через элемент И 30 поступает на полюс 88. Таким образом, импульс переполнения с полюса 100 блока 29 управления, распространяясь по моделям от полюса 88 к полюсу 89 или от полюса 89 к полюсу 88, появится на полюсе 101 блока 29 управления. Следует заметить, что импульс может про7533 !4 ходить только по тем моделям 28, у которых одновременно триггер 55 и триггеры 53 и 54 соответственно находятся в нулевом и единичном состоянии.

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

В противном случае устройство переходит к дальнейшему его нахождению.

Это осуществляется следующим образом. Имггульс генератора 86, который пройдет через элемент И 71, поступит на нулевой вход триггера 85 и установит его в нулевое состояние. Нулевое состояние триггера 85 запретит

20 прохождение импульсов генератора 86 через элемент И 70 и разрешит их прохождение через элемент И 64. Это приводит к тому, что весь описанный процесс повторяется, т.е . устройство сно25 ва переходит к выполнению операций первого и второго этапов. При этом из моделируемой сети будут исключены модели 28, в которьм триггеры 55 находятся в единичном состоянии,а остальные триггеры — в нулевом.

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

78 поступают на единичный вход триггеров 82, 84 и устанавливают их в еди4ц ничное состояние. Единичное состояние триггера 82 снимает разрешение с полюсов 99 и выдает разрешение на полюса 98 всех моделей 28.

В моделях 28 разрешение с полюса

4 98 поступает через элемент ИЛИ 49 на нулевой вход триггера 54 и уста— навливает его в нулевое состояние.

Нулевое состояние триггера 54 разрывает закоротку полюсов 88 и 89.

Одновременно с этим импульсы генератора 86 начинают опять поступать на полюс 100. Это происходит потому,что единичное состояние триггера 84 блока 29 управления выдает сигнал через элемент И 72 на нулевой вход триггера 85 . По этому сигналу триггер 85 устанавливается в нулевое состояние, чем обеспечивает прохождение импульсов генератора 86 через элемент И 64.

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

5 распространяются по сети через модели 28 с полюса 89 на полюс. 88 до тех пор, пока не появятся на полюсе 100 блока 29 управления.

С полюса 100 блока 29 управления импульсы поступят через элемент И 63, так как на другом входе этого элемента есть разрешение с единичного выхода триггера 83, на нулевой вход триггера 80. Первый из этих импульсов установит триггер 80 в нулевое состояние. Нулевое состояние триггера 80 сигнализирует о конце решения задачи. При этом модели 28, у которых триггеры 51 и 52 находятся

2О одновременно в единичном состоянии, принадлежат искомому пути, Эти модели индицируются элементом 60 индикации.

Для пояснения работы устройства

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

На фиг.7а цифрами обозначены пропускные способности соответственно по первичному и вторичному потокам ребер: (Sx 1), (Sx )» (Sxg, (х,хд), (X5Xg) j (XQX7) j (XQ j t) j (X 7j t)» (х х ), {х,t) . Первая цифра указы40 вает на величину пропускной способности по первичному потоку по соответствующему ребру, а вторая цифра указывает на величину пропускной способности по вторичному потоку по тому же

45 ребру. Вершины, которые формируются в результате коммутации моделей 28 между собой полюсами 88 и 89 согласно конфигурации сети, на фиг.7а обозначены 8 х. х х х х » х х

5О х j t. Кроме того, вершины S u t обозначают вершины, между которыми отыскивается путь, оптимизирующий взаимосвязанные потоки, и к которым соответственно подключены полюса 100 и

101 блока 29 управления. В счетчики

57 и 58 каждой модели 28 заносится предварительно соответствующее число импульсов. В счетчик 62 импульсов блоблока 29 управления заносится число

15 1587533

С полюса 100 импульсы генератора

86. поступают на полюса 88 и 89 моделей 28, к полюсам подключен полюс 100 блока 29 управления. При этом в указанных моделях 28 импульсы с полюса 88 поступают на вход элемента И

35 тех моделей 28,.триггер 53 которых находится в единичном состоянии, н пройдет через этот элемент. Далее эти импульсы с выхода элемента И 35 через элемент ИЛИ 45 поступают на единичный вход триггера 51. По первому импульсу из всей серии импульсов, поступивших в модель 28 на полюс "88, триггер 51 установится в единичнЬе состояние. Единичное состо- яние триггера 5 1 выдает разрешение на элемент И 33. Поэтому остальные импульсы из всей серии с полюса 88 . через элемент И 33 поступают на полюс 89 модели 28. Таким образом, импульсы распространяются iso сети через модели 28, у которых триггер

51 находится в единичном состоянии, до тех пор, пока не появятся на полюсе 101 блока 29 управления.

Поступившие на полюс 101 блока 29 управления импульсы пройдут через элемент И 74, ИЛИ 78 и И 69, так как триггеры 85 и 82 соответственно находятся в нулевом, единичном состояниях, и первый из них установит триггер 83 в единичное состояние, Единичное состояние триггера 83 выдает разрешение на полюс 97, снимает разрешение с полюса 96, выдает разрешение на элементы И 63, 68 и снимает разрешение с элемента И 67, при этом с полюсов 96 всех моделей 28 будет снято разрешение, что заблокирует их элементы И 35, а на полюсах 97 по †. явится разрешение, что разрешит прохождение сигналов через элемент И 37.

Одновременно импульсы генератора 86 поступят на полюс 101 и далее на полюса 89 моделей 28, к которым подключен полюсом 101 блок 29.управления.

С плюса 89 в модели 28 импульсы через элементы И 37 и ИЛИ 46 поступят на единичный вход триггера 52.

По первому импульсу из серии импульсов,. поступивших на полюс 89,триггер 52 установится в единичное состояние, которое выдает разрешение на элемент И 31. Поэтому остальные импульсы пройдут через элемент И 31 и поступят на полюс 88. Это происхо-

17 1587533 18 импульсов для всех ветвей сети. Вудем 28 полюса 95 многовходового элемента ИЛИ 87 ° ра6оТа устройства начинается с мо Очередной импульс, поступивший мента установки триггера 80 в единич- на полюс 90 модели 28 ($ х ), устаное состояние Е я ие. Единичное состояние новит триггер 53 в этой модели 28

У триггера 80 разрешает прохождение щ - в нулевое состояние. пульсов генератора 86 через элементы Аналогичный процесс произойдет

И64 И67иЮЫ75

У и ЮЫ 75 на полюс 100 и с моделью 28, которая соответстблока 29 управления. С полюса 100 им- р вует ребру ($ х ) сети.

1О пульсы поступят на полюса 88 моделей При появлении импульса перепол28 к которые соответствуют ребрам нения счетчика 57 в модели 28, ко() э (<) и (S х g моделируе- торая соответствует ребру сети мой сети (фиг.7a). В этих моделях им- (S х ) „ ее триггеры 53 и 54 устанавпульсы пройдут через элементы И 34 15 ливаются a единичное состояние, и ИЛИ 45 на единичный вход триггера Единичное состояние триггера 54 за51

1. По первому импульсу триггер 51 коротит полюса 88 и 89 этой модели . установится в единичное состояние. 28. Одновременно с этим на полюсе

Остальные импульсы подтверждают это 95 этой модели 28 снимается сигнал состояние. Единичное состояние триг 20 и, следовательно, с соответствующего гера 51 моделей 28 (S х,), (S х ) H этой модели полюса 95 многовходово(S x (>) свидетельствует о том, что эти ro элемента ИЛИ 87 тоже снимается модели принадлежат первому разрезу сигнал. В результате на выходе мноК (на фиг.7а разрез обозначен пун- говходового элемента ИЛИ 87 исчектирной линией) из множества разре- 25 зает сигнал, что приводит к появле- зов, что соответствует первому шагу . нию сигнала на полюсе 94 всех модепервого этапа работы устройства. лей 28.

В результате эти модели на свой Появление сигнала на полюсе 94 полюс 95 выдадут сигнап, который по- всех моделей 28 разрешает прохождеступит на соответствующий этой мо- 30 ние сигналам через элемент И 40 в дели вход 95 многовходового элемен- этих моделях 28 на единичный вход та ИЛИ 87. На выходе многовходового триггера 54. элемента ИЛИ 87 появляется сигнал,ко- Таким образом, в моделях ветвей, торый поступает на вход элемента которые соответствуют ветвям (х х „), НЕ 79 и И 65..

В ез ль (х хк) (х х.) (х х ) (х х ) результате на полюсе 94 всех мо- (x

45 а иг. а, прео разуется б па, и разрешает поступать импульсам в сеть, показанную на фиг.7б. На генератора 86 на вход счетчика 61 фиг.7б S обозначены совмещенные в и на полюс 90. При этом через эле- результате закорачивания полюсов 88 мент И 67 импульсы не проходят (сле- и 89 модели 28 вершины S, х, х и довательно, они не проходят на по- 50 х вершиной t — х р Ф люс 100), так как нет разрешения на нулевом выходе триггера 81. поступит на полюса 92 моделей 28 к

Из всего числя моделей 28,принад- которым в новой сети окажется подклюлежащих разрезу К,, первым перепол- чен полюс 100. Такими ребрами будут ни1ся счетчик 57 модели 28 ($ х ) . 55 (S t ) и (S хв) . Импульс, поступивший

Триггер 53 этой модели 28 установит- на полюс 88 этих ребер, установит их ся в единичное состояние, я триг- триггера 51 в единичное состояние. гер 51 — в нулевое, что снимет сиг- Это свидетельствует о построении нонал с соответствующего этой модели вого разреза К и из множества разре19 158753 зов К.С позиции исходной моделируемой сети (фиг.7а) разрезу К> принадлежат, ребра: ($ х,), (S х ), (х х д), (х х ) (х7с ) и (х, х 7)

В результате дальнейшей работы устройства в разрезе К найдено ребро с максимальной пропускной способностью по первичному потоку (S t ) и (S x 8), Нх пропускная спОсобность

Ч = ",3 (фиг.7б). Это соответствует ребрам исходной сети (фиг.7а) (х х ), (х х ) и (х ).

Очередной импульс переполнения счетчика 61, поступивший на плюс 100, появится на полюсе 101, так как он проходит по закороченным ветвям с полюса 88 на полюс 89. Этот импульс устанавливает триггер 85 в единичное 20 состояние. Это свидетельствует о том, что все ребра,. пропускная способность по первичному потоку которых удовле творяе т заданному условию, найдены, и устройство переходит к вы- 25 полнению шагов второго этапа работы.

Ребра исходной сети, пропускная способность по первичному потоку которых удовлетворяет условию, показаны на фиг ° 7в,В дальнейшем устрой- 3< ство работает только с этими ветвями, так как в моделях, соответствующих этим ребрам, триггеры 53 и 54 одновременно находятся в единичном состоянии. На фиг.7в не показаны ребра, которые не удовлетворяют условию.

Единичное состояние триггера 85 выдает разрешение на элементы И 70, 71, 73 и полюса 91 всех моделей 28.

В результате в каждой модели 28 снятс

I разрешение с входа элемента H 43 и выдано разрешение на вход элемента

И 44. Кроме того, единичное состо яние триггера 85 разрешает прохождение импульсов генератора 86 через элемент И 70 на вход счетчика 62 и через элемент ИЛИ 76 на вход счетI чика 61 и полюса 90 всех моделей 28.

В моделях 28 с полюса 90 импульсы через элемент И 44 поступают на вход счетчика 58 до их переполнения. Ребра, соответствующие этим моделям, показаны на фиг.7в. . В каждой такой модели 28 импульс переполнения счетчика 58 через элемент И 41 не поступает на единичный вход триггера 55 и не устанавливает его в единичное состояние. Это возможно только для тех моделей 28,про3 20 пускная способность по вторичному потоку которых меньше или равна Ь

= 8, заданной нами ранее. К таким ребрам относятся (х, х+), (х х ), (х х у), (х х.,), (х х„) и (х t) фиг.7В °

В моделях 28, которые соответствуют ребрам (фиг.7в) (S х ), (х м ), (х х ) и (х t) сети, триггер 55 устанавливается в единичное состояние.

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

В результате импульс переполнения счетчика 62 поступает на полюса 92 всех моделей 28 и устанавливает триггер 56 в единичное состояние, Единичное. состояние триггера 56 вьщает разрешение на вход элемента И 41, что позволяет проходить импульсу переполнения счетчика 58 на единичный вход триггера 55.

Единичное состояние триггера 55 разрыв ает цепи прохождения сигнала с полюса 88 на полюс 89 в таких моделях 28, что исключает их из дальнейшего процесса решения задачи. Такими ребрами для примера будут (S х ), (x x g) (х х 4) H (x t) . Их пропускная способность по вторичному потоку больше Ь, = 8 (фиг.7в).

Очередной импульс переполнения счетчика 61 не сможет пройти по ребрам, которые показаны на фиг.7в, так как в моделях 28 (S х ), (х х ), (х х Р и (х t) заблокированы входы элементов И 30-37.

В результате на полюсе 101 этот импульс не появится. При этом по импульсу счетчика 61 генератор 86 импульсов выдает импульс, который сдвинут относительно входного, на вход элемента И 71, который пройдет через этот элемент, так как триггер

84 остается в нулевом состоянии. Этот импульс устанавливает триггер 85 в нулевое состояние и поступает на полюса 93 всех моделей 28, где он устанавливает триггеры 5 1-55 в нулевое состояние. Это приводит к тому,что устройство снова переходит к выполнению операций.перзого и второго этапов. При этом из моделирумой сети исключаются модели 28, которые не удовлетворяют условию. В таких моделях триггеры 55 находятся в единичном состоянии. Для нашего примера такими моделями 28 будут модели 28, которые соответствуют ветвям (Я х «), (х х ), После этого блок 29 управления выдает импульсы на полюс 101 и далее на полюса 89 моделей 28, Распространяясь, импульсы этой серии проходят от вершины t к вершине S, при этом триггер 52 установлен в единичное состояние, если они проходят с полюса 89 на полюс 88 через элемент И 31 .и одновременно поступают на единичный вход триггера 52. На фиг.7а это распространение показано сплошной стрелкой.

55

21

15875 (Х Х1) . Новая сеть показана на фиг.7г °

Дальнейшая работа устройства с этой сетью (фиг.7г) на первом этапе дает множество ребер, показанное на фиг.7д.

После выполнения устройством вто5 рого этапа получено множество ребер, которое показано на фиг.7е. При этом в процессе выполнения второго этапа импульс переполнения счетчика 61, поступивший на полюс 100, проходит через модели 28 с полюса 88 на полюс 89 и появляется на полюсе 101. Ребрами, по которым пройдет этот импульс, будут (S х ) (х х ) (х хр) (х -х- ) 15 (х-, +).

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

Процесс выделения ребер пути заключается в подаче импульсов в модели 28, связанных с полюсом 100, триггеры 53 которых находятся в единичном состоянии ° Эти импульсы от ге- 25 нератора 86 поступают На полюс 88 модели 28. Такой моделью будет модель

28, соответствующая ребру (S х,) фиг.7е.Импульс с полюса 88 в модели

28 (S х,) поступает через элементы 30

И 35, ИЛИ 45 на единичный вход триггера 51. Первый импульс из всей серии устанавливает триггер 5 1 в единичное состояние, что дает возможность остальным импульсам с полюса 88 через элемент И 33 проходить на полюс 89.

Далее они поступают с полюса 89 модели 28 (S х,) на полюса моделей (1 Ф) (X)X.) °

Таким образом, распространяясь 40 по сети от модели 28 к модели 28 (фиг.7е), они появятся на полюсе 101 блока 29 управления, т. е, в вершине

На фиг.7а это распространение импульсов показано пунктирной стрел- 45 кой от S к t.

33

22

На фиг.7е показно, что в результате действия обеих серий импульсов триггеры 51 и 52 моделей 28, которые соответствуют ребрам (S х ), (х,х 1, в (х х ), (х х z) и .(х t),уст навлива7 ются в единичное состояние. В моделях

28 (х,х, ), (х х ) и (х -х ) толькО триггеры 5 1 устанавливаются в единичное состояние, а триггеры 52 остаются в нулевом.

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

Этот путь на фиг.7е показан жирной линией. Он индицируется элементами

60 индикации этих моделей 28 °

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

1. Устройство для анализа парамет ров се тей, содержащее блок сравнения, блок задания матрицы инцидентности, блок определения концевых вершин ребер, блок определения маршрута и блок синхронизации, вход пуска которого является входом пуска устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет решения задачи оптимизации двух взаимосвязанных потоков между заданной парой вершин, в него введен блок выбора ребер с оптимальной пропускной способностью, причем первый выход блока синхронизации подключен к тактовому входу блока выбора ребер с оптимальной пропускной способностью, вход задания веса К вЂ” го ребра которого (К = i Ð, где P — количество ребер в графе ) является входом задания веса К-го ребра по первичному потоку устройства, вход задания веса К-го ребра по вторичному потоку которого подключен к К-му информационному входу. группы блока сравнения, вход задания критического веса по вторичному потОку устройства подключен к информационному входу блока сравнения, выход признака "Не меньше К-го информационного направления которого подключен к входу удаления К-го ребра блока задания матрицы инцидентности, выход признака инцидентности К-ro ребра М-й вер.шине сети которого (М = 1,...,Â, где

 — количество вершин в сети) подключен к одноименным входам блока

23

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

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

К-гс ребра блока подключен к К-му ин24 формационному входу группы накапливающего узла сравнения и к К-му вхо" ду узла выбора максимума, тактовый вход блока подключен к входу пуска узла синхрониз ации, первый выход которого подключен к тактовому входу накапливающего узла сравнения, выход признака "Не меньше" К-го информаЦионного направления которого подключен к входу признака стягивания К-Fo ребра узла стягивания ребер, вход признака инцидентности К-го ребра М-й вершине блока подключен к одноименному входу узла стягивания ребер, выход признака инцидентности К-го ребра И-й вершине которого подключен к одноименному входу узла определения инцидентных ребер, выход признака принадлежности К-ro ребра массиву инцидентных которого подключен к входу подключения К-ro информационного направления узла выбора максимума, информационный выход которого подключен к информационному входу регистра, информационный вход которого подключен к информационному входу накапливающего узла сравнения, второй и третий выходы узла синхронизации подключены к входу признака записи регистра и входу опроса начальной вершины узла определения инцидентных ребер соответственно.

Фиг.2

1587533 K Bp

If@

22, и

202

20р

1587533

1587533 к t$i3 х, х

Х7 УД3 ХФ ЖВ М х»> > х х> у

4 15;3 Ху 1&,8 Хк

Х 8

«Х х>

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

Редактор Сь Патрушева Техред А.Кравчук Корректор Т.Палий

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

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

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

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