Устройство для исследования путей в графе Советский патент 1987 года по МПК G06F15/173 

t1

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

Ие.иь изобретения - расширение фгункционапьньк возможностей ycTpoiicT ва за счет определения всех незави- С1счых по вершинам максимальных лутей в графе.

На чертеже представлена функциональная схема устройства,

В состав устро1 ства входит наддиа гоиальная матрица 1 моделей дуг, каж да узел которой содержит триггер 2 и элемет-гг ИЛ11-И 3,грунну элементов ИЛИ 4. группу элементов 5 зад.ержки, rpvn;r. регт строп 6, TJMI группы и. ;о- кор 7--9 элементов И, блок 10 шлОпра аксим:1льного кода, группу 1 1 э.ш мон то НЕ, блок 12 элементо ИЛИ, jj c- мснт ИЛИ 13, сумматор Ь , 15 гза., три группы элементов И 16- 1-8, группу элементов НЕ 19, TjinrrepOB 20, группу тйзммутач оров 21 генератор 22 тактовых импульсов, рас пpcдeJИ тeль 23 импульсов, н;-;од пуска устроГютва и вход, Т1рипнака ис1 ;лючен1Ш дуг ycTpoi iCTBa.

Устройство работает следукидим образом,

1(;ред пуском в е;тииич ое состояни ycTaiiaujiriTiaioT триггеры 2, соответст- jjyi.ijiiio единицам, в м, смежности Г1), J3 регистры 6 заносят веса вершин rpaflsa, обнулялит Г ;м ггеры 20, Б исходном гюложонии информацио1П1ые входы коммутаторов 21 но;;к:поче н.1 к пер}1ым ин|1|О11мапио1Пп.м. выходам,

Послй подачи nycicoBoro .iia им пул зС1 1 т енератора 22 поступают па TaKTOB iiii вход распред.е-гпп елл 23, ко- Topi-iti поочередно выдает импульсы на свои первый, BTOpoii и т,д, Г ыхс ды, lir.niy.HbC с его первого выхода л.)оходи на нервыГг выход (in-l)-ro -:оммутатора 21 и далее на вход (гл-1)-гч) эпемента 5 задерх ки, на второй вход (гл-)-го блока 8 и на третш вход соответствующего элеме1гга ИПИ-И, Это обуспаз

верлирает поступление веса шинь с ыход,а (т-1)-го регистра 6 через (т-Г)-и блок 8 и блок ИЛИ 12 на вход первого слагаемого сумматора 14 и поступление веса m-i i )И11Ы с выхода т-го регистра 6 через соот-- ветствую щш блок 9 на вход блока 10 посколтзку в (т-1)-й строке моделей /lyr матриц, 1 лишь трпггер 2 нахоto

t5

20

,

е -т дитея в едрл1Ш111ом состоянии, и единичный сигнал с его выхода проходит на втор(5й вход блока 9 и открывает его для прохождения веса га-й верши- 5 ны на вход блока 10, который выдает на выход числа обратный код веЬа этой вершпн,. Прямой код ее веса с выхода элементов НЕ группы 11 поступает на 1)Ход второго слагаемого сумматора 1), кот орь й выдает код числа, равного сумме ве;ов т-й и (т-1)-й вершин, через открытый к этому времени (га- -1)-й блок 7 на ипформационньш вход- (m-l)-ro регистра 6, который запоминает вес максимального пути из (т-1)-й в гг-ю вершину графа,

Но м)е поступления импульсов на очерод, выходы распределителя 23 ycrpoficTBo работает аналогично, и сигналом с выхода первого элемента 5 задерлпл, поступающим на управляющие входы коммутаторов 21, они подключают свои пнформадионные входы к своим ,iM информадионным , Рас30

40

,

J - пределитель 23 устанавливается в исходное состояние, В регист1)ах 6 после первого этапа работы устройства записаны ве1И1чины максимальных путей в конечную вершину графа из каждой из остальных его вершин,

На втором этапе импульс с первого выхода распределителе 23 проходит через второй В1)1ход (га-1 )-г о коммутатора 21 на вторые входы элементов

35 11 1И-И 3 nepBoii строки матрицы 1, в результате чего единичные сигналы с Бьп:одов триггеров 2, находящихся в единичном cocтo п ии, открывают соответствующие блоки 9, через которые величины максимальных путей тех вершин, связаппых с первой вершршой, nocTyiia)OT на соответствующие входы блока 10, Он выбирает наибольший из весов и выдает единичньй сигнал на тог гчлход признака максимального кода, соответствующий входу, на кото- piiii i подан мз.ксимальпьш код, В это же штульс с второго выхода (т- -1)--го коммутатора 21 через элемент

50 ИЛИ 13 и элемент 15 задержки поступает на вторые входы элементов И 16, что обеспечивает переход в ед1шичное состояние соответствующего максимальному коду триггера 20, Если на пес55 колък1Ех выходах блока 10 появляются едини П1ые сигналы, то через элемент И 16 с меньшим порядковым номером он проходит, а через остальные не про45

ходит благодаря подаче нулевых потенциалов с выходов, соответствующих элементов НЕ 19.

Импульс с второго выхода распределителя 23 проходит на второй выход (т-2)-го коммутатора 21 и далее на второй вход второго элемента И 17, Если второй триггер 20 переключается в единичное состояние, с выхода второго элемента И 17 импульс поступает на вторые входы элементов ИЛИ-И 3 втрой строки матрицы 1. Единичные сигналы с выходов тех триггеров 2, которые в данной строке матрицы 1 находятся в единичном состоянии, так же поступают на входы блока 10, в результате чего после прохождения импульса с (т-1)-го выхода распределителя 23 и останова устройства в еди

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

Для нахождения второго (по длине) 25 (ni-l)-ro блока элементов И третьей

