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

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

Реферат

 

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

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

Аппаратные реализации средств контроля корректности баз знаний при их автоматическом пополнении в известной технической и патентной литературе не встречаются.

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

Устройство содержит матрицу моделей дуг, группу элементов И, генератор импульсов, элемент И, элемент ИЛИ и триггер, причем каждый узел матрицы моделей дуг содержит триггер, вход запуска генератора импульсов является входом пуска устройства, две группы элементов ИЛИ-НЕ, элемент И-НЕ, счетчик и группа счетчиков, причем выход триггера р к-го узла матрицы моделей дуг (р= 1. . . М, к=1...М, где М - количество вершин в сетевом графике) подключен к р-му входу к-го элемента ИЛИ-НЕ первой группы и к-му входу р-го элемента ИЛИ-НЕ второй группы, выход которого подключен к р-му входу элемента И-НЕ и является р-м выходом признака принадлежности р-й вершины контуру сетевого графика устройства, выход элемента И-НЕ подключен к первому входу элемента ИЛИ и является выходом признака наличия контуров в сетевом графике устройства, выход генератора импульсов подключен к первому входу элемента И, выход которого подключен к вычитающему входу счетчика, к первым входам всех элементов И группы и входу установки в "1" триггера, выход которого подключен к второму входу элемента ИЛИ, выход которого подключен к второму входу элемента И, выход к-го элемента ИЛИ-НЕ первой группы подключен к второму входу к-го элемента И группы, выход которого подключен к входам установки в "0" триггеров всех узлов к-й строки матрицы моделей дуг и вычитающему входу к-го счетчика группы, выход признака переполнения счетчика подключен к входу останова генератора импульсов.

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

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

Поставленная цель достигается тем, что в устройство для анализа структуры ориентированного графа, содержащее первую и вторую группы элемента ИЛИ-НЕ, элемент ИЛИ, три элемента индикации, группу элементов индикации, первую группу элементов И, элемент И, дополнительно вводятся первая и вторая группы триггеров, группа элемента задержки, первый и второй элемента ИЛИ-НЕ, блок сравнения, вторая и третья группы элементов И, первая и вторая группы элементов ИЛИ, элемент НЕ, матрица задания топологии графа, содержащая расположенные по строкам и столбцам элементы матрицы, каждая i-я строка (i= 1,2,...,n) содержит i основных элементов и один вспомогательный элемент, вход запрета устройства соединен с первым входом управления вертикальным сдвигом первого основного элемента матрицы строки с номером i=2 и первым входом управления горизонтальным сдвигом всех элементов первого столбца матрицы, прямой выход триггеров второй группы подключен к входам информации о выходящих дугах основных элементов соответствующего столбца матрицы, инверсный выход триггеров второй группы, кроме (n-1)-го, соединен с первыми входами соответствующих элементов ИЛИ-НЕ второй группы, выход j-го элемента ИЛИ-НЕ второй группы (j=2,...n-2) подключен ко второму входу (j-1)-го элемента ИЛИ-НЕ этой же группы, выходы элемента ИЛИ-НЕ второй группы с первого по (n-2)-й подключены к входам с (n-1)-го по второй первой группы входов блока сравнения и второго элемента ИЛИ-НЕ, к первым входам соответствующих элементов И второй группы, прямой выход (n-1)-го триггера второй группы соединен со вторым входом (n-2)-го элемента ИЛИ-НЕ второй группы, первым входом первой группы входов блока сравнения, первым входом второго элемента ИЛИ-НЕ и первым входом (n-1)-го элемента И второй группы, прямой выход к-го триггера первой группы (к=1,...,n-1) подключен к входу информации о входящих дугах основных элементов матрицы соответствующей строки матрицы задания топологии графа, инверсный выход триггеров первой группы, кроме первого, соединен с первым входом соответствующих элементов ИЛИ-НЕ первой группы, выходы которых подключены к соответствующим входам первого элемента ИЛИ-НЕ, второй группы входов блока сравнения и первым входом соответствующих элементов ИЛИ первой группы, прямой выход первого триггера первой группы соединен со вторым входом первого элемента ИЛИ-НЕ первой группы, соответствующим входом первого элемента ИЛИ-НЕ и второй группы входов блока сравнения, первым входом первого элемента И третьей группы, первые входы остальных элементов которой, кроме n-го, подключены к выходам соответствующих элементов ИЛИ первой группы, выход (n-1)-го элемента И второй группы подключен к первому входу n-го элемента И третьей группы, первый вход l-го элемента ИЛИ-НЕ первой группы (l=2,...,n-2) соединен с выходом (l-1)-го элемента ИЛИ-НЕ этой же группы, выход первого элемента ИЛИ-НЕ подключен к входу первого элемента индикации и второму входу всех элементов И второй группы, первому входу элемента ИЛИ и входу элемента НЕ, выход второго элемента ИЛИ-НЕ соединен с входом второго элемента индикации, выход "Больше" блока сравнения подключен ко второму входу элемента ИЛИ, выход которого подключен ко вторым входам всех элементов И третьей группы, выход "Меньше или равно" блока сравнения соединен с первым входом элемента И, выход которого соединен с входом третьего элемента индикации, а его второй вход соединен с выходом элемента НЕ, выходы элементов И второй группы, кроме (n-1)-го, подключены ко вторым входам соответствующих элементов ИЛИ первой группы, выходы элементов И третьей группы соединены с входами соответствующих элементов индикации группы элементов индикации, выход первого элемента И третьей группы подключен к первому входу первого элемента И первой группы и первому входу первого элемента ИЛИ второй группы, выходы элементов ИЛИ второй группы с первого по (n-2)-й подключены к первым входам соответственно элементов ИЛИ этой же группы со второго по (n-1)-й, выходы элементов И третьей группы со второго по n-й соединены со вторыми входами элементов ИЛИ второй группы соответственно с первого по (n-1)-й, выходы которых подключены к первым входам элементов И первой группы со второго по n-й соответственно, вход разрешения записи подключен ко вторым входам элементов И первой группы, выход первого элемента И первой группы подключен и второму входу управления горизонтальным сдвигом элементов первого cтолбца и первому входу управления горизонтальным cдвигом элементов второго столбца матрицы, выход n-го элемента И первой группы соединен со входом (n-1)-го элемента задержки группы, выход которого подключен ко второму входу управления вертикальным сдвигом основных элементов i-й строки матрицы, выход р-го элемента И первой группы (р-2,...,n-1) подключен к второму входу управления горизонтальным сдвигом элементов р-го столбца матрицы и первому входу управления горизонтальным сдвигом элементов (p+1)-го столбца матрицы, а также к входу р-го элемента задержки, выход которого соединен со вторым входом управления вертикальным сдвигом основных элементов р-й строки матрицы и первым входом управления вертикальным сдвигом основных элементов (р+1)-й строки матрицы, в каждой строке матрицы выход элементов, кроме последнего, подключен к первому информационному входу следующего по номеру элемента, в каждом столбце матрицы выход элементов, кроме принадлежащего последней строке, соединен со вторым информационным входом следующего по номеру элемента.

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

