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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„SU„„1462352 А1 (ц 4 С 06 F 15/20 всссоюлия )

Ы)Ы I t Ц

Б 1БЛИ.9

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4306139/24-24 (22) 04.08.87 (46) 28,02.89. Бюл, В 8 (72) В.В,Герасименко, С.А.Ильин, А.Ю.Квасницкий, С.В.Листровой и В.Я.Певиев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 1322307, кл. G 06 F 15/20, 1986, Авторское свидетельство СССР

Ф 1325500, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПУТЕЙ

В ГРАФЕ (57) Изобретение относится к вычисли.тельной технике и может быть испольэовано для решения комбинированных и оптимизационных задач на графах.

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

1462352

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

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

: графе.

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

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

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

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

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

Блок 3 переименования вершин (фиг.1) состоит из регистров 5 и схем

6 формирования номеров вершин, включающих схему 7 сравнения, триггер 8, сборки 9 и 10 элементов И и сборку 11 45 элементов ИЛИ.

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

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

IIo И-ую. на выходе cxBMbl 7 сравнения- 55 нулевой потенциал, триггер 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, служит счетчик 24. В регистр 25 записывается максимальная степень вершины в исследуемом графе. В схеме 26 сравнения сравнивается содержимое регистра 25 и счетчика 24, и в случае совпадения их содержимого на выходе схемы 26 появляется сигнал, который поступает на элемент 27 "Запрет" и элемент И 28, Элемент 27 "Запрет" управляет поступлением импульсов на входы коммутаторов 31 схем 29 и коммутатора 40. Элемент И 28 предназначен Для управления поступлением импульсов на вход коммутаторов 31 и распределителей 38 импульсов схем 29.

Схема 29 служит для форми)сования пакета сигналов, поступающих на вход блока 4 матричной модели дерева путей графа. Для записи номеров тех вершин, с которыми связана данная вершина, предусмотрен регистр 30. Ре1462352 гистр 32 служит для записи номера соответствующей вершины. Схема 33 . сравнения предназначена дпя сравнения номера вершины, записанного в регистре 32, с номером вершины, записанным в блоке 3 переименования вершин. Схема 34 сравнения служит для сравнения номера К-й вершины, записанного в регистре 4 1, с номером вер- !О шины, записанным в блоке 3 переименования вершин. Сборки 3$ и 36 элементов И предназначены для управления поступлением сигналов, соответствующих номерам вершин, с которыми существует связь данной вершины, через сборку 37 элементов ИЛИ на распределитель 38 импульсов. Распределитель

38 импульсов служит для управления передачей сигналов, соответствующих 20 номерам вершин, с которыми существует связь данной вершины, на соответствующие выходы распределителя 38. Для записи связей К-й вершины предназначен регистр 39. Коммутатор 40 предус- 25 мотрен для подключения выходов регистра 39 к входам соответствующих сборок 36 элементов И схем 29. Регистр 41 служит для записи номера последней вершины. Для записи номера 30 корневой вершины предназначен регистр

42.

В исходном состоянии в регистр 20 записано число, соответствующее количеству вершин исследуемого графа. В регистр 25 записано число, соответствукицее максимальной степени вершины исследуемого графа. В регистрах 30 и регистре 39 записаны числа, соответ- 40 ствующие номерам тех вершин, с которыми существует связь данной вершины, номер которой записан в регистрах 32 и регистре 41. В регистре 42 записано число, соответствующее номеру корневой вершины графа. Счетчики импульсов 21 и 24 - в нулевом состоянии.

Элементы 23 и 27 "Запрет" открыты.

На выходах схем 22 и 26 сравнения— низкий потенциал. Если номер вершины, записанный в регистры 32, совпадает с номером, поступающим из соответствующей схемы б блока 3, то на выходе схемы 33 сравнения присутствует высокий потенциал, если нет — низкий. 55

Если номер вершины совпадает с номером, записанным в регистре 41, то на выходе схемы 34 сравнения появляется высокий потенциал, если нет — низкий.

Блоки 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 к входу сборки Зб элементов И. Через сборку 37 элементов ИЛИ от сборки 35 или

36 сигнал поступает на вход распределителя 38 импульсов. Распределитель 38 импульсов подает на свой первый выход число, соответствующее но-. меру первой вершины, с которой есть связь у данной вершины. Этот сигнал . выдается в блок 4. При приходе второго импульса от генератора 1 импульсов схема работает аналогичным образом, только происходит передача чисра соответствующего номеру второй вершины, с которой есть связь. Таким образом схема работает до тех пор, пока содержимое счетчика 24 не сравняется с содержимым регистра 25. В этом случае на выходе схемы 26 сравнения появляется высокий потенщ ал, который закрывает элемент 27 "Запрет" и открывает элемент И 28. Новый им5 14623 пульс. проходит через элемент И 28 на вход счетчика 21 и записывает там "1", обнуляет счетчик 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 пос.—

40 тупает на вход сборки 11 элементов

ИЛИ и через нее на соответствующий выход блока 3.

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

Блок 13 работает следующим образом.. С предыдущего блока 12 в регист- 4> ры 44 записываются числа, соответствующие номерам вершин, которые входят в соответствующий путь, причем в регистр 44 последней схемы 43 информация .записывается из блока 3 переи менования вершин. При приходе из блока 2 управления информации о выбранной вершине срабатывают схемы 46 и

48 сравнения. Схемы 46 сравнивают с содержимым регистров 44 число, переданное с соответствующего выхода 19, а схема 48 — с числами, переданными с соответствукицих выходов 18 В том случае, когда содержимое одного из

52 6 регистров 44 совпадает с величиной

I I числа, переданного с, соответствующего выхода 19, на выходе соответствующей схемы 46 сравнения появляется высокий потенциал, который через элемент ИЛИ

42 запрещает прохождение сигнала через сборки 45. Если в схеме 48 произойдет совпадение сравниваемых числе, то высокий потенциал через элемент ИПИ 49 поступает на вход сборок

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

12 запись первого элемента осуществляется с блока 2 управления путем выбора номера корневой вершины.

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

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

К-ю. При поступлении от генератора 1 импульсов серии импульсов с 1-го по

P-й (где P — максимальная степень вершины, не считая корневую) в блока

12 формируются пути дерева путей ран.— га 2, которые записываются в блоки 13.

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

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

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

> (P-1) блоков формирования путей, где P — число вершин в исследуемом графе, входы первой группы каждого блока формирования путей матрицы со- 15 единены с входами первой группы блока матричной модели дерева путей графа, с входами кода для сравнения группы блока управления и информаци.онными выходами группы блока переи- 20

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

1462352

Жив. Ф

Составитель О.Гречухина

Редактор А.Огар Техред Л.Олийнык Корректор И.Муска, Заказ 715(49 Тирам 667 Подписное

ВНЯИПИ Государственного комитета по изобретениям и открытия р иям а и ГЕНТ СССР

113035, Москва„Ж-35, Рауаская наб., д. 4/5

Производственно-издательс ельский комбинат "Патент", г. Ужгород, ул. Гагарина,101