344464

344464 О П И С А Н И ЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических РеспубликЗависимое от авт. свидетельстваЗаявлено 26,Х.1970 ( 1485208/18-24)с присоединением заявкиПриоритетОпубликовано 07.Ч 1,1972, Бюллетень21Дата опубликования описания 2.Ч 11.1972 М Кл б 06 г 7/48 Комитет по делам изобретений и открытий при Совете Иинистрав СССРАвторыизобретения П. М, Рыбаков и Л, А. Снежкова Заявитель Таганрогский радиотехнический институт т:ь; ф МОДЕЛЬ ДУГИ ГРАФА Изобретение относится к области вычислительной техники.Известны модели дуги графа, содержащие диоды, логические схемы и триггеры.Эти модели имеют малые быстродействие и точность решения задачи.Предложенная модель дуги графа отличается от известных тем, что ней входная клемма поиска пути соединена со входом первой схемы НЕ, входом, первой схемы И и через обратно включенный диод подключена к единичному выходу первого триггера возбуждения, выходная клемма поиска пути соединена со входом второй схемы НЕ, входом второй схемы И и через обратно включенный диод подключена к единичному выходу второго триггера возбуждения, входная, клемма переориентации дуги соединена со входом третьей схемы И и через обратно включенный диод подключена к выходу четвертой схемы И и нулевому входу триггера ориентации, выходная клемма переориентации дуги соединена со входом четвертой схемы И и через обратно включенный диод подключена к выходу третьей схемы И и единичному входу триггера ориентации, вход третьей схемы И подключен к единичному выходу второго триггера возбуждения, а вход четвертой схемы И - к единичному выходу первого триггера возбуждения. Входная клемма установки начальной ориентации модели дуги соединена с нулевым входом триггера ориентации, входная клемма снятия возбуждения дуги модели дуги связана с нулевыми входами первого и 5 второго триггеров возбуждения, а входнаяклемма возбуждения дуги - со вторыми входами первой и второй схем И, третий и четвертый входы первой схемы И подключены соответственно,к выходу второй схемы НЕ 10 и нулевому выходу трипгера ориентации, атретий и четвертый входы второй схемы И - к выходу первой схемы НЕ и единичному выходу триггера ориентации, выходы первой и второй схемы И соединены с единичными 15 входами второго и первого триггеров возбуждения соответственно.Это позволяет повысить точность и скоростьрешения задачи.На фиг. 1 показана модель дуги графа.20 Модель содержит схемы НЕ 1 и 2, схемыИ 3, 4, 5 и 6, триггер 7 ориентации и триггеры 8 и,9 возбуждения. Для решения задачи определения Йц-связ.25 ности графа модели дуг графа соединяют согласно топологии сети в блок определения и переориентации дуг соединительного пути 10, который подключают к блоку 11 управления и блоку 12 индикации (фиг, 2). Соединение 30 моделей дуг графа осуществляют с помощью55 60 моделей начального узла (фиг. 3) и моделей конечвого узла (фиг 4).Блок определения и переориентации дуг соединительного пути 10 соединяют щинами 13, 14, 5 и 1 б, 17, 18 с блоком 11 управления, по которым поступают потенциалы возбуждения Г, Г, и" и 1, 1, п моделей конечных узлов, цепями 19, 20, 21 - с блоком 12 индикации, по которым поступают сигналы счета Й, соотьетственно для моделей начальных узлов У", ", и", шинами 22, 23, 24 - с блоком 11 управления, по которым подаются импульсы устаяовки ориентации дуги в начальное состояние, снятия возбуждения дуги и возбуждения дуги.Блоки управления и индикации имеют шины 25, 26, по которым проходят сигналы управления блоком индикации и окончания счета,Каждая модель дуги графа имеет входную клемму 27 поиска, пути, выходную клемму 28 поиска пути, выходную клемму 29 переориентации дуги, входную клемму 30 переориентации дуги (входы и выходы определены по начальной ориентации дуги).Модель каждого начального узла содержит соединительное поле 31 входов и выходов дуг, пропускающих сигналы поиска пути, схему И 32, соединительное поле 33 входов и выходов дуг, пропускающих сигнал переориентации.Модель каждого конечного узла содержит соединительное поле 34 входов и выходов дуг, пропускающих сигнал поиска пути, схему И 35, соединительное поле Зб входов и выходов дуг, пропускающих сигнал переориентации,Процесс вычисления йц-связаности графа разбивают на шагив каждом из которых начальный и конечный узлы постоянны, Каждый шаг раскладывают на последовательность тактов, внутри каждого из которых определяют соединительный путь и производят переориентацию ето дуг.При переходе с одного шага на друтой блок 11 управления вырабатывает сигнал возбуждения пары моделей узлов, отличающейся от рассмотренных на предыдущих шагах, В начале каждого шага из блока 11 поступают последовательно сигналы установки начальной ориентации и снятия возбуждения дуг соответственно по цепям 22 и 23, Далее носредством подачи единичных потенциалов из блока 11 на вход соединительного поля 31 одной из моделей начальных узлов и на вход схемы И 35 одной из моделей конечных узлов, возбуждаются узлы (например, г" и 1). Единичный потенциал, подаваемый на вход соединительного поля 31, является сигналом поиска. Он поступает на входы всех инцидентных узлу Г дуг (например, на входную клемму 27 модели дуги) Г, 1,Так,как триггер 7 находится в нулевом состоянии и выходная клемма 28 не возбуждена, то яа три из четырех входов схемы И 3 подаются единичные потенциалы. При поступ 5 10 15 20 25 30 35 40 45 50 лении импульса возбуждения по цепи 24 на выходе схемы И 3 появляется импульс, перебрасывающий триггер 8 возбуждения в единичное состояние, выходное напряжение которого возбуждает через диод выходную клемму 28 поиска пути. На выходе схемы НЕ 1 появляется нулевой потенциал, который уже не влияет на возбуждение модели дуги.Триггер 9 возбуждения остается в нулевом состоянии, так как;при поступлении сигнала поиска на входную клемму 27 схема И 4 оказывается закрытой сразу по двум входам (со стороны схемы НЕ 2 и триггера 7 ориентации), Вследствие того, что в рассмотренном примере выходная клемма 28 подключена к соединительному полю 34, на выходе схемы И 35 (фиг. 4) появляется сигнал, который является сигналом переориентации, проходящий через соединительное поле Зб, входную клемму 30 переориентации, подготовленную к открытию схему И б - на:выходную клемму 29 и далее через соединительное поле 33 на,вход схемы И 32. Триггер 7 ориентации перебрасывается в единичное состояние, и в блок 12 индикации поступает сигнал о наличии соединительного пути.Аналогичные явления происходят в более общем случае, когда сигнал поиска достигает модели конечного узла, проходя через ряд моделей дут и узлов,Индикация единственного пути гарантируется некоторым разнесением во времени импульсов возбуждения для различных моделей дуг графа, а также способностью схемы при поиске пути строить прадерево с корнем в начальном узле. Если до возбуждения входной клеммы 27 выходная клемма 28 возбудится по какому-то другому пути, то на выходе схемы НЕ 1,присутствует нулевой потенциал, и модель дути графа остается не возбужденной.Следовательно, в рассмотренном такте будет отмечен единственный путь.Пусть на определенном шаге уже найдено К путей и выполнено К переориентаций (К= =1, 2 ), Тогда в начале (К+1)-го такта подается импульс снятия возбуждения дуг, устанавливающий триггеры 8 и 9 всех моделей дуг в нулевое состояние В результате процесс отыскания соединительното пути и переориентации его дуг повторяется.Счет числа путей прекращается, еслина каком-нибудь такте не оказывается соединительного пути. При этом из блока 12 по цепи 26 в блок 11 подается сигнал прекращения счета, заставляя ето перейти к определению Й для другой пары узлов. Предмет изобретенияМодель дуги графа, содержащая диоды, логические схемы и триггеры, стличающаяся тем, что, с целью повышения точности и скорости решения задачи, в ней входная клемма поиска пути соединена со входом первой схемы НЕ, входом первой схемы И и через обратно включенный диод подключена к едн344464 22 24 23 ничному выходу первого триггсра возбуждения, выходная клемма поиска,пути соединена со входом второй схемы НЕ, входом второй схемы И и через обрато включенный диод подключена к единичному выходу второго триггера возбуждения, входная клемма переориентации дуги соединена со входом третьей схемы И и через обратно включенный диод подключена к выходу четвертой схемы И и нулевому входу триггера ориентации, выходная клемма переориентации дуги соединена со входом четвертой схемы И и через обратно включенный диод подключена к выходу третьей схемы И и единичному входу триггера ориентации, вход третьей схемы И подключен к единичному выходу второго триггера возбуждения, а вход четвертой схемы И - к единичному выходу первого триггера возбуждения, входная клемма установки начальной ориентаци модели дуги соединена с нулевым входом триггера ориентации, входная клемма снятия возбуждения дуги модели дуги соединена с нулевыми входами первого и второго триггеров, возбуждения, а входная клемма возбуждения дуги - со вторыми входами первой и второй схем И, третий и четвертый входы первой схемы И подключены соответственно к выходу второй схемы НЕ и нулевому выходу триггера ориентации, а третий и четвертый входы второй схемы И подключены соответственно, к выходу первой схемы НЕ и единичному выходу триггера ориентации, выходы первой и второй схемы И соединены с единичными входами второго и,первого триггеров возбуждения соответственно.344464 20 Ри 4 Составитель Ю, Сериков Техред Т, Ускова Корректор Л. Орлова Редактор Т. Рыбалова Заказ 2251/5 Изд,949 Тираж 406 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРМосква, Ж, Раушская наб., д. 4/5 ТипограФия. пр. Сапунова, 2