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

СОВЕТСКИХ ИСТИЧЕСНИХЛИН 1259281 ПВ 4 С ПИСАНИЕ ИЗОБРЕТ СТВ 35 Назальство ССС 5/20, 1982 ство СССР 15/20, 198 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕ(5 б) Авторское свидет9 943738, кл. О Об РАвторское свидетельУ 1174937 э кл. 0 06 Р(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯПАРАМЕТРОВ ОРИЕНТИРОВАННЫХ ГРАФОВ( 57) Изобретение относится к вычислительной технике и может быть использовано для определения расстояний мвкду вершинами ориентированныхграфов, являюшихся математическимимоделями сетей связи, информационно расчетных систем и т.д. Цель изобретения - расширение функциональных возможностей устройства за счет определения длины путей между вершинами ориентированного графа. Устройство содержит группу из и элементов И, группу из п регистров, матрицу из лп элементов И, вход "Начальная установкаи, элемент ИЛИ-НЕ, дешифратор, генератор тактовых импульсов, счетчик, два,элемент И, вход "Запуск", наборное поле, коммутирующие элементы, вертикальные и горизонтальные шины наборного поля. Поставленная цель достигается введением генератора тактовых импульсов, и групп по п индикаторных счетчиков, группы элементов задержки. 4 ил. С:Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением расстояний между вершинами ориентированных граФов, являющихся математическими моделями сетей связи, информационно- расчетных систем и т,д.Цель изобретения - расширение функциональных возможностей устройства за счет определения длины пути между вершинами ориентированного графа.На фиг. 1 представлена функциональная схема устройства для исследования параметров ориентированных графов, на фиг. 2 - пример граФа С(Х,А); на фиг. 3 - матрица расстояний графа; на фиг. 4 - временныедиаграммы,поясняющие принцип работы устройства,Устройство содержит группу элемен-, тов 1-1 задержки, группу из и элементов И 2 (и -максимально возможное количество вершин граФа), и групп по и индиаторных счетчиков 3 3 4 -4 регистров 8,-8 матрицу из и х и элементов И 9,-9, 10 -10, 11-11, 12,-12, 13, -13, вход Начальная установка" 14, элемент ИЛИ-НЕ 15, дешифратор 16, генератор 17 пакетов импульсов, счетчик 18, элемент И 19 элемент И. 20, генератор 21 тактовых импульсов, вход "Запуск" 22, наборное полу 23 и коммутирующие элементы 24.Наборное поле содержит п вертикальных 25 и п горизонтальных 26 шин, которые через коммутирующие элементы 24 соединены между собой в соответствии с топологией исследуемого графа, один вывод вертикальных шин наборного поля 23 подключены к первым входам группы элементов И 2-2 выходы 5.-го элемента И группы 2 -2 соединены с первыми входами элемента И 1-й строки, матрицы п 1 п элементов И 9 -9, 1 О, -10,12 12 3 13 д элементов И )-го столбца соединены с одноименными информационными входами 1-го регистра 8, вход начальной установки счетчика 18 соединен с входами начальной установки регистров 8 и является входом "Начальная установка" 14 устройства, счетный вход счетчика. 18 подключен к. выходу первого элемента И 19, первый и55.подается импульс, который устанавливает в нулевое состояние счетчик 8, регистры 8, -8. Индикаторные счетчи 1 О20 25 30 3540 45 50 второй входы которого соединены соответственно с выходом второго элемента И 20 и выходом элемента ИЛИ-НЕ 15, который подключен .также к вторым входам элементов И 2 -2 а вход элеи фмента ИЛИ-НЕ 15 соединен с п+1)-м выходом дешифратора 16, выход счетчика 18 подключен к входу дешифратора 16, первый вход первого элемента И 20 является входом "Запуск" 22 устройства, второй вход второго эле",мента И 20 подключен к выходу генератора 21 тактовых импульсов, а -й (=1,2п) выход дешифратора 16 соединен с первыми входами элементов И 1-го столбца матрицыпп элементов И 91 -9 10, -1011-11, 2 -12, 13, -13, выходы элементов 1, -1 задержки соединены с горизонтальными шинами 25 наборного поля 23, а входы соединены с выходами соответствующих элементов И, группы 2 -2, вход запуска генератора 17 пакетов импульсов соединен с выходом второго элемента И 19, а выход соединен с информационными входами соответствукяцих индикаторных счетчиков 3 -3 , 4 -4, 5.-5;, б, -б, 7-7, входы сброса которых соединены с соответствующими выходами регистров 8-8.Генератор 17 пакетов импульсов вырабатывает пакеты из п импульсов и запускается задним фронтом тактового импульса с генератора 21, Период следования импульсов в пакете равенсВ.1спгде. 1,- период следования тактовых импульсов генератора 21,Элементы- 1 задержки обеспечивают время. задержки, равное 1сВ 2 фУстройство для определения паралметров ориентированных графов работает следующим образом.Предварительно на наборном поле 23.набирается структура исследуемого графа при помощи коммутирующих элементов 241 Если между вершинами х,; и х" есть ребро, то между -й горизонтальной и -й вертикальной шинами устанавливается элемент 24 в проводящем направлении. По входу 14торые находятся не в нулевом состоянии, сбрасываются в нулевое состояние при переходе соответствующегоразряда регистров 8 -8 из "1" в "О".На вход элемента ИЛИ-НЕ 15 коммутируется (К+1)-й выход дешифратора,где К - количество вершин в исследуемом графе. Максимальное количество вершин равно числу п, После этогоустройство готово к работе. ОПри.подаче на вход 22 единичногопотенциала через второй элемент И 20начинают проходить тактовые импульсыс генератора 21, Тактовые импульсыс выхода элемента И 20 поступают на 5один вход элемента И 19, на другойвход которого подается единичныйпотенциал с выхода элемента ИЛИ-НЕ 15,Тактовые импульсы с выхода элемента И 19 поступаот на счетный вход 20счетчика 18. В зависимости от состояния счетчика 18 на соответствующем выходе дешифратора появляетсяединичный потенциал, который открывает элементы И соответствующего 25столбца матрицы пМп элементов И9, -96, 1 О -10, 11 -11, 2 -12,13, -13 соответствующего регистра8-8, а также подается на вход соответствующей вертикальной шины наборного поля 23Выходы вертикальных шин наборного поля 23 подключены к первым входам элементов И 21 -2,на вторые входы которых подаетсяединичный потенциал с выхода инвер 35тора 15. Тактовые импульсы с выходаэлемента И 19 поступают на управля-.ющий вход генератора 17 пакетов импульсов.и задним входом запускаютгенератэр после чего тот выдает па40кет из п импульсов, задержанных относительно начала тактового импульса на величину , = (Фиг. 4 ги д), Счетчики 3,-3, 4,-4, 5 -56 -61, 7 -7 , рассчитаны на подсчет45(п)-го импульса, так как максимальиый путь в графе между двумявершинами равен п, где п - количество вершин в графе. С приходомп-го импульса счетчики сбрасывают50ся в нулевое состояние.Пример работы устройства. Исследуемый граф изображен на фиг, 2,временные диаграммы работы устройства - на Фиг. 4.55При.поступлении первого тактовогоимпульса на первом выходе дешифрато- .ра появляется напряжение .логической единицы ("Фиг. 4 б), Генератор пакетовимпульсов запускается и выдает. пакетиз и импульсов (фиг, 4 г). Напряжениелогической "1" с первого выхода дешифратора 16 поступает на первыевходы элементов И 9, -9, и открываетих. Кроме того,;это же напряжениепоступает на один вывод первой вертикальной шины 25, наборного поля 23,на котором набрана топология исследуемого графа (фиг. 1). С другоговывода шины 25, это напряжение поступает на элемент И 2 который открыт напряжением логической "1"с выхода элемента ИЛИ-НЕ 15, С выхода элемента И 2 (фиг. 4 д) напряжение логической "1" поступает насхему И 9 и записывает в первыйразряд регистра Я"1". Кроме того,это напряжение поступает на линию 1,задержки и через нее задержанное время Тм =С; - на горизонтальную шину 26, наборного поля 23. Напряжение логической "1" с инверсноговыхода первого разряда регистра 8, при его переходе в единичное состояние пропадает (фиг. 4 е), запрещая тем самым запись в индикаторный счетчик 3, импульсов с генератора 17, так как первый импульс пакета задержки на величинуТ , = (фиг, 4 д и а), Первый импульс пакета записывается во все счетчики 3,-3, 4 -4,ме счетчи ка З.Напряжение логической "1" с горизонтальной шины 26 наборного по" ля 23 через элемент 24 попадает на вертикальную шину 25 , через элемен" ты И 2 и 9 записывает "1" в третий разряд регистра 8 и запрещает дальнейшую запись импульсов в счетчик Зз (фиг. 4 з). Поэтому второй импульс запишется только в счетчике 3 ,3 Напряжение логической "1" с выхода элемента И 25 поступает на вход линии 1 задержки и через нее - на5горизонтальную шину 26 наборного поля 23, а затем через коммутирующий элемент 24, элемент И 2, записывает вчетвертый разряд регистра 8 "1", запрещая тем самым дальнейшую запись импульсов в счетчик 34 (Фиг. 4 к). После этого во все счетчики, кроме счетчиков Зу, 35 и 34 запишутся пимпульсов, а затеми-й импульс, сбросив их содержимое в 03 1Таким образом, в первой строкематрицы расстояний после первоготакта. работы (счетчики 3, -3 ) будетзаписано 0012 (фиг. 3), а во всехостальных счетчиках будут записанынули, Аналогично будет работать устройство и во втором, третьем и четвертом тактах, С приходом пятоготактового импульса на пятом выходедешифратора 16, который скоммутирован на вход элемента ИЛИ-НЕ 15, по,является напряжение логической "1",которое через элемент ИЗИ-НЕ 15 запрещает дальнейшую работу устройства.В первых четырех разрядов регистров8 8 8 . и 8 записывается матрица достижимостей графа (фиг. 2), ав индикаторных счетчиках 3-3,4 5,-5 , 6 -6 ,записывается4 Ф. матрица расстояний (фиг, 3) исследуемого графа (Фиг, 2). Во всех остальных разрядах регистров и счетчиках будут записаны нули,Формула изобретенияУстройство для исследования параметров ориентированных графов, содержащее генератор тактовых импульсов, группу из и элементов И (где и - максимально возможное количество исследуемого графа), два эле-.мента И, матрицу идти элементов И, элемент ИЛИ-НЕ, дешифратор, счетчик, и регистров, коммутирующие элементы, наборное поле, содержащее вертикальные и горизонтальные шины, горизонтальные шины. наборного поля через коммутирующие элементы соединены с соответствующими вертикальными шинами в соответствии с монологией графа, один выход каждой вертикальной шины наборного поля подключен к первому входу одноименного элемента И группы, выход которого подключен к первым входам элемента И одноименной строки матрицы из и)и элементов И, вторые входы всех элемен 259281 Ьтов И группы объединены и подключены к выходу элемента ИЛИ-НЕ, выхщткаждого -го элемента И каждого дго столбца матрицы из идти элемен 5тов И подключен к "му информационному входу группы. входов 1-го регистра (где .)=-1, 2, 3,; и) входыначальной установки всех регистрови счетчика объединенй и являются 10 Входом начальной установки устройст-ва, счетный вход счетчика. соединенс вьгходом первого элемента И, первый вход которого подключен к выходувторого элемента И, а второй выход - 15 к выходу элемента ИЛИ-НЕ, группавходов которого подкл 1 очена к выходамдешифратора, выход счетчика подключен к входу дешифратора, первый входвторого элемента И является входом 20 запуска устройства, а второй входподключен к выходу генератора тактовых импульсов, вторые входы всехэлементов И каждого -го столбцаматрицы из пхи элементов И объединер 5 ны и подключены к -му выходу дешифратора, другой выход каждой вертикальной шины наборного поля подключен к одноименному выходу дешифратора, о т л и ч а ю щ е е с я тем, ЗО что, с целью расширения функциональных воэможностей за счет определениядлины пути между вершинами, в неговведены генератор пакетов импульсов,и групп индикаторных счетчиков по исчетчиков в каждой, группа из и элементов задержки, выходы которых соединены с горизонтальными шинами наборного поля, а.вход каждого элемента задержки группы подключен к 4 О выходу одноименного элемента И группы, вход запуска генератора запускапакетов импульсов подключен к выходупервого элемента И, а выход подключен к счетным входам всех индикатор Яых счетчиков Группы, ВхоД сбросакаждого -го индикаторного счетчикаФкаждой -й Группы подключен к мувыходу группы выходов 1-го регистра.1259281 Составитель Т. СапунЯцола Техред И.Попович уска Орректо дак одпиР/5 Производственно-полиграфическое предприятие Ужгород, ул. Проектна аказ 5123/47 ВНИИПИ по 113035, Тира осударст лам изобсква, Женного комитета С етений и открытий 5, Раушская наб.,