Устройство для исследования графов Советский патент 1989 года по МПК G06F15/173 

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

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

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

Устройство содержит генератор 1 -, импульсов, элемент ЮТИ 2, первьй счетчик 3, матрицу 4 элементов И, группу 5 элементов ИЛИ, первьй блок 6 памяти, второй блок. 7 памяти, блок 8 определения мощности базы, набор- нее поле 9, элемент И 10, второй счетчик 11.:

Генератор 1 предназначен для син- хронизащн работы устройства счетчи 3 для перебора всех подмножеств

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

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

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

fQ

J5

20 5

30

дд 35

95

5

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

Наборное поле 9 предназначено для ввода топологии графа перед началом моделирования. Элемент И Ю пред- назнач-ен для проверки условия, во все ли вершины гр$фа имеется достижимость из подмножества вершин, проверяемых на принадлежность базе. Счетчик (1 предназначен для подсчета количества баз графа и формирования соответствующих им адресов в первом блоке 6 .памяти и во втором блоке 7 памяти.

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

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

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

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

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

0 мощности. При этом на выходе блока 8 .определения мощности базы форг«1И- руется двоичный код, соответствующий мощности базы; с выхода блока 8 определения мощности базы двоичный код

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

через него и далее поступает на вто- 25 записьгеается по. тому же адресу, что

рую строку, которая образована вторыми нходами элементов И 4

2j

Поскольку в соответствии с топологией графа на первые входы элементов г iJ поданы высокие уровни, то на их выходах также формируются высокие уровни, которые поступают на вторые входы элементов ИЛИ 5, 5-). Таким образом, на всех входах элемента И 10 присутствуют высокие уровни. Поэтому на его выходе также формируется высокий уровень, .По поло.г. жительному перепаду уровня на.выходе элемента И 10, который поступает на . вход W записи блока 6 памяти и вход запуска блока 8 определения мощности базы, в нулевой адрес блока 6 памяти (Записывается .код. .ОШ,. соответствую-:.. щгй тому, что базой данного графа является вторая верпшна. Одновременно запускаятся блок 8 определения мощности базы, который преобразует код 010, поступающий на его входы с первого по третий, в код 001, который в двоичной форме соответствует тому, что мощность базы равна 1. По отрицательному перепаду уровня на выходе элемента И 10, который поступает на вход записи, этот код записывается по нулевому адресу блока 7 памяти. о этому же перепаду уровня счетчик 11с задержкой, определяемой параметами элемента ШШ 2, устанавливается в следующее состояние,и спустя время

30

35

и код.состава базы, но в блок 7 памяти;, далее происходит смена адреса блоков 7 и 6 памяти.

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

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

40

0

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

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

и/пвяят Cfftt

-П.

iHtti umftmept UlJTJTJT rU-l njtHirtH

nmnriurt

«я7

.

11 i / «7 f