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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН

2229 А1 (19) SU((() ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4375471/24-24 (22) 03.02.88 (46) 15.11.89. Бюл. N 42 (72) Г.С.Колесник (53) 681.333(088.8) (56) Авторское свидетельство СССР

В 1241266, кл. G 06 G 7/48, 1984.

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

9 1251097, кл. С 06 F 15/20, )984. (54) УСТРОЙСТВО ДЛЯ АНАПИЗА IIAPANETPOB ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано дпя создания цифровых и аналоговых вычислительных устройств для решения задач на графах. Цель изобретения — сокращение аппаратурных затрат при определении вершин., входящих (д11 4 G 06 F 15/20, G 06 G 7/122

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

152?229

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

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

На фиг.1 представлена функциональная схема устройства; на фиг.2 временная диаграмма работы блока синхронизации; иа фиг.3 — функциональная схема базовой модели ориентированного графа (орграфа); на фиг.4— функциональная схема универсальной модели орграфа; на фиг.5 - способ имитации состояния функциональной 20 модели вершины (Ф!1В) и функциональной модели дуги (ФИД); на фиг.б способ задания начальных вершин орграфа; на фиг.7 — способ регистрации

C OCT ORHHH ФИВ H ФМД; Ha фиг . 8 соб задания конечных вершин орграфа; на фиг.9 — способ регистрации событий, связанных с моделированием вершин и дуг орграфа; на фиг.10 — пример топологии орграфа; на фиг.11 — 0 пример структурной оптимизации базовой модели орграфа; на фиг.12 — пример структурной оптимизации универсальной модели орграфа, на фиг.13-15| примеры модульнои оптимизации универсальной модели орграфа„на фиг.16 функциональная схема базовой модели неориентированного графа; на фиг.17 его универсальная модель; на фиг,l8 способ имитации состояния ФИР; на фиг.19 — способ имитации состояния

ФМВ; на фиг.20 — способ задания начальных вершин (ребер) неориеитирован. ного графа; на фиг.21 — способ регистрации состояния вершин (ребер) неориентированного графа; на фиг.22— способ задания конечнык вершин (ве;

6ep) неориентированного графа; На. фиг.23 — способ регистрации событий, связанных с состоянием ФИВ и ФМР; на фиг.24 — пример топологии неориентированного графа,", на фиг.25 " пример структурной оптимизации базовой модели неориентированного графа; на фнг.26 — пример структурной оптимиэа55 ции универсальной модели неориентированного графа; на фиг.27 — пример модульной оптимизации универсальной модели неориентированного графа, ; на фиг,28 — пример функциональной схемы блока определения кратчайшего пути.

Устройство содержит блок 1 определения кратчайшего пути, времяимпульсный интегрирующий преобразователь 2, блок 3 синхронизации и накапливающий блок 4 логического сложения. Кроме того, на фиг.! обозначены: вход 5 пуска устройства, первый б и второй 7 выходы блока 3 синхронизации, вход 8 задания радиуса окрестности радиуса устройства, входы 9 задания центра графа устройства и выходы 10 признаков принадлежности вершин составу вершин окрестности центра графа устройства.

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

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

После выдачи на вход 5 пуска устно и ройства импульса уровня лог. 1 блок 3 синхронизации начинает формирование последовательности сигналов, предусмотренной временной диаграммой его работы (фиг.2). Сигнал на выходе 6 блока 3 устанавливает в "0" преобразователь 2, сигнал на нервом выходе группы блока 3 задает начальную вершину графа (т.е. вершину, проверка которой на принадлежность ссставу вершин окрестности графа производится в первом такте работы).

Через время, достаточное для установки в "0" преорразователя 2, блок 3 снимает сигнал с выхода 6. Потенциал уровня лог. "1 " с выхода 7 блока 3 разрешает работу пресбраэоьателя 2.

Последний формирует на своем информационном выходе линейно возрастающий сигнал (например, цифровой код или напряжение), который имитирует состояние начальной вершины графа. Через время, достаточное для достижеи и ния порога, сигнал уровня ло-, с выхода признака достижеHHH порога преобразователя 2 разрешает очередной такт работы блока 3 синхронизации. Последний формирует последовательность сигналов, предусмотренную временной диаграммой его работы. Сигнал с выхо« да б блока 3 устанавливает в "0" пре5 152222 образователь 2, сигнал на втором выходе группы блока 3 задает начальную вершину графа (т ° е. вершину (вторую), проверка которой на принадлежность сосоставу вершин окрестности центра графа производится во втором такте работы). Далее работа устройства повторяется до полного перебора всех В вершин графа. Если в каком-либо такте работы устройства моделирование конечной вершины графа будет закончено (конечная вершина будет достигнута из начальной), на выходе признака окончания моделирования конечной вер- 15 шины модели 1 появляется потенциал уровня лог. "О". По этому сигналу накапливающий блок 4 логического сложения произведет сложение (по ИЛИ) информации, накопленной в предыдущих цик- 20 лах работы, с текущими сигналами с выходов группы блока 3 (т.е ° присоединение вершины, опрошенной в данном такте работы, к составу вершин, принадлежащих окрестности центра графа). 25

Рассмотрим конструкцию блока определения кратчайшего пути.

Часто для решения критических задач (определения кратчайшего или ... длиннейшего пути, максимального или 3р минимального потока и т.п.) в системах, описываемых графами, используют их

{т, е. систем) матричные модели. Поскольку модели систем, описываемых ориентированными гРафами (орграфами) 35 и неориентированными графами (графами), имеют некоторые отличия, они разбираются отдельно.

Рассмотрим моделирование систем, опи.сываемых орграфами (т.е. модепирова.- 40 ние орграфов).

Представленная на фиг.3 базовая модель орграфа содержит матрицу из

ВхВ функциональных моделей ll дуг и

rpynny из В функциональных моделей 12 45 вершин, причем вход 13 задания параметров моделирования (К,М)-й дуги модели орграфа (К = 1,...,В; М = 1,...В, где  — количество вершин в графе) подключен к одноименному входу К-й 5р модели 11 М-й строки матрицы, выход з: значения функций которой является выходом 14 состояния (К,М)-й дуги модели орграфа и подключен к входу М-ro аргумента К-й модели 12 группы, выход значения функции которой является выходом 15 состояния К-й вершины модели орграфа и подключен к выходам аргумента всех моделей 11 К-й строки

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

Поскольку (К,М)-я ФМД ll матрицы соответствует (К,М)-му элементу матрицы смежности графа, базовая модель орграфа позволяет моделировать орграфы произвольной топологии, количество вершин в которых не превьппает В.

Однако необходимость каждый pas перед началом работы задавать параметры всех дуг и вершин независимо от их наличия в моделируемом орграфе значительно усложняет моделирование, особенно в орграфах с большим количеством вершин (в случае отсутствия каких-либо дуг в орграфе приходится задавать бесконечно большие параметры, например бесконечно большие времена задержек или бесконечно большие пороги срабатывания, а при отсутствии взвешенных вершин — бесконечно малые параметры моделирования).

Указанного недостатка в значительной мере лишена представленная универсальная модель орграфа (фиг.4), По сравнению с базовой моделью орграфа в нее введена матрица иэ ВхВ ключей 17 (в общем случае любых коммутационных элементов, начиная от коммутационных (распаянных) перемычек, устанавливаемых между информационным входом и выходом ключа непосредственно перед моделированием, и кончая электронными ключами с многоразрядными входом и выходом), причем выход значения функции (К,М)-й ФМД 11 матрицы подключен к информационному входу (К,М}-ro ключа 17 матрицы, информационный выход которого является выходом состояния (К,М)-й дуги модерн орграфа и подключен к входу М-го аргумента К-й ФМВ 12 группы, управляющий вход (вход включения) (К,М)-го ключа 17 матрицы является входом 18 признака наличия (К,М)-й дуги модели орграфа, Остальные связи универсальной модели полностью соответству". ют связям базовой модели орграфа.

Подавая на входы 18 потенциалы уровня лог. "1" (например, с соответст» вующих выходов блока задания матрицы с " ..;ности), можно легко изменить топологию орграфа1 не перенастраивая

ФМД 11, что особенно удобно, когда исследуются части орграфа.

1522229

Моделирование орграфа рассмотрим ,на примере решения задачи определения величины кратчайшего пути.

Пусть в качестве ФМД 11 использу;ются элементы задержки, причем вход элемента задержки является в данном случае входом аргумента ФМД 11, выход - выходом значения функции, а вход задания величины задержки — входом задания параметров моделирования; в качестве ФМВ 12 используется элемент ИЛИ, причем его входы являются в данном случае входами аргументов ФМВ 12, а выход — выходом значения функции ФМВ 12. Пусть требуется определить величину кратчайшего пути между начальной (Н-й) и конечной (Е-й) вершинами.

Перед началом работы задают топологию орграфа и устанавливают величи ны задержек пропорциональными весам соответствующих дуг графа. На Н-й выход 15 модели орграфа (т.е. приме нительно к данному случаю на выход

Н-го элемента ИЛИ) подают импульсный сигнал или потенциал уровня лог. "1" ! (т.е. имитируют исполнение началь- ной вершины орграфа), который поступает на входы всех ФМД 11 Н-й строки матрицы,(т.е. на входы всех элементов задержки данной строки), По окончании моделирования дуг (т.е. по появлению задержанных на величину веса соответствующих дуг сигналов уровня лог. "1" на выходе элементов задержки) сигналы с выходов соответствующих им

ФМВ 12 (т.е. фактически с выходов элементов ИЛИ) поступают на входы

ФМД 11 следующих строк матрицы и т.д. до тех пор, пока сигнал уровня лог. "1" не появится на выходе E-й

ФМВ 12 (Е-ro элемента ИЛИ), что свидетельствует об окончании моделирования Е-й вершины. Время, прошедшее от момента имитации исполнения начальной вершины до момента окончания моделирования конечной вершины графа, соответствует величине кратчайшего пути между этими вершинами.

Пусть в качестве ФМД 11 использу- ются пороговые элементы, причем вход порогового элемента является в данном случае входом аргумента ФМД 11, выход — выходом значения функции, а вход задания величины порога — входом задания параметров моделирования. В качестве ФМВ 12 в этом случае могут быть использованы блоки выбора мак5

55 симума, причем его информационные входы являются входами аргументов

ФМВ 12 а информационный выход — выходом значения функции ФМВ 12,Пусть требуется определить величину кратчайшего пути между начальной Н-й и конечной

Е-й вершинами орграфа.

Перед началом работы задают топологию графа и устанавливают величины порогов пропорциональными весам соответствующих дуг графа. На Н-й выход 15 модели орграфа подают возрастаюший по значению сигнал, например цифровой код или напряжение (т.е. имитируют исполнение начальной вершины орграфа), который (сигнал) поступает на входы всех ФМД Н-й строки матрицы (т.е. на входы всех пороговых элементов данной строки). По окончании моделирования дуг (т,.е. по достижении сигнала на входах пороговых элементов величины порога) сигналы с выходов ФМД 11 (численно равные разности между значением сигнала на его входе и значением соответствующего ему порога) поступают на входы соответствующих им ФМВ !2 и с их выхода — на входы ФМД 11 следукмцих строк матрицы и т.д. до тех пор, пока сигнал на выходе Е-й ФМВ 12 не станет больше "0", что свидетельствует об окончании моделирования орграфа. Разность значений сигналов на выходах Н-й и Е-й ФМВ 12 соответствует величине кратчайшего пути между этими вершинами.

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

СКД 11 и @ИВ 12, а также независимо от осуществляемых ими функциональных преобразований функциональная схема модели орграфа и ее работа не изменяются, что оправдьвает терминологию, выбранную для описания моделей дуг, моделей вершин и их функциональных входов. Аргументы и значения функций

ФМД 11 и ФМВ 12 могут быть представлены любыми аналоговыми величинами (значением напряжения, тока, частоты, фазы и т.п.) или цифровыми кодами (числовым — в любой системе счисления, кодоимпульсным, числоимпульсом, амплитудно-импульсным и т.п.), Очень часто элементная база, выбранная для моделирования дуг и вершин орграфа, не допускает подключения входа 19 имитации исполнения вершины

1522229 (дуги) непосредственно к выходу

МВФ 12 .(ФМД 11), как показано на фиг.5а. В этом случае используют развязывающие элементы (элемент ИЛИ 20 на фиг.5б), а при наличии в орграфе

5 циклов и петель, когда на выходе развязывающего элемента может образоватьсяя- логическая сумма сигналов ими" тации исполнения вершины (дуги) и сигналов ее собственного состояния, используют ключи 21, 22 или коммутаторы 23. При подаче на вход 24 признака имитации исполнения вершины (дуги) сигнала уровня лог. "1" ключи 21 и 22 !5 обеспечивают отключение выхода ФМВ 12 (ФМД 11) от входа 19 и подключение входа 19 к входам всех ФМД 11 (к одному из входов ФМВ.12) соответствующей строки матрицы (соответствующего 20

ФМВ 12 группы) (фиг.5в,г) или изменения направления коммутации (фиг. 5д) .

Объединение вторых информационных направлений всех коммутаторов 23, всех ФМВ 12 группы (всех ФМД 11 мат- 25 рицы) (фиг.6) позво. пяет ввести понятие — вход 25 имитации исполнения начальной вершины. В этом случае входы 24 признаков имитации исполнения вершин (дуг) орграфа допустимо называть входами задания начальных вершин (дуг) ор графа.

Регистрация состояния ФИВ 12 (ФМД 11) иногда также требует отключения выхода 15 (14) от выхода значения функции ФМВ 12 (ФМД 11). В этом

3S случае выход 15 (14) подключают к выходу ФМВ 12 (ФМД 11) через нормально разомкнутый ключ 26. Подавая на вход 27 опроса состояния вершины (ду- 40 ги) сигнал уровня лог. "1", подключают выход ФМВ 12 (ФМД 11) к выходу 15 состояния вершины (дуги) модели орграфа. Объединяя по ИЛИ (на фиг.8 показано монтажное ИЛИ) информацион- 45 ные выходы всех ключей 26, можно ввести понятие — выход 28 состояния конечной вершины (дуги) графа, В этом случае входы 27 опроса состояния вершин (дуг) модели орграфа допустимо называть входами задания конечной вершины (дуги) орграфа.

Решение некоторых задач требует регистрации каких-либо характерчых состояний ФМВ 12 и ФМД 11, например начало моделирования вершины (дуги), окончание моделирования, переход через минимум или максимум значения функции на выходе ФМД 11 или ФМВ 12, 10 и т.п. В этом случае к выходам 15 (14)

ФМВ 12 (фиг.9а) подключают блоки 29 сравнения, настроенные на фиксацию определенного состояния, выходы признаков отношения (равно, не равно, больше, меньше и т.п.) которых являются выходами 30 событий модели орграфа. Подключение блока 29 сравнения к выходу 28 состояния конечной вершины (дуги) орграфа позволяет фиксировать события, связанные с конечной вершиной орграфа (фиг.9б).

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

Метод структурной оптимизации предполагает исключение всех аппаратных средств устройства, которые не añпользуются при данном его применении.

Например, если автомобиль применяют как укрытие от непогоды, из его состава могут быть исключены колеса и двигатель. Применительно к моделированию орграфов это означает, что из состава модели могут быть исключены все ФИД 11, ФМВ 12 и любые другие элементы, структура совокупности которых отражает топологию орграфа, ко торые не предусмотрены топологией кон. кретного орграфа. Например, для орграфа, топология которого представлена на фиг.10, структурная оптимизация базовой и универсальной модели показана на фиг,11 и !2 соответственно.Обычно в этом случае говорят,что модели дуг 11 и 12 вершин соединены в соответствии с топологией орграфа, Пунктиром показаны <ИЩ 11 и ФИВ 12 и ключи 17,которые исключены из базовой и универсальной моделей орграфа в результате их структурной оптимизации, Конструктивно аппаратные средства моделей орграфов, как и любых других устройств, могут быть выполнены в виде модулей, которые соединяют между собой в соответствии с требованиями конкретной задачи. В модуль может быть выделена любая повторяющаяся часть аппаратных средств.. Например, на фиг.13а показан модуль 31, в состав которого введены К я ФМВ 12 и все соответствующие ей ФМД 11. В этом случае базовая модель орграфа принимает вид, показанный на фиг.13б. На фиг.14а показан модуль 32, в состав которого введены все ФМД 11, соответ11 !

52 ствующие дугам инцидентным К-й вершине графа. В этом случае базовая модель орграфа принимает вид, показанный на фиг.14б. На фиг.15а показан модуль 33, в состав которого введены ключ 17 и ФМД ll соответствующие ( (К,М)-й дуге графа. В этом случае универсальная модель орграфа принимает вид, показанный на фиг.15б.

Среди преимуществ модульной организации аппаратуры можно указать сл едующие: возможность сокращения аппаратурных затрат за счет замены совокупности аппаратуры, выделенной в модуль ее моделью (например, цифровой); повышение эффективности структурной оптимизации модульно организованного устройства, так как, исключая из его состава модули в соответствии с методом структурной оптимизации, фактически подвергают структурной оптимизации все блоки, включенные в состав модуля.

Рассмотрим моделирование систем, описываемых неориентированными графа1 ми (т. е.моделирование неориентированных графов) . .Неориентированные графы можно исследовать на моделях орграфов. В этом случае каждое ребро неориентированного графа представляется как две противоположно направленные дуги и; каждой дуге ставят в соответствие

ФИД 11.

Однако для моделирования неориентированных графов используют модели неориентированных ребер и вершин.

Представленная на фиг.16 базовая модель неориентированного графа (графа) содержит матрицу из 1/2 В(В+!) функциональных моделей 34 ребер (ФИР 34) и группу из В функциональных моделей 35 вершин (ФМВ 35), причем вход 36 задания параметров моделирования (К,N)-го ребра графа (К =

М,...,В; М = 1,...,В) подключен к одноименному входу (К,М)-й ФМР 34 матрицы, первый вход аргумента (вход значения функции) которой подключен к К-му входу аргумента (выход значения функции) M-й ФМВ 35 группы, второй вход .аргумента (выход значения функции) (К,N) -й ФМР 34 матрицы подключен к (М вЂ” 1)-му входу К-й ФМВ 35, вход задания параметров моделирования которой является одноименным входом 37 модели графа, Пунктирог. на

2229 1 ? фиг.!6 показаны те ФМР 34, которые исключены из модели графа в силу симметрии его матрицы смежности.

Необходимость задания перед началом работы параметров всех ФМР 34 матрицы при изменении топологии графа является недостатком базовой модели графа. В значительной мере он оп1р :,ðåäeëåí в универсальной модели графа, функциональная схема которой представлена на фиг.!7. По сравнению с базовой моделью в универсальную модель графа введена матрица из 1/2 В(В+1) ключей 38, причем второй вход аргумента (выход значения функции)(К,И) -й

ФМР 34 матрицы подключен к первому информационному входу/выходу (К,И)-го ключа матрицы, второй информационный вход/выход которого подключен к (М-1)-му входу аргумента (выходу значения функции)К-й ФМВ 35 группы, вход

39 признака наличия (К,М)-го ребра модели графа подключен к управляюще26 му входу (к входу включения)(К,M)-ro ключа 38 матрицы. Остальные конструктивные признаки базовой и универсальной моделей совпадают. Подавая на входы 39 потенциалы, уровня лог, "1", 30 например, с выходов блока задания матрицы смежности, задают топологию моделируемorо графа.

Процесс моделирования графа ничем не отличается от процесса моделирова- ния орграфа. Точно так же имитируют:-: исполнение вершины или ребра графа и регистрируют изменения параметров других вершин и ребер, Однако поскольку

ФМР 36 и ФИВ 35 двунаправлены имитировать исполнение вершины (ребра) приходится на каждом из ее входов (выходов). С этой целью к выходам 40 состояния (К,M)-й ФМР 34 по И-й и К-й вершинам модели графа подключают вхо45 ды 41 имитации исполнения ребра по

И-й и К-й вершинам модели графа (фиг,18а). Если элементная база, выбранная для моделирования графа,или

его топология (с циклами и петлями) не допускает подключения входов/выходов ФИР 34 к соответствующим входам 41, используют ключи 42-45 или ксммутаторы 46 и 47. При подаче сигнала уровня лог. "1" на вход 48 признака имитации исполнения (К,M)-ребра модели графа ключи 42 и 43 отключают входы/выходы ФМР 34 от входов 41, ключи 44 и 45 подключают входы 41 к соответствующим входам 40 (фиг,18б,в), 13

15222 а коммутаторы 46 и 47 изменяют на. правление коммутации (фиг.18г). Варианты схем для имитации исполнения взвешенных вершин показаны иа фиг.l9a-r, Точно так же при подаче

5 сигнала на вход 48 признака имитации исполнения вершины модели графа ключи 49 группы отключают входы/выходы

ФИВ 35, ключи 50 группы подключают входы 51 имитации исполнения К-й вершины по И-му ребру модели графа к соответствующим выходам 40, а коммутаторы 52 группы изменяют направление, отключая входы/выходы ФМВ 35 от выходов 40 и подключая к выходам 40 соответствующие входы 51. Во всех случаях нулевой индекс в обозначении входов относится к обозначению петли, принадлежащей вершине, обозначенной вторым индексом того же цифрового обозначения входа.

Объединение вторых информационных направлений коммутаторов 46 и вторых информационных направлений коммутаторов 47 (т.е.объединение всех однотипных входов 41 имитации исполнения ребер) (фиг.20) позволяет ввести понятие входов 53 имитации исполнения начального ребра модели графа по

К-й и И-й вершинам графа, В этом случае входы 48 признаков имитации исполнения ребер допустимо называть входами задания начальных ребер (фиг.20}.

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

Регистрация состояния ФМР 34 по каждой из инцидентных вершин и состояния ФИВ 35 пО каждому инцидентнОиу ребру иногда также требует отключения выходов 40 от каждого из входов/выходов NIP 34 и ФИВ 35. С этой целью используют ключи 54 и 55. Подавая на вход 56 опроса состояния (К,И)-й

ФИР 34 или вход 57 опроса состояния

К-й ФМВ 35 модели графа потенциал уровня лог.. "1", подключают входи/ выходы ФМР 34 и АВИВ 35 к соответствую.щим выходам 40. Объединяя по ИЛИ (на фиг.22 показано монтажное ИЛИ) информационные выходы ключей 55 с одноименными индексами можно ввести поР

L$ нятие выхода 40 состояния конечной вершины графа по К-му ребру модели графа. В этом случае входы 57 опроса состояния вершин модели графа допусти29 14 мо называть входами задания конечной вершины графа.

Таким же образом можно задавать конечные ребра графа»

Р ешение некоторых задач требу ет регистрации некоторых характерных состояний ФИР 34 и ФИВ 35, например, начало моделирования вершины (ребра), окончания моделирования и т.п. В этом случае ко всем или некоторым выходам 40 состояния ФИР 34 и/или

ФИВ 35 подключают блоки 58 и/или 59 сравнения. По входам 60 и/или 61 задают значения параметров по каждому выходу 40, совокупность которых (параметров) служит признаком осуществления события, о появлении которой говорит появление сигнала уровня лог. "1 и и на выходе признака отношения (" Больше", "Иеньше", "Равно" и т.п.) блока 58 и/или 59 сравнения, который является выходом 62 и/или 63 осуществления события модели графа (фиг.23а,б). Аппаратные средства моделей графов можно значительно упростить, используя метод структурной оптимизации, например, для графа, топология которого представлена на фиг.24 (цифрами обозначены номера вершин, взвешенные вершины изображены в в:--,;..е жирной точки)р структурная Оптимизация базОВОй и универсальной моделей графа показана на фиг.25 и 26 соответственно;

ОбычнО В этОм случае гОВОрят, что

ФИР 34 и ФНВ 35 соединены в соответствии с топологией графа. Пунктиром на фиг.25 и 26 показаны ФИР 34 и ФИВ 35, которые исключены из базовой н универсальной моделей графа в результате их структурной оптимизации.

Конструктивно аппаратные средства моделей графов могут быть Выполнены в виде модулей. В модуль может быть введена любая повторякщаяся часть аппаратных средств. На фиг.27а показан мОдуль 64» В cocTGs KoTopoFo Вве дены ФИР 34 и ключ 38. В этом случае универсальная модель графа принимает вид, показанный на фиг.27б, Таким образом, методы и средства моделирования, оптимизации и построения моделей графов практически ничем не отличаются от аналогичных методов и средств моделей орграфсв, если не с .ать использование элементов двунаправленных по своим входам/выходам и исключение всех поддиагональных элементов из структуры соответствую»

15 152222 щих неориентированным графам аппаратных средств.

В соответствии с изложенным блок 1 определения кратчайших путей для не5 ориентированного графа беэ взвешенных ребер может быть выполнен по схеме, показанной на фиг.28.

В том случае, если ФМР 34 выполнены в виде двунаправленных пороговых элементов и перед началом работы по входам 36 задан порог срабатывания каждой ФМР 34, то при подаче возрастающего сигнала на вход 65 имитации исполнения начальной вершины указанный сигнал через один из ключей 67, открытый подачей на его управляющий вход сигнала уровня лог, "1" с одноименного входа 66 задания начальной вершины графа, поступает на ФИР 34, соответствующие ребрам, инцидентным начальной вершине. Когда значение сигнала на входе 65 превысит величину кратчайшего пути иэ начальной в конечную вершину графа, ФЪР 34 25

{т.е, фактически, пороговые элементы) срабатывают и на резисторе 68 образуется падение напряжения, которое в качестве признака окончания моделирования конечной вершины графа поступает на выход 69 блока 1.

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

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

9 16 вершины блока определения кратчайшего пути, входы задания конечной верши. ны графа которого являются входами задания центра графа устройства, о т л и ч а и щ е е с я тем, что, с целью сокращения аппаратурных затрат при определении вершин, входящих в окрестность центра графа, в него введены блок синхронизации и накапливаюпцгй блок логического сложения, причем вход задания радиуса окрестности графа устройства подключен к входу задания-порога интегрирования времяимпульсного интегрирующего преобразователя, выход признака достижения порога которого подключен к входу пуска устройства и к тактовому входу блока синхронизации, первый и второй выходы которого подключены к входу установки в "О." и к входу разрешения работы времяимпульсного интегрирующего преобразователя соответственно, К-й выход группы блока синхронизации (К-=1.. °,,.В; где  — количество вершин в графе) подключен к К-му разря" ду информационного входа накапливающего блока логического сложения и к

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

4.4

° °

° 11

11

15222

° 1

ЮЮ ЮЮ

1522229

Е Е В Д

В В °

М"

В ° °

В В °

В В °

В Е °

О В В

В В В

° ° ° l7

Жю

ВВ ° ° °

М

Ю ° ° °

tg

М Ду

f5s

4 Н

Ж Ы

1522229 е е °

1522229!

522229

1522229

1522229

° °

° °

° lt

° !1 е )t

)522229!

522229

1522229

Фиг. ЯЗ

puz 25 ®ЮМ

62км ки

l 522225

1522229 б °

Ф °

Редактор М.Петрова

Заказ 6965/47 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

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

I.

) I

g I

Составитель - А.ушаков

Т ехред A. Кравчук Коррек тор М. Шар оши е I

° I

° I