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

408312 ОПИСАНИЕ ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУСоюз Советских Социалистических РеспубликЗависимое от авт, свидетельстваЗаявлено 09 У 11.1971 ( 1680876/18-24)с присоединением заявкиПриоритет М, Кл. б 06 15/20 государственнай комитетСовета Министров СССРно делам изобретенийи аткрмтий Опубликовано 10.Х 11.1973, Бюллетень47Дата опубликования описания 29.111,1974 УДК 681.33.157.001Авторизобретения В, В. Епихин Заявитель УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ Изобретение относится к вычислительнойтехнике и может быть использовано для исследования характеристик графов, в частности для определения доступности графа дляипроизвольной вершины , т. е. величиныд.(/), где- произвольная вершина графа,п - число вершин графа, А,; - расстояниемежду вершинамии /.Известно устройство для определения расстояния между вершинами графа, содержащее запоминающие триггеры вершин, многовходовые схемы ИЛИ, ключи, двухвходовую схему ИЛИ, управляемые ключевыесхемы, управляющие входы которых подключены к единичным выходам запоминающихтриггеров вершин, а выходы соединены между собой в схему, отображающую граф, распределитель с шиной окончания испытаний,линию задержки, счетчик, шину тактовыхимпульсов и шину установки в исходное состояние.Однако при использовании известного устройства требуется много времени.Целью изобретения является сокращениевремени определения доступности графа дляпроизвольной вершины,Для этого в устройстве выходы управляемых ключевых схем подключены ко входаммноговходовых схем ИЛИ, выходы многовходовых схем ИЛИ подключены к единичным входам запоминающих триггеров вершин, причем единичный вход запоминающего триггера исследуемой вершины соединен с выхо дом двухвходовой схемы ИЛИ, единичныевходы запоминающих триггеров остальных вершин подключены к первым входам ключей, выходы распределителя подключены ко вторым входам ключей, выходы которых соеди иены между собой и подключены к нулевымвходам запоминающих триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы 15 ИЛИ, шина тактовых импульсов подключена к первому входу счетчика и входу управляемой ключевой схемы исследуемой вершины, а шина установки в исходное состояние соединена со счетными входами запоми нающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы ИЛИ.На чертеже приведена блок-схема устройства.25 Устройство содержит запоминающие триггеры 1 с единичными входами 2, нулевыми входами 3 и единичными выходами 4, управляемые ключевые схемы 5 со входами 6 и выходами или входами 7, многовходовые схе мы ИЛИ 8, ключи 9, распределитель 10,линию задержки 11, двухвходовую схему35 40 45 50 55 60 65 ИЛИ 12, счетчик 13, шину 14 установки, шину 15 тактовых импульсов и шину 16 окончания испытания.Выходы 7 управляемых ключевых схем 5 соединены между собой в схему, отображающую граф,Работа устройс-ва рассматривается па примере определения доступности графа для первой вершины. Для этого шину 15 подключают ко входу 6 управляемой ключевой схемы 5 первой вершины, а выход схемы ИЛИ 12 подключают к единичному входу 2 запоминающего триггера 1 первой вершины. После этого по шине 14 поступает импульс, по которому устройство устанавливается в исходное состояние, при этом счетчик 13 находится в нулевом положении, распределитель 10 находится в первом положении и на его первом выходе имеется потенциал, запоминающий триггер 1 первой вершины находится в единичном положении (устанавливается через схему ИЛИ 12), а запоминающие триггеры остальных вершин находятся в нулевом положении,Запоминающий триггер 1 первой вершины открывает управляемую ключевую схему 5 первой вершины и между ее входом 6 и выходами 7 образуется электрический контакт.Распределитель 10 первым выходом открывает ключ 9, подключенный к единичному выходу 4 запоминающего триггера 1 второй вершины (каждый -ый выход распределителя 10 подключен ко входу ключа 9, второй вход которого подключен к единичному выходу 4 запоминающего триггера 1 соответствующего (+1) вершине).После установки устройства в исходное состояние по шине 15 начинают поступать тактовые импульсы на вход счетчика 13 и на вход 6 управляемой ключевой схемы 5 первой вершины. Через выходы 7 открытой управляемой схемы 5 первой вершины импульс поступает на входы 7 управляемых ключевых схем 5, соответствующих вершинам графа, расстояние до которых от первой вершины равно единице. Со входов 7 управляемых ключевых схем 5 этих вершин импульс через схемы ИЛИ 8 перебрасывает запоминающие триггеры 1 в единичное положение. Открываются соответствующие управляемые ключевые схемы 5 и между входами 6 и выходами 7 этих управляемых ключевых схем 5 образуется электрический контакт.Второй импульс, поступающий по шине 15, перебросит в единичное положение запомичающие триггеры 1 вершин, расстояние до которых от первой вершины равно двум.Время срабатывания управляемых ключевых схем 5 должно превышать длительность импульса, поступающего по шине 15.Таким образом, запоминающий триггер 1 вершины (исключая первую) перебросится в единичное положение после серии импульсов,5 10 15 20 25 30 равной расстоянию до этой вершины от первой.Как только запоминающий триггер 1 второй вершины перебросится в единичное положение после А импульсов (/г, - расстояние от первой вершины до второй), поступивших по-шине 15, через ключ 9 поступит импульс с этого запоминающего триггера 1 ца сброс всех запоминающих триггеров 1 в нулевое положение и на вход линии задержки 11.С выхода линии задержки импульс переводит распределитель 10 во второе положение и через схему ИЛИ 12 устанавливает запоминающий триггер 1 первой вершины в единичное положение.Устройство устанавливается в положение для определения расстояния от первой вершины до третьей. Последующие й импульсов (Й - расстояние от первой вершины до третьей), поступающие по шине 15, приведут устройство в положение для определения рас. стояние от первой вершины до. четвертой и т. д.При переходе распределителя 10 из (и - 1) положения в г положение (и - число вершин графа) на шине 16 появляется сигнал окончания испытания, по которому прекращается поступление тактовых импульсов по шине 15.Счетчик 13 показывает величину, равную /г+Й,++Й - ь т. е. доступности графа для первой вершины.Предмет изобретенияУстройство для исследования графов, содержащее запоминающие триггеры вершин, многовходовые схемы ИЛИ, ключи, двухвходовую схему ИЛИ, управляемые ключевые схемы, управляющие входы которых подключены к единичным выходам запоминающих триггеров вершин, а выходы соединены между собой в схему, отображающую граф, распределитель, линию задержки, счетчик, шину тактовых импульсов и шину установки в исходное состояние, о т л и ч а ю щ е е с я тем, что, с целью сокращения времени определения доступности графа для произвольной вершины, в нем выходы управляемых ключевых схем подключены ко входам многовходовых схем ИЛИ, выходы многовходовых схем ИЛИ подключены к единичным входам запоминающих триггеров вершин, причем единичный вход запоминающего триггера исследуемой вершины соединен с выходом двухвходовой схемы ИЛИ, единичные выходы запоминающих триггеров остальных вершин подключены к первым входам ключей, выходы распределителя подключеныко вторым входам ключей, выходы которых соединены между собой и подключены к нулевым входам запоминающих триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы ИЛИ, шина тактовых импульсов подключена к первому входу счетчика и входу упТехред Л. Богданова Редактор А. Зп ньковский Заказ 847/16 Изд309 Тираж 647 Подписное ЦИИИПИ Государственного комитета Ссвета Министров СССР по делам, изобретений и открытий Москва, Ж.35, Раушская наб., д, 4/5Типография, пр, Сапунова, 2 5равляемой ключевой схемы исследуемой вершиины, а шина установки в исходное состояние соединена со счетными входами запоминающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы ИЛИ,