Устройство для анализа параметров графа Советский патент 1988 года по МПК G06G7/122 

со

О) ел

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит первую группу из Д элементов 1 задержки, (где Д - количество дуг в графе), три группы из В триггеров 2-4 (где В - количество вершин в графе), три группы из В элементов ИЛИ 5- 7, две группы из В элементов И 8 и 9. элемент И 10, вторую группу из В элементов 11 задержки, триггер 12, времяимпульс- ный интегрируюш.ий преобразователь 13 и группу из В элементов НЕ 14.

Для большей наглядности первое и второе наборные поля не имеют цифровых обозначений и представлены на чертеже первой группой из В контактов 15 первого наборного поля, второй группой из Д контактов 16 первого наборного поля, первой группой из Д контактов 17 второго наборного поля и второй группой из в массивов контактов 18 второго наборного поля.

Устройство имеет вход 19 начальной установки, вход 20 пуска, вход опроса 21, /(-и (К ,---,В) вершины графа, вход 22 задания /(-и вершины графа, выход 23 признака наибольшей удаленности /(-и вершины графа и выход 24 величины внешнего радиуса графа.

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

Перед началом работы с помошью первого и второго наборных полей задают топологию графа. При этом K-fi контакт 15 первой группы первого наборного поля (соответствует выходу /(-и вершины) соединяют с Л1-м контактом 16 второй группы первого наборного поля (соответствует входу М-к дуги графа), М-й контакт 17 первой группы второго наборного поля (соответствует выходу М-н дуги г рафа) подключают к Р-му контакту 18 массива второй группы наборного поля (соответствует входу /(-и вершины графа) (Р,...,Т, где Т - количество дуг, ВХОДЯШ.ИХ в К-к вершину графа). На один из входов 21 подают единичный потенциал (задают опрашиваемую величину), на входы 22 подают единичные или нулевые потенциалы (задают вершины графа). На вход 19 начальной установки подают импульсный сигнал единичного уровня. При этом информация о вершинах графа записывается в триггеры 3, информация об опрашиваемой вершине записывается в триггеры 2, обнуляются триггеры 12 и 2 и преобразователь 13. На вход 20 пуска устройства подают импульсный сигнал единичного уровня, который поступает на первые в.ходы всех элементов ИЛИ 5 первой группы.

С выхода Я-го элемента ИЛИ 5 (// - номер опрашиваемой вершины) импульсный сигнал единичного уровня через элементы 6 и 8 поступает на вход установки в «О //-го триг- гера 3, который переходит в «О и запре- шает через элемент 11 задержки прохождение сигналов через элемент 8 И. Через Я-й контакт 15 сформированный импульс поступает на входы элементов 1 задержки, подключенных к данному контакту (осуще0

ствляется исполнение вершин, исходящих из

5

Я-й вершины графа). Через время, равное весу пути, сигналы с выходов соответствующих эле.ментов задержки поступают через контакты 17 и 18 второго наборного поля на входы элементов ИЛИ 7 и с их выходов на вторые входы элементов ИЛИ 6. Далее устройство работает аналогично. После того, как на выходах всех элементов НЕ устанавливаются единичные сигналы (достигнуты все вершины в графе), единич0 ный потенциал с выхода элемента И 10 устанавливает в «О триггер 12, останавливая преобразователь 13, и, поступая на вторые входы всех элементов И 9, разрешает прохождение единичного импульса с выхода /7-й вершины графа (где Я - последняя из достигнутых вершин) на вход установки в «1 Я-го триггера 4. На этом работа устройства заканчивается.

Таким образом, суть изобретения состоит в определении значения внешнего радиуса

Q вершины

S(Zi)max la(xi, х/),

Xj С X

где я - множество вершин исследуемого графа;

г a(xi,Xj) -длина (вес) кратчайшего пути из

i-й в /-Ю вершину.

Для неориенти 2ованных графов a(x,, Xj) a(Xj, Xi), vi, , т (где, т - количество вершин исследуемого графа; а (л ,, л ,) - длина кратчайшего пути из /-и вер0 пJины в i-K). Следовательно,полученные значения S(Xi)R(x,) - внутреннему радиусу (-Й вершины. По совокупности значений радиусов вершин исследуемого графа могут быть определены центры графа, являю- щиеся для неориентированных графов одновременно внешними, внутренними и абсолютными, т. е. найдена вершина л. для которой

5(4) tninlS(Xi)} min{R(xi) {S(x,}+

.

+ R(X,)}.

Кроме того, предлагаемое устройство позволяет определить две наиболее удаленные друг от друга вершины дерева графа и длину (вес) пути между ними (диаметр дерева) {а(х,, А-/)}. Xt.xyex

При использовании в качестве элементов 1 задержки регистров сдвига может быть

построено цифровое устройство для моделирования.

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

Устройство для анализа параметров графа, содержащее первую группу из Д элементов задержки, где Д - количество дуг в графе, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения внешнего радиуса любой вершины графа, в него введены три группы из В триггеров, где В - количество вершин в графе, три группы из В элементов ИЛИ, две группы из В элементов И, элемент И, два наборных поля, вторую группу из В элементов задержки, группу из В элементов НЕ, триггер и времяимпульсный интегрирующий преобразователь, причем вход начальной установки устройства подключен к входам признаков записи всех триггеров первой и второй групп, входам установки в «О всех триггеров третьей группы, входу установки в «О триггера и входу установки в «О времяимпульсного интегрирующего преобразователя, вход пуска устройства подключен к первым входам всех элементов ИЛИ первой группы и входу установки в «1 триггера, вход опроса /С-й вершины графа (,...,5) устройства подключен к информационному входу /(-го триггера первой группы, выход которого подключен к второму входу /С-го элемента ИЛИ первой группы, выход которого подключен к первому входу /(-го элемента ИЛИ второй группы, вход задания /(-и вершины графа устройства подключен к информационному входу /С-го триггера второй группы, выход

0

5

которого подключен к входу Л -го элемента НЕ группы и входу Д -го элемента задержки второй группы, выход которого подключен к первому входу Л, -го элемента И первой группы, выход которого подключен к входу установки в «О /(-го триггера второй группы, первому входу /(-го элемента И второй грун- пы и /(-му контакту первой группы первого наборного поля, М-й контакт второй группы которого (,...Д) подключен к входу /И-го элемента задержки первой группы, выход которого подключен к /М-му контакту первой группы второго наборного поля, Я-й контакт /(-го массива второй группы

которого (, где Т - количество дуг,

находящих в /(-ю вершину графа) подключен к Я-му входу /(-го элемента ИЛИ третьей группы, выход которого подключен к второму входу /(-го элемента ИЛИ, второй группы, выход которого подключен к второму входу /(-го элемента И первой группы,

0 выход Д -го элемента НЕ группы подключен к /(-му входу элемента И, выход которого подключен к вторым входам всех элементов И второй группы и входу установки в «О триггера, выход которого подключен к входу

5 разрешения работы времяимпульсного интегрирующего преобразователя, выход которого является выходом величины внешнего радиуса графа устройства, выход Д -го элемента И второй группы подключен к входу установки в «1 /(-го триггера третьей группы, выход которого является выходом признака наибольшей удаленности Д-й вершины графа устройства, контакты первого и второго наборных полей соединены в соответствии с топологией графа.

0

Изобретение относится к вычислительной технике и может быть использовано д. 1Я определения внешнего ра-диуса /побои liepiiuiHbi в графе. Устройство содержит группу из Л элементов 1 задержки, 1-де Л количество дуг в графе, три группы из В триггеров 2, 3 и 4, где В - количество верпшп в графе, три группы из В э,:1ементов ИЛИ 5. 6 п 7, две группы из В ;1емептов И 8 и 9, эле.мент И 10, вторую руину из В элементов 1 1 задержки, триггер 12 и времяимпульс1п |й интегрирующий преобразователь 13 и группу из В элементов НЕ 14. Первое и второе наборные поля представлены на чертеже группами контактов 15, 16 и 17, 18 соответственно. Устройство содержит также: вход 19 начальной установки, в.ход 20 пуска, вход 21 онроса /(-и вершины графа (/(1В), вход 22 задания верп1ины графа, выход 23 признака наибольн1ей удаленности вер1нины графа, выход 24 величины внешнего радиуса графа. Перед началом работы с помощью первого и второго наборного полей задают топологию графа. После пуска устройства начинается испо пнение ветвей, выходящи.х из опрашиваемой вер1нины графа. При этом достигнутые вершины блокируются установкой в «О соответствующего триггера 3. После того, как все вернщны в графе будут достигнуты (единичный потенциа, на выходе элемента И 10), останавливается преобразователь 13, а на триггерах 14 фиксируется последняя из достигнутых вершин (на выходе элемента И 8 которой еще сохраняется единичный потенциал). I ил. ю (Л