На фиг.1,2 приведена структурная схема устройства для анализа ориентированного графа; на фиг.3 - структурная схема элемента матрицы; фиг.4...9 иллюстрируют процесс функционирования предлагаемого устройства.

Устройство для анализа структуры ориентированного графа (фиг.1,2) содержит матрицу 1 задания топологии графа, состоящую из элементов 2 матрицы, первую 3 и вторую 4 группы триггеров, первую 5 и вторую 6 группы элементов ИЛИ-НЕ, группу элементов задержки 7, первый 8 и второй 9 элементы ИЛИ-НЕ, элемент ИЛИ 10, первый 11, второй 12 и третий 13 элементы индикации, блок 14 сравнения, первую 15, вторую 16 и третью 17 группы элементов И, первую 18 и вторую 19 группы элементов ИЛИ, группу элементов индикации 20, вход 21 запрета устройства и вход 22 разрешения записи, элементы НЕ 23, И 24.

Элемент матрицы (фиг.3) содержит триггер 25, с первого по шестой элементы И 26. ..31, первый 32 и второй 33 элементы ИЛИ, первый 34 и второй 35 элементы НЕ, элемент задержки 36, входы информации о входящих 37 и выходящих 38 дугах, первый 39 и второй 40 входы управления вертикальным сдвигом, первый 41 и второй 42 входы управления горизонтальным сдвигом, первый 43 и второй 44 информационные входы, выход 45 элемента, вход 46 признака дуги, вход 47 синхронизации.

В основу функционирования предлагаемого устройства положена известная теорема, согласно которой следующие свойства орграфа эквивалентны: 1) D - безконтурный граф; 2) вершины орграфа D можно упорядочить таким образом, что матрица смежностей А будет нижней треугольной матрицей.

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

