Патент ссср 344464

344464

О П И С А Н И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 26.Х.1970 (№ 1485208/18-24) с присоединением заявки №

Приоритет

Опубликовано 07.VII.1972. Бюллетень № 21

Дата опубликования описания 2! VII.1972

M. Кл. б 06 7/48

Комитет по делам изобретений и открытий при Совете Иинистрав

СССР

УДК 681.333:66,012 (088.8) Авторы изобретения

П. М. Рыбаков и Л. А. Снежкова

Заявитель

Таганрогский радиотехнический институт

МОДЕЛЬ ДУГИ ГРАФА

Изобретение относится к области вычислительной техники.

Известны модели дуги графа, содержащие диоды, логические схемы и триггеры.

Эти модели имеют малые быстродействие и точность решения задачи.

Предложенная модель дуги графа отличается от известных тем, что ней входная клемма поиска пути соединена со входом первой схемы «НЕ», входом, первой схемы «И» и через обратно включенный диод подключена к единичному выходу первого триггера возбуждения, выходная клемма поиска пути соединена со .входом второй схемы «НЕ», входом второй схемы «И» и через обратно включенный диод подключена к единичному выходу второго триггера возбуждения, входная, клемма переориентации дуги соединена со входом третьей схемы «И» и через обратно включенный диод подключена к выходу четвертой схемы «И» и нулевому входу триггера ориентации, выходная клемма переориентации дуги соединена со входом четвертой схемы «И» и через обратно включенный диод подключена к выходу третьей схемы «И» и единичному входу триггера ориентации, вход третьей схемы «И» подключен к единичному выходу второго триггера возбуждения, а вход четвертой схемы

«И» — к единичному выходу первого триггера возбуждения. Входная клемма установки начальной ориентации модели дуги соединена с нулевым входом триггера ориентации, входная клемма снятия возбуждения дуги модели дуги связана с нулевыми входами первого и второго триггеров возбуждения, а входная клемма возбуждения дуги — со вторыми входами первой и второй схем «И», третий и четвертый входы первой схемы «И» .подключены соответственно,к выходу второй схемы «НЕ»

10 и нулевому выходу трипгера ориентации, а третий и четвертый входы второй схемы «И»вЂ” к выходу первой схемы «НЕ» и единичному выходу триггера ориентации, выходы первой и второй схемы «И» соединены с единичными

15 входами второго и первого триггеров возбуждения соответственно.

Это позволяет повысить точность и скорость решения задачи.

На фиг. 1 показана модель дуги графа.

20 Модель содержит схемы «НЕ» 1 и 2, схемы

«И» 8, 4, 5 и 6, триггер 7 ориентации и триггеры 8 и 9 возбуждения.

Для решения задачи определения h;;-связ25 ности графа модели дуг графа соединяют согласно топологии сети в блок определения и переориентации дуг соединительного пути 10, который подключают к блоку 11 управления и блоку 12 индикации (фиг. 2). Соединение

30 моделей дуг графа осуществляют с помощью

344464

60 моделей начального узла (фиг. 3) и моделей конечного узла (фиг 4).

Блок определения и переориентации дуг соединительного пути 10 соединяют щи нами 18, 14, !5 и 16, 17, 18 с блоком 11 управления, по которым поступают потенциалы возбуждения

I", 1", n" и I, j, n моделей конечных узлов, цепями 19, 20, 21 — с блоком 12 индикации, по которым .поступают сигналы счета h, соотьетственно для моделей начальных узлов 1", i", и", шинами 22, 28, 24 — с блоком 11 управления, по которым подаются импульсы установки ориентации дуги в начальное состояние, снятия возбуждения дуги и возбуждения дуги.

Блоки управления и индикации имеют шины 25, 26, по которым проходят сигналы управления блоком индикации и окончания счета.

Каждая модель дуги гра фа имеет входную клемму 27 поиска;пути, .выходную клемму 28 поиска пути, выход|ную клемму 29 переориентации дуги, входную клемму 80 переориентации дуги (входы и выходы определены по начальной ориентации дуги).

Модель каждого начального узла содержит соединительное поле 81 входов и выходов дуг, пропускающих сигналы поиска пути, схему

«И» 82, соединительное поле 88 входов и выходов дуг, пропускающих сигнал переориентации.

Модель каждого конечного узла содержит соединительное поле 84 входов и выходов дуг, пропускаю|щих сигнал поиска пути, схему «И»

85, соединительное поле 86 входов и выходов дуг, пропускающих сигнал переориентации.

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

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

