Устройство для исследования путей в графе

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 91 11 С 06 Г ИСАНИЕ ИЗОБРЕТЕНИЯТОРСКОМУ СВИДЕТЕЛЬСТВУ ство СССР/20, 1982,ЕДОВАНИЯ ПУ я к выч быть исполь- параметров ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) УСТРОЙСТВО ДЛЯ ИССЛТЕЙ В ГРАФЕ(5) Изобретение относитлительной технике, можетзовано при исследовании сетевых графов беэ циклов и петельи позволяет определить все независимые по вершинам максимальные пути вграфеС этой целью при помощи наддиагональной матрицы моделей дуг(матрицы связности графа) группы регистров, в которых записаны веса вершин графа, блока выделения максимального кода и сумматора находят первыймаксимальный путь в графе, Затем изнаддиагональной матрицы моделей дугисключают дуги, соответствующие первому максимальному пути, и цикл работы усФройства повторяют, 1 ил,Иэобретсзние отцссгся к л, Гзсзительцой технике и может быть использовацо при исследовании пдрдметровсетевых графов без циклоз и летел.Иезь изобретения - расширениефуцкциоцдльных возможностей устройства за счет опредевеция всех еэдвисимых по вершинам максимальных путейв графе.Ид чертеже представлена функциональная схема устройства,В сОсгав устр 011 ствд 13 хОД 1 т цдддиагоцдльцая матрица 1 моделей Дуз, );дждый узел которой содержит триггер 2и элемент ИЛИ-И 3, группу .элементов15ИГИ Гз) группу элементов 5 зд,)ер;к.ки,гр);Г;" ре) и.Тров б, тр; гру:Ги 6 "оГон 7-. )лсзмсцтв И, 6:к 10 зыбГ)6 г);) З ОМ.Г Д ГуСК 011 3 с;.)1111 Г 1 Ге ССТяц 110устгзз)Г)здс)т три герь , сотнетст)зу )э)е с;ицд)Г) 11 ".3 чДс) с)1 Кс)стиграфа, л )0 истры б:3;знсс)ят 3 сз Зершиц грд.)д) с)бцуеньэт григгерь 20, В 3511 схГГ 10 м ,О Гожсц 1111 11/1 фОР 1 д 1110 цые13 ходь) кс)мм"1 сто)01) 21 1 сэдс:11)э 10)ц кПСЭЦ Г,)ГфЮДЦИОЦЦ Е ЗЬХОКС)1 Е 110 ГД)1 И 1 УС 1 О 301 О СИГ Д 31)Г 1Гг,л) с 1 гецерзтора 22 3 остудот цд ге)такт н)й Езгход р)ц цреелггеля 3, который цосчерс)дцо вь цдет импульсы цдс)зон Гервы 11) второй и т,д. ыходы.Иц)ульс с его первого Глходд н;)ходит.) гцд первый вепход ,и-)- с) кз)ьз)утеэторд ")-)21 и дс 31 ее цд сход ,Г) - Гч) .Гэ г 0)1 ецд5 зддержки, цд второй вха (п-)-гоблока 8 и ц д трсэ т 1 й 13)ход соо) ез Г тстлуюзцеголемецтд ИПИ-И. Ото 6 ус двЛцгздвт ПОСтунЛЕНИЕ ЛЕСд (ГГ-)-1 ВЕршиць; с 3 ХОГ)д (т)-го регистр бчерез Г,п-)-Г блок 8 и блок ИПИ 2ца вход перого слагаемэго суммдторд14 и поступление веса ш-й лер.нныс выхода ш-го регистра 6 через соответствуюпий блок 9 на ход блока 10,посколку л Г,11-1)-й строке ьо)езей;туг .дтрицы 1 лишь трггерндходитсл л едззичцом состоянии, и едининый сгнал с его выхода проходит цд вторэ вход блока 9 и открывает его дзи прохождецги веса Гп-й вершины цд вход блока 10, который выдает цд Гзиход чсла обратный код веса этой нершши. 3)ямой код ее веса с выхода элементв ИЕ группы 11 поступает навход второго слагаемого сумматораГопрьй выдает код числа, равного сумме ле:ов п-й и ,ш-,1)-й вершин,через открыгый к этому времени (тп)-й блок 7 цд информационный вход,ш-)-го регистра 6, который запоминает лес: мдксимального пути из),п)- Г л п-ю вершину графа,Ио и .рс постуцлеци импульсов нао )с)рг дГе гьходь распределителя 23у. ГГ)г)йС Г 0 рдбОтдЕт;ШдЛОГИЧцО, Исигцдлсм с зыхода первого элемента 5э;д рж,и, поступающим ца управляющиез)Гзь коммутаторов 21, они подключаютсвои ицфрмдциоццые входы к своимвторим информационным зехсгдам, Расг;р де:штоль 23 устанавливается в исходное состояние. В регистрах б послепервого этапа работы устройства залсдцы елчины максималышлх путей вкоцечцую вершину графа из каждой изостальных его вершин.Пд втором этапе импульс с первогоппходд рдсг)еделителя 23 проходит через цтрой Гц ход (п) -1 о коммутатора 21 нд вторые входы элементовИ:И-И 3 первои строки матрицы 1, вре:зу.и,тате чего единичные сигналы сльг:одоп триггероз 2, цдходящихся вГ:ии)шом сос гояции, открывают соотГзетстцующе б)локи 9, через которые)ели Гши мдксимдльцых путей тех вер.:иГц) Г.Гзяздшгх с первой вершиной,1 астуцдют цд соответствующие входыблока 10. Оц выбирает наибольший изесо 3 н выдает единичный сигнал натт г)ЫХОД ПРИЗНаКа МаКСИМаЛЬНОГО кодл, соответствующий входу, нд который подан 3 аксимальцый код. В это же время )Гмпульс с второго выхода (ш- -.1)-г комм:,татора 21 через элемент ГЛИ 13 и злемецт 15 задерэкки постуцдет цд вторые входы элементов И 16, что обеспечшзает перЕход в единичное состояние соответствующего максимальному коду триггера 20. Если на нескольких выходах блока 10 появляются единичные сигналы, то через элемент И 16 с меньппзм порядковым номером он проходит, а через остальные не про 3 1323ходит благодаря подаче нулевых потенциалов с выходов, соответствующихэлементов НЕ 19,Импульс с второго выхода распределителя 23 проходит на второй выход(щ)-го коммутатора 21 и далее навторой вход второго элемента И 17,Если второй триггер 20 переключаетсяв единичное состояние, с выхода второго элемента И 17 импульс поступает Она вторые входы элементов ИЛИ-И 3 второй строки матрицы 1, Единичные сигналы с выходов тех триггеров 2, которые в данной строке матрицы 1 находятся в единичном состоянии, так 15же поступают на входы блока 10, в результате чего после прохождения импульса с (щ)-го выхода распределителя 23 и останова устройства в единичном состоянии оказываются те триггеры 20 через соответствующие номерам которых вершины проходят максимальный путь иэ первой начальной вконечную тп-ю вершину графа,Для нахождения второго (по длине) 25максимального пути независимо повершинам от первого найденного пути подают единичный сигнал на вход исключения дуг устройства, при этом обнуляются регистры 6 (кроме щ-го) и 30 открываются элементы И 18, вследствие чего единичный сигнал с выходов тех триггеров 20, которые соответствуют вершинам первого максгпчального пути и находятся в единичном состоянии, поступает на входы установки в "0", триггеров 2 одноименных строк матрицы 1 и устанавливают их в "0", Этим из топологии графа исключаются дуги, исходящие из вершин первого 40 максимального пути. Далее в регистры 6 заносят веса вершин графа, обнуляют триггеры 20 и распределитель 23, а коммутаторы 21 возвращают в исходное состояние. После этого вновь за пускают устройство, по окончании работы которого единичные состояния триггеров 20 укажут вершины, через которые проходит искомый второй максимальный путь. По схеме графа проверяют полноту найденного второго пути (так как при отсутствии второго пути независимо по вершинам от первого пути найденные с помощью триггеров 20 вершины могут оказаться не связанными с конечной вершиной). Формула изобретенияУстройство для исследования путей в графе, содержащее группу элементов 07 4101 И, группу элементов задержки, три группы блоков элементов И, две группы элементов И, группу триггеров, группу регистров, блок выбора максималь - ного кода, сумматор, блок элементов ИЛИ. генератор тактовых импу.тьсов и наддиагональную матрицу моделей дуг из (щ - 1) строк и (щ) столбцов, где тп - число вершин в графе, каждый узел которой содержит элемент ИЛИ-И и триггер, выход которого подключен к первому входу элемента ИЛИ-И того же узла наддиагональной матрицы моделей дуг, вход пуска генератора тактовых импульсов является входом пуска устройства, вьгхоч 1 с-го элемента эадержки группы (1 с=1 щ) подключен к информационному входу 1-го регистра группы, выход которого подключен к первому входу блока элементсв И второй группы и первому вхо. ду (Е)-го (1 г) блока элементов И третьей группы, выход щ-го регистра группы подключен к первому входу (щ)-го блока элементов И третьей группы, выходы блоков элементов И второй группы подключены к соответствующим входам блока элементов ИЛИ, выход которого подключен к входу пер.вого слагаемого сумматора, выход которого подключен к вторым входам всех блоков элементов И первой группы, выходы блоков элементов И третьей группы подключены к соответствующим входам блока вгпбора максимального кода, 1-й выход признака максимального кода которого подключен к первому входу 1-го элемента И первойгруппы, выход которого подключен к информационному входу 1-го триггера группы, выход которого подключен к первому входу 1-го элемента И второй группы, выход которого подключен к вторым входам всех элементов ИЛИ-И (1 с+1)-й строки (1 спт) наддиагональной матрицы моделей дуг, выходы всех элементов ИЛИ-И (1+1)-го столбца (1 сгщ) наддиагональной матрицы мс - делей дуг подключены к соответствующим входам 1 с-го элемента ИЛИ группы, вьгход которого подключен к второму входу (1+1)-го блока (1 щ) элементов И третьей группы, выход .лемента ИЛИ-И первого столбца наддиагональной матрицы моделей дуг подключен к второму входу первого блока элементов И третьей группы, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройст 5 13223 ва за счет определения всех независимых по вершинам максимальных путей в графе, в него введены распределитель импульсов, группа коммутаторов, группа элементов НЕ, третья группа элемен тов И, элемент задержки и элемент ИЛИ, причем выход генератора тактовых импульсов подключен к тактовому входу распределителя импульсов, К-й выход которого подключен к информационному 10 входу (щ)-го коммутатора группы, первый выход которого подключен к входу К-го элемента задержки группы, третьим входам всех элементов ИЛИ-И 1-й строки наддиагональной матрицы 15 моделей дуг и второму входу Е-го блока элементов И второй группы, первые выходы всех элементов И третьей группы подключены к входам установки в "О" с первого по (щ)-й регистров 2 О группы и входу признака исключения дуг устройства, выход 1-го триггера группы подключен к второму входу к-го элемента И третьей группы, выход которого подключен к входам установки 25 в "О" всех триггеров (1+1)-строки (1 щ), наддиагональной матрицы моделей дуг, выход первого элемента задержки группы подключен к входу на 076чальной усгановки распределителя импульсов и управляющим входам коммутаторов группы, второй выход Е-гокоммутатора группы (Ещ) подключенк второму входу (щ)-го элемента Йвторой группы и к-му входу элементаИЛИ, выход которого подключен квходу элемента задержки, выход которого подключен к вторым входам всехэлементов И первой группы, выход первого коммутатора группы подключенк входу ос"анова генератора тактовыхимпульсов, выход (щ)-го коммутатора группы подключен к (щ)-мувходу элемента ИЛИ и третьим входамвсех элементов ИЛИ-И первой строкинаддиагональной матрицы моделейдуг, 1-й выход признака максимального кода блока выбора максимальногокода подключен к входу к.-го элементаНЕ группы, выход которого подключенк соответствующим входам с (1+1)-гопо (щ)-й элементов И первой группы,информационный выход блока выбора максимального кода подключен к входу элемента задержки , выход которого подключен к входу второго слагаемогосумматора.1 322307 Составитель А,МишинТе х р ед Л. Олийнык Корректор А, Тяско Редактор Н. Рогулич Закаэ 2867/47 Тираж 672 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раущская наб., д. 4/5 Праиэводственно-полиграфическое предприятие, г, Ужгород, ул. Проектная,