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

 

Изобретение относится к вычислительной технике и может быть использовано д. 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 ил. ю (Л

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

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

РЕСПУБЛИК д51) 4 G 06 G 7/122

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

К д BTGPCHOMY СВИДЕТЕЛЬСТВУ

Я" 9

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ!

2l) 4194563/ 24-24 (22) 26.!1.86 (46) 30.07.88. Вюл. № 28 (72) О. Г. Алексеев и H. И. Ячкула (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 1241266, кл. G 06 G 7/48, 1984.

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

N<> 623208, кл. С) 06 Сл 7/122, 1966. (54) УСГРО)!СТВО ),. !Я ЛНА.г(ИВА ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано д1я определения внешнего радиуса любой вер >чины в графе. Устройство содержит группу из г(, элементов 1 задержки, где 1, количество дуг в графе, три группы из В триггеров 2, 3 и 4, где В количество вершин в графе, три группы из В элементов И,. И 5. 6 и 7, две группы из В элементов И 8 и 9, элемент И 10, вторую группу из В элементов 11 задержки, триггер

l2 и врсмяимпульспый интегрирующий пре„„SU„„1413650 А1 образователь 13 и группу из В элементов НЕ 14. Первое и второе наборные поля представлены на чертеже группами контактов 15, 16 и 17, 18 соответственно. Устройство содержит также: вход 19 начальной установки, вход 20 пуска, вход 21 опроса

К-й вершины графа (К=!,...,В), вход 22 задания К-й вершины графа, выход 23 признака наибольшей удаленности К-й вершины графа, выход 24 величины внешнего радиуса графа. Перед началом работы с помощью первого и второго наборного полей задают топологию графа. После пуска устройства начинается исполнение ветвей, выходящих из опрашиваемой вершины графа. При этом достигнутые вершины блокируются установкой в «О» соответствующего триггера 3.

После того, как все вершины в графе будут достигнуты (единичный потенциал на выходе элемента И 10), останавливается преобразователь 13, а на триггерах 14 фиксируется последняя из достигнутых вершин (на выходе элемента И 8 которой еще сохраняется единичный потенциал). 1 ил.

14!3650

S(x;)=тах (,а (х„х,)), х «х исследуемого

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

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

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

Устройство содержит первую группу из Д элементов 1 задержки, (где Д вЂ” — количество дуг в графе), три группы из В триггеров 2 — 4 (где  — количество вершин в графе), три группы из В элементов ИЛИ 5—

7, две группы из В элементов И 8 и 9, элемент И 10, вторую группу из В элементов 11 задержки, триггер 12, времяимпульсный интегрирующий преобразователь 13 и группу из В элементов НЕ 14.

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

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

К-й вершины графа, выход 23 признака наибольшей удаленности К-й вершины графа и выход 24 величины внешнего радиуса графа.

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

Перед началом работы с помощью первого и второго наборных полей задают топологию графа. При этом К-й контакт 15 первой группы первого наборного поля (соответствует выходу К-й вершины) соединяют с

М-м контактом 16 второй группы первого наборного поля (соответствует входу М-й дуги графа), М-й контакт 17 первой группы второго наборного поля (соответствует выходу М-й дуги графа) подключают к P-му контакту 18 К-го массива второй группы наборного поля (соответствует входу К-й вершины графа) (Р=1,...,Т, где Т вЂ” количество дуг, входящих в К-ю вершину графа).

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

При этом информация о вершинах графа записывается в триггеры 3, информация об опрашиваемой вершине записывается в триггеры 2, обнуляются триггеры 12 и 2 и преобразователь 13. На вход 20 пуска устпойства подают импульсный сигнал единичного уровня, который поступает на первые входы все, элементов ИЛИ 5 первой группы.

С выхода Н-го элемента ИЛИ 5 {Н вЂ” номер опрашиваемой вершины) импульсный сигнал единичного уровня через элементы 6 и 8 поступает на вход установки в «О» Н-ro триггера 3, который переходит в «О» и запрещает через элемент 11 задержки прохождение сигналов через элемент 8 И. Через

Н-й контакт 15 сформированный импульс поступает на входы элементов 1 задержки, подключенных к данному контакту (осуществляется исполнение вершин, исходящих из

Н-й вершины графа). Через время, равное весу пути, сигналы с выходов соответствующих элементов задержки поступают через контакты 17 и 18 второго наборного поля на входы элементов ИЛИ 7 и с их выходов на вторые входы элементов ИЛИ 6.

Далее устройство работает аналогично. После того, как на выходах всех элементов НЕ устанавливаются единичные сигналы (достигнуты все вершины в графе), единичный потенциал с выхода элемента И 10 устанавливает в «О» триггер 12, останавливая преобразователь 13, и, поступая на вторые входы всех элементов И 9, разрешает прохождение единичного импульса с выхода

П-й вершины графа (где П вЂ” последняя из достигнутых вершин) на вход установки в

«!» П-го триггера 4. На этом работа устройства заканчивается.

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

1-й в )-ю вершину.

Для неориентипованных графов а(х„х;)=

=a(x,, х,), И, j=1, m (где, m — количество вершин исследуемого графа; а (х,, х,) длина кратчайшего пути из j-й вершины в i-ю) . Следовательно, полученные значения S(x,)=R(x,) — внутреннему радиусу i-й вершины. По совокупности значений радиусов вершин исследуемого графа могут быть определены центры графа, являющиеся для неориентированных графов одновременно внешними, внутренними и абсолютными, т. е. найдена вершина ло. для которой

S(xo) = minlS(x;)}=min(R(x;))=min z {S(x,)+ х еХ Х<еХ

+R())

Кроме того, предлагаемое устройство позволяет определить две наиболее удаленные друг от друга вершины дерева графа и длину (вес) пути между ними (диаметр дерева) В=тах )а(х„х;)). х;,х ех

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

1413650

Составитель А. Чишин

Редактор 71. Пчелннская Техред И. Верее Корректор.!. Патай

Заказ 3788!53 Тираж 704 I1îëïèсíос

В1!ИИПИ Государственного комитета СССР flo делам изобретс ннй н открытий

113035, Москва, Ж вЂ” 35, Раушская най.. д. 4 5

Производственно-полиграфическое предприятие, г. Ужгород, 1,л. Проектная, 4 построено цифровое устройство для моделирования.

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

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

HE группы и входу К-го элемента задержки второй группы, выход которого подключен к первому входу K-го элемента И первой группы, выход которого подключен к входу установки в «О» К-го триггера второй группы, первому входу К-го элемента И второй группы и К-му контакту первой группы первого наборного поля, М-й контакт второй группы которого (М= 1,...Ä) подключен к входу М-го элемента задержки первой группы, выход которого подключен к М-му контакту первой группы второго наборного поля, Р-й контакт К-го массива второй группы которого (Р=1,...,T, где Т вЂ” количество дуг, находящих в К-ю вершину графа) подключен к P-vy входу К-го элемента ИЛИ третьей группы, выход которого подключен к второму входу К-го элемента ИЛИ, второй группы, выход которого подключен к второму входу К-го элемента И первой группы, 20 выход К-го элемента HE группы подключен к

К-му входу элемента И, выход которого подключен к вторым входам всех элементов

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