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 канала подключен к К-му информационному входу блока выбора минимума, К-й выход позиции минимума которого является выходом признака соответствия К- ой вершины внешнему центру графа устройства.
название | год | авторы | номер документа |
---|---|---|---|
Устройство для решения задач на графах | 1989 |
|
SU1716538A1 |
Устройство для решения задач на графах | 1989 |
|
SU1683037A1 |
Устройство для решения задач на графах | 1989 |
|
SU1765832A1 |
Устройство для решения задач на графах | 1989 |
|
SU1765833A1 |
Устройство для решения задач на графах | 1989 |
|
SU1626256A1 |
Устройство для решения задач на графах | 1988 |
|
SU1596343A1 |
Устройство для решения задач на графах | 1988 |
|
SU1658171A1 |
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ | 1996 |
|
RU2100838C1 |
Устройство для исследования параметров графа | 1988 |
|
SU1559353A1 |
Устройство для решения задач оптимизации | 1989 |
|
SU1730644A1 |
Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Цель изобретения - расширение функциональных возможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами. Устройство содержит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок определения кратчайшего пути, блок 4 памяти, блок 5 умножения, многоканальный накапливающий блок 6 выбора максимума, блок 7 выбора минимума, вход 8 пуска устройства, выходы 9-11 блока 1 синхронизации и выходы 12 признаков соответствия вершин внешнему центру графа. Перед началом работы устанавливают в исходное состояние блок 2 перечисления подмножеств пар вершин, в блок 3 заносят информацию о топологии графа, в блок 4 памяти заносят веса вершин графа, обнуляют каналы блока 6. На вход 8 пуска устройства подают импульс уровня логической единицы. При этом на одном (или нескольких) выходах 12 будет сформирован признак соответствия вершины внешнему центру графа. 2 ил. NV ё
Фиг 2
Устройство для исследования параметров графов | 1984 |
|
SU1241266A1 |
кл | |||
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Устройство для исследования параметров графа | 1988 |
|
SU1559354A1 |
Приспособление для точного наложения листов бумаги при снятии оттисков | 1922 |
|
SU6A1 |
Авторы
Даты
1991-04-23—Публикация
1989-01-30—Подача