Вптб

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства ¹â€”

Заявлено 1,3.1Х.1971 (39 1696778/18-24) с присоединением заявки № 1696777/18-24

Приоритет

Опубликовано 22.И11.1973. Бюллетень № 34

Дата опубликования описания 12.XII.1973

М. Ел. 6 06f 15/20

Государственный комитет

Совета Миниатрав СССР па делам изобретений и открытий

УДК 681.313i3:66.012 (088.8) Авторы изобретения

А. Г. Додоноь и В. В. Федотов

Институт электродинамики AH Украинской ССР

Заявитель

МОДЕЛЬ ВЕТВИ СЕТЕВОГО ГРАФИ1(А

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

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

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

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

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

1 оторого подiiл10 Iсllы ко 13ход> 1141нулi>соli

10 тактовой ча топ! модели ветви. !гходу раз; .шення вычнташ>я IIAIIAIcIII>L! Ilo длине всп!н модели ветви, выходу принадлежности вс!ч!н длиннейшему пути модели ветви и I3l,Idol!, чс!вертого элемента «I IЕ», элемент «11Л11»», 15 вкл!очсн вы и меж LI> BI>lxoдам1! 115ITol o ll и!сс гого элементов «И» и входом счетчика импульсов, и седьмой элемент «li», подкл1оченный входамн к в!>!ходу шестого элсмснra "! i: выходу счетчика импульсов и «о динснн тг

20 выходом с выходом индикации нулев!!!! д,1;Hbl ветви модели ветви, причем выхо$ пятог!! элемента «11» соединен с треп им вхо <ом третьего a;ieilell ra «И».

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

Модель содержит счетчик импульсон 1, триггеры 2 н 3, элементы «НЕ» 4, б ц 6, эл менты «И» 7 — 11, н выход 12 модели всгвн, выход 13 принадлежности ветви дл11нпейш. му

30 пути модели ветви, вход 14 нмпульсон так, >9479,3 товой частоты модели ветви, вход 15 сдвинутых импульсов тактовой частоты модели всгви, вход 1б сигнала управления решением задачи о,длиннейшем пути модели ветви, 13ход

17 модели ветви, элементы «И» 18 и 19, элемент «ИЛ!Л» 20, элемент «НЕ» 21, вход 22 разрешения вычитания наименьшей по длине ветви модели ветви и выход 23 индикации нулевой длины ветви модели ветви.

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

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

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

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

Сигнал с нулевого выхода триггера 3 поступает на один из входов элемента «И» 10, второй вход которой управляется входом 1б. Сигнал с выхода элемента «И» 10 поступает на вход схемы совпадения, которая образуется соединением элементов «НЕ» б выходами 12, сходящихся в одном из узлов сети. При этом на выходе 12 появится разрешающий потенциал только тогда, когда все триггеры 3 моделей ветвей, входящих в один узел, установятся в единичное состояние. Если же на выходе

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

12 разрешающего потенциала, триггеры 2 будут установлены в нулевое состояние выходными сигналами элемента «И» 8.

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

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

4

Для индикации формы длиннейшего пути заземляют конечный узел модели сети. На выходе 18 элемента «И» 9 появится сигнал, ипдпцирующий принадлежность данной ветви длиннейшему пути. Этот сигнал через элендеиr

«НЕ» 4 передается на следующий узел моде 111 сети. По окончании переходного процесса единичные сигналы будут на выхода.х 13 моделей ветвей, составляющих длинней ший путь.

Затем из всех длани ветвей, принадлежащих длиннейшему пути, вычитают величину наименьшей по длине ветви. Beëè÷è11ó паиме: ьшей по длине ветви запоминают. Для чего по входу 22 разрешения вычитания наименьшей по;1лине ветви модели вети в счетчики импульсов 1 моделей ветвей через элемент «И»

18 и элемент «ИЛИ»,20, принадле>кащих длпнней шему пути, будут поступать импульсы тактовой серии, т. к. у этих моделей ветвей на одном из входов элемента «И» 18,имеется разрешающий потенциал.

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

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

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

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

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

«И» 11 и элемент «И» 7 установит в единичное состояние триггеры 2 и 3, т. е. сразу пройдет на выход модели ветви 12.

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

3947М

Предмет изобретения

Составитель Г. Сорокин

Техред T. Курилко

Редактор Э. Шибаева

Корректор А. Васильева

Заказ 3308/6 Изд. № 1828 Тираж 647 Подписное

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

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

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

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

«И» и первымн входами третьего и четвертого элементов «И», выход первого элемента

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

15 «НЕ», элемент «ИЛИ», включенный м жду выходами пятого и шестого элементов «! I . н входом счетчика импульсов, и седьмой элемент «И», подключенньш входами к выходу шестого элемента «И» и выходу счетчика,нм20 пульсов и соединенного выходом; ныхн 1с индикации нулевой длины ветви модели негви, причем выход пятого элемента «Il» соединен с третьим входом третьего элемента «И».