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

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