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

 

Изобретение относится к вычислительной технике и может быть использовано для определения параметров достижимости в ориентированных графах. Цель изобретения - расширение фyнкlI oнaльныx возможностей за счет нахождения баз ориентированного графа и определения их количественньк характеристик - достигается тем, что в устройство, содержащее генератор 1 импульсов, первьш счетчик 3, матрипу 4 элементов И, наборное поле 9, дополнительно введены элемент ИЛИ 2, группа 5 элементов ИЛИ, первый 6 и второй 7 блоки памяти , блок 8 определения мощности базы , элемент И 10, второй счетчик 11. 3 ил. g

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (112

4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

К A BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4215158/24-24 (22) 24.03.87 (46) 15,01.89. Бюл. N - 2 (71) Институт проблем надежности и долговечности машин АН БССР (72) А.И.Волошаненко, А.А.Чернык, Н.Н.Рожкевич и В.И.Исаев (53) 681..325 (088.8) (56) Авторское свидетельство СССР

Р 637822, кл. С 06 F 15/20, 1976.

Авторское свидетельство СССР

У 1174937, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для определения параметров достижимости в ориентированных графах. Цель изобретения — расширение функциональных возможностей за счет нахождения баз ориентированного графа и определения их количественных характеристик — достигается тем, что в устройство, содержащее генератор 1 импульсов, первый счетчик 3, матрицу 4 элементов И, наборное поле 9, дополнительно введены элемент ИЛИ 2, группа 5 элементов

ИЛИ, первый 6 и второй 7 блоки памяти, блок 8 определения мощности базы, элемент И 10, второй счетчик 11.

3 ил.

1451715

Изобретение относится к вычислительной технике и может быть использовано цля определения параметров достижимости в ориентированных графах.

Цель изобретения — расширение функциональных возможностей за счет нахождения баз ориентированного графа и определения их количественных характеристик.

На фиг,1 приведена структурная схема устройства; на фиг.2 - gapa@ на примере которого описывается рабо- та устройства; на фиг.3 — временная диаграмма работы устройства при определении параметров графа, изображенного на фиг. 2.

Устройство содержит генератор импульсов, элемент ИЛИ 2, первый 20 счетчик 3„ матрицу 4 элементов И, группу 5 элементов ИЛИ, первый блок

6 памяти, второй блок. 7 памяти, блок

8 определения мощности базы, наборное поле 9, элемент И 10, второй 25 счетчик 11.

Генератор 1 предназначен для синхронизации работы устройства; счетчик

3 — дчя перебора всех подмножеств

1вершин исследуемого графа; кроме того, с разряпных ьыходов этого счетчика двоичный код выбранного подмножества поступает на. информационные входы блока 6 памяти и разрядные входы блока 8 определения мощности базы.

Элементы И матрицы 4 предназначе35 ны для моделирования дуг графа. Единичный уровень сигнала на первом входе элемента И матрицы 4, поступающий от наборного поля 9, определяет нади-4 чие соответствующей ему дуги. ЕдиничJ ные уровни на вторых входах этих элементов, поступающие с выходов соответствующих элементов ИЛИ группы 5, соответствуют вершинам, принадлежащим всем ориентированным дугам, которые начинаются в вершинах, проверяемых на принадлежность базе.

Элементы. HJIN группы 5 предназначены для моделирования вершин графа.

Единичные уровни на нулевых входах этих элементов соотве-.ствуют вершинам, которые проверяются на принадлежность базе. Единичные уровни на входах. этих элементов поступающие

55 с выходов элементов И матрицы 4, соответствуют тем вершинам, в которые имеется достижимость из..вершин, проверяемых на.принадлежность базе, Блок 6 памяти предназначен для хранения информации о составе баз графа. В.конце работы устройства по каждому адресу блока 6 памяти, задействованному в процессе работы, хранится. двоичный код, ециничные разряды которого соответствуют номерам вершин, которые образуют текущую базу, Блок 7 памяти предназначен для хранения двоичных кодов, соответствующих мощностям баз, Эти двоичные коды записываются в блок 7 памяти с выхода .блока 8 определения мощности базы, Блок определения 8 мощности базы. предназначен для подсчета количества единиц в коде, поступающем со. счетчика 3, которое соответствует. количеству вершин в подмножестве, проверяемом на принадлежность базе.

Наборное поле 9 предназначено для ввода топологии графа перед началом моделирования. Элемент И 10 предназначен для проверки условия, во все ли вершины гр@фа имеется достижимость из подмножества вершин, проверяемых на принадлежность базе.

Счетчик 11 предназначен для подсчета количества баз графа и формирования соответствующих им адресов в первом блоке 6,памяти и во втором бло" ке 7 памяти.

Устройство работает следующим образом.

В соответствии с .топологией графа посредством наборного поля 9 единичные уровни должны быть поданы на элементы И 4,, 4z» что соответствует дугам из второй вершины в первую и из второй в третью. После введения топологии устройство инициируется путем подачи на его первый вход положительного запускающего импульса, который поступает на вход сброса счетчика 3 и вход вброса счетчика 11 и устанавливает эти счетчики в исходное (нулевое) состояние. При этом на выходе переполнения счетчика 3 устанавливается единичный уровень, который подается на вход генератора

1 и разрешает его работу. В исходном состоянии на выходе генератора

1 присутствует единичный потенциал, поэтому формирование импульсной последовательности, поступающей на счетный вход счетчика 3 и вход элемента

И 10, начинается с отрицательного перепада. По первому положительному

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

14517 перепаду уровня на выходе генератора 1 счетчик 3 устанавливается в состояние 001, при этом с его первого выхода единичный уровень поступает на вход 0 элемента ИЛИ 5,, проходит через него и поступает на первую строку, которая образована вторымн входами элементов И 4, . Поскольку ни на одном первом входе элементов

И 4 первый стрбки матрицы не при1 сутствует единичный уровень (в соответствии с топологией графа), а единичный уровень присутствует только на первом выходе счетчика 3, то на выходе элемента И 10 — низкий уровень. Это означает, что первая вершина не является базой графа. При поступлении на счетный вход счетчика 3 второго положительного перепа- 2О да счетчик устанавливается в состояние 010. При этом с второго выхода счетчика 3 высокий уровень поступает на вход 0 элемента ИЛИ 5<, проходит через него и далее поступает на вто- 25 рую строку, которая образована вторыми входами элементов И 4 . Поскопьку в соответствии с топологией графа на первые входы элементов

И 4,, 4z> поданы высокие уровни, то на их выходах также формируются высокие уровни, которые поступают на вторые входы элементов KIN 5<, :5 . Таким образом, на всех входах элемента И 10 присутствуют высокие уровни. Поэтому на его выходе также

35 формируется высокий уровень..По поло.= ,жительному перепаду уровня на. выходе элемента И 10, который поступает на . вход W записи блока 6 памяти и вход запуска блока 8 определении мощности базы, в нулевой адрес блока 6 памяти

,записывается код 010, соответствую\ щий тому, что базой данного графа является вторая вершина. Одновремен- 45 но запускавтся блок 8 определения мощности базы, которьпЪ преобразует код 010, поступающий на его входы с первого по третий, в код 001, который в двоичной форме соответствует тому, что мощность базы равна 1. По отрицательному перепаду уровкя на выходе элемента И 10 который поступает на вход записи, этот код записывается по нулевому адресу блока 7 памяти.

По этому же перепаду уровня счетчик

11 с задержкой, определяемой параметрами элемента ИЛИ 2, устанавливается в следующее состояние,и спустя время

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

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

6 памяти записывается двоичный код, соответствующий составу базы, т ° е. номера единичных разрядов этого кода соответствуют номерам вершин, образующих базу; с помощью блока 8 определения мощности. базы производится подсчет количества единиц в коде состава базы, что соответствует количеству вершин, входящих в базу, или ее мощности, При этом на выходе блока

8 .определения мощности базы формируется двоичный код, соответствующий мощности базы; с выхода блока 8 определения мощности базы двоичный код записывается.по.тому же адресу, что и код.состава базы, но в блок 7 памя- . ти;.далее происходит. смена адреса блоков 7 и 6 памяти.

Аналогичньпч образом устройство работает до тех пор, пока в счетчике

3 не будет выполнен перебор всех подмножеств вершин. После завершения перебора подмножеств вершин графа на выходе переполнения счетчика 3 устанавливается низкий потенциал, который запрещает работу генератора 1.

В результате работы устройства получается. следующая информация о базах графа: состояние счетчика 11 соответствует количеству баз графа М;.по каждому адресу блока 6 памМти хранится двоичный код состава базы, номера единичных разрядов которого соответствуют номерам вершин; по.каждому адресу блока 7 памяти хранится. двоичный код мощности базы, код состава которой записан по соответствующему адресу блока 6 памяти.

Формула и з о бр ет ения

1451715

at.7

1 Й Я Ф Х б 7 о б rrrrtrrrrrrt

Яж

ЬаМ ttaepawpa

УЮббм

lwhr rarrrt

Э йиФм

Ю мбябФВФФ

Jynrr б

Хб

Аеа1 ыУ Ю

o o

o o

I 1

Orat.J 1аьм

Составитель О.Гречухина .Техред А. Кравчук Корректор В.Гирняк

Редактор И.Рыбченко

Заказ 7082/48 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Прбизводственно-полиграфическое Предприятие, r. Ужгород, ул. Проектная, 4, функциональных возможностей за счет нахождения баз ориентированного графа и определения их количественных характеристик, в него введены элемент ИЛИ, группа элементов ИЛИ, элемент И, второй счетчик, первый и второй блоки памяти, блок определения мощности базы, вход синхронизации которого соединен с входами записи первого и второго блоков памяти, первым входом элемента ИЛИ и выходом элемента И, входы с первого по К-й которого соединены с выходами соответствующих элементов ИЛИ группы, а (К+1)-й вход соединен с выходом генератора импульсов и счетным входом первого счетчика, выход переполнения которого соединен с входом останова генератора импульсов, а информационные выходЫ первого счетчика соединены с информационными вхоцами первого блока памяти и блока определения мощности базы, каждый из информационных выходов первого счетчика соединен с первым входом сбответствующего элемента ИЛИ группи, входи с второго по К-й которого соединены с выходами соответствующих элементов И соответствующего столбца матрицы,.а выход соединен с первыми входами элементов И соответствующей строки матрицы, вторые входы элементов И матрицы соединены с соответствующими информационными выходами на10 борного поля, второй вход элемента

ИЛИ является входом считывания информации устройства, выход элемента

ИЛИ соединен со счетным входом второго счетчика, информационные выходы

15 которого соединены с адресными входами первого и второго блоков памяти и являются адресными выходами устройства, информационные выходы блока определения мощности базы соединены

2р с информационными входами второго блока памяти, информационные выходы первого и второго блоков памяти являются соответственно первым и вторым информационными выходами устройства, 25 входы сброса первого и второго счетчиков соединены и являются входом сброса устройства.