Устройство для решения задач на графах

 

Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа. Целью изобретения является расширение функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из начальной в конечную вершину графа. Устройство содержит С лок 1 синхронизации, блок 2 определен я концевых вершин дуг. Блок 3 задания матрицы смежности, коммутатор 4, блок 5 памяти, сумматор 6, вход 7 пуска Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа. Целью изобретения является расширение функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из начальной в конечную вершину графа. На фиг.1 представлена функциональная схема устройства, на фиг.2 - временная диаграмма работы блока синхронизации . устройства, выходы 8, 9, 10 блока 1 синхронизации , выходы 11 группы блока 1 синхронизации и выходы 12 количества различающихся маршрутов из вершин графа в его конечную вершину Перед началом работы номера вершин графа упорядочивают таким образом чтобы матрица смежности i рафа стала треугольной наддиагональной. Топологию полученного таким образом графа ззчисят в блок 3 задания матрицы смежности В блок 5 памяти по адресу В/где В - количество вершин в графе/ заносят единицу, а остальные ею ячейки обнуляют На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах 7...11 последовательность сигналов уровня логической единицы, под управлением которой в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршрутов из первой по В-ю вершин в В-ю (конечную) вершину графа 2 ил СП с Устройство содержит блок 1 синхронизации , блок 2 определения копцепых вершин дуг, блок 3 задания матрицы смежности , коммутатор 4, блок 5 памяти, сумматор 6, вход 7 пуска устройства, с первого по третий выходы 8 9,10 блока 1 синхронизации, ьыходы 11 группы блока синхронизации и выходы 12 количества различающихся маршрутов из вершин графа а его конечную вершину. Устройство работает следующим образом . СЬ 00 Ј vl О сл

СОЮЗ СОВЕТСКИХ сОци Ал истин е c KL l x

