Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/419 

Описание патента на изобретение SU1644166A1

8 1

УТ

Фиг1

К

Г

О

t

ON О

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

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

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

Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок 3 определения кратчайшего пути, блок 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 умножения формирует на своем выходе произведение поступивших на его входы сомножителей (т.е. величину произи

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

сигнал уровня логической единицы со своего выхода 10 и формирует сигнал уровня логической единицы на выходе 11, При этом, выбранный канал многоканального блока 6 (номер которого совпадает с номером текущей начальной вершины пути)срав- нивает значение, накопленное в предыдущих тактах работы, с текущим значением, поступившим на его информационный вход, выбирает большее из них и

фиксирует (запоминает) его. Через время, достаточное для окончания указанной операции, блок 1 снимает сигнал со своего выхода и формирует сигнал уровня логической единицы на своем выходе 9, после чего работа устройства повторяется.

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

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

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

35

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

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

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

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

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

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

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

0

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

Похожие патенты SU1644166A1

название год авторы номер документа
Устройство для решения задач на графах 1989
  • Алексеев Олег Глебович
  • Борисов Александр Михайлович
  • Ячкула Николай Иванович
SU1716538A1
Устройство для решения задач на графах 1989
  • Лапин Александр Юрьевич
SU1683037A1
Устройство для решения задач на графах 1989
  • Ильин Сергей Александрович
  • Листровой Сергей Владимирович
  • Певнев Владимир Яковлевич
  • Мариян Владимир Николаевич
  • Сова Вадим Иванович
SU1765832A1
Устройство для решения задач на графах 1989
  • Лапин Александр Юрьевич
SU1765833A1
Устройство для решения задач на графах 1989
  • Додонов Александр Георгиевич
  • Приймачук Виктор Порфирьевич
  • Сасюк Николай Макарович
  • Щетинин Александр Михайлович
SU1626256A1
Устройство для решения задач на графах 1988
  • Анисимов Владимир Юрьевич
  • Галимзянов Ильдар Хафизович
  • Денисович Павел Владимирович
  • Тихобаев Андрей Валентинович
  • Шевчик Александр Григорьевич
  • Сидоренко Наталья Анатольевна
SU1596343A1
Устройство для решения задач на графах 1988
  • Васильев Всеволод Викторович
  • Баранов Владимир Леонидович
SU1658171A1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ 1996
  • Игнатьев В.М.
  • Афанасьева Н.Ю.
  • Крючков А.Н.
RU2100838C1
Устройство для исследования параметров графа 1988
  • Алексеев Олег Глебович
  • Зотов Сергей Николаевич
  • Мержанов Валентин Юрьевич
  • Ячкула Николай Иванович
SU1559353A1
Устройство для решения задач оптимизации 1989
  • Алексеев Олег Глебович
  • Барабанов Владимир Викторович
  • Буслаев Владимир Александрович
  • Васильковский Сергей Александрович
  • Шалимов Владимир Александрович
SU1730644A1

Иллюстрации к изобретению SU 1 644 166 A1

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

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

Формула изобретения SU 1 644 166 A1

Фиг 2

Документы, цитированные в отчете о поиске Патент 1991 года SU1644166A1

Устройство для исследования параметров графов 1984
  • Бороденко Евгений Иванович
  • Назаренко Владимир Евгеньевич
SU1241266A1
кл
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1
Устройство для исследования параметров графа 1988
  • Алексеев Олег Глебович
  • Зотов Сергей Николаевич
  • Мержанов Валентин Юрьевич
  • Ячкула Николай Иванович
SU1559354A1
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

SU 1 644 166 A1

Авторы

Радионов Геннадий Анатольевич

Бороденко Евгений Иванович

Горев Павел Григорьевич

Казарцев Вадим Алексеевич

Даты

1991-04-23Публикация

1989-01-30Подача