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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Со Св»

Соцнелнстмсесюа рвспубпин (6l) дополнительное к авт, свил-ву(22) Заявлено15.12.75 (2l) 2199 27/18-24 с присоединением заявки №(23) ПриоритетГа&УД&Р&т&е&&ай &&метет

СССР

&& ДИ&М &306P& flNl н Фткфмтм&

Опубликовано 15.03. 79.Бюллетень №1О

Дата опубликования описания 19.03.79

В. В.. Васильев, О. H. Голованова и А, Г. Иодонов изобретения

Институт электродинамики АН Украинской ССР (ЩЗаявитель

t (54) МОДЕЛЬ ВЕТВИ ГРАГРА

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

Известна модель ветви графа, содержащая эпементы И, блоки задания начапьных и конечных адресов, элементы ИЛИ, инверторы, пинии задержки, блок автоматического формирования топологии графа, генератор кмпупьсов (11.

Недостатком этой модели является невозможность моделирования минимаксных и максиминных путей на графе.

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

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

652566 мента ИЛИ, выход которого подключен к первому в-.оду четвертого элемента

ИЛИ, выход которого соединен с блоком управления и со вторым входом четвертого элемента И, первый выход блока уп- у равпения подкщочен ко второму входу . четвертого элемента ИЛИ, второй выход блока .управления соединен со вторым входом второго элемента ИЛИ, первый выход генератора импульсов подключен 10 и ко второму входу третьего элемента И, второй выход генератора импульсов соединен с первым входом седьмого элемента И, второй вход которого подключен к выходу первого инвертора, выход седь- !Ф мого эпемента И соединен с первым входом формирователя временного интервала, выход блока задания начального адреса подключен к третьему входу пятого эпемента И, второй вход кото- 20 рого соединен со вторым входом четвертого элемента И (2j.

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

На чертеже показана .предлагаемая модель.

Она состоит из элементов И 1-6, иивертора 7, счетчика 8, блока зада ния начального адреса 9, блока задания 4 . конечного адреса 10, триггеров 11, 12, формирователя временного интерваиа 13.

На чертеже также обозначены модель ветви 14, блок автоматического форми.рования топопогии 15, блок управления

16, генератор импульсов 17, элементы

ИЛИ 18-21, эпементи И 22, 23, инвертор 24, входы модели ветви 25-27, выходы модели ветви 28, 29, группы входов блока автоматического формиро55 вания топологии 30,31, входы блока автоматического формирования топологии 32-35, выходы бпока автоматического формирования топологии 36-38, выходы генератора импульсов 39, 40, вход блока управления 41, выходы блока управления 42,43. ;Работа модели ветви рассматривается на примере реализации следующей вход ной функции ветви

Х„= (а ч 5) (c d) (1) где Х вЂ” входная функция рассматриваемой

1 -й ветви, выходящей из 1 -го узна графа;

Ц, ф, C,, d - выходные функции ветвей, входящих в 1 -ый узел графа.Пусть изображенная на чертеже модель ветви 14 является моделью -й ветви графа, а дпя записи j -ro узла в блоках задания начального и конечных адресов отведены два разряда: m -ый и (Ф+ 1)-ый. Тогда до начала работы в блоки задания конечных адресов моделей

Q -й и b-й ветвей заносится по одной единице в tn-й разряд, в блоки задания конечных адресов моделей С -й и д -й ветвей заносится по одной единице в (nl+ 1)-.ый разряд, а в блок задания начального адреса модели 1 -й ветви заносится две единицы - в щ-ый и (ted+1)-ый разряд. В блок задания конечного адреса модели 1--ой ветви заносится единица в pagpsrg, соответствующий номеру узла, в который ьходит 1-я ветвь.

В счетчик 8 заносится число 4-2, где

Й-емкость счетчика. В формирователи временных интервалов всех ветвей заносятсядлины ветвей, а триггеры 1 1, 12 устанав- пиваются в нупевое состояние.

Пусть, далее, длины ветвей таковы, что среди рассматриваемых ветвей первой оканчивается O-я ветвь, второй

В-я, третьеи — С-я и четвертой — (3 -я.

Работа устройства рассматривается, начиная с момента окончания 0-й ветви.

Сигнал с выхода 28 модели ol-й ветви (на чертеже не показана) поступает в блок автоматического формирования топологии 15 на один из входов 30 элемента ИЛИ 18, к остальным входам ко.торого присоединены одноименные выходы других моделей ветвей, как не изображенных на чертеже, так и j-ой.,Пройдя через элемент ИЛИ 18, сигнал поступает на вход инвертора 24, который вырабатывает запрет на одном из входов элемента И 22. Второй вход элемента И 22 соединен со входом 32 бпока автоматического формирования топопогии и далее

652566 с выходом 39 генератора импульсов 17 поэтому серия импульсов ГИ1 больше не -" поступает на входы 25 всех моделей ветвей. Одновременно с выхода элемен- та ИЛИ 18 на один из входов элемента/

И 23 поступает разрешение, и через элемент И 23, второй вход которого соединен со.входом 33 и далее — с выходом

40 генератора импульсов 17, серия импульсов ГИ2 через элемент ИЛИ 20 поступает по выходу 37 на входы 26 всех моделей ветвей.

Имульсы серии ГИ2 одновременно сдвигают содержимое всех блоков задания адресов.

Сигнал с выхода блока задания начального адреса 9 поступает на первый вход элемента И 2. Сигнал с выхода блока задания конечного адреса модели О-й ветви поступает на выход 29 соответ

20 ствующей модели ветви, который соединен с одним из входов 31 элемента ИЛИ

19, к остальным входам которого присоединены одноименные выходы всех моделей ветвей, и с выхода элемента ИЛИ

19, который соединен со входом элемен-та ИЛИ 21 указанный сигнал поступает на выход 38, и далее — на вход 27 рассматриваемой j -й модели ветви соеди1

30 ненный со вторым входом элемента И 2, и на одноименные входы остальных вет вей. Так как третий вход элемента И 2 соединен с нулевыМ выходом триггера

11, находящегося в нулевом состоянии, 35 то сигнал с выхода блока задания на- . чального адреса 9 пройдет через элемент И 2 и. увеличит содержимое счетчика 8 на "1". Выходной сигнал инвертора 7 запретит прохождение этого единичного сигнала через элемент И 6 в блок задания начального адреса 9. Сигнал с выхода блока задания конечного адреса модели ф-й ветви поступает на первый, вход элемента И 3 соответствующей модели ветви; поскольку на входах 27 всех моделей ветвей присутствуют разрешающие сигналы, то в моделях ветвей Q и ц (т.е. в тех моделях, где на выходе блока вадания конечного адреса присутствуют уу единичные сигналы), выходной сигнал элемента И 3 установит в единичное состояние триггер 11, выходной сигнал которого запретит прохождение единичного сигнала с выхода триггера 12 . M через элемент И 5 на выходе 28 (для модели 0-й ветви), и запретит установку в единичное состояние триггера 12 от элемента И 1 (для модели Q- ok ветви).

Нулевой сигнал с выхода 28 через вход 30 блока автоматического форм.

Рования топологии поступает на вход элемента ИЛИ 18 и на первый вход элемента И 23, чем запрещает поступление серии ГИ2 на входы 26 всех моделей ветвей. Одновременно единичный сигнал с выхода инвертора 24 разрешает поступление импульсов серии ГИ1 с выхода 39 генератора импульсов 17 через элемент И 22 на входы 25 всех моделей ветвей. В тех моделях ветвей,, где присутствуют разрешающие сигналы на входах формирователей временных интервалов, последние производят счет импульсов серии ГИ1.

Единичный сигнал на выходе формирователя временного интервала 5-й вет-! ви не установит триггер 1 2 этой ветви в ! единичное состояние, так как на втором входе схемы И 1 Ь-й ветви присутствует запрещающий сигнал с выхода триггера 11 той же ветви. Поэтому импульсы серии ГИ1 по-прежнему постулают с выхода 36 на входы 25 всех моделей ветвей. Триггер 11 с-й ветви находится в нулевом состояни и, поэтому выходной сигнал формирователя временного интервала этой ветви через элемент

И 1 установит триггер 12 в единичное состояние; этот единичный сигнал пройде г на выход 28 и далее — на рдин из входов 30 блока автоматического формирования топологии. Последний прекратит подачу импульсов серии ГИ1 на входы 25 всех моделей и начнет подачу им- . пульсов серии ГИ2 на входы 26.

Сигнал с выхода блока задания конечного адреса с-й ветви через элемент И

4 пройдет на выходы 29 этой же ветви, а оттуда — на один из входов 31 элемента ИЛИ 19 и через элемент ИЛИ 21— на вход 27 всех моделей ветвей. Со входа 27 с-й ветви этот сигнал через, элемент И 3 устанавливает в единицу триггер 11. Следовательно, на второй вход элемента И 2 модели 14 i -й ветви поступает разрешающий сигнал; на третьем входе этого же элемента,также присутствует разрешение с нулевого выхода триггера 11. Таким образом, сигнал с выхода блока задания начального адреса 9 через элемент И 2 пройдет с на вход счетчике 8; сигнал переполнения с выхода последнего поступает на вход формйроватепя временного интерва652566 па 13, и поспений начинает отсчет им-. пупьсов сегчи ГИ1, поступающих на первый вход формироватепя 13.

Перезапись единицы в бпок задайия начального адрес запрещается инверто- 5 ром 7. После отсчета числа импульсов, серии ГИ1, пропорционапьного дпине -й ветви, сигнап с выхода формироватепя

1 З устанавп ивает в единицу триггер 1 2; единичный сигнап через элемент И 5 по- 16 ступает на выход 28 -й модели ветви .

Суммарное чиспо импупьсов серии

ГИ1, отсчитанное измеритепьным счет« чиком, входящим в состав бпока управпе"яия, от момента начапа cf-й ветви до 35 момента начала i -й ветви, пропорцио- йально произведению длин ветвей О и с, что соответствует реапизации функции (Ц "" црИ указанных выше соотношениях между дпинами ветвей.

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

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

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

"йербоьф входу второго эпемента И, выход которого соединен с соответствующим входом первого эпемента ИЛИ, выход которого подкпючен ко входу первого ин4Î вертора и к первому входу третьего. элемента И, выхбд которого подкпючен к первому входу второго эпемента ИЛИ, выход которого соединен с первыми вхо-. дами блоков задания начального и конеч45 ного адресов, выход бпока задания конечного адреСа соединен с его входом и с первым входом четвертого эпемента И, - вьИод которого подключен к единичному входу второго триггера, нупевой выход которого соединен со вторым входом второго эпемента И, со вторым входом первоro эпемента И и с первым входом пятого элемента И, шестой эпемент И, первый вход которого соединен с единичным выходом первого триггера, второй вход шестого эпемента И подкпючеи к выходу блока задания конечного адреса, выход шестого эпемента И соединен с соответствующим входом третьего эпемента ИЛИ, выход которого подкпючен к первому входу четвертого эпемента

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

И, о т л и ч а ю ш а я c ÿ тем, чго, с ценно расширения функционапьных возможностей з@ счет опредепения минимаксных ипи максиминных путей в графе, в устройство введены восьмой эпемент

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

1, Авторское свидетельство СССР

И 422002, кп. 5 06 5 7/48, 1974.

2. Авторское свидетельство СССР

М 470811, кп. G 06 Р 15/20, 1875., 652566

Составитель А. Колчин

Редактор Н, Каменская Техред С. Мигай Корректор Л. Небола

Заказ 1062/46 Тираж 779 Подписное

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

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

Филиал ППП Патент», г. Ужгород, уп. Проектная, 4