Вптб

О П И С А Н И Е 394793ИЗОБРЕТЕНИЯ союз Советских Социалистических РеспубликК АВТОРСКОМУ С ТЕЛЬСТВУ ависимо авт, свил ел в аявлецо 1,3.Х.1971 ( 77 8-24 1 хл. 6 061 15,/2 77,/18 хГе соедицсццсм заявк Гооударотвенныи комитеСовета Миниотрав СССРпо делам изобретенийи открытий 1 риоритет Опубликова 22,7111.197 теньУДК 681.333:66.01в 11.1973 ата опубликования описаци вторызобретеция Г. Додоиоь и В. Федото Институт электродинамик АИ Украинской ССР аявител ОГО ГРАФИН МОДЕЛЬ ВЕТВИ СЕТЕ Изобрстецие отцосится к области вычислильцой техники. Известны модели ветви сетевого графика, содержащие триггер, единичный выход которого соединен с первым входом первого элемента И и единичным входом второго триггера, нулевой выход которого соедицсц с псрвым входом второго элемента И, полк:1 очеццого вторым входом ко входу сигнала уцравлецця решением задачи о длиннейшем пути модели ветви, выход второго элемента И через первый элемент НЕ соедицец с выходом модели встви, который через второй элсмецт НЕ соединен со вторым входом первого элемецта И и первыми входами третьего и четвертого элементов И, выход цсргого элемента И соединен с выходом прццадлсжцости ветви длиццейшему пути модели ветви и через третий элсмецт НЕ полключсц ко входу модели ветви и первому входу пятого элемента И, второй вход которого подключен ко входу импульсов тактовой частоты модели ветви, второй вход третьего элемента И подключец к выходу счетчика импульсов, а второй вход четвертого элемсцта И подключен ко входу сдвинутых импульсов тактовой частоты модели ветви, выход четвертого элемента И соедицец с цуледым входом первого триггера,Все цзвсстцс модели ветви це позволяют решать задачу о минимальном потоке ц сети,В предложенной модели указаццый целостаток цсклочец,Модель гствц сетевого графика отличается от,извсстцых тем, ч го оца содержит четвертый элемент 1-1 Е, цолключсццый к выходу счетчика импульсов, цс.той элемент 1, молы которого подкло 1 иь ко вхол 1 и п,псоц тактовоц чатоты молслц ветви, виолу раз; .- шецця вычцташя цацмсцьшей по ллццс встпц модели ветви, выходу прццаллсжностц истиц длиннейшему пути модели ветви,ц и,холу ствертого элсмецта 11 Е, элемент 11,11 И, Включсцц 11 ц между Вь 1 одамц п 5 того ц цос го го элементов И ц входом счетчика импульсов, и седьмой элемент Н, полилочеццый вхоламц к вхолу шестого элсмсцта 11 ц выходу счетчика импульсов и сосдццсцццо выходом с выходом ццлцкациц цу,ел 1" Л,11- цы ветви модели ветви, причем ьчхол пятого элемента 11 соелццсц с треп им входом третьего элемсгга И,Блок-схема молелц встык приведена ца ч ртеже.Модель содержит счетчик цмпульсоц 1, триггеры 2 ц 3, элементы НЕ 4, 5 ц 6, эл- менты И 7 - 11, ц выход 12 молслц всгцц, выход 13 принадлежности ветви ллцццейш. му пути модели ветви, вход 14 цмпульсоц так 39479,3товой частоты модели ветви, вход 15 сдвинутых импульсов тактовой частоты модели ветви, вход 1 б сигнала управления решением задач,и о,длиннейшем пути модели ветви, вход 17 модели ветви, элементы И 18 и 19, элемент ИЛЛ 20, элемент НЕ 21, вход 22 разрешения вычитания наименьшей по длине ветви модели ветви и выход 23 индикации нулевой длины ветви модели ветви.Модели ветви сетевого графика соединяются между собой входами 17 и выходамц 2 в соответствии с топологией сети в устройство для решения задачи о минимальном потоке в сети.Устройство работает следующим образом.В счетчик, импульсов 1 модели ветви предварительно заносится число импульсов, дополцяющес цкокцюю границу пропускной способности ветви до полной емкости счетчика импульсов 1, триггеры 2 и 3 находятся первоначально в нулевом состоянии.Среди численных значений нижних границ пропускных способностей ветвей устройство отыскивает длиннейший путь, для чего ца вход 16 подастся разрешающий сигнал, если в некоторый момент времени ца входе 17 появится сигнал разрешения отсчета числа импульсов, равного пслу импульсов максимальной емкости счетчика импульсов 1, то этот сигнал откроет элемент И 11 и через элемент ИЛИ 20 в счетчик импульсов 1 начнут поступать импульсы тактовой серии через вход 14, При появлении ца выходе счетчика импульсов переполнения триггера 2 и 3 установятся в единичное состояние, Сигнал с единичного выхода триггера 2 поступает на один из входов элемента И 9.Сигнал с нулевого выхода триггера 3 поступает на один из входов элемента И 10, второй вход которой управляется входом 1 б, Сигнал с выхода элемента И 10 поступает на вход схемы совпадения, которая образуется соединением элементов НЕ б выходами 12, сходящихся в одном из узлов сети. При этом ца выходе 12 появится разрешающий потенциал только тогда, когда все триггеры 3 моделей ветвей, входящих в один узел, установятся в единичное состояние. Если же ца выходе 2 еще це появился разрешающий сигнал, то элемент НЕ 5 дает разрешающий сигнал на элементы И 7 и 8. На второй вход элемента И 8 поступают сдвинутые импульсы тактовой частоты, т. е. все установившиеся в единичное сосгояцие до появления на выходе 12 разрешающего потенциала, триггеры 2 будут установлены в нулевое состояние выходными сигналами элемента И 8,Те же триггеры 2, которые установились в единя 1 ное состояние с появлением сигнала ца выходе 12, останутся в единичном состоянии, так как будет снят разрешающий потенциал со входа элемента И 8.Таким образом, состояние триггеров 2 моделей ветвей будут ццдицировать дерево длинцейших путей с корнем в начальном узле сети. 5 10 15 20 25 30 35 40 45 50 55 60 65 4Для индикации формы длиннейшего пути заземляют конечный узел модели сети. На выходе 13 элемента И 9 появится сигнал, ицдццирующий принадлежность данной ветви длиннейшему пути. Этот сигнал через элемент НЕ 4 передается на следующий узел модели сети. По окончании переходного процесса единичные сигналы будут ца выхода.х 13 моделец ветвей, составляющих длинцейший путь.Затем из всех длин ветвей, принадлежащих длиннейшему пути, вычитают величину наименьшей по длине ветви. Величину паиме: ьшей по длине ветви запоминают. Для чего по входу 22 разрешения вычитания наименьшей цо;1 лцце ветви модели вети в счетчики импульсов 1 моделей ветвей через элемент И 18 и элемент ИЛИ,20, принадлеяац 1 их длццнейшему пути, будут поступать импульсы тактовой серии, т. к, у этих моделей ветвей ца одном из входов элемента И 18,имеется разрешающий потенциал.Поступление этих имптульсов прекратится после появления сигнала на выходе 23 ицдикации нулевой длины ветви модели ветви прц совпадении на элементе И 19 выходного сигнала элемента И 18 и импульса переполнения счетчика импульсов 1 наименьшей по величине длины модели ветви, принадлежащей длиннейшему пути.Одновременно число этих импульсов запо. минаегся в счетчике определения минималь. ного потока достаточно большей емкости (ца чертеже не показан).Таким образом, исходная сеть видоизменилась: наименьшая по величине ветвь длиннейшего пути становится в сети ветвью нулевой длины, а остальные ветви этого пути умень шаются на ее величину. Далее на полученной сети вновь определяют длиннейший путь. Про. исходит вычитание величины наименьшей ненулевой по длине ветви из остальных нового длицней 1 шего пути.Величину наименьшей по длине вегви нового длиннейшего пути складывают с предыду. щей аналогичной величиной и запоминают в счетчике определения минимального потока (на чертеже не показан),Процесс заканчивается, когда все ветви сети становятся ветвями нулевой длины. Сумма величин наименьших по длине ветвей длиннейших путей определит величину минимального потока.Если длиннейший путь включает ветвь нуле. вой длины, у которой счетчик импульсов 1 находится в нулевом состоянии, то сигнал пуска ее со входа модели ветви 17 через элемент И 11 и элемент И 7 установит в единичное состояние триггеры 2 и 3, т. е, сразу пройдет ца выход модели ветви 12.Для этого, чтобы запретить поступление им. пульсов в счетчики импульсовмоделей ветвей нулевой длины, принадлежащих длиннейшему пути, нулевой выход счетчика импульсов 1 через элемент НЕ 21 соединен с одним цз выходов элемента И 18,3947 ш Предмет изобретения Составитель Г, Сорокин Техред Т, КурилкоРедактор Э. Шибаева Корректор А. Васильева Заказ 3308/6 Изд.1828 Тираж 647 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретении и открытий Москва, Ж. Раушская наб., 4/5Типография, пр. Сапунова, 2 Модель ветви сетевого графика, содержагцая триггер, единичный выход которого соединен с первым входом первого элемента И и единичным входом второго триггера, нулевой выход которого соединен с первым входом второго элемента И, подключенного вторым входом ко входу сигнала управления решением задачи о длиннейшем пути модели ветви, выход второго элемента И через первый элемент НЕ соединен с выходом модели ветви, который через второй элемент НЕ соединен со вторым входом первого элемента И и первымн входами третьего и четвертого элементов И, выход первого элемента И соединен с выходом принадлежности ветви длиннейшему пути модели ветви и через третий элемент НЕ подключен ко входу модели ветви и первому входу пятого элемента И, второй вход которото подключен ко входу импульсов тактовой частоты модели ветви, второй вход третьего элемента Их подключен к выходу счетчика изгпульсов, а второй вход четвертого элемента 1 Л подклочен ко входу сдвинутых импульсов тактовой частоты модели ветви, выход четвертого элемента И соединен с нулевым входом перво го триггера, от.шпающаяся тем, что, с цельюрасширения круга решаемых задач, она содержит четвертый элемент НЕ, подключенный к выходу счетчика, импульсов, шестой элемент 11, входы которого подкгночены ко 10 входу импульсов тактовой частоты моделиветви, входу разрешения вычитания наименьшей по длине ветви модели ветви, выходу принадлежности ветви длиннейшсму пути модели ветви и выходу четвертого элемента 15 НЕ, элемент ИЛИ, включенный м.ждувыходамн пятого и шестого элементов 11. и входом счетчика импульсов, и седьмой элемент И, подключенньш входами к выходу шестого элемента И и выходу счетчика 41 м.20 пУльсов и соелиненного выхопом с ныхо Ггминдикации нулевой длины ветви модели 1 и гви, причем выход пятого элемента 1 соединен с третьим входом третьего элем ита И,