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

 

408312

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 09Х11.1971 (№ 1680876/18-24) с присоединением заявки №

Приоритет

М, Кл. G 061 15/20

Государственный комитет

Совета Министров СССР но делам изобретений и открытий

Опубликовано 10.Х11.1973, Бюллетень № 47

Дата опубликования описания 29.Ш,1974

УДК 681.33.157.001 (088,8) Автор изобретения

В. В. Епихин

Заявитель

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

Изобретение относится к вычислительной технике и может быть использовано для исследования характеристик графов, в частности для определения доступности графа для и произвольной вершины i, т. е. величины g Ch.

j= l (j®i) где — произвольная вершина графа, п — число вершин графа, C„,; — расстояние между вершинами i u j.

Известно устройство для определения расстояния между вершинами графа, содержащее запоминающие триггеры вершин, многовходовые схемы «ИЛИ», ключи, двухвходовую схему «ИЛИ», управляемые ключевые схемы, управляющие входы которых подключены к единичным выходам запоминающих триггеров вершин, а выходы соединены между собой в схему, отображающую граф, распределитель с шиной окончания испытаний, линию задержки, счетчик, шину тактовых импульсов и шину установки в исходное состояние.

Однако при использовании известного устройства требуется много времени.

Целью изобретения является сокращение времени определения доступности графа для произвольной вершины, Для этого в устройстве выходы управляемых ключевых схем подключены ко входам многовходовых схем «ИЛИ», выходы многовходовых схем «ИЛИ» подключены к единичным входам запоминающих триггеров вершин, причем единичный вход запоминающего триггера исследуемой вершины соединен с выходом двухвходовой схемы «ИЛИ», единичные входы запоминающих триггеров остальных вершин подключены к первым входам ключей, выходы распределителя подключены ко вторым входам ключей, выходы которых соединены между собой и подключены к нулевым входам запоминающих триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы

15 «ИЛИ», шина тактовых импульсов подключена к первому входу счетчика и входу управляемой ключевой схемы исследуемой вершины, а шина установки в исходное состояние соединена со счетными входами запоми20 нающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы «ИЛИ».

На чертеже приведена блок-схема устройства.

25 Устройство содержит запоминающие триггеры 1 с единичными входами 2, нулевыми входами 3 и единичными выходами 4, управляемые ключевые схемы 5 со входами 6 и выходами или входами 7, многовходовые схеч0 мы «ИЛИ» 8, ключи 9, распределитель 10, линию задержки 11, двухвходовую схему

408312

«ИЛИ» 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 соответствующего (i+1) вершине).

После установки устройства в исходное состояние по шине 15 начинают поступать тактовые импульсы на вход счетчика 13 и на вход 6 управляемой ключевой схемы 5 первой вершины. Через выходы 7 открытой управляемой схемы 5 первой вершины импульс поступает на входы 7 управляемых ключевых схем 5, соответствующих вершинам графа, расстояние до которых от первой вершины равно единице.

Со входов 7 управляемых ключевых схем

5 этих вершин импульс через схемы «ИЛИ» 8 перебрасывает запоминающие триггеры 1 в единичное положение. Открываются соответствующие управляемые ключевые схемы 5 и между входами 6 и выходами 7 этих управляемых ключевых схем 5 образуется электрический контакт.

Второй импульс, поступающий по шине 15, перебросит в единичное положение запомичающие триггеры 1 вершин, расстояние до которых от первой вершины равно двум.

Время срабатывания управляемых ключевых схем 5 должно превышать длительность импульса, поступающего по шине 15.

Таким образом, запоминающий триггер 1 вершины (исключая первую) перебросится в единичное положение после серии импульсов, 5

65 равной расстоянию до этой вершины от первой.

Как только запоминающий триггер 1 второй вершины перебросится в единичное положение после А импульсов (/: — расстояние от первой вершины до второй), поступивших по-шине 15, через ключ 9 поступит импульс с этого запоминающего триггера 1 ца сброс всех запоминающих триггеров 1 в нулевое положение и на вход линии задержки 11.

С выхода линии задержки импульс переводит распределитель 10 во второе положение и через схему «ИЛИ» 12 устанавливает запоминающий триггер 1 первой вершины в единичное положение.

Устройство устанавливается в положение для определения расстояния от первой вершины до третьей. -Последующие и импульсов (kq — расстояние от первой вершины до третьей), поступающие по шине 15, приведут устройство в положение для определения расстояние от первой вершины до. четвертой и т. д.

При переходе распределителя 10 из (n — 1) положения в и положение (n — число вершин графа) на шине 16 появляется сигнал окончания испытания, по которому прекращается поступление тактовых импульсов по шине 15.

Счетчик 13 показывает величину, равную

k +kq+ ... +k <, т. е. доступности графа для первой вершины.

Предмет изобретения

Устройство для исследования графов, содержащее запоминающие триггеры вершин, многовходовые схемы ИЛИ», ключи, двухвходовую схему «ИЛИ», управляемые ключевые схемы, управляющие входы которых подключены к единичным выходам запоминающих триггеров вершин, а выходы соединены между собой в схему, отображающую граф, распределитель, линию задержки, счетчик, шину тактовых импульсов и шину установки в исходное состояние, о т л и ч а ю щ е е с я тем, что, с целью сокращения времени определения доступности графа для произвольной вершины, в нем выходы управляемых ключевых схем подключены ко входам многовходовых схем «ИЛИ», выходы многовходовых схем

«ИЛИ» подключены к единичным входам запоминающих триггеров вершин, причем единичный вход запоминающего триггера исследуемой вершины соединен с выходом двухвходовой схемы «ИЛИ», единичные выходы запоминающих триггеров остальных вершин подключены к первым входам ключей, выходы распределителя подключены ко вторым входам ключей, выходы которых соединены между собой и подключены к нулевым входам запоминающих триггеров всех вершин и ко входу линии задержки, выход которой подключен к первому входу распределителя и к первому входу двухвходовой схемы

«ИЛИ», шина тактовых импульсов подключена к первому входу счетчика и входу уп408312

Составитель В. Озеров

Корректоры: Е. Давыдкина и В. Петрова

Техред Л. Богданова

Редактор A. Зпньковский

Заказ 847 16 Изд. № 309 Тираж 647 Подписное

ЦИИИПИ Государственного комитета Ссвета Министров СССР по делам .изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5 типография, пр. Сапунова, 2

5 равляемой ключевой схемы исследуемой вершиины, а шина установки в исходное состояние соединена со счетными входами запоминающих триггеров всех вершин, кроме исследуемой, и со вторыми входами распределителя, счетчика и двухвходовой схемы «ИЛИ».