1
Изобретение относится к вычислительной технике и может быть исиользовано для исследования характеристик графов, в частности для определения доступности графа для произвольной вершины i, т. е. величины 2 ij
(), где i - произвольная вершина графа, п - число вершин графа, dj, j - расстояние между вершинами i и /.
Известно устройство для определения расстояния между вершинами графа, содержаш.ее запоминаюшие триггеры вершин, многовходовые схемы «ИЛИ, ключи, двухвходовую схему «ИЛИ, управляемые ключевые схемы, управляюшие входы которых подключены к единичным выходам запоминаюших триггеров вершин, а выходы соединены между собой в схему, отображаюш,ую граф, распределитель с шиной окончания испытаний, линию задержки, счетчик, шину тактовых импульсов и шину установки в исходное состояние.
Однако при использовании известного устройства требуется много времени.
Целью изобретения является сокращение времени определения доступности графа для произвольной вершины.
Для этого в устройстве выходы управляемых ключевых схем подключены ко входам многовходовых схем «ИЛИ, выходы многовходовых схем «ИЛИ подключены к единичным входам запоминаюш,их триггеров вершин, причем единичный вход запоминаюш,его триггера исследуемой вершины соединен с выходом двухвходовой схемы «ИЛИ, единичные
/I входы запоминающих триггеров остальных вершин подключены к первым входам ключей, выходы распределителя подключены ко вторым входам ключей, выходы которых соединены между собой и подключены к нулевым входам запоминающих триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы
«ИЛИ, шина тактовых импульсов подключена к первому входу счетчика и входу управляемой ключевой схемы исследуемой вершины, а шина установки в исходное состояние соединена со счетными входами запоминающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы «ИЛИ. На чертеже приведена блок-схема устройства.
Устройство содержит запоминающие триггеры 1 с единичными входа.ми 2, нулевыми входами 3 и единичными выходами 4, управляемые ключевые схемы 5 со входами 6 и выходами или входами 7, многовходовые схемы «ИЛИ 8, ключи 9, распределитель 10, линию задержки 11, двухвходовую схему 3 «ИЛИ 12, счетчик 13, шину 14 установки, шину 15 тактовых импульсов и шину 16 окончания испытания. Выходы 7 управляемых ключевых схем 5 соединены между собой в схему, отображаю-5 щую граф. Работа устройства рассматривается па при- .мере определения доступности графа для первой вершины. Для этого шину 15 подключают ко входу 6 управляемой ключевой схе-Ю мы 5 первой вершины, а выход схемы 12 подключают к единичному входу 2 запоминающего триггера 1 первой вершины. После этого по шине 14 поступает импульс, по которому устройство устанавливается в15 исходное состояние, при этом счетчик 13 находится в нулевом положении, распределитель 10 находится в первом .положении и на его первом выходе имеется потенциал, запоминающий триггер 1 первой вершины нахо-20 дится в единичном положении (устанавливается через схему «ИЛИ 12), а запоминающие триггеры остальных вершип находятся в нулевом положении. Запоминающий триггер 1 первой вершины25 открывает управляемую ключевую схему 5 первой вершины и между ее входом 6 и выходами 7 образуется электрический контакт. Распределитель 10 первым выходом открывает ключ 9, подключенный к единичному вы-30 ходу 4 запоминаюшего триггера 1 второй вершины (каждый t-ый выход распределителя 10 подключен ко входу ключа 9, второй вход которого подключен к единичному выходу 4 запоминающего триггера 1 соответ-35 ствующего (г+1) вершине). После установки устройства в исходное состояние по щине 15 начинают поступать тактовые импульсы на вход счетчика 13 и на вход 6 управляемой ключевой схемы 5 пер-40 вой вершины. Через выходы 7 открытой управляемой схемы 5 первой вершины импульс поступает на входы 7 управляемых ключевых схем 5, соответствующих вершинам графа, расстояние до которых от первой вер-45 щины равно единице. Со входов 7 управляемых ключевых схем 5 этих верщин импульс через схемы «ИЛИ 8 перебрасывает запоминающие триггеры 1 в50 единичное положение. Открываются соответствующие управляемые ключевые схемы 5 и между входами 6 и выходами 7 этих управляемых ключевых схем 5 образуется электрический контакт.55 Второй импульс, поступающий по шине 15, перебросит в единичное положение запомичающие триггеры 1 вершин, расстояние до которых от первой вершины равно двум. Время срабатывания управляемых ключе-60 вых схем 5 должно превышать длительность импульса, поступающего по шине 15. Таким образом, запоминающий триггер 1 вершины (исключая первую) перебросится в единичное положение после серии импульсов,65 4 равной расстоянию до этой вершины от первой. Как только запоминающий триггер 1 второй вершины перебросится в единичное положение после ki импульсов (ki - расстояние от первой вершины до второй), поступивших ногшине 15, через ключ 9 поступит импульс с этого запоминающего триггера 1 на сброс всех запоминающих триггеров 1 в нулевое положение и на вход линии задержки 11. С выхода линии задержки импульс перевоДит распределитель 10 во второе положение и через схему «ИЛИ 12 устанавливает запоминающий триггер 1 первой вершины в единичное положение. Устройство устанавливается в положение для определения расстояния от первой вершипы до третьей. Последующие k импульсов (kz - расстояние от первой вершины до третьей), поступающие по шине 15, приведут устройство в положение для определения расстояпие от первой вершины до четвертой и т. д. При переходе распределителя 10 из (я-1) положения в л положение (я - число вершин графа) на шине 16 появляется сигнал окончания испытания, по которому прекращается поступлепие тактовых импульсов по шине 15. Счетчик 13 показывает величину, равную . т. е. доступности графа для нервой вершины. Иоедмет изобретения предмет изооретения Устройство для исследования графов, содержащее запоминающие триггеры вершин, многовходовые схемы ИЛИ, ключи, двухвходовую схему «ИЛИ, управляемые ключевые схемы, управляющие входы которых подключены к единичным выходам запоминающих триггеров верщин, а выходы соединены между собой в схему, отображаюшую граф, распределитель, линию задержки, счетчик, шину тактовых импульсов и шину установки в исходное состояние, отличаюшееся тем, что, с целью сокращения времени определения доступности графа для произвольной верщины, в нем выходы управляемых ключевых схем подключены ко входам многовходовых схем «ИЛИ, выходы многовходовых схем «ИЛИ подключены к единичным входам запоминающих триггеров верщин, причем единичный вход запоминающего триггера исследуемой верщины соединен с выходом двухвходовой схемы «ИЛИ, единичные выходы запомипающих триггеров остальных верщин подключены к первым входам ключей, выходы распределителя подключены ко вторым входам ключей, выходы которых соединены между собой и подключены к нулевым входам запоминаюших триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы «ИЛИ, щина тактовых импульсов подключена к первому входу счетчика и входу управляемой ключевой схемы исследуемой вершиины, а шина установки в исходное состояние соединена со счетными входами запоминающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы «ИЛИ.
