Модель ветви графа

 

4708Ill

ОПИСАНИЕ

ИЗОБРЕТЕН ЙЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Совэ Советских

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

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 04.06.73 (21) 1925527/18-24 с присоединением заявки № (51) М. Кл. G 06f 15/20

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

Опубликовано 15.05.75. Бюллетень № 18

Дата опубликования описания 21.08.75 (53) УД К 681.326 (088.8) (72) Авторы изобретения

А. Г. Додонов и В. В. Хаджинов

Институт электродинамики АН Украинской ССР (71) Заявитель (54) МОДЕЛЬ ВЕТВИ ГРАФА

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

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

Известна модель ветви графа, содержащая триггер, формирователь временного интервала, счетчики начального и конечного адреса и элементы «И». Один вход первого элемента

«И» соединен с выходом формирователя временного интервала, первый вход которого соединен с выходом второго элемента «И», первый вход которого соединен с выходом счетчика начального адреса. Выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов «И». Второй вход третьего элемента «И» соединен со вторым входом второго элемента «И», третий вход которого соединен с выходом триггера, а выход счетчика начального адреса соединен со входом модели.

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

Цель изобретения — сокращение оборудования.

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

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

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

Модель ветви графа содержит элементы «И»

1 — 5, счетчик начального адреса 6, счетчик конечного адреса 7, триггеры 8 и 9, формирователь временного интервала 10, модель ветви

11, блок автоматического формирования топологии 12, блок управления 13, генератор импульсов 14, элементы «ИЛИ» 15 — 18, элементы «И» 19 и 20, инвертор 21, входы 22 — 24 модели ветви, выходы 25 и 26 модели ветви, группы входов 27 и 28 блока автоматического формирования топологии 12, входы 29 — 32 блока автоматического формирования топологии, выходы 33 — 35 блока автоматического формирования топологии, выходы 36 и 37 генератора импульсов 14, вход 38 и выходы 39 и 40 блока управления 13.

470811

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

Генератор импульсов 14 вырабатывает на своих выходах 36 и 37 импульсы ГИ и ГИ2, сдвинутые относительно друг друга.

Г1редварительно в счетчики начального и конечного адресов 6 и 7 заносятся соответственно адреса начального и конечного узлов моделируемой ветви графа.

В формирователь временного интервала !О заносится длительность ветви, а триггеры 8 и

9 устанавливаются в нулевое состояние.

Для запуска модели ветви 11 блок автоматического формирования топологии 12 подает на вход 23 модели ветви 11 импульсы серии

ГИ2 до тех пор, пока на выходе счетчика начального адреса б не появится сигнал. В этот момент блок управления 13 прекращает подачу импульсов серии ГИ2 из блока автоматического формирования топологии 12 на вход 23 и одновременно с импульсом ГИ2 подает на вход 22 модели ветви 11 через элемент «ИЛИ»

18 пусковой импульс из блока автоматического формирования топологии 12. Пусковой импульс со входа 22 поступает на второй вход элемента «И» 2. Сигнал с выхода триггера 9 поступает на третий вход элемента «и» 2. Если модель ветви 11 принадлежит ветви, исходящей из начального узла, сигнал с выхода счетчика начального адреса 6 поступает на первый вход элемента «И» 2. Выходной сигнал элемента «И» 2 разрешает для формирователя временного интервала 10 счет импульсов серии ГИ, поступающий по входу 24 из блока автоматического формирования топологии 12. Отсчитав, число импульсов, пропорциональное длительности данной ветви, формирователь временного интервала 10 выдает сигнал, который поступает на первый вход элемента «И» 1. При наличии на втором входе элемента «И» 1 разрешающего сигнала с выхода григгера 9, сигнал с выхода этого элемента устанавливает в единичное состояние триггер 8. Сигнал с единичного выхода триггера 8 поступает на первый вход элемента «И»

5 и при наличии разрешающего сигнала на втором входе элемента «И» 5 с выхода триггера 9, сигнал с выхода элемента «И» 5 по выходу 25 поступает в блок автоматического формирования топологии 12 на один из входов группы входов 27 элемента «ИЛИ» 15, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже. Пройдя через элемент «ИЛИ» 15, сигнал поступает на вход инвертора 21, который вырабатывает запрет на одном из входов элемента «И» 20. Второй вход элемента «И» 20 соединен со входом 31 и далее с выходом 36 генератора импульсов

14, поэтому серия импульсов ГИ больше не поступает на вход 24 модели ветви 11. Одновременно с выхода элемента «ИЛИ» 15 на один из входов элемента «И» 19 поступает разрешение, и через элемент «И» 19, второй вход которого соединен со входом 32 и далее — с выходом 37 генератора импульсов 14, 5

1О

4 серия импульсов ГИ2, пройдя элемент «ИЛИ» .о, поступает по выходу 34 на вход 23 модели вегви 11.