Для простоты интерпретации алгоритма упорядочения матрицы смежностей к треугольной рассмотрим орграф, имеющий пять вершин (фиг.4) и соответствующую ему матрицу (фиг.5).

Допустим, что в структуру графа введена новая вершина такая, что в нее входят дуги из вершин 3 и 5, а из нее выходит дуга в вершину 1 (фиг.6). Нетрудно заметить, что для сохранения треугольности матрицы необходимо выполнить два условия; наибольший номер вершин, в которые входят дуги из новой вершины, должен быть меньше, чем на единицу уменьшенный минимальный номер вершин, из которых дуги входят в новую вершину; новой вершине должен быть присвоен минимальный номер вершин, из которых дуги входят в новую вершину, а к номерам вершин, следующих за вновь образованной вершиной, должна быть прибавлена единица.

Математически эти условия можно записать как j_max < i_max - 1; N= N_imim; N_k=N_k+1, K = , (1) где j - номера (ранги) вершин, в которые входят дуги из новой вершины; i - номера (ранги) вершин, из которых дуги входят в новую вершину; N - номер (ранг), присваиваемый новой вершине; p - общее число вершин в орграфе.

Для рассмотренного примера j_max=1, i_min=3, орграф и его матрица смежностей преобразуются к виду, представленным на фиг.7,8.

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

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

Таким образом, поиск контура заключается в проверке условий (1). Если условия выполняются, то производится "рассечение" матрицы соответствующим сдвигом элементов и внесение на это место строки и столбца, списываемых новой вершиной, ранг которой определяется автоматически.

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

В исходном состоянии на входе 21 присутствует нулевой потенциал, в триггеры 25 узлов 2, заносится информация о топологии графа, подлежащего последующему усложнению: по сигналу единичного уровня, подаваемому на вход 46, устанавливаются в единичное состояние триггеры тех узлов 2, на входы 47 которых подан сигнал единичного уровня.

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

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

Логика работы элементов ИЛИ-НЕ 5, 6 одинакова. Сигналы с инверсных выходов триггеров 3, поступающие на входы элементов ИЛИ-НЕ 5, вызывают установление единичного уровня на выходе того элемента ИЛИ-НЕ 5, который соответствует дуге (входящей в добавляемую вершину), имеющей наименьший номер - фактически i_min-1. Для элементов ИЛИ-НЕ 6 (из-за их коммутации со стороны старших номеров к младшим) произойдет установление элемента ИЛИ-НЕ 6, соответствующего дуге (выходящей из добавляемой вершины), имеющей наибольший номер - i_max. На входах второй и первой группы входов блока 14 устанавливаются позиционные коды соответственно в прямой и обратной последовательности. В результате сравнения на одном из выходов блока 14 появится сигнал единичного уровня: на выходе "Больше" при выполнении условия (1); на выходе "Меньше или равно" - в противном случае.

В первом случае сигнал единичного уровня проходит через элемент ИЛИ 10 и стробирует элементы И 17, на второй вход которых поступает информация с триггера 3₁ и элементов ИЛИ-НЕ 5 (через элементы ИЛИ 18). Сигнал единичного уровня появится на выходе элемента И 17, соответствующего наименьшему номеру добавляемой вершины; этот сигнал индицируется элементом 20; этот же сигнал, проходя через соответствующий элемент ИЛИ 19 и попадая на вход следующего по номеру элемента ИЛИ 19 и далее по цепочке до последнего приводит к установлению на выходе всех этих элементов единичного потенциала. При подаче на вход 22 сигнала разрешения записи единичного уровня установится единичный потенциал на выходах соответствующих элементов И 15.

Наличие сигналов нулевого уровня на входах элемента ИЛИ-НЕ 8 приводит к появлению единичного потенциала на его выходе и входе элемента 11, индицирующего наличие хвостовых вершин в графе; этот сигнал стробирует элементы И 16, разрешая прохождение информации с выходов элементов ИЛИ-НЕ 6 и прямого выхода триггера 4_n-1, через элементы ИЛИ 18 на входы элементов И 17; этот же сигнал проходит через элемент ИЛИ 10 и стробирует элементы И 17. Далее устройство работает, как было описано выше; сигнал единичного уровня установится на выходах элементов И 15 с номерами равными и большими максимального при подаче сигнала на вход 22.

Наличие сигналов нулевого уровня на входах элемента ИЛИ-НЕ 9 приводит к появлению единичного потенциала на его выходе и входе элемента 12, индицирующего наличие в графе тупиковых вершин.

