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

,О1 синхро- (Я концевых рицы смежмяти, сум- д ойства. с 10 блока 1 ппы блока количества ершин грасодержит блок2 определенияк 3 задании маттор 4, блок 5 па7 пуска устртий выходы 8.9, выходы 11 Груи выходы 12маршрутов из вую вершину.работае 1 след ноитанали ени азл кон аль рем они ющим обГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР АНИЕ ИЗОБ У СВИДЕТЕЛЪСТВУ(56) Авторское свидетельство СССР М 1312602, кл. 0 06 Г 15/20, 1985.Авторское свидетельство СССР М 1587535, кл. 6 06 Р 15/20, 1989.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа, Целью изобретения является расширение функциональных возможностей устройства за счет подсчета количества различающихся маршрутов из начальной в конечную вершину графа, Устройство содержит 1 лок 1 синхронизации, блок 2 определен я концевых вершин дуг, блок 3 задания матрицы смежности, коммутатор 4, блок 5 памяти, сумматор 6, вход 7 пуска зобретение относится к вычислительехнике и может быть использовано для за связности вершин графа.елью изобретения является расшие функциональных воэможностей усства за счет подсчета количества ичающихся маршрутов из начальной ечную вершину графа.э фиг.1 представлена функционая схема устройства; на фиг.2 - енная диаграмма работы блока синхзации,Ж 16847 Ю А устройства, выходы 8, 9, 10 блока 1 синхронизации, выходы 11 группы блока 1 синхронизации и выходы 12 количества различающихся маршрутов из вершин графа в его конечную вершину, Перед началом работы номера вершин графа упорядочивают таким образом. чтобы матрица смежнос 1 и графа стала треугольной наддиагональной, Топологию полученного таким образом графа заносят в блок 3 задании матрицы смежности, В блок 5 памяти по адресу В/где В - количество вершин в графе/ заносят единицу, а остальные его ячейки обнуляют, На вход 7 пуска устройства подают импульс уровни логической единицы, При этом блок 1 синхронизации формирует на своих выходах 711 последовательность сигналов уровня логической единицы, под управлением которой в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршру 1 ов из первой по В-ю вершин в В-ю (конечную) вершину графа, 2 ил,Устроиство низации, блок вершин дуг, бло ности, коммута матор 6, вход первого по тре синхронизации синхронизации различающихся фа в его конечн Устройство разом.Псрсд лчалом работы номера вершинр;.ф у;ос:ядочивают таким образом, что- ГЧ КОЕЧая ВЕГ)шина графа имела макси- Га цй номер (В), а номера остальных е)и убывлли по мере того, как будутреумерованы концевые вершины всех ИСХОДЯЦИХ ИЗ ИХ ДУГ, ТОПОЛОГ ИЮ ПОЛУЧЕНО О таки 1 обг)азом графа ээнос 5 т в блок .3 задаия матрицы сменности. В блок 5 Ггл ти по адресу В заносят единицу, а СГгг:Н; Е ЕгО ЯЕйКИ ОбНуЛЯОт. а ВХОД 7 7,;л угтрпйстга подаю импул с. уровя лг вг, Ои единицы, При этом блок 1 син) Рг.;.1 ЗГИ фОРМЛРУЕт На СВОИХ ВЬХПДаХпоследсватегьность сигналов р : Лц,и с.ской единицы, предусмот,с.У .ремсчной диаграммой его рабоц. Оскольку работа устройства состоитОд Отипных тактов, рассмотрим К-й.г. т,Кг рвботЫ бЛОК 1 СИНХроИЗацИИ" Уег потенцалы уровня логическойна К-м выходе 11 группы и наск" ":.д"оде 8. Г ри 3) ом блок 2 формирус;г)1 х выходах с)гтав множества вер" .:, г. орце являются концевыми точкамиСх)дяцсх из (В+1-К)-й вершины графа.г:;:г, 1 комутатор 4 подключает к своим. ),"Оцоныи выходам информацион. О входы Г)ородй групы (тем самым воз.у,сг)тся ) с входы блока 5 памяти. ;) ,рые сгоогвстсгвуют составу указанных цышс коце.ых Гочедк), а блок 5 памяти вы- ,Г;вта свои информационные выходы значсиЛаг;ислные в предыдущих тактах РЛГ, гы 1"М СЛМЫМа ВХОДЫ СУММатОРа 6 О, "ЮС ЗНСгОН 1 Я КОЛИЧЕСТВ РаЗЛИЧаО ц, ":", Ггуе из каждой концевой точки теу:.".)гг) акта работы в конечнуо вершину),дг). ЕРЕЗ ВЭЕМЯ, ДОСтаТОЧНОО ДЛЯ ОКОН- "с. ,:" уЛзанх вьше )Оцесгов, блок 1 сг,) зл," )г)рмрует имГульс уровня:,." ь суг.;ТО б фиксируета своемз л еие сук;мы поступивших на его.ЛаОЕМЫХ /ТЕ СОМЫМ ОГРСЕЛЯЕтСЯ ЧИСЛ, РЛЗгаСЦ 1)СЯ ГУТЕ 1 ИЗ ТЕКУЩИХ ВЕ).епцины в конечную вершиу гра;.,. Через время, дост точное для опера , 1) л О н: еи 51, б Г О кс и и х р О н и 3 э Ц и и гН ее г погдциал с выхода 8, При этом) Га ),) 4 Годключает свои информацис. Оы:оды к первой группе информаци- С)Цдг, аХ)ДОВ /ГЕМ СаЧЫМ ВОЗбУжДОЕтСЯ (д1-К) й адесный вход блока Гамяти/. Чер-:; ремя, достаточое для выбора Ячейки ц б цчц) 5 Гамяти. блок 1 синхронизации ; - Р 1,г:.; И гУЛЬС УРОВНЯ ЛОГИЧЕСКОЙ ЕДИ;,: ц с.Ось выходе 9. Гри этом блок 5: 51икгируег значеисд, поступивцее 10 15 20 25 30 35 40 45 50 55 нс его информационный вход в выбранную ячейку памяти /тем самым по адресу (В)1- К)-й вершины заносится число различаощихся маршрутов из нее в конечную вершину графа/. Через время, достэгочное для записи, блок 1 синхронизации снимает пс тенциал уровня логической единицы с К- го выхода 11 и формирует потенциалы уровня логической единицы на выходе 8 и(К+1)-м выходе 11 группы /тем самым происходит переход копределению количества маршрутов из (В-К)-й вершины/,Работа устройства повторяетсг В раз, При этом в блоке 5 памяти по адресам с первого по В-й будут зафиксированы количества различающихся маршрутов из первсй по В-ю вершин в В-ю (конечную) вершину графа,Формула изобретения Устройство для рец)ения задач на графах, содержащее блок синхронизации, блок определения концевых вершин дуг, блок задания матрицы смекности, коммутатор и блок памяти, причем вход пуска устройства подключен к входу пуска блока сихроизации, первый и второй выходы которого подключены к управляющему входу коммутатора и к входу признака записи блока памяти соответственно, выход значения (К,М)-го элемента блока задания матрицы смежности (К = 1.,В; М = 1,В, где В - количество вершин в графе) подключен к входу признака наличия (К,М)-й дуги блока определения концевых вершин дуг, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет подсчета количе;тца различающихся маршрутов из начальй в конечную верц)ину графа, в него введен суматор, причем К-й выход группы блока синхрснизации подключен к (В+1-К)-у и- формационному входу первой группы коммутатора и к входу опроса (В+1-К)-й начальной вершины блока определения концевых вершин дуг, выход признака принадлежности М-й вершины множеству концевых вершин дуг оторого подключен к М-у информационному входу второй группы коммутато, М-й информационный выход котороо подключен к М-у адресному входу блэка памяти, М-й информационный выход которого является выходом количества разли аощихся маршрутов из М-й в конечную вершину графа устройства и подключен к входу М-го слагаемого сумматора, выход которого подключен к информационному входу блока памяти; третий выход блока си хронизации подключен к тактовому входу сумматора..скал наб, 4/б Редактор 11,КагиенскЗак 13 3508111 ИИПИ 1 осуда 1 ираж енОГО ко 1;3035, Ыо игеа го иапо ГОРРек Г 013 А.О и Г 111 Г(,ГР. комбинатнп", , Ужгород ул егорин 1(1