ВПТБ Советский патент 1973 года по МПК G06F15/173 

Изобретение относится к области 1зычислительной техники.

Известны модели ветви сетевого графика, содержащие триггер, единичный выход которого соединен с первым входом первого элемента «И и единичным входом второго триггера, нулевой выход которого соединен с первым ВХОДОМ второго элемеита «И, подключенного вторым входом ко входу сигнала уиравления решением задачи о длиннейшем пути модел.н «етви, выход второго элемента «И через первый элемент «НЕ соединен с выходам модели ветви, который через второй элемент «МБ соединен со вторым входом первого элемента «И и первыми входами третьего « четвертого элементов «И, выход первого элемента «И соединен с выходом прннадлежности ветви длиННейшему путн модели ветви и через третий элемент «ИЕ подключей ко входу модели ветви и первому входу пятого элемента «И, второй в.ход которого подключен ко входу импульсов тактовой частоты моделей ветви, второй вход третьего элемеита «И подключен к выходу счетчнка импульсов, а второй вход четвертого элемента «И подключен ко входу сдв инутых импульсов тактовой частоты модели ветви, выход четвертого элемента «И соединен с нулевым входом первого триггера.

Все известные модели ветви не позволяют рен1ать задачу о минимальном потоке « сетн.

iB предложенно ; модели указанны недостаток исключен.

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