При появлении сигнала единичного уровня на выходе "Меньше или равно" блока 14 (входе элемента И 24) и отсутствии хвостовых вершин (сигнал нулевого уровня с выхода элемента ИЛИ-НЕ 8 инвертируется элементом НЕ 23 и поступает на другой вход элемента И 24) элементом 13 индицируется образование контура в графе при добавлении новой вершины. Исходная информация нуждается в коррекции.

При отсутствии контуров, независимо от наличия хвостовых и (или) тупиковых вершин, корректировка графа (пополнение базы знаний) выполняется, начиная с подачи сигнала разрешения записи на вход 22.

Матрица 1 задания топологии графа представляет собой двухмерный управляемый сдвигающий регистр, позволяющий сдвигать информацию, хранящуюся в элементах 2, как в вертикальном (по столбцам вниз), так и в горизонтальном (по строкам вправо) направлении, начиная со строки и столбца, определенных сигналами управления с выходов элементов И 15, а также записывать хранящуюся в триггерах 3 и 4 информацию в определенные столбец и строку соответственно.

Сигналы с выходов элементов И 15 поступают на столбцы элементов 2 матрицы 1 непосредственно (на входы 42 и 41 соседних по строке элементов), а на строки - через элементы задержки 7 (на входы 40 и 39 соседних по столбцу элементов). Входы 41, 42 управляют горизонтальным сдвигом и записью информации с триггеров 3, входы 40, 39 - вертикальным сдвигом и записью информации с триггеров 4.

В зависимости от возможных комбинаций сигналов на этих входах элемент 2 выполняет следующие функции.

1. На входах 41 и 42 сигналы нулевого уровня. Первый не разрешает прохождение сигнала от соседнего слева элемента 2, поступающего на вход 43, через элемент И 28 и далее через элемент ИЛИ 32 на D-вход триггера 25. Сигнал нулевого уровня с выхода 42, поступающий на один из входов элемента И 26, обеспечивает запрет прохождения сигнала с выхода соответствующего триггера 3 на D-вход триггера 25 по цепочке: вход 37, элементы И 29, ИЛИ 32.

2. На входах 39 и 40 сигналы нулевого уровня. Первый, поступая на один из входов элемента И 27, запрещает прохождение сигнала, поступающего на вход 44 с выхода соседнего сверху элемента 2, на D-вход триггера 25 по цепочке: элементы И 27, ИЛИ 32. Сигнал нулевого уровня на входе 40, поступая на один из входов элемента И 30, запрещает прохождение сигнала с выхода соответствующего триггера 4 на D-вход триггера 25 по цепочке: вход 38, элементы И 31, ИЛИ 32.

Таким образом, рассмотренные управляющие комбинации не изменяют информацию, записанную в триггере 25 элемента 2.

3. На входе 41 сигнал нулевого уровня, на входе 42 - единичного. Первый запрещает прохождение сигнала от соседнего слева элемента 2 (вход 43, элементы И 28, ИЛИ 32) на D-вход триггера 25; он же, инвертированный элементом НЕ 34, поступает на один из входов элемента И 26. На втором входе этого элемента сигнал единичного уровня с входа 42. Сигнал единичного уровня с выхода элемента И 26 поступает на один из входов элемента И 29, разрешая прохождение сигнала с соответствующего триггера 3 на D-вход триггера 25 по цепочке: вход 37, элемент И 29, элемент ИЛИ 32; этот же сигнал через элементы ИЛИ 33 и задержки 36 поступает на С-вход триггера 25, обеспечивая запись содержимого триггера 3 в триггер 25.

4. На входе 39 сигнал нулевого уровня, на входе 40 - единичного. Первый запрещает прохождение сигнала от соседнего сверху элемента 2 (вход 44, элементы И 27, ИЛИ 32) на D-вход триггера 25, он же, инвертированный элементом НЕ 35, поступает на один из входов элемента И 30. На втором входе этого элемента сигнал единичного уровня с входа 40. Сигнал единичного уровня с выхода элемента И 30 поступает на один из входов элемента И 31, разрешая прохождение сигнала с соответствующего триггера 4 на D-вход триггера 25 по цепочке: вход 38, элементы И 31, ИЛИ 32; этот же сигнал через элементы ИЛИ 33 и задержки 36 поступает на С-вход триггера, обеспечивая запись содержимого триггера 4 в триггер 25.

