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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН ЯО 14117 3 6 Р 15/2 ПИС ОБРЕТЕНИЯ ДЛЯ ИССЛЕДОВАНИтся к выч ке и может быть едования достижи1(54) УСТРОЙСТФОВ (57) Изобретелительной тех ГРА ие относи ос ля и менен верши до ри .решении задачетико-графовое прью изобретения яфункциональных втва за счет опрей и ус к ающих т е ставление, Ц вляет- змож- елея расширени остей устро ния ма следуемого ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЪСТВ(22) 18 .03.87 (46) 23,07.88. Бюп. Яф 27 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О,Н.Костюк и Г.В.Моисеенко (53) 681.333(088,8) (56) Авторское свидетельство СССР В 1218392, кл. С 06 Г 15/20, 1986.Авторское свидетельство СССР Нф 1174937, кл. С 06 Г 15/20. 1985.6 раниченных достижмостейграфаУстройство содер1411773 Изобретение относится к вычислительной технике и может быть использовано для исследования достижимости вершин графа, а также для автоматизированного решения задач обработки информации, допускающих теоретикографовое представление.Цель изобретения - расширение Функциональных возможностей устройстваэа счет определения матриц ограниченных достижимостей исследуемого графа,На чертеже приведен пример реали-.зации структурной схемы устройства.Устройство содержит генератор 1тактовых импульсов, элемент И 2, элемент НЕ 3, группу из и элементов И 4,.матрицу из и х и моделей 5; дуг,каждая из которых состоит иэ элементаИ 6, первого 7 и второго 8 триггеров, дешифратор 9, счетчик 10,выход 11 признака окончания работыустройства, группу из и элементов ИЛИ12, группу из и элементов 13; задержки, группу из и триггеров 14, регистр 15, реверсивный счетчик 16, Формирователь 17 импульсов, элемент 18задержки, вход 19 признака ограничения достижимости устройства, вход 20Начальной установки устройства и вход21 пуска устройства.Устройство работает следующим образом.В исходном состоянии сигнал "Пуск"21 отсутствует, что блокирует прохождение импульсов с генератора 1 черезэлементы И 2, на выходе которого присутствует логический "0", блокируюпий работу триггеров 14 и элементовИ 6 моделей 5 дуг, счетчик 10 обнуленсигналом 20 начальной .установки, на На каждом 3-ом шаге осуществляется Формирование 3-й строки матрицы достижимостей (3 1,и) следующим обра- зоме жит генератор тактовых импульсовэлементы 2 И, 3 НЕ, 4 И, матрицу моделей дуг 5 из элемента 6 И и триггеров 7,8, дешифратор 9, счетчик 10,выходы которого подключены к входамдешифратора 9, соединенного выходамис первыми входами элементов 4 И, элементы задержки 13, триггеры 14, регистр 15, реверсивный счетчик 16, инФормационные входы которого нодключены к выходам регистра 15. Информацияо топологии графа заносится в триггеры 7 моделей дуг 5, а значение числаограничения достижимости - в регистр15, При работе устройства происходитпреобразование исходной информациив матрицу ограниченной достижимостис заданным числом ограничения, которая заносится в триггеры Я моделейдуг 5. 1 ил,выходах дешифратора 9 с первого по (и+1)-й сигналы логического "О", блокирующие прохождение сигналов разрешения записи к вторым триггерам 8 моделей 5 дуг, состояние триггеров 14 и реверсивного счетчика 16 - произвольное.Исходная информация о топологии исследуемого графа заносится в виде матрицы смежности в триггеры 7 моделей 5 дуг через информационные входы устройства, значение числа К ограничения достижимости заносится через входы 19 в регистр 15 по сигналу 20 начальной установки, одновременно устанавливаются в "О" счетчик 10, после чего устройство готово к работе.При подаче на выход 11 сигнала "Пуск", уровня логической "1", импульсы с генератора 1 через элемент И 2, открытый по третьему входу логической "1" с выхода элемента НЕ 3, начинают поступать к реверсивному счетчику 16, который переполняется и на его выходе отрицательного переполнения появляется сигнал логической "1", обеспечивающей выработку формирователем 17 сигнала обнуления триггеров 14, по которому также осуществляется перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение содержимого счетчика 10 на "+1 ф. После этого устройством отрабатывается цикл, содержащий и шагов по числу строк матрицы достижимостей.После (1-1)-го шага содержимое счетчика 10 равно 1-1 р а 1-ый шаг начинается с его увеличения на единицу сигналом с выхода элемента 18 задерж 5 ки с одновременным обнулением триггеров 14 и перезаписью кода числа ограничения достижимости с регистра 15 в реверсивный счетчик 16, Обнуление 1 риггеров 14 обеспечивает наличие логического "0" на выходах всех элементов И б моделей 5 дуг. Состояние счетчика 10 преобразуется дешифратором 9 в унитарный код вида ООО,1103Од, р где 1 - номер выхода дешифратора 9. "1" с 1-го выхода дешифратора 9 поступает через элемент ИЛИ 12 на информационный вход триггера 14 й и по первому на данном шаге сигналу с генератора 1 тактовых 20 импульсов записывается в триггер 14 в остальные триггеры 14 р первоначально переписывается "0" с выходов элементов ИЛИ 12 р (1 = 1,п, 1 Ф 1)р поскольку на входах этих элементов при сутствуют только "0" с выходов дешифратора 9 и выходов элементов И 6 моделей 5 дуг. "1" с выхода триггера 14 й р задержанная элементом 13 задержки на время окончания тактового им-ЗО пульса с генератора 1, поступает к элементам И бЬ = 1,п) и появляется на выходе только тех элементов И 6 моделей 5дуг, у которых соот 3 иветствующие им первые триггеры 7 моделей дуг содержат "1". Множество ,и 1 ср 1 с = 1 рп в исследуемом графе соответствует индексам вершин достижимых из вершины 1 с числом достижимости, равным единице. Сигналы с 40 выходов элементов И 6 поступают3 кк соответствующим триггерам 14, через элементы ИЛИ 12 . По следующему сигналу с генератора 1 тактовых импульсов логическая 1 записывается 45 в эти триггеры 14, и аналогичным образом сформнронано мноиестео р.,з се, фиксируемое установкой в длительное единичное состояние триггеров 14 р, где 1 = Е О К 2, а Е - индексы вершин достижимых из в ршины 1 с числом достижимости, равным двум. Уставка триггеров 14 осуществляется в момент появления следующего тактового сигнала и так до появления (К+1)- 55 го тактового сигнала, когда в единичное состояние установлены триггеры .14 . Р - индексы вершин достижимых в исследуемом графе из вершины с числом ограничения достижимостиКр т.е. р = з,н Н р.рН, ото соответствует строке 1 матрицы ограниченной достижимости исследуемого графа. Появление (и+1)-го тактового сигнала вызывает отрицательное переполнение реверсивного счетчика 16, сигнал отрицательного переполнения со счетчика 16 через формирователь 17 и элемент И 4 обеспечивает прохождение сигнала разрешения записи к вторым триггерам 8 строки 1 матрицы модепей дуг, в которых занесена информация с выходов триггеров 14, представляющая собой строку 1 матрицы ограниченной достижимости. Сигнал с формирователя 17, задержанный элементом 18 задержки на время, необходимое для занесения информации во вторые триггеры 8 моделей 5 дуг, обеспечивает обнуление триггеров 14, перезапись содержимого регистра 15 в реверсивный счетчик 16 и изменение состояния счетчика 10 на 1+1, После этого устройством отрабатывается Я+1)-й шаг, по окончании которого сформулирована (1+1) -я строка матрицы ограниченной достижимости графа и так до окойчания шага и, когда сформирована последняя строка матрицы достижимости ограниченной числом К. Переход счетчика 10 в состояние и+1 вызывает появление логической "1 Г на (п+1)-м вьмоде дешифратора 9, которая после инвертирования в элементе НЕ 3 обеспечивает блокировку прохождения импульсов с генератора 1 через элемент И 2, а также служит сигналом 11 окончания работы устройства, По этому сигналу с входа устройства снимается сигнал 21 "Пуск" и устройство после занесения новой информации о значении числа 12 ограничения достижимости или новой исходной информации о топологии исследуемого графа готово к следующему циклу работы по определению матрицы ограниченной достижимости для данного исследуемого графа.Формула изобретенияУстройство для исследования графов, содержащее генератор тактовых импульсов, элемент И, элемент НЕ, группу из и элементов И матрицу моделей дуг из и х и элементов И (и - число вершин графа), дешифратор и счетчик, выходы которого соединены сЗаказ 3656/46 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 5 14117 соответствующими инФормационными входами дешифратора, первый вход элемента И является входом пуска устройства, второй вход элемента И соединен5 с выходом генератора тактовых импуль; сов, третий вход элемента И соединен ,с выходом элемента НЕ, вход которого ,соединен с (и+1)-м выходам дешифратара, о т л и ч а ю щ е е с я тем, 10 что, с целью расширения функциональных возможностей устройства за счет ,определения матриц ограниченных дастижимостей исследуемого графа, в него введены группа из и элементов ИЛИ, группа из и элементов зйдер,жки, группа из п триггеров, регистр, реверсивный счетчик, формирователь импульсов, и элемент задержки,. причем каждая модель дуги матрицы росодержит первый и второй триггеры, выход элемента задержки соединен с входами установки в ноль всех триггеров группы, с счетным входом счетчика и с входом разрешения записи ревер сивного счетчика, информационные вхо,ды которого соединены с соответствующими выходами регистра информаФционные входы которого являются входом признака ограничения достижимос- ЗО ти устройства, 3-й выход дешифратора Ц = 1,п) соединен с (и+1)-м входом 1-го элемента ИЛИ группы и с первым входом 1-го элемента И группы, второй вход которого соединен с вторыми 35 входами всех элементов И группы, с входом 1-го элемента задержки (х1,п, х = 3) и с выходом формирователя импульсов, вход которого соединен с выходом признака переполнения реверсивного.счетчика, выход 1-го элемента И группы соединен с входами синхронизации всех вторых триггеров мдделей дуг х-й строки матрицы (1 п, 1 =,1), входы установки в п 111 всех вторых триггеров моделей дуг го столбца матрицы соединены с выхо-, дом 1-го триггера группы и входом 1- го элемента задержки группы, выход которого соединен с первым входом всех элементов И моделей дуг -й страки матрицы, второй вход элемента И ,-й модели дуги матрицы соединен с выходом первого триггера этой модели, выход элемента И ,1-й модели дуги матрицы соединен с х-и входом (3. = - 1,п) 1-го Ц = 1,п) элемента ИЛИ группы, выход которого соединен с входом установки в "1" 1-го триггера группы, вход синхронизации которого соединен с входаьж синхронизации всех триггеров группы, с выходом элемента И и с счетным входом реверсивного счетчика, вход установки в "0" счетчика соединен с входом разрешения записи информации регистра и является входом начальной установки устройства, входы установки в " 1" первых триггеров моделей дуг матрицы являются информационным входом устройства, вы-ф ходы вторых триггеров моделей дуг матрицы являются информационным выходом устройства, (и+1)-й выход дешифратора является выходом окончания работы устройства.