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

(50 4 С 06 Р 5 ПИСАНИЕ ИЗОБРЕТ ий са а с час 1 ааа ЕЛЬСТВ ОРСКОМУ К В 46Л,Г.П убанов авых во ССС 978 СССР 1982ель 15/ а с ОСУДАРСТВЕННЫЙ КОМИТЕТ ССС О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ(54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА(57) Изобретение относится к областивычислительной техники и может бытьиспользовано для определения истокаориентированного графа. Устройствосодержит блок 1 синхронизации, блок2 определения связности вершин графа, элемент ИЛИ 3, вход 4 начальнойустановки устройства, тактовый выход5 блока синхронизации, вход 6 опрос1444809 блока 2, выход 7 признака связности всех вершин графа, вход 8 останона блока 1, выходы 9 группы блока 1, вход 1 О задания истока подграфа, вход 11 пуска устройства, блок 12 задания топологии графа, элементы ИЛИ13 группы, элемент И 14, входы 15 опроса вершин графа блока 12, выходы 16 признаков достижимостн вершин графа блока 12, вход 17 разрешения работы блока 12, триггеры 18 матрицы, элементы ИЛИ 19 группы, элементы И 20 группы, элементы И 21 матриИзобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа.5Целью изобретения является расширение функциональных возможностей устройства за счет определения истока ориентированного графа.На Фиг. 1 представлена функцио нальная схема устройства; на фиг,2 - временная диаграмма работы блока синхронизации.Устройство содержит блок 1 синхронизации, блок 2 определения связ ности .вершин графа и элемент ИЛИ 3, причем вход 4 начальной установки устройства подключен к одноименному входу блока 1 синхронизации, тактовый выход 5 которого подключен к входу б Опроса блока 2 определения связности вершин графа, выход 7 признака связности всех вершин графа которого подключен к второму входу элемента 3 ИЛИ, выход которого подключен к вхо ду 8 останова блока 1 синхронизации, М-й выход 9 группы которого подключен к М-му входу 1 О задания истока подграфа (М=1В, где В - количество вершин в графе), вход 11 пуска 30 ус гройства подключен к входу пуска блока 1 синхронизации. Блок 2 определения связности вершин графа содержит блок 12 вадания топологии, группу из В элементов ИЛИ 13 и элемент И 14 выход 7 которого является выходом признака связности всех вершин графа,цы и входы 22 признаков наличия ветвей между вершинами графа. Послепуска блок 1 синхронизации производит последовательный опрос вершинграфа, В там случае, если опрошеннаявершина является истоком графа, навыходе 7 появляется сигнал уровнялогической единицы, который останавливает блок 1 синхронизации. Выход9, на котором присутствует потенциал высокого уровня, соответствует номеру вершины, являющейся истокомграфа. 2 ил. причем М-й вход 10 задания истокаподграфа подключен к второму входуМ-го элемента ИЛИ 13, выход которогоподключен к входу 15 опроса М-й вершины графа блока 1 2 задания топологии, выход 16 признака достижимостиК-й ветви графа которого ( К=1В)подключен к К-му нходу элемента И 14и к первому нходу К-го элемента ИЛИ13, вход 6 опроса блока 2 определения связности подключен к входу 17разрешения работы блока 12 заданиятопологии графа,Блок 12 задания топологии содержит матрицу из ВВ триггеров 18,группу из В элементов ИЛИ 19, группу из В элементов И 20 и матрицу изВВ элементон И 21, причем вход 22признака наличия ветви из М-Й в К-ювершину графа подключен к входу установки в единицу К-го триггера М-йстроки матрицы.Устройство работает следующим образом,Перед началом работы на вход 4 начальной установки подают импульсный сигнал уровня. "1, при этом происходит установка в исходное состояние блока 2 определения связности вершин графа и блока 1 синхронизации. В блок 2 заносится информация о топологии графа. На вход 11 пуска устройства подают импульсный сигнал единичного уровня, пои этом блок 1 синхронизации формирует импульсные1444809 сигналы уровня "1" в соответствии свременной диаграммой работы (фиг.2).Импульсный сигнал уроння "111 появляется на первом выходе 9 блокасин 5хронизации, при этом блок 2 подготавливаетсяся к определению вершин,связных с первой вершиной, Через время Т 1, достаточное для подготовки блока 2, блок 1 синхронизации формирует 10импульсный сигнал уровня "1" на выходе 5, при этом производится опросблока 2, В том случае, если все вершины графа связаны, на выходе 7 блока2 появляется импульсный сигнал уровня "1", при этом производится останов блока 1 синхронизации, а потенциал уровня "1" на первом выходе 9 блока 1 синхронизации является признаком соответствия первой вершинь истоку графа (т,е, из первой вершины может быть достигнута любая вершинаграфа). В том случае, если из первойвершины все остальные вершины достигнуты быть не могут, сигнал на выходе.7 блока 2 не появляется и через время Т 2, достаточное для опроса блока2, блок 1 синхронизации снимает сигнал уровня "1" со своего первого выхода 9 и формирует его на втором выходе 9, После этого работа устройства повторяется. Если граф не имеетистока, то через В циклов опроса сигнал уровня "1" появляется на В+1-мвыходе 9. При этом происходит останов З 5блока синхронизации, а потенциалуровня "1" на В+1-м выходе блока 1служит признаком отсутствия истока вграфе,Блок 2, определения связности работает следующим образом. достаточное для окончания переходныхпроцессов, на выходах 16 формируется состав всех вершин, связных с М-й.Если связными являются все вершиныграфа., на выходе элемента появляетсясигнал уровня логической единицы,который н качестве признака связностивсех вершин графа поступает на выход7 блока 2,Блок 12 задания топологии работает следующим образом.Сигнал уровня "1" на входе 4 устанавливает все триггеры 18 матрицыв нулевое состояние, На вход 22 установки в единицу М-го триггера 18К-й строки матрицы подают импульсныйсигнал единичного уровня (при наличии ветви из М-й в К-ю вершину графа), Тем самым задают топологию графа в соответствии с его матрицей смежности. При наличии сигналов уровня"1" на входе 17 разрешения работы иМ-и входе 15 опроса блок 12 выдаетсигналы уровня " 1" на те выходы 16,соответствующие которым триггеры 18М-й строки матрицы установлены вединичное состояние,Перед началом работы на вход 4 начальной установки подают импульсныи сигнал ровняпри этом про 45 исходит установка н исходное состояние блока 12 задания топологии графа, В блок 12 заносится информация о топологии графа, При поступлении на М-й вход 10 задания истока подграфа сигнала уровня "1" производится опрос М-й вершины графа, при этом блок 12 при наличии сигнала уровня "1" на входе 17 разрешения работы выдает на свои выходы 16 сигналы уров. ня "1", позиции которых соответствуют составу вершин, связных с М-й.Указанные сигналы поступают на соответствующие входы 15 и через время,Формула изобретения Устройство для анализа параметров графа, содержащее матрицу из В Х В триггеров, гце В - количество вершин в графе, матрицу из В л В элементов И, первую группу из В элементов ИЛИ и элемент И, причем вход начальной установки устройства подключен к входам установки в "0" всех триггеров матрицы, вход признака наличия пути из М-й в К-ю вершину графа (К=1,В М=1В) подключен к входу установки в "1" К-го триггера М-й строки матрицы, выход которого подключен к первому входу К-го элемента И М-й строки матрицы, выход которого подкпючен к М-му входу К-го элемента ИЛИ первой группы, выход которого подключен к К-му входу элемента И, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения истока ориентированного графа, в него введены вторая группа из В элементов ИЛИ, группа из В элементов И, элемент ИЛИ и блок синхронизации, вход пуска которого является входом пуска устройства, вход начальной ус, Редакт ки 1 одписно Тираж 704 аказ б 508/5 комите открытии ая наб д. 4 тановки устройства подключен к одноименному входу блока синхронизации,тактовый выход которого подключен кпервым входам всех элементов И группы, выход К-го элемента ИЛИ первойгруппы подключен к первому входу К-гоэлемента ИЛИ второй группы, М-й выходгруппы блока синхронизации являетсявыходом признака соответствия М-йвершины истоку графа устройства иподключен к второму входу М-го элемента ИЛИ второй группы, выход котоВНИИПИ Государственног по делам изобретений113035, Москва, Ж, Рау эводственно-полиграфическое рого подключен к второму входу М-гоэлемента И группы, выход которогоподключен к вторым входам всех элеч 5ментов И М-й строки матрицы (В+1)-йвыход группы блока синхронизации является выходом признака отсутствияистока в графе устройства и подключенк первому входу элемента ИЛИ, выход 10 элемента И подключен к второму входуэлемента И 1 П 1, выход которого подключен к входу останова блока синхронизации. приятие, г, Ужгород, ул. Проектная