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

-24 присоединением заявки твеввыв ввмвтетСССРам взебрвтвейвтврмтюю 23) П тет публиковано 15.03. 79.Бюллетень 1Дата опубликования описания 19.03.7(73)Заявитель инской С ститут эл инамики 54) МОДЕЛЬ И ГРАФА Изобретение относится к области вычиспитеньной техники, в частности к эпектронным моделирующим устройствам и может быть испопьзовано при построении цифровых специапизированных машин дпя ревюния задач исследования операций,Известна модель ветви графа, содержащая эпементы И, блоки задания начальных и конечных адресов, элементы ИЛИ, инверторы, пинии задержки, блок автоматического формирования топологии гра- В фа, генератор импульсов 11.Недостатком этой модели является невозможность моделирования минимаксных и максиминных путей на графе.Наибопее близкой по технической сущности к данному изобретению является модепь,ветви графа, содержащая генератор импульсов, формирователь временного интервапа, выход которого йодключен к информационному входу первого эпемента И, выход которого соединен С"единичным входом. первого триггера, единичный выход которого подкпючен к первому входу второго элемента И, выход которого соединен ссоответствующим входом первого элемента ИЛИ, выход которого подключен ко входу первого инвертора и к первому входу третьего элементаИ, выход которого подкшочен к первомувходу второго элемента ИЛИ, выход которогс соединен с первыми входами бпоков задания начапьного и конечного адресов, выход блока задания конечногоадреса соединен с его входом и с первым входом четвертого элемента И, выход которого подключен к единичномувходу второго триггере, нулевой выходкоторого соединен со вторым входомвторого элемента И, со вторым входомпервого элемента И и с первым входомпятого элемента И, шестой эпемент И,первый вход которого соединен с единичным выходом "йервого триггера, второй вход шестого эпемента И подключенк выходу блока задания конечного адреса, выход шестого эпемента И соединенс соответствующим входом третьего эпемента ИЛИ, выход которого подключенк первому в-.оду четвертого элементаИЛИ, выход которого соединен с блокомуправления и со вторым входом четвертого элемента И, первый выход блока уп- уравнения подкщочен ко второму входучетвертого элемента ИЛИ, второй выходблока.управления соединен со вторымвходом второго элемента ИЛИ, первыйвыход генератора импульсов подкщочен 10ико второму входу третьего элемента И,второй выход генератора импульсов соединен с первым входом седьмого элемента И, второй вход которого подключенк выходу первого инвертора, выход седьмого элемента И соединен с первымвходом формирователя временного интервала, выход блока задания начального адреса подкпючен к третьему входупятого эпемента И, второй вход которого соединен со вторым входом четвертого элемента И 2.Белью изобретения явпяется расширение функциональных возможностей засчет.определения минимаксных и максиминных путей в графе,. Это достигается тем, чю в предлагаемое устройство введены восьмойэлемент И, второй инвертор и счетчик,вход которого подкщочен к выходу пято-, 36го эпемента И и к входу второго инвертора, выход счетчика соединен со вторым входом формирователя временногоинтервала, вйход второго инвертораподкщочен ко второму входу восьмого Иэпемента И, вьход которого соединен совторым входом бпока задания начального адреса, первый вход восьмого элемента И подкщочен к третьему входупятого элемента И,40На чертеже показана предлагаемаямодель.Она состоит из элементов И 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.;Работа модели ветви рассматривается на примере реализации следующей вход. ной функции ветвиХ= (а ч Ф) (счд 1 11) где Х - входная функция рассматриваемой 1 -й ветви, выходящей из 1 -го узна графа; Ц, 33, С, с 1 - выходные функции ветвей, входящих в 1 -ый узел графаПусть изображенная на чертеже модель, ветви 14 является моделью 1 -йветви графа, а дпя записи 1 -го узлав блоках задания начального и конечныхадресов отведены два разряда: ГП -ыйи Ф+ 1)-ый. Тогда до начала работыв блоки задания конечных адресов моделейО -й и Ь-й ветвей заносится по однойединице в В-й разряд, в блоки заданияконечных адресов моделей С -й и д -йветвей заносится по одной единице вФ+ 1)-.ый разряд, а в блок задания начального адреса модели 1 -й ветви заносится две единицы - в щ-ый и (1+1)-ыйразряд. В блок задания конечногоадреса модели 1 -ой ветви заноситсяединица в ррряд, соответствующий номеру узла, в который ьходит 1-я ветвь.В счетчик 8 заносится число Й -2, .гдеЙ-емкость счетчика. В формирователивременных интервалов всех ветвей заносятсядлины ветвей, а триггеры 1 1, 12 устанав-пиваются в нупевое состояние,Пусть, далее, длины ветвей таковы,что среди рассматриваемых ветвей первой оканчивается О-я ветвь, второйВ-я, третьеи - С-я и четвертой - б -я.Работа устройства рассматривается,начиная с момента окончания с 1-й ветви.Сигнал с выхода 28 модели с 1-йветви (на чертеже не показана) поступаетв блок автоматического формирования топологии 15 на один из входов 30 элемента ИЛИ 18, к остальным входам ко,торого присоединены одноименные выходы других моделей ветвей, как не изображенных на чертеже, так и 1-ой.,Пройдячерез эпемент ИЛИ 18, сигнал поступаетна вход инвертора 24, который вырабатывает запрет на одном из входов элемента И 22. Второй вход эпемента И 22соединен со входом 32 бпока автоматического формирования топопогии и дапеес выходом 39 генератора импульсов 17поэтому серия импульсов ГИ 1 больше не-"поступает на входы 25 всех моделейветвей. Одновременно с выхода элемен-та ИЛИ 18 на один из входов элемента)И 23 поступает разрешение, и черезэлемент И 23, второй вход которого соединен со.входом 33 и далее - с выходом40 генератора импульсов 17, серия импульсов ГИ 2 через элемент ИЛИ 20 поступает по выходу 37 на входы 26всех моделей ветвей.Имульсы серии ГИ 2 одновременносдвигают содержимое всех блоков задания адресов,Сигнал с выхода блока задания на чального адреса 9 поступает на первыйвход элемента И 2. Сигнал с выхода блока задания конечного адреса модели О-йветви поступает на выход 29 соответ20ствующей модели ветви, который соединен с одним из входов 31 элемента ИЛИ19, к остальным входам которого присоединены одноименные выходы всех моделей ветвей, и с выхода элемента ИЛИ2519, который соединен со входом элемен та ИЛИ 21, указанный сигнал поступаетна выход 38, и далее - на вход 27 рассматриваемой 1 -й модели ветви соеди 1ЗОненный со вторым входом элемента И 2,и на одноименные входы остальных ветвей, Так как третий вход элемента И 2соединен с нулевыМ выходом триггера11, находящегося в нулевом состоянии,35то сигнал с выхода блока задания на- .чального адреса 9 пройдет через элемент И 2 г. увеличит содержимое счетчика 8 на "1 ф. Выходной сигнал инвертора 7 запретит прохождение этого единичного сигнала через элемент И 6 в блокзадания начального адреса 9, Сигнал свыхода блока задания конечного адресамодели -й ветви поступает на первый,вход элемента И 3 соответствующей модели ветви; поскольку на входах 27 всехмоделей ветвей присутствуют разрешающие сигналы, то в моделях ветвей О и Ф(,т.е. в тех моделях, где на выходе блокавадания конечного адреса присутствуют ууединичные сигналы), выходной сигналэлемента И 3 установит в единичноесостояние триггер 11, выходной сигналкоторого запретит прохождение единичного сигнала с выхода триггера 12 . Ячерез элемент И 5 на выходе 28 длямодели с-й ветви), и запретит установкув единичное состояние триггера 12 отэлемента И 1 для модели Ф-ой ветви). Нулевой сигнал с выхода 28 через вход 30 блока автоматического форм рования топологии поступает на вход элемента ИЛИ 18 и на первый вход элемента И 23, чем запрещает поступление серии ГИ 2 на входы 26 всех моделей ветвей. Одновременно единичный сигнал с выхода инвертора 24 разрешает поступление импульсов серии ГИ 1 с выхода 39 генератора импульсов 17 через элемент И 22 на входы 25 всех моделей ветвей. В тех моделях ветвей где присутствуют разрешающие сигналы на входах формирователей временных интервалов, последние производят счет импульсов серии ГИ 1. Единичный сигнал на выходе формирователя временного интервала Ь-й ветви не установит триггер 12 этой ветви вединичное состояние, так как на втором входе схемы И 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 1-й ветви поступает разрешающий сигнал; на третьем входе этого же элемента, также присутствует разрешение с нулевого выхода триггера 11. Таким образом, сигнал с выхдЬа блока заданияначального адреса 9 через элемент И. 2 пройдет на вход счетчике 8; сигнал переполнения с выхода последнего поступает на вход формйроватепя временного интервапа 13, и поспений начинает отсчет им-.пупьсов сегчи ГИ 1, поступающих на первый вход формироватепя 13,Перезапись единицы в бпок задайия "начального адресе запрещается инвертором 7. После отсчета числа импульсов, серии ГИ 1, пропорционапьного дпине 1 -йветви, сигнап с выхода формироватепя13 устанавливает в единицу триггер 12;единичный сигнап через элемент И 5 поступает на выход 28 1-й модели ветви.Суммарное чиспо импупьсов серииГИ 1, отсчитанное измеритепьным счетчиком, входящим в состав бпока управпе "яия, от момента начапа б-й ветви до 1момента начала 1 -й ветви, пропорцио " нально произведещпо длин ветвей О и с,что соответствует реапизации функции ЦцрИ"указанных выше соотношениях междудпинами ветвей.Рассматриваемая модепь бпагодарявведению допопнитепьных бпоков позвопя-ет расширить функционапьные возмож-"Вности модели эа счет отыскания минимаксных и максиминных путей в графах.Форму а изобретенияМодень ветви графа, содержашая гене-.фратор импульсов, формироватепь временного интервапа, выход которого подкпючен к информационйому входу"первогоэлемента И, выход которого соединенс единичным входом первого триггера,3едйнйчйый выход которого подкпочеи к "первоь входу второго эпемента И, выходкоторого соединен с соответствующимвходом первого эпемента ИЛИ, выход коОторого подкпючен ко входу первого инвертора и к первому входу третьего.элемента И, выход которого подкпюченк первому входу второго эпемента ИЛИ,выходкоторого соединен с первыми вхо-.45дами блоков заданияначапьного и конечного адресов, выход бпока задания конеч-.ного адреСа соединен с его входом и с -первым входом четвертого эпемента И,"вьИод которого подключен к единичномувходу второго триггера, нупевой выходкоторого соединен со вторым входом второго эпемента И, со вторым входом первого эпемента И и с первым входом пятого элемента И, шестой эпемент Ипервый вход которого соединен с единичным выходом первого триггера, второйвход шестого эпемента И подкпючеи квыходу блока задания конечного адреса,выход шестого эпемента И соединен ссоответствующим входом третьего эпемента ИЛИ, выходкоторого подкпюченк первому входу четвертого эпементаИЛИ, выход которого соединен с блокомуправпения и со вторым входом четвертого элемента И, первый выход блокауправпения подкпючен ко второму входучетвертого элемента ИЛИ, второй выходблока управления соединен со вторым входом второго эпемента ИЛИ, первый выход генератора импупьсов подключенко второму входу третьего эпемента И,второй выход генератора импупьсов соединей с первым входом седьмого эпемента И, вход которого подкнючен квыходу первого инвертора, выход седьмого элемента И соединен с первым входом формироватепя временного интервапа,выход бпока задания начапьного адресаподкпючен к третьему входу пятого элемента Ивторой вход которого соединенсо вторым входом четвертого эпементаИ, отличающаяся тем,чго,с ценно расширения функционапьных возможностей за счет опредепения минимаксных ипи максиминных путей в графе,в устройство введены восьмой эпементИ, второй инвертор и счетчик, вход кото.рого подкпючен к выходу пятого эпемента И и к вхоЬу второго инвертора, выход счетчика соединен со вторым входомформчроватепявременного интервапа, выход второго инвертора подкпючен ковторому входу восьмого элемента И, вы-ход которого соединен со вторым входомбпока задания начапьного адреса, первый вход восьмого элемента И подкшбчен к-третьему входу пятого эпемента И,Источники информации, принятые во внимание при экспертизе 1, Авторское свидетельство СССР Мо 422002, кп, 6 06 6 7/48 1974. 2. Авторское свидетельство СССР М 470811 кп. б 06 Р 15/20, 1975.Составитель А. Колчинр Н, Каменская Техред С. Мигай Коррек э 1062/46 Тираж 779 ЦНИИПИ Гомударственного .ко по делам изобретений и от 11 Э 035, Москва, Ж, Рауш