РЕСПУБЛИК (sl>s 6 06 F 15/20

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ,О ((.П (21) 4479414/24 (22) 01.09.88 (46) 15.10,91. Бюл. М 38 (72) А.В.Александров, Н.Б.Парамонов и Е.В.Фролов (53) 681.333(088,8) (56) Авторское свидетельство СССР

N 1312602, кл. G 06 F 15/20, 1985.

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

М 1587535, кл. G 06 F 15/20, 1989. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа, Целью изобретения является расширение функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из начальной в конечную вершину графа. Устройство содержит (гюк 1 синхронизации, блок 2 определен(я концевых вершин дуг, блок 3 задания матрицы смежности, коммутатор

4, блок 5 памяти, сумматор 6, вход 7 пуска

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

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

На фиг.1 представлена функциональная схема устройства; на фиг.2— временная диаграмма работы блока синхронизации, „„. Ж„„1684/95 А1 устройства, выходы 8, 9, 10 блока 1 синхронизации, выходы 11 группы блока 1 синхронизации и выходы 12 количества различающихся маршрутов из вершин графа в его конечную вершину, Перед началом работы номера вершин графа упорядочивают таким образом. чтобы матрица смежнос1и графа стала треугольной наддиагональной, Топологию по ученного таким образом графа заносят в блок 3 задании матрицы смежности. В блок 5 памяти по адресу В/где  — количество вершин в графе/ заносят единицу, а остальные его ячейки обнуляют. На вход 7 пуска устройства подают импульс уровни логической единицы, При этом блок 1 синхронизации формирует на своих выходах 7...11 последовательность сигналов уровня логической единицы, под управлением которой в блоке 5 памяти по адресам с первого по

В-й будут зафиксированы количества различающихся маршру1ов из первой по В-ю вершин в В-ю (конечную) верш1 ну графа, 2 ил. и о ,QQ

Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин дуг, блок 3 задании матрицы смежности, коммутатор l, блок 5 памяти, сумматор 6, вход 7 пуска устройства. с первого по третий выходы 8.9,10 блока 1 синхронизации, выходы 11 группы блока синхронизации и выходы 12 количества различающихся маршрутов из вершин графа в его конечную вершину.

Устройство работае1 следующим образом.

1604795

Парад началом работы номера вершин ! р;.>фB у!,0;:«доч<иоают таким образом, чтот»I i;i»lpшина графа IMOJIB макси>;:>iii-lil i<1 т Оглер (В), а номера остальных . ар ли;т убыолли по мере того, как будут

i!i ра>тумерованы концевые вершины всех

: С:.ОДЯ < 1Х ИЗ НИХ ДУГ, ТОПОЛОГИЮ ПОЛУЧЕН«0: 0 т <3K>1> f Об> г> 330>1 т рафа заносят в блОк

3 з f!1BII« l матрицы смежности. В блок 5 пл .!

0с.":т:. »< е его Я-f<>éKL1 обнулчтот. 1-!а вход 7

i!7<»: угтрпйстт>а подаю импульс уровня

;:.:г<т!00! Ой ади>тицЫ. При ЭТОМ бЛОК 1 СИН>.р ..fçBf!L и форм<лрует на своих выходах посл",äñоатагтьность сигналов ,. р <:..<я л, и i00K0> единицы, прадусмотi

> 0 LIlf>Tiff!>ff,Ix тактов, рассмотрим К-й. т -г. т:;Кг . работЫ бЛОК 1 СИНХрот>ИЗацИИ

>1: т<УОГ ПвтЕНЦ>таЛЫ УРОВНЯ ЛОГИЧЕСКОЙ

l<а К-м выходе 11 группы и на о.: ":.I I>";äå U. Г!ри этом блок 2 формиру;«<3<1х выходах согтао множества оер" .::, Г. <ОРЫЕ ЯОЛЯЮтС!f КОНЦЕВЫМИ тОЧКаМИ

"!: ..Сх.>дящих из (В+1-К)-й вершины графа.

i Ir "> Г.>1 f:0!1>лутатор 4 ffofLK."I>0. .T К СВОИМ

<>иттлцff0ffilf.lf1 выходам иттформацион>I!::: входы тзторой группы (тем самым воз<>>,,л<отсл l(1 входы блока 5 памяти.

>(От,рые соответствуют составу указанных

",I,I:. f> K0>Ii;,а<тых To«BK), а блок 5 памяти оы.>тттвт ><а свои информационные выходы зна<3<» < < >1 3 B, 3 rlif<".Л I I I1 ы е о Гт РеДЬ>ДУ<31их TBKTBx

;>лт: >!If !т.-м слмым IIB входы сумматора 6

i<,>, юг« I зна!0>ilfff коли:тесто различа>о

iI«;<::.;, ттуте<3 из каждой концевой точки те«у:. .:-го тактл работы о кона»ну>о вершину т i> .<><: l. "I p03 ет!эемя, достаточное для Окон а . <, >»(3BB!Illiix оь>ше < >1>ОЦесгов, блОК 1

<, < < <, > < : < i (" т l (j! 0 р тл !1 р у ат >1 м и у л ь с у > 0 о и я < - С. т: <3 l 3fi!Ll! !IÖ<

руат lfc3 сооатл

З>.Л апца СУММ>Л ООСтУПИВШИХ На ЕГО

<...,:.,;т.; . ii . f «0RI.,!К /3 е;. Са>лым огтре<теляатся

«<<Г,<:, г;ЛЗ if! IBI;><Цт<каff т>УтаИ Из таКУЩ>1Х !!> К)- i ттершины о кона тную BBptUL

" I l. тле! 00! .;Ifttиал с выхода 0. При эTОм утB >, ; 4 f10+I(ffючает свои информаци<л "« iн.* г>:;0fqI к первой группе информациflil!тремя, достато«ное для выбора Ячейки о б l!LK« . > !IBìÿTLf, блск 1 синхронизации

> -;"1»0;:.; и тг>УЛЬС УРООНЯ ЛОГИЧЕСКОЙ ЕДИ: < т<: «;<:,."..Осм выходе 9. При этом блок 5

:,, икгттруег зн 3 fåf!>f0, поступившее

5>

55 нл его информационный вход в выбранную ячейку памяти /тем самым по адресу (Вч1К)-й вершины заносится число paBfilfлируат потенциалы уровття логической единицы на оь!ходе 8 и (К+1)-м выходе 11 группы /тем самым происходит переход копраделению количества маршрутов из (В-К)-й вершины!, Работа устройства повторяетсг В рлз.

При этом в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршрутов из первсй по В-ю вершин в В-I0 (конечную) вершину графа, Формула изобрете>тия

Устройство для решения задач на графах, содержащее блок синхронизации, блок определения концевых вершин дуг, блок задания матрицы смекности, коммутатор и блок памяти, причем вход пуска устройства подключен к входу пуска блока cf1!!Kpofi«BBции, первый и второй выходы которого подключены к управляющему входу ко>лтлутатора и к входу признака записи блока памяти соответственно, выход значения (К,М)-ro элемента блока задания матрицы смежности (К = 1„.,В; М = 1,.„,В, где В— количество вершин о графе) подключен к входу признака наличия (К,М)-й дуги блока определения концевых вершин дуг, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет подсчета количе;тоа различающихся маршрутов из началь. >й о конечную вершину графа, о него введен су;лматор, причем К-й выход группы блока синхрснизации подключен к (В+1-К)-у и>>формационному входу первой группы коммутатора и к входу опроса (В+1-К)-й начальной вершины блока определения концевых вершин дуг, выход признака принадлежности M-й вершины множеству концевых вершин дуг .оторого подключен к M-y информац,снному входу второй группы коммутато>-..., M-й информационный выход которогG подключен к М-у адресному входу блэка памяти, M-й информационный выход которого является выходом количества разли >аютцихся маршрутов из М-й в конечную вершину графа устройства и подключен к входу M-го слагаемого сумматора, выход которого подключен к информационному Ох0ду блска памяти; третий выход блока си тхронизации подключен к тактовому входу сумматора.,1

Щ/я;

Соста вите п ь Л,.Ь1 и шин

Текред М.ПЛоргенп зл

Коррекгор А.Оса иенкc!

Редактор f I,Каменская

Заказ 3508 1ирак Подгиб.сное

ВНИИПИ Государственного комиге а гго изобретениям и открьiтиял ори 1I П! C(..ÃÐ

113035, Ыосква, Ж-35, Раун скал наб„4/б

Производственно издан.лг,с .llé комбинат Патент", т, Узкгород. ул i агарин» 1(11