Устройство для решения задач на графах

Устройство для решения задач на графах

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Цель изобретения - расширение функциональных возможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами. Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок определения кратчайшего пути, блок 4 памяти, блок 5 умножения, многоканальный накапливающий блок 6 выбора максимума, блок 7 выбора минимума, вход 8 пуска устройства, выходы 9-11 блока 1 синхронизации и выходы 12 признаков соответствия вершин внешнему центру графа. Перед началом работы устанавливают в исходное состояние блок 2 перечисления подмножеств пар вершин , в блок 3 заносят информацию о топологии графа, в блок 4 памяти заносят веса вершин графа, обнуляют каналы блока 6. На вход 8 пуска устройства подают импульс уровня логической единицы. При этом на одном (или нескольких) выходах 12 будет сформирован признак соответствия вершины внешнему центру графа. 2 ил. NV ё

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

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

РЕСПУБЛИК (н)з G 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

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

12д

Фиг,1 (21) 4644734/24 (22) 30.01.89 (46) 23.04.91. Бюль 15 (72) Г;А.Радионов, Е.И.Бороденко, П.Г.Горев и В.А.Казарцев (53) 681.333 (088.8) (56) Авторское свидетельство СССР

И. 1241266, кл. 6 06 G 7/48,1986.

Авторское свидетельство СССР

t4- 1559354, кл. G 06 F 15/20,1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Цель изобретения — расширение функциональных возможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами. Устройство содер„„!Ы„„1644166 А1 жит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок определения кратчайшего пути, блок 4 памяти, блок 5 умножения, многоканальный накапливающий блок 6 выбора максимума, блок 7 выбора минимума, вход 8 пуска устройства. выходы 9-11 блока 1 синхронизации и выходы 12 признаков соответствия вершин внешнему центру графа. Перед началом работы устанавливают в исходное состояние блок 2 перечисления подмножеств пар вершин, в блок 3 заносят информацию о топологии графа, в блок 4 памяти заносят веса вершин графа, обнуляют каналы блока 6. На вход 8 пуска устройства подают импульс уровня логической единицы. При зтом на одном (или нескольких) выходах 12 будет ф сформирован признак соответствия вершины внешнему центру графа. 2 ил.

1644166

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

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

Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок 3 определения кратчайmего пути, блок 4 памяти, блок 5 умножения, многоканальный накапливающий блок 6 выбора максимума, блок 7 выбора минимума, вход 8 пуска устройства, выходы 9-11 блока

1 синхронизации и выходы 12 признаков соответствия вершин внешнему центру графа.

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

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

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

9-11 последовательность сигналов, предусмотренную временной диаграммой его работы. Потенциал уровня логической единицы появляется на выходе 9. блока 1 синхронизации. При этом блок 2 формирует на своих выходах 9-11 последовательность сигналов, предусмотренную временной диаграммой его работы. Сигнал уровня логической единицы появляется на выходе 9 блока 1 синхронизации. При этом блок 2 формирует очередное подмножество вер- шин (т.е. выдает на свои выходы очередные номера начальной и конечной вершин графа). Через время, достаточное для выполнения указанной операции, блок 1 синхронизации снимает сигнал с выхода 9 и формирует сигнал уровня логической единицы на своем выходе 10. При этом блок 3 определения кратчайшего пути выдает на свой выход величину веса кратчайшего пути между заданной парой вершин, Одновременно блок 4 памяти выдает на свой информационный выход значение. соответствующее выбранному адресному входу (т.е. вес конечной вершины пути). При этом блок 5 умножения формирует на своем выходе произведение поступивших на его входы сомножителей (т.е, величину произ40

50 где В количество вершин в графе) подклю55 чен к M- лу входу задания конечной вершины пути блока определения кратчайшего пути и к M-му адресному входу блока памя10

30 ведения веса кратчайшего пути и scca конечной вершины пути). Через время, достаточное для выполнения указанных операций, блок 1 синхронизации снимает сигнал уровня логической единицы со своего выхода 10 и формирует сигнал уровня логической единицы на выходе 11, При этом, выбранный канал многоканального блока 6 (номер которого совпадает с номером текущей начальной вершины пути) сравнивает значение, накопленное в предыдущих тактах работы, с текущим значением, поступившим íà его информационный вход, выбирает большее из них и фиксирует (запоминает) его. Через время, достаточное для окончания указанной операции, блок 1 снимает сигнал со своего вь:-хода и формирует сигнал уровня логической единицы на своем выходе 9, после чего работа устройства повторяется, После того, как будут просмотрены все без исключения пары вершин графа, в каналах многоканального блока 6 будут накоплены значения максимальных произведений кратчайших путей из предполагаемых внешних центров графа (вершин графа) на веса конечных вершин, соединенных кратчайшим путем. При этом блок 7 выберет минимальное из этих значений и выдаст его на один из выходов 12 устройства в качестве признака соответствия одной иэ вершин внешнему центру графа, Формула изобретения

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

1644166

Составитель A.Ìèøèí

Тех ред M. Моргентал Корре кто р С. Ш екма р

Редактор Е.flan

Заказ 3242 тираж 436 Подписное

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

313035, Москва, Ж-35, Раушская наб., 4/5

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

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