максимального пути независимо по вершинам от первого найденного пути подают единичный сигнал на вход исключения дуг устройства, при этом обнуляются регистры 6 (кроме т-го) и открываются элементы И 18, вследстви чего единичный сигнал с выходов тех триггеров 20, которые соответствуют вершинам первого максимального пути и находятся в единичном состоянии, поступает на входы устан овки в О, триггеров 2 одноименных строк матрицы 1 и устанавливают их в О. Этим из топологии графа исключаются дуги, исходящие из вершин первого максимального пути. Далее в регистры 6 заносят веса вершин графа, обнуляют триггеры 20 и распределитель 23,

40 информационному входу k-ro триггера группы, выход которого подкдпочен к первому входу k-ro элемента И второй группы, выход которого подключен к вторым входам всех элементов 1и1И-И

а коммутаторы 21 возвращают в исходное состояние. После этого вновь за-45 (k+1)-й строки (kfni-l) на тдиагональ- пускают устройство, по окончании ра- ной матрицы моделей дуг, выходы всех боты которого единичные состояния элементов ИЛИ-И (k+1)-ro столбца триггеров 20 укажут вершины, через () наддиагональной матрицы мо- которые проходит искомьй второй мак- делей дуг подключены к соответствую- симальный путь. По схеме графа про- щ„ входам k-ro элемента ILIH группы.

веряют полноту найденного второго пути (так как при отсутствии второго пути независимо по вершинам от первого пути найденные с помощью триггеров 20 вершины могут оказаться не связанными с конечной вершиной). Формула изобретения Устройство для исследования путей в графе, содержащее группу элементов

выход которого подключен к второму входу (k-t-l)-ro блока () элементов И третьей группы, выход элемента ИЛИ-И первого столбца наддиагональной 55 матрицы моделей дуг подключен к второ му входу первого блока элементов И третьей группы, отличающе е- с я тем, что, с целью расширения функциональных возможностей устройст

IL IH, группу элементов задержки, три группы блоков элементов И, две группы элементов И, группу триггеров, группу регистров, блок выбора максимал.- ного кода, сумматор, блок элементов ИЛИ. генератор тактовых иьтульсов и над1;иагональную матрицу моде.чей дуг из (т-1) строк и (тп-1) столбцов, где m - число вершин в графе, каждый узел которой содержит элемент 11ПИ-И и триггер, выход которого подктпочен к первому входу элемента ИЛИ-И того же узла наддиагональной матрицы моделей дуг, вход tiycKa генератора тактовых импульсов является входом пуска устройства, выход k-ro элемента задержки группы (,,,,, m-1)i подключен к информационному входу k-ro регистра группы, выход которого

ментов И второй группы и первому входу (k-l)-ro () блока элементов И третьей группы, выход т-го регистра группы подключен к первому входу

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

информационному входу k-ro триггера группы, выход которого подкдпочен к первому входу k-ro элемента И второй группы, выход которого подключен к вторым входам всех элементов 1и1И-И

(k+1)-й строки (kfni-l) на тдиагональ- ной матрицы моделей дуг, выходы всех элементов ИЛИ-И (k+1)-ro столбца () наддиагональной матрицы мо- делей дуг подключены к соответствую- щ„ входам k-ro элемента ILIH группы.

выход которого подключен к второму входу (k-t-l)-ro блока () элементов И третьей группы, выход элемента ИЛИ-И первого столбца наддиагональной 55 матрицы моделей дуг подключен к второму входу первого блока элементов И третьей группы, отличающе е- с я тем, что, с целью расширения функциональных возможностей устройства за счет определения всех независимых по вершинам максимальных путей в графе, в него введены распределитель импульсов, группа коммутаторов, группа элементов НЕ, третья группа элементов Н, элемент задержки и элемент ИЛИ, причем выход генератора тактовых импульсов подключен к тактовому входу распределителя импульсов, k-й выход

которого подключен к информационному Ю элементов И первой группы, выход пер

входу (m-k)-ro коммутатора группы, первый выход которого подключен к входу k-ro элемента задержки группы, третьим входам всех элементов ИЛИ-И k-й строки наддиагональной матрицы моделей дуг и второму входу k-ro блока элементов И второй группы, первые выходы всех элементов И третьей группы подключены к входам установки в О с первого по (т-1)-й регистров группы и входу признака исключения дуг устройства, выход k-ro триггера группы подключен к второму входу k-ro элемента И третьей группы, выход которого подключен к входам установки в О всех триггеров (k+1)-cTpoKH (), наддиагональной матрицы моделей дуг, выход первого элемента задержки группы подключен к входу на

чальной установки распределителя импульсов и управляющим входам коммутаторов группы, второй выход k-ro коммутатора группы (kfm-1) подключен к второму входу (ra-k)-ro элементами второй группы и k-му входу элемента ИЛИ, выход которого подключен к входу элемента задержки, выход которого подключен к вторым входам всех

5

0

вого коммутатора группы подключен к входу останова генератора тактовых импульсов,, выход (га-1)-го коммута-- тора группы подключен к (т-1)-му входу элемента ИЛИ и третьим входам всех элeмer тoв ИЛИ-И первой строки наддиагональной матрицы моделей дуг, k-й выход признака максимального кода блока выбора максимального кода подключен к входу k-ro элемента НЕ группы, выход которого подключен к соответствующим входам с (k+1)-ro по (т-2)-й элементов И первой группы, информапионный выход блока вы- 5 бора максимального кода подключен к входу элемента за - держки , выход которого подключен к входу второго слагаемого сумматора.

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

Редактор Н. Рогулич

Составитель А.Мишин

Техред Л.Олийнык Корректор А.Тяско

2867/47

Тираж 672Подписное

ВНШШИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4