5. На входах 41 и 42 сигналы единичного уровня. Первый разрешает прохождение сигнала от соседнего слева элемента 2 (вход 43, элементы И 28, ИЛИ 32) на D-вход триггера 25; он же через элементы ИЛИ 33 и задержки 36 поступает на С-вход триггера 25, обеспечивая запись в него содержимого триггера 25 соседнего слева элемента 2; этот же сигнал, инвертированный элементом НЕ 34, запрещает прохождение сигнала с входа 42.

6. На входах 39 и 40 сигналы единичного уровня. Первый разрешает прохождение сигнала от соседнего сверху элемента 2 (вход 44, элементы И 27, ИЛИ 32) на D-вход триггера 25; он же через элементы ИЛИ 33 и задержки 36 поступает на С-вход триггера 25, обеспечивая запись в него содержимого триггера 25 соседнего сверху узла; этот же сигнал, инвертированный элементом НЕ 35, запрещает прохождение сигнала с входа 40.

Вспомогательные узлы выполняют только функции сдвига информации. На фиг. 9 для рассмотренного выше примера показана интерпретация процесса пополнения матрицы по этапам: 1) до сигнала разрешения записи формирование исходной информации (фиг.9, а); 2) после сигнала разрешения записи: рассечение по вертикали и запись столбца (фиг.9, б); рассечение по горизонтали (после задержки) и запись строки (фиг.9, в).

Принятые обозначения: А, С - состояние триггеров 3, 4; В, D - состояние выходов элементов ИЛИ-НЕ 5, 6; Е, F - состояние вертикальных и горизонтальных шин управления (выходов элементов И 17).

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

