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

(51) 5 АНИЕ БРЕТЕНИЯ ЕТЕЛЬСТВУ ВТОРСКОМУ(56) Авторское свидетельство СССР И. 1241266, кл. 6 06 6 7/48,1986.Авторское свидетельство СССР Ю 1559354, кл. 6 06 Р 15/20,1988.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Цель изобретения - расширение функциональных возможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами. Устройство содер 12 у 72 В ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР жит блок 1 синхронизации, блок 2 перечисления подмножеств пар вершин, блок определения кратчайшего пути, блок 4 памяти, блок 5 умножения, многоканальный накапливающий блок 6 выбора максимума, блок 7 выбора минимума, вход 8 пуска устройства, выходы 9-11 блока 1 синхронизации и выходы 12 признаков соответствия вершин внешнему центру графа. Перед началом работы устанавливают в исходное состояние блок 2 перечисления подмножеств пар вершин, в блок 3 заносят информацию о топологии графа, в блок 4 памяти заносят веса вершин графа, обнуляют каналы блока 6. На вход 8 пуска устройства подают импульс уровня логической единицы. При зтом на одном (или нескольких) выходах 12 будет ) сформирован признак соответствия вершины внешнему центру графа. 2 ил.Изобретение относится к области вычислительной техники и может быть использовано для исследования путей в графе,Цель изобретения - расширение функциональных возможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами,На фиг,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 последовательность сигналов, предусмотренную временной диаграммой его работы. Сигнал уровня логической единицы появляется на вь 1 ходе 9 блока 1 синхронизации. При этом блок 2 формирует очередное подмножество вершин (т.е. выдает на свои выходь 1 очередные номера начальной и конечной вершин графа). Через время, достаточное для выполнения указанной операции, блок 1 синхронизации снимает сигнал с выхода 9 и формирует сигнал уровня логической единицы на своем выходе 10. При этом блок 3 определения кратчайшего пути выдает на свой выход величину веса кратчайшего пути между заданной парой вершин, Одновременно блок 4 памяти выдает на свой информационный выход значение, соответствующее выбранному адресному входу (т,е, вес конечной вершины пути). При этом блок 5 умножения формирует на своем выходе произведение поступивших на его входы сомножителей (т.е, величину произ 40 50 где В количество вершин в графе) подклю чен к М-лу входу задания конечной вершины пути блока определения кратчайшего пути и к М-му адресному входу блока памя 10 15 20 25 30 ведения веса кратчайшего пути и веса конечной вершины пути). Через время, достаточное для выполнения указанных операций, блок 1 синхронизации снимает сигнал уровня логической единицы со своего выхода 10 и формирует сигнал уровня логической единицы на выходе 11, При этом, выбранный канал многоканального блока 6 (номер которого совпадает с номером текущей начальной вершины пути) сравнивает значение, накопленное в предыдущих тактах работы, с текущим значением, поступившим на его информационный вход, выбирает большее из них и фиксирует (запоминает) его. Через время, достаточное для окончания указанной операции, блок 1 снимает сигнал со своего вь: - хода и формирует сигнал уровня логической единицы на своем выходе 9, после чего работа устройства повторяется,После того, как будут просмотрены все без исключения пары вершин графа, в каналах многоканального блока 6 будут накоплены значения максимальных произведений кратчайших путей из предполагаемых внешних центров графа (вершин графа) на веса конечных вершин, соединенных кратчайшим путем, При этом блок 7 выберет минимальное из этих значений и выдаст его на один из выходов 12 устройства в качестве признака соответствия одной иэ вершин внешнему центру графа,Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, блокопределения кратчайшего пути и блок выбора минимума, причем вход пуска устройства подключен к входу пуска блока синхронизации, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет определения внешнего центра в графе со взвешенными вершинами и ребрами, в него введены блок перечисления подмножеств пар вершин, многоканальный накапливающий блок выбора максимума, блок памяти и блок умножения, причем первый выход блока синхронизации подключен к тактовому входу блока перечисления подмножеств пар вершин, М-й выход позиции первого элемента подмножества которого (М=1 В,ти, информационный выход которого подключен к выходу первого сомножителя блока умножения, К-й выход позиции второго1644166 Составитель А.Миши Техред М. Моргентал едактор Е.Па Корре кто р С. Ш екма р Заказ 1242 Тираж 436 Подписное ВНИКНИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 313035, Москва, Ж-ЗЬ, Раушская наб 4/5 роизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 элемента подмножества (К,., В) подключен к К-му входу задания начальной вершины пути блока определения кратчайшего пути и к входу разрешения работы К-го канала многоканального накапливающего блока выбора максимума, второй выход блока синхронизации подключен к входу пуска блока определения кратчайшего пути, выход веса пути которого подключен к входу второго сомножителя блока умножения, выход которого подключен к информационному входу многоканального накапливающего блока выбора максимума, третий выход блока синхронизации подключен к тактовому входу многоканальногс накапливающего блока 5 выбора максимума, информационный выход К-го канала подключен к К-му информационному входу блока выбора минимума, К-й выход позиции минимума которого является выходом признака соответствия К ой вершины внешнему центру графаустройства.