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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) СЮ 4 G 06 F 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 4061523/24-24 (22) 24.03.86 (46) 07.07.87. Бюл. У 25 (72) Г.С.Колесник (53) 681.333(088.8) (56) Авторское свидетельство СССР

Р 1005066, кл. G 06 F 15/20, 1981, Авторское свидетельство СССР

В 1076909, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФЕ (57) Изобретение относится к вычислительной технике, может быть использовано при исследовании параметров сетевых графов беэ циклов и петель и позволяет определить все независимые по вершинам максимальные пути в графе ° С этой целью при помощи наддиагональной матрицы моделей дуг (матрицы связности графа) группы регистров, в которых записаны веса вершин графа, блока выделения максимального кода и сумматора находят первый максимальный путь в графе, Затем из наддиагональной матрицы моделей дуг исключают дуги, соответствующие первому максимальному пути, и цикл работы ус)ройства повторяют. 1 ил, 1322307

Иэобретс:нис от«се(!гся к л!.! (ислительной технике и 3!<э((ст быть использовано при исследовании пс(рл((етров сетевых графов без циклов и летеJII .

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

На чертеже представлена функциональн 151 схема устройства, В сОс ГBB ycTpOII(cтвл 13хОДит нлддил гонлльная матрица 1 моделей :(yi, каждый узел которой содержит тр!гггер 2 и элемент ИЛИ-И 3, группу .элементол

ИГ!И 4. группу элементов 5 злдс ржки, ! руг; t (3(I )!< трон б, тр;! «ру:I!Ii (б "о)с<э« 7-. bt сэ)(с, (С((T<>!3 И u;! c!!c 1 0 it«!t t top!(."<:<к < It. (J(ü(I0 ÃÎ !Годар 1 ;)уп(1 1 1 ) )(с. (с. 11 т )!3 III" > блок 12 зле((енто« II.III> э. с(< (!т ИВИ 13, су(м !атор 1, э.-н:*i< (т 15 3H!(. (эжки, три гру!!Ггы ээ!сэ!<эi(T013 И 6-! 8, группу э (cite» To!3 lll, 19, i pytt((y

Гр и«ге ров 20, группу к<э)-(((у !э(т< ров 21, 25 геJIcpc(Top 22 тактовых иг(!(уэ!(,с эГ), рлс» прсдслитель 23 импульсо, 1<х(»(!!ус:кл устрсй< тла и вход (Ip(t!JIIQII;1 ис(сс(!<эчсlilM г(уг устройства.

Устройство рлботлс.т слс(ду clt(J(3(30

Об t);13 0(.t. !

II! !<Од Г!уcKotl I3 с д(!((IГ(нос cocTcбнуня! т григгсрь! 20. В 35

IIСХО((!IОМ l .O:10"CC. tt И((Jl/1фОР((аЦIIОН!!Ыс

l3 YOJ(I ) К O it Iy t <1 тO pOI(2 1 (I

<(ll tltA I) (l ll1(0 tl Ill i <

lIoc Il<» 1(од<(ли 1!ус(::!1!0(О Сиг

Гул<.с((генср;(тnpа 22 (эосгу((а(с)т нл !0 такт< н((й вход p:.1< прс„!ел!«геля ?3, который пoc ÷cðc ä!(О выцаcт импульcû на с((он первый, второй и т.д. «ыходы.

И. <ульс с сг0 первого (в(хода н;)входит лг нл )lop l3b(II ль!ход ((и ) I <) к<э. 11! . T(1 Ора

21 и !(!«!tee нл вход (ш-1) — го .3

5 задержки, нл второй вход (ш- !)-го блОкл 8 и на Tpc ти(! л:од сОО t !3< тcT1ly3в)!(егo лемснтл РИ1И-И. Ото «буi.(CJJJГ!и(лает 1(o< тупленис несл (ш- ) -й вер- 50 шины с 13!(хо<<а (m-1)-го регистр;< 6 через (m-1)-й блок 8 и блок ИПИ !2 на вход перног0 сла(ае(!<эгO cyì÷JI (opä

14 и поступление веса m-й веj)!III(;Ibl с выхода ш-го регистра 6 через roîT- 55 ветствующ(rf(блок 9 на 1!к<э,<(Г).Г(uк(1 10, поскол(,ку л (1(1 1) -й строке модслси

;туг ((лтрицы 1 лишь тр!(ггер ? !<лходится л сд((3(ичном состоянии, и едиI(It<(it(I(I с((гнал с его выхода проходит нл JJторой вход блока 9 и открывает его для прохожденьи веса m-й вершины на вход блока 10, который выдает нл выход числа обратный код веса этой

«ерш(и(. Л!эямой(код ее веса с выхода элементов klE группы 11 поступает на вход второгo слагаемого сумматора !

«, ((О(орьй выдает код числа, равного су(((!е не=он m-й и (m-,1)-й вершин, через от(срыть(Г(к этому времени (тп-1)-й блок 7 на информационный вход (m-1)-го регистра 6, который запомиIt;t

<) !с р,,! !с (ыходь(pаспределителя 23

vc . г р йс.(!3<э !элГ)отлет <и(ллог Г(чно, и

el((-l1llлсм с вихода первого элемента 5 э;д< рж(,è, поступающим на управляющие (33 o! (t l ком.!утлторов 21, они подключают с!30 и (!!1

И !И-И 3 первой строки матрицы 1, в рсэу.и,тате чего единичные сигналы с

«ьг:одоп триггеров 2, находящихся в

<: <,(III;«»to (сос гоянии, открывают соответствующие б)локи 9, через которые ! ели (н!и максимальных путей тех не рш(!!1, < нязснгиих с первой вершиной, ((Остуилют нл соотнетствующие входы блока 10. Он выбирает наибольший из

«ссол и выдает единичный сигнал на

lt!r -.<ыход признака максимального кодл, соответствующий входу, на кото-! э!ш1! подан 1)аксимальный код. В это же время ьмпульс с второго ныхода (т--1)-го комм,татора 21 через элемент

ИЛИ !3 I(элемент 15 задержки поступает нл DToрые входы эJIåME:íòoB И 16, что обеспеч(иэает перЕход в единичное состояние соответствующего максималь(!Ому коду триггера 20. Если на нескольких выходах блока 10 появляются единичные сигналы, то через элемент

И 16 с ((ель(((и((порядковым номером он проходит, а через остальные не про3 132? 3 ходит благодаря подаче нулевых потенциалов с выходов, соответствующих элементов НЕ 19, Импульс с второго выхода распределителя 23 проходит на второй выход (m-2)-го коммутатора 21 и далее на второй вход второго элемента И 17.

Если второй триггер 20 переключается в единичное состояние, с выхода второго элемента И 17 импульс поступает ip на вторые входы элементов ИЛИ-И 3 второй строки матрицы 1, Единичные сигналы с выходов тех триггеров 2, которые в данной строке матрицы 1 находятся в единичном состоянии, так 15 же поступают на входы блока 10, в результате чего после прохождения импульса с (m-1)-го выхода распределителя 23 и останова устройства в единичном состоянии оказываются те триг- 20 геры 20 через соответствующие номерам которых вершины проходят максимальный путь иэ первой начальной в конечную ш-ю вершину графа, Для нахождения второго (по длине) 25 максимального пути независимо по вершинам от первого найденного пути подают единичный сигнал на вход исключения дуг устройства, при этом обнуляются регистры 6 (кроме m-го) и 30 открываются элементы И 18, вследствие чего единичный сигнал с выходов тех триггеров 20, которые соответствуют вершинам первого максичального пути и находятся в единичном состоянии, поступает на входы установки в "0". триггеров 2 одноименных строк матрицы 1 и устанавливают их в "0". Этим из топологии графа исключаются дуги, исходящие из вершин первого 40 максимального пути. Далее в регистры

6 заносят веса вершин графа, обнуляют триггеры 20 и распределитель 23, а коммутаторы 21 возвращают в исходное состояние. После этого вновь за- 4g пускают устройство, по окончании работы которого единичные состояния триггеров 20 укажут вершины, через которые проходит искомый второй максимальный путь. По схеме графа проверяют полноту найденного второго пути (так как при отсутствии второго пути независимо по вершинам от первого пути найденные с помощью триггеров 20 вершины могут оказаться не связанными с конечной вершиной).

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

Устройство для исследования путей в графе, содержащее группу элементов

07 4

101И, группу элементов э аде ржк и, три

t руппы блоков элементов И, две группы элементов И, группу триггеров, г руину регистров, блок выбора максималь— ногс кода, сумматор, б:ок э:IpMPHToB

ИЛИ. генератор тактовых импу.п,сов и наддиагональную матрицу моде. ей дуг из (m — 1) строк и (m-1) столбцов, где

m — число вершин в графе, каждый узел которой содержит элемент ИЛИ-И и триггер, выход которого подключен к первому входу элемента ИЛИ-И того же узла наддиагональной матрицы моделей дуг, вход пуска генератора тактовых импульсов является входом пуска устройства, выхоч k-го элемента эадержки группы (k=1,..., m-1) подключен к информационному входу

k-го регистра группы, выход которого подключен к первому входу блока элементсв И второй группы и первому входу (k-1)-го (1 1) блока элементов И третьей группы, выход m-ro регистра группы подключен к первому входу (m-1)-го блока элементов И третьей группы, выходы блоков элементов И второй группы подключены к соответствующим входам блока элементов ИЛИ, выход которого подключен к входу первого слагаемого сумматора, выход которого подключен к вторым входам всех блоков элементов 11 первой группы, выходы блоков элементов И третьей группы подключены к соответствующим входам блока выбора максимального кода, k-й выход признака максимального кода которого подключен к первому входу k-го элемента И первой группы, выход которого подключен к информационному входу k-го триггера группы, выход которого подключен к первому входу k-го элемента И второй группы, выход которого подключен к вторым входам всех элементов ИЛИ-И (k+1) é строки (kgm-1) наддиагональной матрицы моделей дуг, выходы всех элементов ИЛИ-И (k+1)-го столбца (kpm-1) наддиагональной матрицы мс— делей дуг подключены к соответствующим входам 1с-го элемента ИЛИ группы, вьгход которого подключен к второму входу (k+1)-го блока (kjm-1) элементов И третьей группы, выход лемента

ИЛИ-И первого столбца наддиагональной матрицы моделей дуг подключен к второму входу первого блока э",åìåíòîH И третьей группы, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройст5 13223 ва за счет определения всех независимых по вершинам максимальных путей в графе, в него введены распределитель импульсов, группа коммутаторов, группа элементов НЕ, третья группа элемен- 5 тов И, элемент задержки и элемент

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

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

"0" с первого по (т-1)-й регистров группы и входу признака исключения дуг устройства, выход k-ro триггера группы подключен к второму входу k-го элемента И третьей группы, выход которого подключен к входам установки 25 в "0" всех триггеров (1 +1)-строки (kpm-1), наддиагональной матрицы моделей дуг, выход первого элемента задержки группы подключен к входу на07 6 чальной ус гановки распределителя импульсов и управляющим входам коммутаторов группы, второй выход Е-го коммутатора группы (kpm-1) подключен к второму входу (m-k)-го элемента Й второй группы и k-му входу элемента

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

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

I 322307

Составитель A.Ìèøèí

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

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

Закаэ 2867/47

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

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

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

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