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

19 158753зов К.С позиции исходной моделируемойсети (фиг,7 а) разрезу К принадлежат,ребра: (Б х,), (Ях), (хх),(хх) э (х 7 с )(хх 7)В результате дальнейшей работы устройства в разрезе Кнайдено реброс максимальной пропускной способностью по первичному потоку (Б с ) и(Бх 8), их пропускная способностьЧ = ",3 (фиг,7 б). Это соответствует ребрам исходной сети (фиг,7 а) (х х ), (х х ) и (х 7 С ).Очередной импульс переполнения счетчика 61, поступивший на плюс 100,появится на полюсе 101, так как он проходит по закороченным ветвям сполюса 88 на полюс 89, Этот импульс устанавливает триггер 85 в единичное 20состояние, Это свидетельствует о том,что все ребрапропускная способность по первичному потоку которых удовлетворяет заданному условию, найдены, и устройство переходит к выполнению шагов второго этапа работы,Ребра исходной сети, пропускнаяспособность по первичному потоку которых удовлетворяет условию, показаны на фиг7 в,В дальнейшем устройство работает только с этими ветвями,так как в моделях, соответствующихэтим ребрам, триггеры 53 и 54 одновременно находятся в единичном состоянии. На фиг,7 в не показаны ребра,которые не удовлетворяют условию.Единичное состояние триггера 85выдает разрешение на элементы И 70,71, 73 и полюса 91 всех моделей 28.В результате в каждой модели 28 снятсразрешение с входа элемента И 43 ивыдано разрешение на вход элементаИ 44, Кроме того, единичное состо яние триггера 85 разрешает прохождение импульсов генератора 86 черезэлемент И 70 на вход счетчика 624и через элемент ИЛИ 76 на вход счетчика 61 и полюса 90 всех моделей 28,В моделях 28 с полюса 90 импульсычерез элемент И 44 поступают на входсчетчика 58 до их переполнения, Реб.ра, соответствующие этим моделям,показаны на фиг.7 в..В каждой такой модели 28 импульспереполнения счетчика 58 через элемент И 41 не поступает на единичныйвход триггера 55 и не устанавливаетего в единичное состояние, Это возможно только для тех моделей 28,про 3 20пускная способность по вторичномупотоку которых меньше или равна Ь(хх ), (х.х ), (х х ) и (х с) фиг,7 в,В моделях 28, которые соответствуют ребрам (фиг,7 в) (Б х ), (хр ),(х х ) и (х с) сети, триггер 55 устанавливается в единичное состояние.Это происходит потому, что импульспоявится раньше, чем импульсы переполнения счетчика 58 этих моделей 28.В результате импульс переполнениясчетчика 62 поступает на полюса 92всех моделей 28 и устанавливает триггер 56 в единичное состояние, Единичное. состояние триггера 56 вьщаетразрешение на вход элемента И 41,что позволяет проходить импульсу переполнения счетчика 58 на единичныйвход триггера 55,Единичное состояние триггера 55разрывает цепи прохождения сигналас полюса 88 на полюс 89 в таких моделях 28, что исключает их из дальнейшего процесса решения задачи, Такими ребрами для примера будут (Б х ),(хнах ), (хх ) и (хС) . Их пропускная способность по вторичному потоку больше Ь, = 8 (фиг.7 в),Очередной импульс переполнениясчетчика 61 не сможет пройти по ребрам, которые показаны на фиг,7 в, таккак в моделях 28 (Б х ), (хзх),(хх ) и (х С) заблокированы входыэлементов И 30-37.В результате на полюсе 101 этотимпульс не появится. При этом по импульсу счетчика 61 генератор 86импульсов выдает импульс, которыйсдвинут относительно входного, навход элемента И 71, который пройдетчерез этот элемент, так как триггер84 остается в нулевом состоянии. Этотимпульс устанавливает триггер 85 внулевое состояние и поступает на полюса 93 всех моделей 28, где он устанавливает триггеры 5 1-55 в нулевоесостояние. Это приводит к тому,чтоустройство снова переходит к выполнению операций.перзого и второго этапов. При этом из моделирумой сетиисключаются модели 28, которые неудовлетворяют условию, В таких моделяхтриггеры 55 находятся в единичном состоянии. Для нашего примера такимимоделями 28 будут модели 28, которыесоответствуют ветвям (Б х ), (хх),После этого блок 29 управления выдает импульсы на полюс 101 и далее на полюса 89 моделей 28, Распространяясь, импульсы этой серии проходят от вершины С к вершине Б, при этом триггер 52 установлен в единичное состояние, если они проходят с полю.са 89 на полюс 88 через элемент И 31 и одновременно поступают на единичный вход триггера 52, На фиг.7 а это распространение показано сплошной стрелкой. 50 55 2115875(х х ). Новая сеть показана на фиг.7 гДальнейшая работа устройства с этойсетью (фиг,7 г) на первом этапе даетмножество ребер, показанное на фиг,7 д,После выполнения устройством вто 5рого этапа получено множество ребер,которое показано на фиг,7 е, При этомв процессе выполнения второго этапаимпульс переполнения счетчика 61, поступивший на полюс 100, проходит черезмодели 28 с полюса 88 на полюс 89 ипоявляется на полюсе 101, Ребрами,по которым пройдет этот импульс, будут (Б х ), (х х ), (х хр), (хгху)э 15(х-, ).В результате устройство переходитк выполнению третьего этапа, т,е,к выделению ребер искомого пути иего индикации, 20Процесс выделения ребер пути заключается в подаче импульсов в модели 28, связанных с полюсом 100, триггеры 53 которых находятся в одиничном состоянииЭти импульсы от генератора 86 поступают на полюс 88 модели 28, Такой моделью будет модель28, соответствующая ребру (Б х,)фиг,7 е.Импульс с полюса 88 в модели28 (Б х,) поступает через элементы 30И 35, ИЛИ 45 на единичный вход триггера 51. Первый импульс из всей серииустанавливает триггер 5 1 в единичноесостояние, что дает возможность остальным импульсам с полюса 88 черезэлемент И 33 проходить на полюс 89,Далее они поступают с полюса 89модели 28 (Я х,) на полюса моделей(х х ) и (х,х ),Таким образом, распространяясь 40по сети от модели 28 к модели 28(фиг,7 е), они появятся на полюсе 101блока 29 управления, т,е, в вершинеНа фиг,7 а это распространениеимпульсов показано пунктирной стрелкой от Я к с. 3322На фиг,7 е показно, что в результате действия обеих серий импульсов триггеры 51 и 52 моделей 28, которые соответствуют ребрам (Я х ), (х,х ),ф(хх), (хх ) и .(х С),уст навливаются в единичное состояние, В моделях 28 (хх), (хх) и (хх) только триггеры 51 устанавливаются в единичное состояние, а триггеры 52 остаются в нулевом.Триггеры 5 1 и 52, находящиеся одновременно в единичном состоянии,определяют ребра пути, который оптимизирует два взаимосвязанных потока, Этот путь на фиг.7 е показан жирной линией . Он индицируется элементами 60 индикации этих моделей 28Формула изобретения1. Устройство для анализа парамет ров сетей, содержащее блок сравнения, блок задания матрицы инцидентности, блок определения концевых вершин ребер, блок определения маршрута и блок синхронизации, вход пуска которого является входом пуска устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи оптимизации двух взаимосвязанных потоков между заданной парой вершин, в него введен блок выбора ребер с оптимальной пропускной способностью, причем первый выход блока синхронизации подключен к тактовому входу блока выбора ребер с оптимальной пропускной способностью, вход задания веса К - го ребра которого (К = 1 Р, где Р - количество ребер в графе ) является входом задания веса К-го ребра по первичному потоку устройства, вход задания веса К-го ребра по вторичному потоку которого подключен к К-му информационному входу. группы блока сравнения, вход задания критического веса по вторичному потоку устройства подключен к информационному входу блока сравнения, выход признака "Не меньше К-го информационного направления которого подключен к входу удаления К-го ребра блока задания матрицы инцидентности, выход признака инцидентности К-го ребра М-й вер.шине сети которого (М = 1 В, где В - количество вершин в сети) подключен к одноименным входам блока23158753 определения концевых вершин ребер блока определения маршрута и блока выбора ребер с оптимальной пропускной способностью, выход признака при, надлежности К-го ребра множеству оптимальных которого подключен к входу опроса К-го ребра блока определения концевых вершин ребер и к в входу разрешения включения К-го ребра в дерево10 допустимых маршрутов, второй вход блока синхронизации подключен к входу опроса блока определения концевых вершин ребер, выход признака принад- лежности конечной вершины сети масси ву концевых которого подключен к входу останова блока синхронизации и к входу опроса конечной вершины бло" ка определения маршрута, выход признака принадлежности К-й вершины маршруту которого является одноименным входом устройства.2. Устройство по п.1. о т л и - ч а ю щ е е с я тем, что блок выбора ребер с оптимальной пропускной способностью содержит узел стягивания ребер, узел определения инцидентных ребер, узел выбора максимума, накапливающий узел сравнения, регистр и узел синхронизации, причем вход на чальной установки блока подключен к входу установки в "О" накапливающего .узла сравнения, вход задания веса К-гсребра блока подключен к К-му ин 24 формационному входу группы накапливающего узла сравнения и к К-му вхо"ду узла выбора максимума, тактовыйвход блока подключен к входу пускаузла синхронизации, первый выходкоторого подключен к тактовому входунакапливающего узла сравнения, выходпризнака "Не меньше" К-го информационного направления которого подключенк входу признака стягивания К-го ребра узла стягивания ребер, вход признака инцидентности К-го ребра М-йвершине блока подключен к одноименному входу узла стягивания ребер, выход признака инцидентности К-го ребра М-й вершине которого подключен кодноименному входу узла определенияинцидентных ребер, выход признакапринадлежности К-го ребра массивуинцидентных которого подключен к входу подключения К-го информационногонаправления узла выбора максимума,информационный выход которого подключен к информационному входу регистра, информационный вход которого подключен к информационному входунакапливающего узла сравнения, второй и третий выходы узла синхронизации подключены к входу признака записи регистра и входу опроса начальной вершины узла определения инцидентных ребер соответственно..Пал 2 рытиям.при ГКНТ СССР 4/5 итета ква твенно-издательский комбинат "Патент" г. Ужгород, ул. Гагарина, 10 роизв ЗакВНИИПИ Государственного к113035, Мо Подписноепо изобретениям и от1587533 при Ь (Ь,1) рует последовательность сигналов уровня единицы на выходах 11, 12, предусмотренную временной диаграммой его работы. При этом на выходах13 устройства Формируется множество ребер в пути между начальной и коФ Изобретение относится к вычислительной технике и может быть использовано для исследования потоков в 15сетях.Цель изобретения - расширениефункциональных возможностей устройства за счет решения задачи оптимизации двух взаимосвязанных потоков3между заданной парой вершин сети."Н а фиг. 1 представлена функциональная схема устройства; на фиг,2 - временная диаграмма работы блока синхронизации; на Фиг,3 - функциональная 25схема блока выбора ребер с оптимальной пропускной способностью;на Фиг,4 -временная диаграмма работы его узласинхронизации; на фиг,5 - пример модульной реализации устройства; наФиг,6 - блок управления; на фиг7иллюстративный пример решения задачи оптимизации двух взаимосвязанныхпотоковУстройство содержит (фиг. 1) блок1 сравнения, блок 2 задания матри 35цы инцидентности, блок 3 определения концевых вершин ребер, блок 4определения. маршрута, блок 5 выбораребер с оптимальной пропускной спо"собностью, блок 6 синхронизации, входы7 задания веса ребер по первичномупотоку устройства, входы 8 заданиявеса ребер по вторичному потоку устройства, вход 9 задания критического веса по вторичному потоку устройства, вход 10 пуска устройства, выходы 11 и 12 блока 6 синхронизации,выходы 13 признаков принадлежностидуг маршруту устройства,50Блок 5 выбора ребер с оптимальной пропускной способностью содержит узел 14 стягивания ребер, узел15 определения иницидентных ребер,узел 16 выбора максимума, накапливающий узел 17 сравнения, регистр 18,55узел 19 синхронизации, тактовыйВход 20 блока 5, входы 21 заданияВеса ребер, входы 22 признаков иннечной вершинами сети, у которогопропускная способность по первичномупотоку максимальна, а пропускнаяспособность по вторичному потоку небольше максимально допустимой величины, 1 з.п, ф-лы, 7 ил,цидентности ребер вершинам сети блока 5, вход 23 начальной установки блока 5, с первого по третий выходы 24-26 узла 19 синхронизации и выходы 27 признаков принадлежности ребер множеству оптимальных.Устройство работает следующим образом,Задача оптимизации двух взаимосвязанных потоков, является задачей определения пути между заданной парой вершин сети, у которого пропускная способность П по первичному потоку удовлетворяет условию пути с наибольшей пропускной способностью, а пропускная способность по вторичному потоку не превосходит или, в крайнем случае, равна максимальной допустимой величине. Пропускная способность такого пути удовлетворяет условию шп 1 шах (ц), Ь ) где Ь, - величина вторичного потока по ребру (х;,х);Ь - заданная максимальйаядопустимая величина вторичного потока для каждогоребра сети;- величина первичного пото 3,ка по ребру (х;, х );- любой (Б-г) разрез в мноФжестве сети;8 и с - соответственно начальнаяи конечная вершины сети,Перед началом работы в блок 2 задания матрицы инцидентности заносятинформацию о топологии сети. На входы 7 и 8 устройства подают информациюо весе (пропускной способности) ребер по первичному и вторичному потоку соответственно. На вход 9 подают информацию о максимально допустимой (критической) величине вторич7533 6 5 10 15 20 25 30 35 40 45 50 55 5 158ного 1. с 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, и накапливает (по ИЗИ) результаты сравнения ("не меньше") для каждого инФормационного направления. При этомузел -14 стягивает все ребра, вес которых превосходит значение, записанное в регистре 18. Через время, достаточное для окончания операции.сравнения, узел 19 снимает сигналуровня логической единицы с выхода24При поступлении на вход 20 очередного тактового импульса работаблока 5 повторяется.Устройство может быть выполненов виде моделей 28 ребер (фиг,5) иблока 29 управления (фиг,6),Модель 28 ребра содержит элементы И 30-44, элементы ИЛИ 45-50, триггеры 51-56, счетчики 57 и 58, элемент НЕ 59 и элемент 60 индикации,Блок 29 управления содержит счетчики 61 и 62, элементы И 63-74, элементы ИЛИ 75-78, элемент НЕ 79,триггеры 80-85, генератор 86 импульсов,элемент ИЛИ 87Устройство имеет полюса 88-101, среди которых 88 и 89у моделей 28 ребер служат для коммутации их между собой, согласно конфигурации моделируемой сети. Полюса90-99 в моделях 28 ребер служат дляподключения к блоку управления, чтообеспечивает их синхронную работу,Полюсами 100 и 101 блок 29 управления подключается соответственно к полюсам 88 и 89 тех моделей ребер,между которыми отыскивается оптимальный путь.Задание исходных данных задачиоптимизации двух взаимосвязанных потоков осуществляется с помощью коммутации моделей 28 ребер посредст 158753320 50 Перед началом работы устройства триггеры 51-56 всех моделей 28 и55 триггеры 80-85 и счетчик 61 блока 29 управления устанавливаются в нулевое состояние, Цепи установки н занесения исходных данных не показаны.вом полюсов 88 и 89 между собой всоответствии с конфигурацией моделируемой сети, подключением полюсом 100и 101 блока 29 управления к полюсамтех моделей 28 ребер, между которы 5ми отыскивается путь, занесения (Ю -я") (М - Ь; ) и (М - Ъ) числаимпульсов соответственно в счетчики57, 68 моделей 28 ребер и счетчик62 блока 29 управления,где М - емкость счетчиковПроцесс нахождения пути можнопредставить в виде трех этапов.Первый этап содержит циклическиповторяющиеся шаги: нахождение разре"за (х , х ) из множества разрезов К;1 Эвыделение ребра разреза (х;, х ) сшах Ч выбор ребер, у которйх величина первичных потоков больше илиравна величине первичного потока,выбранного ребра разреза.Второй итретий шаги первого этапа выполняются устройством одновременно, Выполнение третьего шага состоит в закорачивании полюсов 88 и 89 моделей 28,что приводит к исключению их из дальнейшего рассмотрения на этом этапе,Второй этап заключается в проверке выполнения ограничений на вели чину вторичного потока Ь; для каждого ребра, выбранного на первом этапе, с заданной максимальной допустимой вепичиной Ь, В результате проверки может оказаться, что ребра удовлетворяют или не удовлетворяют ограничению. В этом случае эти ребраисключаются из процесса решения задачи, Исключение ребер представляет собой блокирование в модели 28 цепи прохождения сигнала от полюса 88к полюсу 89, и наоборот, Кроме того, на этом этапе одновременно производится проверка наличия пути междузаданными вершинами, проходящего по 45ребрам. Если такого пути нет, устрой 3ство переходит к выполнению операций первого этапа, при наличиипути - к выполнению третьего этапа.Третий этап заключается в выделении ребер этого пути и его индикации,Работа устройства начинается с момента установки триггера 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 управления. Единичное состояние триггеров 5 1 ияи 52 свидетельствует о том, что данная модель 28 принадлежит выбранному разрезу (х, х 1) из множества разрезов К. Это соответствует первому шагу первого этапа решения задачи.Выбор ветви разреза (х х;) с щах с, и выбор ребер сети, величи 1на первичных потоков через которые больше или равна величине потока выбранного ребра разреза, что соответствует выполнению второго и третьего шагов первого этапа, происходит следующим образом, Разрешениес выхода многовходового элементаИЛИ 87 поступает на вход элементаНЕ 79 и одновременно, через элементИ 65 на единичный вход триггера 8 1,В результате элемент НЕ 79 сниметразрешение с полюса 94 блока 29 управления и, следовательно, с полюсов. 94 всех моделей 28, что блокируетвход элемента И 39 в каждой модели 28,Разрешение, поступившее на единичный вход триггера 81, устанавливает его в единичное состояние, чтозапретит прохождение импульсов генератора 86 на полюс 100 блока 29 управления и разрешит прохождение импульсов на вход счетчика 61 и полюс 90. Единичное состояние триггера 81 свидетельствует о том, чтоустройство начинает выполнять второй и третий шаги первого этапа.В моделях 28 импульсы с полюса 90поступают через элемент И 43 на 25вход счетчика 57 до его переполнения.Импульс переполнения счетчика 57модели 28 поступает на единичныйвход триггера 53 и одновременно через 30элемент ИЛИ 43 на нулевые входы триггеров 51 и 52. В результате триггеры 51 и 52 установятся в нулевоесостояние, если ранее они были установлены в единичное состояние импульсами, поступившими на полюса 88 и89 моделей 28,Триггер 53, установленный в единичное состояние поступившим на еговход импульсом переполнения счетчика 57, установится в нулевое состояние очередным импульсом, которыйпоступит на полюс 90. Это происходитпотому, что триггер 54 находится внулевом состоянии и он выдает разрешение на вход элемента И 39. В результате очередной импульс, который поступает на полюс 90, пройдетчерез элементы И 39 и ИЛИ 48 на нулевой вход триггера 53,50В результате установки триггеров51 и 52 в модели 28 происходит снятие разрешения с полюса 95 и, следовательно, с соответствующего входамноговходового элемента ИЛИ 87, Втот момент, когда будет снято последнее разрешение с полюса 95 многовходового элемента ИЛИ 87, блок 29управления выдаст разрешение на по 1587533 Олюс 94 моделей 28, При этом в модели 28 выбранного разреза с наибольшей пропускной способностью по первичному потоку триггер 54 установится в единичное состояние. Единичноесостояние триггера 54 запретит установку триггера 53 в нулевое состояние очередным импульсом, которыйпоступит на полюс 90 модели 28. Этопроисходит потому, что на нулевомвыходе триггера 54 будет снято разрещение, которое заблокирует элементИ 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 управления. Он начинает свойсчет с 0 и его емкость равна И, асчетчики 57 моделей 28 начинают счетс (И - с; ),Импульс пе ре полнения сче тчика 61блока 29 управления поступает черезэлемент ИЛИ 75 на полюс 00. Крометого, импульс переполнения счетчика 61 поступает на вход генератора 86, который по этому импульсу выдает на вход элемента И 71 импульс,ко"торый сдвинут относительно входного,Через элемент И 71 этот импульс непройдет, так как нет разрешения сединичного выхода триггера 85.Далее этот импульс с полюса 100блока 29 управления поступает на полюс 88 или 89 тех моделей 28, которые в результате коммутации этими полюсами между собой образуют вершину сети, из которой отыскиваетсяпть, и весь процесс выполнения шагов первого этапа повторяется аналогично описанному. Итерационное выполнение шагов первого этапа повторяется до тех пор, пока очереднойимпульс переполнения счетчика б 1блока 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 импульс пройдет, таккак есть разрешение с нулевого выхода 10 15 20 25 30 35 40 45 50 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, у которых выполняется условие Ь;Ьсчетчики 58 переполнятся раньше илиодновременно со счетчиком 62 блока29 управления, В этих моделях 28 импульс переполнения сетчика 58 непройдет через элемент И 41, так кактриггер 56 находится в нулевом состоянии. Следовательно, триггер 55 утаких моделей 28 останется в нулевомсостоянии, а триггеры 53 и 54 - вединичном,В моделях 28, у которых не выполняется условие Ь; ( Ь счетчики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 управления начинает соответственно свой счет с (И - Ь) и (И - Ъ ),оС выхода элемента ИЛИ 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 находятся в единичном состоянии,а остальные триггеры - в нулевом.В случае появления импульса на.полюсе 10 1 устройство переходит к выполнению третьего этапа, т.е, к выделению ребер искомого пути и его индикации, Это происходит следующим образом, С полюса 101 импульсы в блоке 29управления через элементы И 73 и ИЛИ78 поступают на единичный вход триггеров 82, 84 и устанавливают их в еди 41 ничное состояние, Единичное состояниетриггера 82 снимает разрешение с полюсов 99 и выдает разрешение на полюса 98 всех моделей 28,В моделях 28 разрешение с полюса45 98 поступает через элемент ИЛИ 49на нулевой вход триггера 54 и уста -навливает его в нулевое состояние.Нулевое состояние триггера 54 разрывает закоротку полюсов 88 и 89.Одновременно с этим импульсы генератора 86 начинают опять поступать наполюс 100. Это происходит потому,чтоединичное состояние триггера 84 блока 29 управления выдает сигнал черезэлемент И 72 на нулевой вход триггера 85, По этому сигналу триггер 85устанавливается в нулевое состояние,чем обеспечивает прохождение импульсов генератора 86 через элемент И 64.16 дит только у тех моделей 28, у которых триггер 53 находится в единичномсостоянии. Таким образом импульсы 5распространяются по сети через модели 28 с полюса 89 на полюс. 88 дотех пор, пока не появятся на полюсе 100 блока 29 управления.С полюса 100 блока 29 управленияимпульсы поступят через элемент И 63,так как на другом входе этого элемента есть разрешение с единичного выхода триггера 83, на нулевой входтриггера 80, Первый из этих импульсов установит триггер 80 в нулевоесостояние. Нулевое состояние триггера 80 сигнализирует о конце решения задачи, При этом модели 28, укоторых триггеры 51 и 52 находятся 2 О одновременно в единичном состоянии,принадлежат искомому пути, Эти модели индицируются элементом 60 индикации.Для пояснения работы устройства 25 рассмотрим пример решения задачиоптимизации двух взаимосвязанных потоков в сети; первичный поток удовлетворяет условию пути с наибольшейпропускной способностью, а вторич ный поток не превосходит максимальной допустимой величины (фнг,7),На фиг,7 а цифрами обозначены пропускные способности соответственнопо первичному и вторичному потокам ребер: (Бх 1), (Бх , (Бх), (х,х),(х 7 х ), (х , г) . Первая цифра указыщо вает на величину пропускной способности по первичному потоку по соответствующему ребру, а вторая цифра указывает на величину пропускной способности по вторичному потоку по тому же 45 ребру. Вершины, которые формируютсяв результате коммутации моделей 28между собой полюсами 88 и 89 согласноконфигурации сети, на фиг,7 а обозначены Б х; х ххх р х х 5 О х, с. Кроме того, вершины Б и й обозначают вершины, между которыми отыскивается путь, оптимизирующий взаимосвязанные потоки, и к которым соответственно подключены полюса 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. Таким образом,импульсы распространяются по сетичерез модели 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 8импульсов для всех ветвей сети, Будем 28 полюса 95 многовходового элемента ИЛИ 87Работа устройства начинается с мо Очередной импульс, поступившиймента установки триггера 80 в единиц- на полюс 90 модели 28 (Б х ), устаное состояние Ея ие. Единичное состояние новит триггер 53 в этой модели 285Утриггера 80 разрешает прохождение щ- в нулевое состояние,пульсов генератора 86 через элементы Аналогичный процесс произойдетИ 64 И 67 и щи 75Уи ЮЫ 75 на полюс 100 и с моделью 28, которая соответстблока 29 управления. С полюса 100 нм вует ребру (Б х,) сети.1 Опульсы поступят на полюса 88 моделейПри появлении импульса перепол 28 ккоторые соответствуют ребрам нения счетчика 57 в модели 28, ко(Я х ), (Б х) и (Б хз) моделируе- торая соответствует ребру сетимой сети (фиг.7 а). В этих моделях им- (Б х ) ее триггеры 53 и 54 устанавпульсы пройдут через элементы И 34 15 ливаются в единичное состояние,и ИЛИ 45 на единичный вход триггера Единичное состояние триггера 54 за 511. По первому импульсу триггер 51 коротит полюса 88 и 89 этой моделиустановится в единичное состояние. 28, Одновременно с этим на полюсеОстальные импульсы подтверждают это 95 этой модели 28 снимается сигналсостояние. Единичное состояние триг О и, следовательно, с соответствующегогера 51 моделей 28 (Б х,), (Б х ) и этой модели полюса 95 многовходово(Б х( э) свидетельствует о том, что эти го элемента ИЛИ 87 тоже снимаетсямодели принадлежат первому разрезу сигнал. В результате на выходе мноК (на фиг.7 а разрез обозначен пун- говходового элемента ИЛИ 87 исчектирной линией) из множества разре зает сигнал, что приводит к появлезов, что соответствует первому шагу . нию сигнала на полюсе 94 всех модепервого этапа работы устройства. лей 28,В результате эти модели на свой Появление сигнала на полюсе 94полюс 95 выдадут сигнап, который по- всех моделей 28 разрешает прохождеступит на соответствующий этой мо О ние сигналам через элемент И 40 вдели вход 95 многовходового элемен- этих моделях 28 на единичный входта ИЛИ 87. На выходе многовходового триггера 54.элемента ИЛИ 87 появляется сигнал,ко- Таким образом, в моделях ветвей,торый поступает. на вход элемента которые соответствуют ветвям (хх),НЕ 79 и И 65В ез ль(хх), (хх), (хх),(х. ) ирезультате на полюсе 94 всех мо- (хс), триггеры 53 и 54 также устаделей 28 сн тя о разрешение, что бло- навливаются в единичное состояние.кирует элемент И 40, Пропускная способность по первич- .Сигнал, поступивший на вход ному потоку в этих ребрах равнаэлемента И 65,проходит на единичный О нли больше пропускной способности,вход триггера 81 и устанавливает его ребра (Б хь) разреза Кт.е чФв единичное состояние. Это состояние = 14. В этих моделях 28 полюсы 88 итриггера 81 свидетельствует о том, 89, аналогично модели 28 (Б х ), бучто устройство начинает выполнять дут закорочены Дз корочены, Другими словами сеть,вторую и третью операцию первого эта- - показанная на фи 745 а иг. а, прео разуетсябпа, и разрешает поступать импульсам в сеть, показанную на фиг.7 б, Нагенератора 86 на вход счетчика 61 фиг,7 б Б обозначены совмещенные ви на полюс 90. При этом через эле- результате закорачивания полюсов 88мент И 67 импульсы не проходят (сле- и 89 модели 28 вершины Б, х , х идовательно, они не проходят на по О х вершиной с - хр Флюс 100), так как нет разрешенияна нулевом выходе триггера 81. поступит на полюса 92 моделей 28 к%Из всего числя моделей 28,принад- которым в новой сети окажется подклюлежащих разрезу К первым перепол- чен полюс 100, Такими ребрами будутниФся счетчик 57 модели 28 (Б х). 5 (Б й ) и (Б х ), Импульс, поступившийТриггер 53 этой модели 28 установит- на полюс 88 этих ребер, установит ихся в единичное состояние, я триг- триггера 51 в единичное состояние.гер 51 - в нулевое, что снимет сиг- Это свидетельствует о построении нонал с соответствующего этой модели вого разреза К и.из множества разре