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

€

(Л

Од

Од

из Р элементов ИЛИ 4, вторую группу из Р элементов ИЛИ 5, пер1 ую группу из Р элементов И 6, вторую группу из Р элементов И 7, блок 8 синхронизации, первый регистр 9, второй регистр 10, первый дешифратор 11, второй дешифратор 12, элемент ИЛИ 13с Перед началом работы задают информацию о топологии графа После подачи сигнала на вход пуска блок 8 начинает вырабатывать импульсы единичного уровня. В момент перехода через нуль К-го счетчика 2 начальной строки матрицы (исполнена ветвь, соединяющая начальную и К-ю вершины графа (К 1,...,Р) на его выходе признака переполнения появляется потенциал, открывающий К-й элемент И 6 (разрешение исполнения всех дуг, выходящих

из К-й вершины). Работа устройства продолжается аналогично до тех пор, пока на выходе элемента И 7, номер которого соответствует коду в регистре 10, не появится единичный потенциал (достигнута конечная вершина пути), который поступит на вход соответствующего элемента ИЛИ 5 и с его выхода на вход элементов И 3. Те элементы И 3, которые открыты единичным потенциалом с выхода признака переполнения счетчиков 2, выдают на информационные входы триггеров 1 (относящихся к кратчайшему пути) единичные потенциалы. После подачи сигнала на вход опроса устройства все. триггеры 1, соответствующие ветвям кратчайшего пути, будут установлены в единичное состояние. 1 ил.

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

1

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

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

На чертеже представлена функциональная схема устройства

Устройство содержит матрицу из РхР триггеров 1, где Р - количество вершин в графе, матрицу из РхР счетчиков 2, матрицу из РхР элементов И 3, первую группу из Р элементов ИЛИ 4, вторую группу из Р элементов ИЛИ 5, первую группу из Р элементов И 6, вторую группу из Р элементов И 7, блок 8 синхронизации, первый регистр 9, второй регистр 10, первый дешифратор 11,Бторой дешифратор 12, элемент ИЛИ 13.

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

Перед началом работы установкой в единицу соответствующих триггеров 1 задают информацию о топологии графа,в счетчики 2 заносят информацию о весе пути из К-й в М-ю вершины графа (,.,.Р; ,...Р), в регистр 9 заносят код номера начальной

вершины графа, в регистр 10 - код номера конечной вершины.

После подачи сигнала единичного уровня на вход пуска блока 8 синхро- 5.низации последний начинает вырабатывать импульсы единичного уровня,поступающие на вторые входы всех элементов И 6. Код, записанный в регистр 9, определяет номер открытого элемен0 та И 6, с выхода которого импульсы единичного уровня поступают на вычитающие входы всех счетчиков 2 строки матрицы с номером, равным номеру начального узла (начинается исполнение

5 ветвей, исходящих из начальной вершины графа). В момент перехода через нуль К-го сч-етчика 2 данной строки (исполнена ветвь, соединяющая начальную и К-ю вершину графа) на его вы ходе признака переполнения появляется потенциал единичного уровня, открывающий К-й элемент И 6 (разрешение исполнения всех дуг, выходящих из К-й вершины) и устанавливающий в нуль все триггеры 1 К-го столбца (запрет исполнения дуг, входящих в К-ю вершину графа). С выхода К-го элемента И 6 импульсы блока 8 синхронизации прступают на вычитающие вхо5

0

ды всех счетчиков К-й строки матрицы

(.исполнение ветвей, исходящих из К-й вершины графа). Работа устройстН ва продолжается аналогично до тех пор, пока на выходе элемента И 7, номер которого соответствует коду в регистре 10, не появится потенциал высокого уровня (достигнута конечная вершина пути). С выхода элемента ИЛИ 13 потенциал единичного уровня останавливает блок 8 синхронизации Кроме того, сигнал единичного уровня с выхода элемента И 7, соответствующего номеру конечной вершины пути поступает на (Р+1)-й вход соответст- вующего элемента ИЛИ 5, с вькода которого потенциал единичного уровня поступает на вторые входы всех элементов И 3 соответствующего столбца матрицы Те элементы И 3, которые открыты единичным потенциалом с выхода признака переполнения соответствующих счетчиков 2, выдают на информационные входы триггеров 1 (относящихся к кратчайшему пути) единичные потенциалы и, кроме того, через элементы ИЛИ 5 разрешают выдачу единичных потенциалов на все пред- ществующие триггеры 1 кратчайшего пути. После подачи единичного потен- циала на вход опроса устройства все триггеры 1, соответствующие ветвям кратчайшего пут.и, будут установлены в единичное, а не относящиеся к кратчайшему пути - в нулевое состояние .

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

Устройство для анализа параметров графа, содержащее матрицу из РхР счетчиков, где Р - количество вершин в графе, матрицу из РхР триггеров, две группы из Р элементов И, две группы из Р элементов ИЛИ и блок синхронизации, причем выход К-го триггера М-й строки матрицы (К 1,..., Р; М 1,...,Р) подключен к входу разрешения счета К-го счетчика М-й строки матрицы, выход признака переполнения которого подключен

ВНИИПИ Заказ 3195/45 Тираж 70Д

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4

0

0

5

5 о

5

0

5

0

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

Подписное