Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/173 

началом работы номера вершин (р.фл го; «дочипают таким образом, что- ПЦРЧИЛЧ пепшина графа имела макси- гллмнт номер (В), а номера остальных чрршип убыппли по мере того, как будут перенумерованы концевые вершины всех ч «едящих ит мич дуг Тополо ич) получен ио;о ташм образом фафа заносят в блок

3 чд1нип матрицы смежности. В блок 5 по чдресу В заносят единицу, а ьг ч ч и Mr; fro з юйки обнуляют. На вход 7 и I, п /пргн ттп. подают импульс уровня

п ГЦ 1Т.| 1)И г.инИЦЫ При ЭТОМ 6/ЮК 1 СИН рiviчлции фопмирует на своих выходах 11 М по;п°дспат л1 ность сшналов /р и 1 и if единицы, продусмот- РГЧПЬ/К рроменной диаграммой его рабоч Плп-ольку работа устройства состоит и к однотипных тактов, рассмотрим К-й.

1 г т работы блок 1 синхронизации ip ii, потенциалы уровня логической MI ч: на К-м выходе 11 группы и на 4i -. и ,еО При этом блок 2 формиру, i , ги выходах состав множества вер- i лорме являются концевыми точками

- одчщих из (В-i 1-К)-и вершины графа. i ir i к ч копмугатор 1 подкпючает к своим

in | ргпционным чыходам информацион- н пходы второй группы (тем самым воз- i s /пются те входы блока 5 памяти, mrnpue c.coiFicrcrnyiOT составу указанных ы- и концевых точек), а блок 5 памяти вы- /i. на свои информационные выходы зна- ч. в предыдущих тактах if (гм (том f. на оходы сумматора 6 ii ония ко/ячеств различаю |ц| ч n/icii из каждой р.онцепой точки тек/г .л о Гсжта работы ь конечную г ершину

р ijn) lepf 3 время, достаточное для окоиJ, выше чроцессоя, бпок 1 г1 i. ; i ,vk-iU M фогмпруег импупьс i ч. пи д Т ицч а гвоом ОПУОДС 10 i , i i суг мачор 0 фиксирует на (.воем . (.1 л гтшние поступиппих ьа его г , , л Поомых/1сг«1 самым опрйделтется п ., г- , r. j- цтшо ци ся путей из текущих (Т К) л , щиины в конечную вершину гра- ( kpo,3 время, достаточное для опера- ло/;ония, блок I синхронизации г,( потенциал с выхода 8. При этом jH. ra-o,) 4 гюл слючает свои информаци- .Н( jf к первой группе информаци- .. ;дор /IDM самым возбуждается (Р Ч-К) и адресной вход блока памяти/. He- jit i (ромя, достаточное для выбора ячейки

4Г un.r rj памяш блы 1 синхронизации ; чрмии и. уровня логической оди- .н иг , Я ixоде 9 При этом блок 5 . эначение, поступившее

но его информационный вход в выбранную ячейку памяти /тем самым по адресу (П 1- К) и вершины заносится число различающихся маршрутов из нее в конечную

вершину графа/ Через время, достаточное для записи, блок 1 синхронизации снимает потенциал уровня логической единицы с К- го выхода 11 и формирует потенциалы уровня логической единицы на выходе 8 и (К Н)-м

выходе 11 фуппы /тем самым происходит переход копределению количества маршрутов из (В-К}-й вершины/,

Работа устройства повторяетсг В раз При этом в блоке 5 памяти по адресам с

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

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

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

подключен к входу пуска блока синхронизации, первый и второй выходы которого под- ключены к управляющему входу коммутатора и к входу признака записи блока памяти соответственно, выход значения

(К,М)-го элемента блока задания матрицы смежности (К 1....В; М 1, , ,Р, где В - количество вершин в графе) подключен к входу признака наличия (К,М)-й дуги блока определения концевых вершин дуг, о тличающееся тем, что, с целью расширения функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из началь11 HI в конечную вершину графа, в него введен

сумматор, причем К-й выход группы блока синхронизации подключен к (ВМ-К)у информационному входу первой группы коммутатора и к входу опроса (В-|1-К)-й начальной вершины блока определения

концевых вершин дуг, выход признака принадлежности М-й вершины множеству концевых вершин д/r -оторого подключен к М-у информаць.синому входу второй группы коммутатор., М-й информационный выход

которого подключен к М-у адресному входу блэка памяти, М-й информационный выход которого является выходом количества рзз- ли юющихся маршрутов из М-й в конечную ве|эшину графа устройства и подключен к входу М-ro слагаемого сумматора, выход которого подключен к информационному входу блока памяти, третий выход блока синхронизации подключен к тактовому пхо ду сумматора

Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа. Целью изобретения является расширение функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из начальной в конечную вершину графа. Устройство содержит С лок 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 О сл