1. УСТРОЙСТВО ДЛЯ АНАЛИЗА СТРУКТУРЫ ОРИЕНТИРОВАННОГО ГРАФА, содержащее первую и вторую группы элементов ИЛИ - НЕ, элемент ИЛИ, три элемента индикации, группу элементов индикации, первую группу элементов И, элемент И, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения контроля корректности баз знаний при их автоматическом пополнении, в него введены первая и вторая группы триггеров, группа элементов задержки, первый и второй элементы ИЛИ - НЕ, блок сравнения, вторая и третья группы элементов И, первая и вторая группы элементов ИЛИ, элемент НЕ и матрица задания топологии графа, содержащая расположенные по строкам и столбцам элементы матрицы, каждая i-я строка (i = 1, 2, ..., n) содержит i основных элементов и один вспомогательный, вход запрета устройства соединен с первым входом управления вертикальным сдвигом первого основного элемента матрицы строки с номером i = 2 и первым входом управления горизонтальным сдвигом всех элементов первого столбца матрицы, прямой выход триггеров второй группы подключен к входам информации о выходящих дугах основных элементов соответствующего столбца матрицы, инверсный выход триггеров второй группы, кроме (n - 1)-го, соединен с первыми входами соответствующих элементов ИЛИ - НЕ второй группы, выход j-го элемента ИЛИ - НЕ второй группы (j = 2, ..., n -2) подключен к второму входу (j - 1)-го элемента ИЛИ - НЕ этой же группы, выходы элементов ИЛИ - НЕ второй группы с первого по (n - 2)-й подключены к входам с (n - 1)-го по второй первой группы входов блока сравнения и второго элемента ИЛИ - НЕ, к первым входам соответствующих элементов И второй группы, прямой выход (n - 1)-го триггера второй группы соединен с вторым входом (n - 2)-го элемента ИЛИ - НЕ второй группы, первым входом первой группы входов блока сравнения, первым входом второго элемента ИЛИ - НЕ и первым входом (n - 1)го элемента И второй группы, прямой выход R-го триггера первой группы (K = 1, ..., n - 1) подключен к входу информации о входящих дугах основных элементов матрицы соответствующей строки матрицы задания топологии графа, инверсный выход триггеров первой группы, кроме первого, соединен с первым входом соответствующих элементов ИЛИ - НЕ первой группы, выходы которых подключены к соответствующим входам первого элемента ИЛИ - НЕ второй группы входов блока сравнения и первым входам соответствующих элементов ИЛИ первой группы, прямой выход первого триггера первой группы соединен с вторым входом первого элемента ИЛИ - НЕ первой группы, соответствующим входом первого элемента ИЛИ - НЕ, второй группы входов блока сравнения, первым входом первого элемента И третьей группы, первые входы остальных элементов которой, кроме n-го, подключены к выходам соответствующих элементов ИЛИ первой группы, выход (n - 1)-го элемента И второй группы подключен к первому входу n-го элемента И третьей группы, первый вход l-го элемента ИЛИ - НЕ первой группы (l = 2, ..., n- 2) соединен с выходом (l - 1)-го элемента ИЛИ - НЕ этой же группы, выход первого элемента ИЛИ - НЕ подключен к входу первого элемента индикации и второму входу всех элементов И второй группы, первому входу элемента ИЛИ и входу элемента НЕ, выход второго элемента ИЛИ - НЕ соединен с входом второго элемента индикации, выход "Больше" блока сравнения подключен к второму входу элемента ИЛИ, выход которого подключен к вторым входам всех элементов И третьей группы, выход "Меньше или равно" блока сравнения соединен с первым входом элемента И, выход которого соединен с входом третьего элемента индикации, а его второй вход - с выходом элемента НЕ, выходы элементов И второй группы, кроме (n - 1)-го подключены к вторым входам соответствующих элементов ИЛИ первой группы, выходы элементов И третьей группы соединены с входами соответствующих элементов индикации группы элементов индикации, выход первого элемента И третьей группы подключен к первому входу первого элемента И первой группы и первому входу первого элемента ИЛИ второй группы, выходы элементов ИЛИ второй группы с первого по (n - 2)-й подключены к первым входам соответственно элементов ИЛИ этой же группы с второго по (n - 1)-й, выходы элементов И третьей группы с второго по n-й соединены с вторыми входами элементов ИЛИ второй группы соответственно с первого по (n - 1)-й, выходы которых подключены к первым входам элементов И первой группы с второго по n-й соответственно, вход разрешения записи подключен к вторым входам элементов И первой группы, выход первого элемента И первой группы подключен к второму входу управления горизонтальным сдвигом элементов первого столбца и первому входу управления горизонтальным сдвигом элементов второго столбца выход n-го элемента И первой группы соединен с входом (n - 1)-го элемента задержки группы, выход которого подключен к второму входу управления вертикальным сдвигом основных элементов i-й строки матрицы, выход p-го элемента И первой группы (p = 2, ..., n - 1) подключен к второму входу управления горизонтальным сдвигом элементов p-го столбца матрицы и первому входу управления горизонтальным сдвигом элементов (p + 1)-го столбца матрицы, а также к входу p-го элемента задержки, выход которого соединен с вторым входом упраления вертикальным сдвигом основных элементов p-й строки матрицы и первым входом управления вертикальным сдвигом основных элементов (p + 1)-й строки матрицы, в каждой строке матрицы выход каждого элемента, кроме последнего, подключен к первому информационному входу следующего по номеру элемента, в каждом столбце матрицы выход каждого элемента, кроме принадлежащего последней строке, соединен с вторым информационным входом следующего по номеру элемента.

2. Устройство по п.1, отличающееся тем, что каждый элемент матрицы задания топологии графа содержит триггер, шесть элементов И, первый и второй элементы ИЛИ, первый и второй элементы НЕ, элемент задержки информации о входящих дугах элемента соединен с первым входом четвертого элемента И, к второму входу которого подключен выход первого элемента И и первый вход второго элемента ИЛИ, выход которого через элемент задержки подключен к C-входу триггера, прямой выход которого является выходом узла, D-вход триггера подключен к выходу первого элемента ИЛИ, первый - четвертый входы которого соединены с выходами второго, третьего, четвертого и шестого элементов И соответственно, а его пятый вход является входом признака дуги элемента, второй вход управления вертикальным сдвигом элемента соединен с первым входом пятого элемента И, второй вход которого подключен к выходу второго элемента НЕ, вход которого соединен с первым входом управления вертикальным сдвигом элемента, вторым входом второго элемента ИЛИ и первым входом второго элемента И, второй вход которого является вторым информационным входом элемента, первый информационный вход элемента соединен с первым входом третьего элемента И, второй вход которого подключен к первому входу управления горизонтальным сдвигом узла, входом первого элемента НЕ и третьим входом второго элемента ИЛИ, четвертый вход которого соединен с выходом пятого элемента И и с первым входом шестого элемента И, второй вход которого является входом информации о выходящих дугах элемента, выход первого элемента НЕ подключен к первому входу первого элемента И, второй вход которого являеттся вторым входом управления горизонтальным сдвигом узла, пятый вход второго элемента ИЛИ является входом синхронизации узла.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9