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

iPat.r

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

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

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

импульсов, блок 2 управления, блок 3 переименования вершин и блок 4 иат-. : ричной модели дерева путей графа.

Генератор 1 импульсов подает на вход блока 2 управления последовательность тактовых импульсов, управляющих работой блоков устройства.

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

Блок 3 переименования вершин слу- жит для выбора корневой вершины.

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

Блок 3 переименования вершин (фиг.1) состоит из регистров 5 и схем 6 формирования номеров вершин, включающих схему 7 сравнения, триггер 8, сборки 9 и 10 элементов И и сборку 11 злементов ИЛИ.

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

Схема 7 сравнения служит для сравнения номера вершины, записанного в регистре 5, с номером корневой вершины.

В исходном состоянии в регистры- 5 записаны номера верпмн графа с 1-й по N-ую. На выходе схемы 7 сравнениянулевой потенциал, триггер 8 - в единичном состоянии. Сборки 9 элементов И открыты, сборки 10 элементов И закрыты. На выходе сборки 11 элементов

ИЛИ - код, соответствукщий номеру вершины, записанной в регистре 5.

Блок 4 матричной модели дерева путей графа (фиг. 2) состоит из блоков 12-15 формирования путей, количество которых по столбцам и строкам одинаково и равно К -1, где К - число вершин в графе.

Входы и выходы устройства обозначены следующим образом: 16 - такто- вьй вход блока управления; 17 - выход номера корневой вершины; 18 - группа информационных входов блока управления; 19 - группа управляющих выходов блока управления.

Блок 2 управления состоит из регистра 20 количества вершин, счетчика 21, схемы 22 сравнения, элемента 23 Запрет, счетчика 24, регистра 25, схемы 26 сравнения, элемента 27 Запрет, элемента И 28, схемы 29, которая содержит регистр 30, коммутатор 31, регистр 32, схему 33 сравнения, схему 34 сравнения, сборки 35 и 36 элементов И, сборку 37 элементов ИЛИ и распределитель 38 импульсов, кроме этого, в блок 2 управления входят регистр 39, коммутатор 40, а также регистры 41 и 42.

Регистр 20 служит для записи количества вершин исследуемого графа. Счётчик 21 предназначен для подсчета количества просмотренных ярусов.Элемент 23 Запрет управляет прохожде- йием импульсов от генератора 1 на устройство. .1ля досчитьшания импульсов, пришедших от генератора 1, служит счетчик 24. В регистр 25 записывается максимальная степень вершины висследуемом графе. В схеме 26 сравнения сравнивается содержимое регистра 25 и счетчика 24, и в случае совпадения их содержимого на выходе схемы 26 появляется сигнал, который поступает на элемент 27 Запрет и элемент И 28. Элемент 27 Запрет управляет поступлением импульсов на входы коммутаторов 31 схем 29 и коммутатора 40. Элемент И 28 предназначен Для управления поступлением им- . пульсов на вход коммутаторов 31 и распределителей 38 импульсов схем 29 Схема 29 служит для формирования пакета сигналов, поступающих на вход блока 4 матричной модели дерева путей графа. Для записи номеров тех вершин, с которыми связана данная вершина, предусмотрен регистр 30, Регистр 32 служит для записи номера соответствующей вершины. Схема 33 сравнения предназначена дпя сравнения номера вершины, записанного в регистре 32, с номером вершины, записанным в блоке 3 переименования вершин. Схема 34 сравнения служит для сравнения номера К-й вершины, записанного в регистре 41, с номером вер- шины, записанным в блоке 3 переименования вершин. Сборки 35 и 36 элементов И предназначены для управления поступлением сигналов, соответствующих номерам вершин, с которыми су- ще-ствует связь данной вершины, через сборку 37 элементов ИЛИ на распределитель 38 импульсов. Распределитель 38 импульсов служит дпя управления передачей сигналов, соответствующих номерам вершин, с которыми существует связь данной вершины, на соответствующие выходы распределителя 38, Дпя записи связей К-й вершины предназначен регистр 39. Коммутатор 40 предусмотрен для подключения выходов регистра 39 к входам соответствующих сборок 36 элементов И схем 29. Регистр 41 служит для записи номера последней вершины. Дпя записи номера корневой вершины предназначен регистр 42.