которого Подключены ко входу НМПуЛ1 С(1В

тактовой частоты модели ветвн, входу раз;0шення вычитания наименьшей но длине ветвп модели ветви, выходу принадлелСности ветлн длиннейшему пути модели ветин .и В1.|ходу чет.вертого элемента «НЕ, элемент «ИЛП, включенньи между выходами riMTOro .и .Hiecroго элементов «И и входом счетчика пмиульсов, и седьмой элемент «И, подключепньи входами К выходу HJecToro элемента «И и выходу счетчика импульсов ai соединенного

выходом с выходом ННДПКаЩЫ НуЛО.ОН ДЛ11ны ветви модели ветви, нрьчем пятого элемента «М соедннен с третьим входом третьего элемеита «И.

Блок-схема модели ветв.н приведена на чертеже.

Модель содержит счетчнк имнульсо /, триггеры 2 и 3, элементы «НЕ 4, 5 и 6, эл --менты «И 7-//, 11 выход 12 модели ветпн, выход 13 прннадлежности ветви дл 1ннеПн1му нути модели ветви, вход /4 импульсов тактойой частоты модели Ветви, вход 15 сдвиИутых импуьПьсов тактовой частоты модели , вход 16 сигнала управления решенном задач и о длиннейшем путн модели ветви, вход 17 модел.и ветви, элементы «И 18 и 19, элемент «ИЛИ 20, элемент «ИЕ 21, вход 22 разрешения вычитания наименьшей ио длине ветви модели ветви ,и выход 23 индикации нулевой длины ветВИ модели ветви.

Модели ветви сетевого графика соединяются между собой входам.и 17 и выходами 12 в соответствии с тонологией сети в устройство для решения задачи о МИНИмальном иотоке в сети.

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

В счетчик -имиульсов / модели ветви иредварительио заносится число «мпульсов, дополняюш;ее нижнюю .границу пропускной способности ветви до полной емкости счетчика имиульсов /, триггеры 2 к 3 иаходятся первоначальио в нулевом состоянии.

Среди численных значений нижних границ проиускиых снособностей ветвей устройство отыскивает длиннейший путь, для чего на вход 16 подается разрешающий сигнал, еслн в 1иекоторый момент времени на входе 17 появится сигнал разрешения отсчета числа импульсов, равного числу имнульсов «максимальной емкости счетчика импульсов /, то этот сигнал откроет элемент «И // и через элемент «ИЛИ 20 в счетчик импульсов / начнут поступать имиульсы тактовой серии через вход 14. При появлении па выходе счетчика импульсов переполнения триггера 2 к 3 установятся в единичное состояние. Сигнал с единичного выхода триггера 2 поступает на один из входов элемента «И 9.

Сигнал с нулевого выхода триггера 3 поступает на один из входов элемента «И 10, второй вход которой управляется входом 16. Сигнал с выхода элемента «И 10 поступает на вход схемы совпа,т,ения, которая образуется соедииен.ием элементов «НЕ 6 вь ходами 12, сходящихся в одном из узлов сети. При этом на выходе 12 появится разрешающий потенциал только тогда, когда все триггеры 3 моделей ветвей, ВХОДЯ1ЩИХ -в один узел, установятся в единичное состояние. Есл.и же па выходе 12 еще не появился разреЩающий сигнал, то элемент «ПЕ 5 дает разрещающий сигнал на элементы «И 7 и 8. Па второй вход элемента «И 8 поступают сдвинутые импульсы тактовой частоты, т. е. все установившиеся в един.ичное состояние до появления на выходе 12 разрешающего потенциала, триггеры 2 будут установлены в нулевое состояние выходиыми сигналами элемента «И 8.

Те же триггеры 2, которые установились в едииичное состояиис с появлением сигнала иа выходе 12, остаиутся в едии41411ом состоянии, так как будет снят разрешающий потен-циал со входа элемента «И 8.

Таким образом, состоя-ние триггеров 2 моделей ветвей будут индицировать дерево длиннейших путей с корнем в начальном узле сети.

Для индикации формы длиннейшего пути заземляют конечный узел модели сети. Па выходе 13 элемента «РЬ 9 появится сигнал, индицирующий принадлежность данной ветви длиннейшему пути. Этот сигиал через элеме1гг «ПЕ 4 передается на следующий узел модели сети. По окончании переходного иро;цесса единичные сигиалы будут на выходах 13 моделей ветвей, составляющих длиннейший путь.

Затем из всех длин ветвей, припадлежаи их длин:нейшему пути, вычитают величину наименьшей по длине ветв.и. Велич.ину наи.меньщей по длине ветви запоминают. Для чего по входу 22 разрешения вычитания наименьшей но длине ветви модели вети в счетчики импульсов / моделей ветвей через элемеит «И 18 и элемент «ИЛИ ,20, принадлежани1Х длиннейшему иути, будут иоступать импульсы тактовой серии, т. к. у этих моделей ветвей на одном нз входов элемента «И J8 имеется разрешающий Потенциал.

Поступление этих и.мпульсов прекратится после иоявления сигнала иа выходе 23 индикации нулевой длины ветви модели ветви при со:впадении на элементе «И 19 выходного сигнала эле.мента «И 18 и импульса переполнения счетчика импульсов У иаимепьшей ло величине длины модели ветви, нринадлежащей длиннейшему пути.

Одновременно число этих импульсов запоминается в счетчике определения .минимального потока достаточно .больщей емкости (на чертеже не показан).

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

Велич.ину .наименьшей по длине ветви нового длиннейшего пути складывают с предыду.щей аналогичной величиной и запоминают в счетчике определения минимального потока (на чертеже не показан).

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

Если длиннейший путь включает ветвь нулевой длины, у которой счетчик импульсов / находится в нулево.м состоянии, то сигнал пуска ее со входа модели :ветви /7 через элемент «И // и элемепт «И 7 установит в единичное состояние триггеры 2 н 3, т. е. сразу пройдет на выход модели ветви 12.

Для этого, чтобы заиретить поступление импульсов в очетчики импульсов 1 моделей ветвей нулевой длины, принадлежа.щих длиннейшему пути, нулевой выход счетчика импульсов / через элемент «ПЕ 21 соединен с одним из выходов элемента «И 18.

5 Предмет и з о б р е т е и и

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

3J)479,i

6

второй вход четвертого элемента «И подключен ко входу сдвинутых импульсов TaKTOiioii частоты модели ветви, выход четвертого элемента «II соединен с нулевым входом первого триггера, отличающаяся тем, что, с иелью расширения круга решаемых задач, она содержит четвертый элемент «НЕ, подключенный к выходу счетчика .импульсов, гнестой элемент «И, входы которого подключен1 1 ко входу импульсов тактовой частоты модели ветви, входу разрешения вычитания наименьшей по длине ветви модели ветви, выходу принадлежности ветви длиннейшему пути модели ветви и выходу четвертого элемента «НЕ, элемент «НЛИ, включенньп между выходами пятого и шестого элемепто) «И и входом счетчика 1мпульсов, и седьмой элемент «И, подключенный входами к выходу шестого элемента «И и выходу счетчика .импульсов и соединенного выходом с iu.ixnuм индикации нулевой длишз вет)И1 модели г,отви, причем выход пятого элемента «П соединен с третьим входом третьего элемента «И.