Серию импульсов 1 И2 начинают считать одновременно счетчики начального и конечного адресов 6 и 7. Сигнал переполнения с выхода счетчика конечного адреса 7 поступает на входы элсментов «И» 3 и 4. Если данная ветвь закончилась, то на втором входе элемента «И»

4 имеется разрешающий сигнал с единичного триггера 8, и сигнал переполнения счетчика конечного адреса 7, пройдя через элемент «И»

4, поступит по выходу 26 в блок автоматического формирования топологии 12 на один из входов гругшы входов 28 элемента «ИЛИ» 17, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже, Выходной сигнал элемента «ИЛИ» 17 блока автоматического формирования топологии 12, пройдя через элемент «ИЛИ» 18, поступает через вход 22 модели ветви 11 на входы элементов «И» 2 и

3. Одновременное появление сигнала на входе

22 и выходе счетчика конечного адреса 7 свидетельствует о том, что данная ветвь закончилась ранее других ветвей, входящих в узел, адрес которого записан в счетчике конечного адреса 7, Так как счетчики начального и конечного адресов 6 и 7 считают импульсы одновременно, то на выходе счетчика начального адреса б модели ветви 11 и других моделей ветвей, исходящих из рассматриваемого узла, будут разрешающие потенциалы. В модели ветви 11 этот потенциал поступает на вход элемента «И» 1. И если на входе 22 имеется в этот момент разрешающий потенциал, то выходной сигнал элемента «И» 1 модели ветви

11, других моделей ветвей, исходящих из рассматриваемого узла, подготавливает формирователь временного интервала 10 для отсчета импульсов, поступающих на вход 24.

Сигналы с выхода счетчика конечного адреса 7 поступают на вход элемента «И» 3 при наличии разрешения на входе 22. Во всех моделях ветвей, входящих в узел графа, выходной сигнал элемента «И» 3 устанавливает в единичное состояние триггер 9, и выходной сигнал триггера 9 запрещает прохождение сигнала с единичного выхода триггера 8 через э емент «И» 5 на соответствующий выход 25 и запрещает установку в единичное состояние триггера 8 с выхода элемента «И» 1, если в модели ветви 11, входящей в данный узел, счет импульсов закончился позже.

Импульсы серии ГИ2 поступают на вход 23 модели ветви 11 до тех пор, пока на любом из входов группы входов 27 блока автоматического формирования топологии 12 присутствует сигнал. Таким образом, в случае одновременного окончания работы блоков-моделей ветвей, входящих в разные узлы графа, каждый из них опрашивается. После того, как опрашиваются все модели ветвей, в которых закончено формирование временного интервала, схема «ИЛИ» 15 блока автоматического фор4?0811

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

)ра

Зб к (:остлзитсси ..к Кггил.;гостил

Те.:род Г. Подуругиин":, 1>сдаитор . (цлиоаа

1,орреи. О 1 И. А . е

Заказ 1986/10 Изд. Ла 1449 Тир1: и 979 Поппи: иос

Ц11ИИГ1И Гссгдаис:::иг: го оз. тстл С.. стл . .:.: сг,с:. CC по делам изсбрете1иш и открь|тиГ.

Москва, )K-35, Раушсиап иао., д. 4, 5

Типографии, п .. Сапу,о и, " мирования топологии 12 запрещает подачу импульсов ГИ на входы 23 и разрешает поступление импульсов ГИ) на входы 24.

При появлении сигнала на входе 22, фиксирующего окончание какой-либо ветви, входящей в конечный узел графа, блок управления

13 прекращаст работу.

Суммарное количество импульсов, поступившее по входу 24 начала счета, равно величине кратчайшего пути. Единичный выход триггера 8 модели ветви 11 индуцирует принадлехкность ветви дереву кратчайших путе)1.

Модель ветви графа, содержащая триггер, формирователь временного интервала, счетчи<и начального и конечного адресов и элементы «И», причем один вход первого элемента

«И» соединен с выходом формирователя 13рсм енного интервала, первый вход которого соединен с выходом второго элемента «И», гсрвый вход которого соединен с выход;:. с.етчи— ка начального адреса, выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов «И», второй вход третьего элемента «И» соединен со вто5 рым входом второго элемента «И», третий вход которого соединен с выходом триггера, а вход счетчика начального адреса соединен со входом модели, отл и ч а ю щ ая ся тем, что, с цель)о сокращения оборудования, она

10 содеркит второй триггер, вход которого соединен с выходом первого элемента «И», второй вход которого и первый вход пятого элемента «И» соединены с выходом первого триггера, второй вход пятого элемента «И» соеди15 нен с выходом второго триггера и со вторым входо.,: четвертого элемента «И», вторые входы формирователя временного интервала и третьего элемента «И» соединены с соответствующими входами модели ветви, выходы

20 которой соединены с выходами четвертого и пятого элемен-.ов «И», а вход счетчика конечного адреса соединен со входом счетчика на-;а,";.ного адреса.