В исходном состоянии в регистр 20 записано число, сооТветствукщее количеству вершин исследуемого графа. В регистр 25 записано число, соответствующее максимальной степени вершины исследуемого графа. В регистрах 30 и регистре 39 записаны числа, соответ- ствуняцие номерам тех вершин, с которыми существует связь данной вершины, номер которой записан в регистрах 32 и регистре 41. В регистре 42 записано число, соответствующее номеру.корне- вой вершины графа. Счетчики импульсов 21 и 24 - в нулевом состоянии. Элементы 23 и 27 Запрет открыты. На выходах схем 22 и 26 сравнения - низкий потенциал. Если номер вершины, записанный в регистры 32, совпадает с номером, поступающим из соответствующей схемы 6 блока 3, то на выходе схемы 33 сравнения присутствует вы- сокий потенциал, если нет - низкий. Если номер вершины совпадает с номером, записанным в регистре 41, то на выходе схемы 34 сравнения появляется высокий потенциал, если нет - низкий.

5 о

5

о g g

Блоки 12 - 15 состоят из схем 43, которые включают в себя регистр 44, сборку 45 элементов Запрет и схему 46 сравнения, элемента ИЛИ 47, схем 48 сравнения, элемента ИЛИ 49 и схемы 50, которая состоит из сборок 51 элементов И.

Регистры 44 служат для записи номеров вершин, входящих в соответствующий путь.

Сборка 45 элементов Запрет управляет поступлением сигналов на сборки 51 элементов И.

Схема 46 сравнения сравнивает содержимое регистра 44 с номером верши-, ны, переданным из блока 2 управления.

Схемы 48 сравнения предназначены для сравнения номеров вершин, переданных из блоков 2 и 3 управления и переименования вершин.

В исходном состоянии все регистры 44 обнулены.

Блок 2 управления работает следующим образом. Первый импульс от гене- . ратора 1 импульсов через открытый элемент 23 Запрет поступает на счетчика 24, элемента 27 Запрет и элемента И 28. В счетчике 24 записывается 1. Через открытый элемент 27 Запрет импульс поступает на входы коммутаторов 31 и 40. Коммутатор 31 подключает первый выход регистра 30, соответствующий номеру первой из записанных вершин в регистре 30, к входу сборки 35 элементов И, Аналогично коммутатор 40 подключает первый выход регистра 39 к входу сборки 36 элементов И. Через сборку 37 элементов ИЛИ от сборки 35 или 36 сигнал поступает на вход распределителя 38 импульсов. Распределитель 38 импульсов подает на свой первый выход число, соответствующее но-. меру первой вершины, с которой есть связь у данной вершины. Этот сигнал , выдается в блок 4. При приходе второго импульса от генератора 1 импульсов схема работает аналогичным образом, только происходит передача чис- ра, соответствующего номеру ВТОРОЙ вершины, с которой есть связь. Таким образом схема работает до тех пор, пока содержимое счетчика 24 не сравняется с содержимым регистра 25, В этом случае на выходе схемы 26 сравнения появляется высокий потенциал, который закрывает элемент 27 Запрет и открывает элемент И 28. Новый им-

1462352

пульс, проходит через элемент И 28 на вход счетчика 21 и записывает там М, обнуляет счетчик 24,при этом на выходе схемы 26 сравнения появляется низкий потенциал, который открывает элемент 27 Запрет и закрывает элемент И 28 Кроме этого, импульс поступает на вход коммутатора 31, обнуляя его, и иа вход распределителя 38 импульсов, :подсоединяя его второй выход к выхо- ;ду 19,2 блока 2 управления. Далее :блок работает аналогично описанному. Как только , записанное в счетчике 21, совпадет с числом, записан- ным в регистре 20, на выходе схемы 22 появляется высокий потенциал, который запрещает прохождение импульсов от генератора 1 импульсов. Устройство заканчивает свою работу.