В начале каждого шага из блока 11 поступают последовательно сигналы установки начальной ориентации и снятия возбуждения дуг соответственно по цепям 22 и 28. Далее носредством подачи единичных потенциалов из блока 11 на вход соединительного поля 81 одной из моделей начальных узлов и на вход схемы «И» 85 одной из моделей конечных узлов, возбуждаются узлы (на пример, i" и ).

Единичный потенциал, подаваемый на вход соединительного поля 81, является сигналом поиска. Он поступает на входы всех инциде нтных узлу i" дуг (например, на входную клемму 27 модели дуги)

Так,как триггер 7 находится в нулевом состоянии и выходная клемма 28 не возбуждена, то яа три из четырех входов схемы «И» 8 подаются единичные потенциалы. При поступ5

50 лении импульса возбуждения по цепи 24 на выходе схемы «И» 8 появляется импульс, перебрасывающий триггер 8 возбуждения в единичное состояние, выходное напряжение которого возбуждает через диод выходную .клемму 28 поиска пути. На выходе схемы «НЕ» 1 появляется нулевой потенциал, который уже не влияет на возбуждение модели дуги.

Триггер 9 возбуждения остается в нулевом состоянии, так как;при поступлении сигнала поиска на входную клемму 27 схема «И» 4 оказывается закрытой сразу по двум входам (со стороны схемы «НЕ» 2 и триггера 7 ориентации). Вследствие того, что в рассмотренном примере выходная клемма 28 подключена к соединительному полю 84, на выходе схемы

«И» 85 (фиг. 4) появляется сигнал, который является сигналом переориентации, проходящий через соединительное поле 86, входную клемму 80 переориентации, подготовленную к открытию схему «И» 6 — на:выходную клемму 29 и далее через соединительное поле 88 на,вход схемы «И» 82. Триггер 7 ориентации перебрасывается в единичное состояние, и в блок 12 индикации поступает сигнал о наличии соединительного пути.

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

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

«НЕ» 1 присутствует нулевой потенциал, и модель дути графа остается не возбужденной.

Следовательно, в рассмотренном такте будет отмечен единственный путь.

Пусть на определенном шаге уже найдено К путей и выполнено К переориентаций (К=

=1, 2 ...), Тогда в начале (К+1)-ro такта подается импульс снятия возбуждения дуг, устанавливающий триггеры 8 и 9 всех моделей дуг в нулевое состояние В результате процесс отыскания соединительното пути и переориентации его дуг повторяется.

Счет числа путей прекращается, если на каком-нибудь такте не оказывается соединительного пути. При этом из блока 12 по цепи

26 в блок 11 подается сигнал прекращения счета, заставляя ето перейти к определению Й для другой пары узлов.

Предмет изобретения

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

22 24 23 ничному выходу первого триггсра возбуждения, выходная клемма поиска, пути соединена со входом второй схемы «НЕ», входом второй схемы «И» и через обрато включенный диод подключена к единичному выходу второго триггера возбуждения, входная клемма переориентации дуги соединена со входом третьей схемы «И» и через обратно включенный диод подключена к выходу четвертой схемы «И» и нулевому входу триггера ориентации, выходная клемма переориентации дуги соединена со входом четвертой схемы «И» и через обратно включенный диод подключена к выходу третьей схемы «И» и единичному входу триггера ориентации, вход третьей схемы «И» подключен к единичному выходу второго триггера возбуждения, а вход четвертой схемы

«И» — к единичному выходу первого триггера возбуждения, входная клемма установки начальной ориентаци модели дуги соединена с нулевым входом триггера ориентации, входная клемма снятия воз буждения дуги модели дуги соединена с нулевыми входами первого и второго триггеров, возбуждения, а входная клемма возбуждения дуги — cO вторыми входами первой и второй схем «И», третий и четвертый входы первой схемы «И» подключены соответственно к выходу второй схемы

«НЕ» и нулевому выходу триггера ориентации, а третий и четвертый входы второй схемы «И» подключены соответственно, к выходу первой схемы «НЕ» и единичному выходу триггера ориентации, выходы первой и второй схемы «И» соединены с единичными входами второго и,первого триггеров возбуждения соответственно.

344464

Ч иг З

gu2. 4

Составитель Ю. Сериков

Техред T. Ускова

Корректор Л. Орлова

Редактор Т. Рыбалова

ТипограФия. пр. Сапунова, 2

Заказ 2251/5 Изд. № 949 Тираж 406 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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