Модель ветви для определения экстремальных потоков в сетях

 

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

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

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

Структурная схема модели ветви изображена на чертеже.

Она содержит узлы 1, 2 регистрации величины потока, триггеры 3, 4, дополнительный триггер 5, элементы И 6 — 19, дополнительные элементы И 20 — 22, элементы ИЛИ

23, 24, выпрямители 25, 26, выходной выпрямитель 27, элементы НЕ 28, 29, счетчики 30, 31, полюса модели 32 — 46.

Модель ветви для определения экстремальных потоков в сетях работает следующим образом.

В начальный момент времени посредством полюсов 36 и 37 соседние модели ветвей соединяются между собой в соответствии с топологией исследуемой сети.

При решении задачи о минимальном потоке нижние границы пропускных способностей ветвей записываются в счетчики 31, а счетчики 30 находятся в нулевом состоянии. Триггеры 3 — 5 всех моделей ветвей устанавливаются в нулевое состояние (установочные шины на чертеже не показаны).

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

Устанавливаются в единичное состояние триггеры 3 всех моделей ветвей. Триггеры

4 и 5 остаются в нулевом состоянии. При наличии в сети ветвей с ненулевой нижней границей пропускной способности, о чем свидетельствует наличие сигнала хотя бы на одном из полюсов 45 моделей ветвей, производится просмотр всех ветвей сети в произвольно заданном порядке. Для этого подается сигнал на полюс 32, чем осуществляется выбор той или иной модели ветви.

Подачей импульса на полюса 34 всех моделей ветвей триггер 3 выбранной модели ветви устанавливается в нулевое состояние.

Нулевое состояние триггера 3 снимает разрешение с входа элемента И 8, чем производит блокировку входа модели ветви.

После этого проверяется наличие пути из

640302 торый будет разрешать прохождение импульсов с полюса 36 па полюс 37. Аналогично, при условии, что триггер 4 находится в единичном состоянии и в реверсивном счетчике 31 записан ненулевой избыток потока, сигнал, пришедший на полюс 37, передается на полюс 36.

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

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

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

Одновременно увеличиваются избытки потока в тех же ветвях в противоположном направлении. Это происходит следующим образом. На полюса 35 всех моделей ветвей подаются счетные импульсы. Предположим, что в рассматриваемой ветви остался в единичном состоянии триггер 3. Тогда сигнал с единичного выхода этого триггера выдаст разрешение на элементы И 9 и 16.

В это же время на элементы И 10 и 17 подан запрет, так как триггер 4 находится в нулевом состоянии. Таким образом, счетные импульсы, поступающие на полюс 35, будут проходить через элемент И 9 на вход счетчика 30, уменьшая тем самым записанный в нем избыток потока, и одновременно через элемент И 16 импульсы поступают на вход счетчика 31, увеличивая тем самым записанный в нем избыток потока.

Аналогично, если в единичном состоянии остался триггер 4, а не 3, при поступлении импульсов на полюс 35 увеличивается содержимое счетчика 30 и уменьшается содержимое счетчика 31.

Поступление импульсов на полюс 35 должно прекратиться как только записанное в одном из счетчиков 30 или 31 содержимое станет равным нулю. Если при этом в счет5

65 чике 30 записан нуль, то его сигнал, пройдя элемент И 12, появится на полюсе 42.

Аналогично, если в счетчике 31 записан пуль. то сго сигнал, пройдя элемент И 19, появится на полюсе 46.

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

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

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

Суммарное количество импульсов, поступивших при этом на полюсе 35, равно суммарной величине максимального потока.

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

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

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

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

Составитель И. Загорбинина

Техред А. Камышникова

Корректор Л. Корогод

Редактор Б. Герцен

Типография, пр. Сапунова. 2

Заказ 2223/7 Изд. № 782 Тираж 799 Подписное

НПО Государственного комитета СССР по делам изобретений и открытий

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