Блок 3 переименования вершин работает следующим образом. При записи в блоке 2 управления информации о корневой вершине в схемах 7 сравнени происходит сравнение чисел, записанных в регистрах 5 и блоке 2 управления. При несовпадении этих чисел триггер 8 остается в единичном состоянии. Содержимое регистра 5 данной строки через открытую сборку 9 элементов И и сборку 11 элементов ИЛИ поступает на соответствующий выход блока 3 переименования вершин. При совпадении этих чисел на выходе схемы 7 появляется сигнал, которьй поступает иа вход триггера 8 и на его нулевом выходе появляется высокий потенциал. Сборка 9 элементов И зак- рьшается, а сборка 10 открьшается. Содержимое последнего регистра 5 поступает на вход сборки 11 элементов ИЛИ и через нее на соответствующий выход блока 3.

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

Блок 13 работает следующим обра- вершины, не считая корневую; ь u..u.. f .п йппкя 12 в оегист- .. 12 формируются пути дерева путей раа50

зом.. с предьщущего блока 12 в регист- 45 ры 44 записьгааются числа, соответствующие номерам вершин, которые входят в соответствующей путь, причем в регистр 44 последней схемы 43 информация записывается из блока 3 переи- менования вершив. При приходе из блока 2 управления информации о выбранной вершине срабатьшают схемы 46 и 48 сравнения. Схемы 46 сравнивают с содержимым регистров 44 число, переданное с соответствующего выхода 19, а схема 48 - с числами, переданными с соответствующих 16ЫХОДОВ 18. В том случае, когда содержимое одного из

55

га 2, которые записываются в блоки 13 При поступлении второй серии импульсов от генератора 1 в блоках 13 формируется дерево путей ранга 3, которое записывается в блоки 13 следукще- го столбца. При записи всех ветвей дерева путей в последнем столбце блока 4 устройство для определений путей в графе прекращает свою работу.

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

Устройство для определения путей в графе, содержащее генератор импуль

регистров 44 совпадает с величиной числа, переданного с соответствующего быхода 19, на выходе соответствующей схемы 46 сравнения появляется высокий потенциал, который через элемент ИЛИ 47 запрещает прохождение сигнала через сборки 45. Если в схеме 48 произойдет совпадение сравниваемых числе, то высокий потенциал через элемент ИЛИ 49 поступает на вход сборок 45 и разрешает прохождение через них сигнала. Одновременно высокий потенциал поступает на вход соответствую- 5 щей сборки 51 элементов И. В том случае, если на выходе элемента ИЛИ 47 присутствует низкий потенциал, а на выходе элемента 49 ИЛИ - высокий, сборки 45 открыты и сигнал, соответ- 0 ствующий содержимому регистров 44, поступает на входы сборок 51 элементов И. Если на выходе одной или нескольких схем 48 сравнения присутствует высокий потенциал, то соответству- 5 кяцие сборки 51 элементов И открыты и информация о пути поступает в адрес соответствующего блока 13 следуклцего столбца. Все остальные блоки 12-15 работают аналогично, только в блоки 12 запись первого элемента осуществляется с блока 2 управления путем выбора номера корневой вершины.

Устройство для определения путей в графе работает следующем образом.

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

0

35

40

вершины, не считая корневую; ь u..u.. .. 12 формируются пути дерева путей раавершины, не считая корневую; ь u..u.. 12 формируются пути дерева путей раа

га 2, которые записываются в блоки 13. При поступлении второй серии импульсов от генератора 1 в блоках 13 формируется дерево путей ранга 3, которое записывается в блоки 13 следукще- го столбца. При записи всех ветвей дерева путей в последнем столбце блока 4 устройство для определений путей в графе прекращает свою работу.

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

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

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

фиг. 2

Omtt

fmtl

a