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

U

М

-

Г56г

О 00 СА) О СА) О

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

-0 5

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

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

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

Устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок 3 определения стоков, блок А задания матрицы смежности, вход 5 пуска устройства и выходы 6 веса пути из вершин в наиболее удаленные от них стоки графа устройства.

На схеме (фиг.2) обозначены группа элементов ИЛИ-НЕ 7, входы 8 признаков наличия дуг и выходы 9 признаков принадлежности вершин массиву стоков графа, причем вход 8 признака наличия (К,М)-й дуги блока определения стоков (К 1,...,В; ,...,В, где В - количество вершин в графе) подключен к К-му входу М-го элемента ИЛИ-НЕ 7 группы, выход которого является выходом 9 признака принадлежности М-й вершины массиву стоков графа.

На фиг.З цифровые обозначения представляют матрицу из В х В триггеров 10, причем вход 11 задания признака наличия дуги из М-й в К-ю вершину графа блока 4 задания матрицы смежности подключен к входу установки в единицу К-го триггера 10 М-й строки матрицы, выход которого является выходом 12 признака наличия (К,М}-й дуги блока 4 задания матрицы смежности, вход 13 удаления дуг, заходящих в К-ю вершину, которого подключен к входам установки в О всех триггеров 10 К-ro столбца матрицы.

На фиг,4 цифровые обозначения представляют группу из В счетчиков 14, причем вход 15 разрешения работы М-го канала многоканального таймера 2 подключен к входу разрешения счета М-го счетчика 14 группы, информационный выход которого является М-ым информационным выходом 16 многоканального таймера 2, вычитающий вход 17 которого подключен к вычитающим входам всех счетчиков 14 группы, выход признака переполнения М-го из которых является выходом 18 признака переполнения М-го канала многоканального таймера 2.

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

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

На вход 5 пуска устройства подают им0 пульсный сигнал уровня логической 1. При этом генератор 1 формирует серию импульсов, количество которых совпадаете полной емкостью канала таймера 2. При поступлении на вычитающий вход таймера 2 импуль5 сов уровня логической 1 те его каналы, работа которых разрешена потенциалами уровня логической 1 с выходов блока 3 определения стоков, работают на вычитание. В момент перехода через О канал

0 таймера 2 формирует импульсный сигнал уровня логической 1 (признак окончания, моделирования вершины, номер которой совпадает с номером канала таймера). При этом блок 4 задания матрицы смежности

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

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

Блок 4 задания матрицы смежности ра5 ботает следующим образом.

Перед началом работы обнуляют триггеры 10 матрицы и по входам 11 заносят информацию о топологии графа. При поступлении на входы 13 импульсов уровня

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

5 Многоканальный таймер 2 работает следующим образом.

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

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

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

Г Г

ПЪ %В1 П ПМ

0

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

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

/У

fe.2

Н

фцг.З

18j f6j JBt 16 г

о

%; %

1Вь «в

Фие.Ь