Патенты с меткой «графах»

Номер патента: 491132

Опубликовано: 05.11.1975

Авторы: Додонов, Хаджинов, Шишмарев

МПК: G06F 15/173

Метки: величин, графах, максимальных, путей

...моделируемого графаи весах дуг. При этом триггеры б формироваЗО телей 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 заносятся числа импульсов, дополняющие длительности ветвей до полной емкости счетчиков.После занесения исходной информации на выходах элементов И 7, объединяющих выходы формирователей 4 в столбцах, соответвующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входящих...

Номер патента: 640314

Опубликовано: 30.12.1978

Авторы: Дроздов, Тафинцев, Титов

МПК: G06G 7/122

Метки: графах, путей, экстремальных

...до полной емкости счетчиков, После занесения исходной информации на выходах элементов И 7, объединяющих выходы формирователей 4 в столбцах, соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входящих ветвей, а следовательно, и триггеры 6 формирователей 4, находящихся на том столбце будут в нулевом состоянии.Работу устройства проследим при определении минимальной величины пути в графе.С появлением пускового сигнала блок 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов ИЛИ 9, При этом импульсы проходят только на входы счетчиков 5 тех формирователей 4, которые моделируют веса дуг,...

Номер патента: 643900

Опубликовано: 25.01.1979

Авторы: Окунев, Романюха, Чистяков

МПК: G06G 7/122

Метки: графах, ориентированных, путей, экстремальных

...следующим образом.В блоке задания конфигурации ориентированного графа 1 устройства по ориентированному графу Формируется модель граФа. При этом каждая Х; Х дуга (ветвь) графа набирается из последовательно включенных элементов 2,3,4, Направленность (ориентирован" ность) ветвей определяется светяшимся диодом входной цепи оптрона 3.Вершины Х,Х , Хп модели графа подключаются к соответствующим входам 22, выходные. цепи оптронов 3 подключаются к соответствующим выходам 23 и вершина Хо (начало проекта) по входу блока 1.Переключатель 8 устанавливается в положение минус источника питания.Формируется команда Исходное по которой блок управления 6 и блок переключения устанавливаются в ис" ходное положение, триггеры 9 и 17 переводятся в нулевое...

Номер патента: 744592

Опубликовано: 30.06.1980

Авторы: Назаров, Титов

МПК: G06F 15/173, G06G 7/122

Метки: величин, графах, максимальных, путей

...Это объясняется тем, что воднонаправленном графе без циклов ипетель начальные узлы не содержатвходящих ветвей, а следовательно,и триггеры б формирователей 4, находящихся в этом столбце, будут в нулевом состоянии (элементы 7 соединены с нулевыми выходами триггеров 6).Счетчики 10 в исходном состояниисброшены в нулевое состояние.Исходный граф заносится в матричную модель сети в инверсном порядке, 40т.е. матрица смежности заносимогографа транспортирована относительнонеглавной диагонали. Это позволяетиспользовать для расчета максимальных путей в графе процедуру динамического программированияС появлением пускового сигналаблок 2 управления разрешает прохождение импульсов с выхода генератора3 на,входы всех элементов И 9. Приэтом импульсы...

Номер патента: 862145

Опубликовано: 07.09.1981

Авторы: Гайдуков, Кильчик, Назаров, Титов

МПК: G06F 17/00, G06G 7/122

Метки: графах, максимальных, путей

...элемента И, выход которого со-.единен с информационными входами элементов И первой и второй групп. Вымодели сети элементы ИЛИ-НЕ 2 -2,генератор тактовых импульсов 3, элемент И 4 по числу столбцов матрицы,вторую группу элементов И 5 -5,счетчики ("весов" дуг) б -би, триггеры управления 7 -7 и, первую груп-.пу элементов И 8. -8 и, регистрирующиесчетчики 9 -9, элемент ИЛИ 10, пусковой вход устройства 11 и триггеры121 по числу строк и столбцов матричной модели сети, где 1,1 = 1, и( И- число вершин в моделируемомграфе),Устройство работает следующим 50образом,Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети), При этом триггеры 12 , которые являются формирова,цтелями дуг, устанавливаются в единичное...

Номер патента: 886006

Опубликовано: 30.11.1981

Авторы: Гудыно, Кузьменко, Титов, Шевченко

МПК: G06G 7/122

Метки: графах, минимальных, путей

...высокий потенциал с выхода переполненного счетчика 6 подается на одноименный вход элемента И-НЕ 10 и элемент НЕ 7. Появление низкого потенциана на выходе элемента НЕ 7 (на управляемом входе элемента И 8) вызывает прекращение подачи счетных импульсов через элементы И 8 на вход регистра счетчика 9.Переброс триггеров 2 в одноименном столбце в нулевое состояние вызывает появление импульса через дифференцирующие цепочки 3 и через элементы ИЛИ 1 4 на входе триггера 4 очередного столбца, Этот импульс переводит триггер 4 в единичное сос, тояние, благодаря чему на управляемом входе элемента И 5 одноименного столбца появляется высокий пстенциал. Появление разрешающего потенциала на управляемом входе элемента И 5 обеспечивает возможность...

Номер патента: 942030

Опубликовано: 07.07.1982

Авторы: Гайдуков, Титов

МПК: G06F 15/173

Метки: графах, минимальных, путей

...на первом входе элемента И1 О обеспечивает возможность прохожде- зния счетных импульсов через элемент И 10 на вход счетчика 11 ( "веса"вершины) очередного столбца матрицы. При этом формируется разрешение поступления импульсов на входы счетчи- щ) ков 11, из соответствующих вершинкоторых исходят дуги, приводящие в сформированную. ранее вершину.Подсчет импульсов продолжается до тех пор,. пока на выходах всех счет 4 чиков 1,1 не будут присутствовать вы- сокие потенциалы, появляющиеся из-за переполнения этих счетчиков, Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких потенциалов на выходах счетчиков 11 обеспечивает через элемент И-НЕ 19 прекращение подачи счетных импульсов с выхода генера-, тора 20...

Номер патента: 943738

Опубликовано: 15.07.1982

Автор: Титов

МПК: G06F 15/173, G06G 7/122

Метки: графах, исследования, путей

...котором появляется сигнал нулевого состояния счетчика 15).С первого выхода счетчика код поступает на вход дешифратора 16, в результате чего на одном из выходов дешифратара 15 появляется высокий потенциал,Появление высокого потенциала на одномиз выходов дешифратора обеспечивает подачу высокого потенциала на управялемыевходы соответствующего столбца элементов И 9 и элементов задержки 6, а также элементов И 3 одноименной строкиматрицы 1. В случае, если триггеры 2в данной строке находятся в единичном9437 38 5состоянии, то через элементы И 3 иИЛИ 4 высокий потенциал с этих триггеров 2 подается на управляемые входысоответствующих элементов И 8, что всвою очередь обеспечивает подачу кодовс регистров 7 на входы узла 17, Узел17 обеспечивает...

Номер патента: 947869

Опубликовано: 30.07.1982

Авторы: Афанасьев, Комаров, Титов

МПК: G06F 15/173

Метки: графах, максимальных, путей

...следующим образом.Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети), При этом триггеры 21 (1, = 1,п), которые являются формирователями дуг, устанавливаются в единичное, состояние, если есть информационная связь из 1-ой вершины в )-ую вершину. Соответствующий триггер 2 1 определяется пересечением 1-ой строки и 1-го столбца.Другие триггеры 2 1, а также триггеры 8 и счетчики 10 и 19 находятся в нулевом состоянии. В счетчики 7 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков, После занесения исходной информации на входах элементов 4 ИЛИ-Н объединяющих выходы триггеров 2 в строках, соответствующим конечным вершинам моделируемого графа, будут...

Номер патента: 995094

Опубликовано: 07.02.1983

Автор: Титов

МПК: G06F 15/173

Метки: графах, максимальных, путей

...в нулевом состоянии. В единичное состояние устанавливается также триггер 12, соответствующий начальной вершине модулируемого графа. В счетчики 8 Соответствующих вершин графа заносятся числа. импульсов, дополняющие фвесафф вершин до полной емкости счетчиков. После занесения исходной информации на выходах элементов 5 ИЛИ-НЕ, объединяющих выходы триггеров 2,в строках, соответствующих конечный вершинам моделируемого графа, будут высокие потенциалы. Это объясняется тем, что в однонап-, равленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом состоянии. со-"тонниив Это происходит благодарятому, что на выходе соответствующихэлементов ИЛИ-НЕ 5 и на...

Номер патента: 1005066

Опубликовано: 15.03.1983

Авторы: Гайдуков, Родионов, Титов

МПК: G06F 15/173

Метки: графах, исследования, путей

...на второй вход сумматора 16подается код с выхода избранногорегистра 9 через соответствующийэлемент И 11 и элемент ИЛИ 15, Результат с выхода сумматора через открытую группу элементов И 8 (к этомумоменту времени на управляемом входе элемента И 8 появляется высокийпотенциал с выхода элемента 7 задержки) поступает на вход соответст-,вующего регистра 9. На этом этапформирования кода максимального пути для одной отдельной вершины заканчивается Далее на вход счетчика 21 поступает очередной импульс,в результате чего содержимое этогосчетчика уменьшается на единицу,поэтому на выходе дешифратора 22возбуждается очередная (и)-явыходная шина, и процесс формирования величины максимального путидля очередной вершины графа про-исходит...

Номер патента: 1051543

Опубликовано: 30.10.1983

Авторы: Попков, Репин

МПК: G06F 15/173

Метки: графах, кратчайших, моделирования, путей

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

Номер патента: 1228112

Опубликовано: 30.04.1986

Авторы: Герасименко, Евтушенко, Неверов, Титов

МПК: G06F 15/173

Метки: графах, исследования, путей

...для и-й отдельной вершины заканчивается.С появлением пускового сигнала на входе 26 устройства элемент И 19 обес печивает прохождение импульсов с выхода генератора 18 на вход счетчика 20, так как на втором входе эле35 50 э 1228 мента И 19 будет высокий потенциал с выхода счетчика 20, на котором появляется обратный сигнал его нулевого состояния. Когда на вход счетчика 20 поступает первый импульс, возбуждается (п - 1)-й выход дешифратора 21, и процесс формирования величины критического пути для очередной вершины графа будет происходить аналогично.Вычислительный процесс будет продолжаться до тех пор, пока на счетчике 20 не появится нулевой код, после чего появится нулевой код и появится низкий потенциал на втором входе элемента И.19, а...

Номер патента: 1242982

Опубликовано: 07.07.1986

Авторы: Денисов, Львов

МПК: G06F 15/173

Метки: графах, минимальных, путей

...выходов соответствующих регистрирующих триггеров 8. Высокий потенциал появится на выходах только тех элементов ф И 32 первой строки блока 12, на первые входы которых подан высокий потенциал с выходов соответствующих регистрирующих триггеров 8, идентифицирующих вершины минимального пути в графе. Под действием высоких потенциалов с выходов элементов И 32 первой строки блока 13 триггеры 33 будут переведены в единичное состояние. Таким образом, триггеры 33 первой строки блока 13 памяти запомнят вершины первого минимального пути.Одновременно импульс с выхода диф. ференцирующей цепочки 14 поступит на вход элемента ИЛИ 18 и произведет новый запуск устройства. При этом пусковой импульс с выхода элемента ИЛИ 18 поступит также на вторые входы...

Номер патента: 1275480

Опубликовано: 07.12.1986

Авторы: Михайленко, Санников, Федотов, Четверухин

МПК: G06G 7/122

Метки: графах, кратчайшего, пути

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

Номер патента: 1280380

Опубликовано: 30.12.1986

Авторы: Дмитриевский, Пыхтин, Смирнов, Соколов, Федоров

МПК: G06F 15/173

Метки: графах, максимальных, путей

...Элементы И 38 -38служат для стробирования выходовтриггеров 37. Стробирование осуществляется единичным сигналом УБлок 15 формирования адреса(фиг. 12) обеспечивает выработку значений адреса строк ,-. и адресастолбцов я 1-д с целью осуществления доступа к выходу каждого триггера (ячейки) 37 блока 14 через коммутатор 13,Блок сравнения 16 (фиг. 14) осуществляет сравнение значений триггеров (ячеек) 37 блока 14 со значением,определенным триггером 78 сравнения,который устанавливается в единичноесостояние единичным сигналом,Блок 17 выделения циклов служитдля хранения значений счетчика строк63 и счетчика столбцов 64 блока формирования адреса 15,Первый узел 39 памяти предназначен для хранения значений счетчика строк 63 блока 15 регистры 46...

Номер патента: 1285487

Опубликовано: 23.01.1987

Автор: Есетов

МПК: G06F 15/173

Метки: графах, максимальных, путей

...графа.После занесения исходной информации на входах элемента ИЛИ-НЕ 5 вательно, на выходе элемента ИЛИ21 устанавливается низкий потенциал, который поступает на вход элемента НЕ 22. С выхода элемента НЕ 22высокий потенциал поступает на второй вход элемента И 23, на первыйвход которого поступает тактовый им;пульс с генератора 17 через элементИ 19.В результате с выхода элемента И23 появляется высокий потенциал, который поступает на первый (Н) входКБ-триггера 26 и устанавливает егов нулевое состояние. С окончаниемдействия тактового импульса с генератора 17 низкий потенциал черезэлемент И 19 поступает на вход элемента НЕ 25. В результате на выходе элемента НЕ 25 устанавливаетсявысокий потенциал, который поступает на второй вход элемента И...

Номер патента: 1320812

Опубликовано: 30.06.1987

Авторы: Райский, Сергеев

МПК: G06F 15/173

Метки: графах, максимальных, путей, сетевых

...шагах) на входы блока 14поступают несколько максимальныхкодов, и единичные сигналы появляются не на одном, а на двух или нескольких выходах блока 14 одновременно,Тогда в единичное состояние перебрасываются все соответствующие триггеры 21, а из триггеров 12-только один,20номер которого наименьший,Пусть, например, единичные сигналы :появляются на третьем и шестом выходах блока 14,Тогда на всехвходах элемента ИЛИ-НЕ 20 присутствует нулевой потенциал, а на выходе - единичный потенциал, которыйоткрывает элемент И 19 для прохождения единичного сигнала с третьеговыхода блока 14 на вход триггера3012 з, который перебрасывается в еди -ничное состояние. В это время наодном из входов элемента ИЛИ-НЕ 20присутствует единичный потенциал .Поэтому на...

Номер патента: 1383386

Опубликовано: 23.03.1988

Авторы: Злобин, Полиско

МПК: G06F 15/173

Метки: графах, максимальных, путей

...элемента ИЛИ 14 появлятся низкий потенциал, который запрещает прохождение счетных импульсов с генеЗ 0 ратора тактовых импульсов.Устройство при определении величиныкритического пути и идентификации вершин работает следующим образом.Пусть задан граф, описываемый матрицей смежности А и вектором Т весов вершин. Т =/2, 1,6,4,2, 5, 2,4, 1,21, где элементы О, если нет дуги из 1-й вершины в 1-ю;а =501, если есть дуга из 1-й вершины в 1-ю;1; - вес 1-й вершины моделируемого графа,После занесения исходной информации навходе элемента ИЛИ - НЕ 5, имеется низхий потенциал, а на выходе - высокий. На 55 выходах элементов ИЛИ - НЕ 5 - 5 о присутствует низкий потенциал, поэтому после подачи пускового сигнала на вход 17 пусковой импульс разрешает...

Номер патента: 1424031

Опубликовано: 15.09.1988

Авторы: Васильев, Левина, Ушаков, Федотов

МПК: G06G 7/122

Метки: графах, задач, решения

...меток, выход которого соединен с инФормационным вхоцом регистра признака, информационный вход,1триггера направлений соединен с выхсдом узла памяти дерева направлениЯ,выход "Выбор кристалла" которого соединен с выходом дещпФратора направлений, вход которого соединен с вторч выходом узла постоянной памяти,трет й адресный вход которого соединен с выходом счетчика каправлений иинформационным входом узла памяти направлений анализа, выход которого соединен с информационным входом счетчика направлений, выход признака. переноса арифметико-логического узла соединен с информационным входом триггера конца ввода, вход записи регистра адреса, входы записи и признака метки узла памяти меток, информационный вход дешифратора меток, синхронизирующие...

Номер патента: 1587534

Опубликовано: 23.08.1990

Авторы: Романов, Славин, Щеглова

МПК: G06F 15/173

Метки: графах, задач, решения

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

Номер патента: 1587535

Опубликовано: 23.08.1990

Авторы: Бездежский, Костюк, Табачников

МПК: G06F 15/173

Метки: графах, операций

...третьих входов элементовИЛИ 30.Устройство работает следующим образом,Пусть необходимо стянуть одну илинесколько вершин графа во внешнююточку или, считая что исходный графимеет В вершин, в (В+1)-ю вершину,5 158753Перед на.алом работы, подавая навход 9 импульс уровня логической единицы, обнуляют регистры 6 и 7,В блок 4 удаления дуг заносят информацию о топологии графа (его ма 5трицу смежности), по входам 11 признаков принадлежности вершин массиву стягиваемых задают состав стягиваемых вершин графа, 10На вход 10 пуска подают импульсуровня логической единицы, При этомблок 1 синхронизации формирует последовательность сигналов уровня логической единицы., предусмотреннуювременной диаграммой его работы,Через время, достаточное для...

Номер патента: 1596343

Опубликовано: 30.09.1990

Авторы: Анисимов, Галимзянов, Денисович, Сидоренко, Тихобаев, Шевчик

МПК: G06F 15/173

Метки: графах, задач, решения

...последовательность сигналов уровня логической единицы, определяющих используемый волновой процесс (те. можно говорить, что блок 5 последовательно (по каждому второму тактовому импульсу) инициализирует волну в диагональных элементах матрицы (точках простран" ства, заданного матрицей), начиная с первого диагонального элемента и5 159 заканчивая В-м диагональным. По каждому последующему (после инициализации) импульсу из инициализированного диагонального элемента матрицы распространяются две волны: вертикальная (вверх и вниз) и горизонтальная (вправо и влево), которые, дойдя до границы матрицы, исчезают за ее пределами, При этом блоки 4 и 6 выдают сигналы уровня логической единицы на выходы тех опрошенных каналов, на информационных входах...

Номер патента: 1596344

Опубликовано: 30.09.1990

Авторы: Баранов, Васильев

МПК: G06F 15/173

Метки: графах, задач, решения

...двойных импульсов, .действующих в первом разряде первогоцикла и в и-м разряде второго цикла работы устройства. Последовательность импульсов выхода элемента ИЛИ 42 блока 4 управления поступает через элементы И-ИЛИ 14 на информационные выходы 21 всех невозбужденных модулей модулирующей структуры, у которых триггер 5 находится в нулевом состоянии.После установки в единичное состояние триггера 33 блока 4 управления через элемент И 39 начинает поступать последовательность импульсов и-го раз35 ряда второго цикла, задержанная элементом 34 задержки на длительностьтактового импульса генератора 24 импульсов блока 4 управления. Первый.импульс последовательности выхода эле 5мента И 39 блока 4 управления устанавлив ае т...

Номер патента: 1605258

Опубликовано: 07.11.1990

Авторы: Авдеев, Ханжиев

МПК: G06F 15/173

Метки: графах, задач, решения

...устройства при определении веса критического пути в графе,На чертеже представлена функциональная схема устройства,Устройство содержит блок 1 задания 10матрицы весов дуг, блок 2 заданияматрицы смежности, блок 3 определениякритического пути, многоканальный коммутатор 4, сумматор 5, вход 6 опросаустройства, выходы 7 признаков принадлежности дуг множеству дуг критического пути в графе устройства ивыход 8 веса критического пути устройства.Устройство работает следующим образом,Пусть необходимо определить вескритического (длиннейшего или кратчайшего) пути в графе, Перед началомработы в блок 1 задания матрицы весов 25дуг заносят информацию о весе дуги,соединяющей К-ю и М-ю вершину графа(К 1 В; М 1 В, где В - количество вершин в графе), в...

Номер патента: 1608683

Опубликовано: 23.11.1990

Авторы: Вареник, Гуринович, Лящук, Черняк

МПК: G06F 15/173

Метки: графах, задач, решения

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

Номер патента: 1626256

Опубликовано: 07.02.1991

Авторы: Додонов, Приймачук, Сасюк, Щетинин

МПК: G06F 15/419

Метки: графах, задач, решения

...выдачу тактовых импульсов. Кроме того, таймер 5 выдает на свой выход (и на выход 11 устройства) номер переполнившегося канала (номер исполненной дуги), При этом блок 1 задания списков заходящих дуг отмечает обращение к заданной записи списка и выдает на один из своих выходов номер списка, к которому относится заданная запись (записи списка соответствует номер дуги, моделирование которой закончено, а номеру списка - номер вершины, в которую заходит дуга). При этом блок 3 памяти по адресу (номеру) списка выдает в прямом и инверсном виде хранимое (однобитовое) слово (признак того, что данная вершина уже исполнена в предыдущих циклах работы устройства). При нулевом значении слова (достигнутая вершина еще не исполнена) блок 1...

Номер патента: 1644166

Опубликовано: 23.04.1991

Авторы: Бороденко, Горев, Казарцев, Радионов

МПК: G06F 15/419

Метки: графах, задач, решения

...сигнал уровня логической единицы на своем выходе 10. При этом блок 3 определения кратчайшего пути выдает на свой выход величину веса кратчайшего пути между заданной парой вершин, Одновременно блок 4 памяти выдает на свой информационный выход значение, соответствующее выбранному адресному входу (т,е, вес конечной вершины пути). При этом блок 5 умножения формирует на своем выходе произведение поступивших на его входы сомножителей (т.е, величину произ 40 50 где В количество вершин в графе) подклю чен к М-лу входу задания конечной вершины пути блока определения кратчайшего пути и к М-му адресному входу блока памя 10 15 20 25 30 ведения веса кратчайшего пути и веса конечной вершины пути). Через время, достаточное для выполнения...

Номер патента: 1658171

Опубликовано: 23.06.1991

Авторы: Баранов, Васильев

МПК: G06F 15/419

Метки: графах, задач, решения

...узел синхронизации формирует импульс уровня логической единицы на своем выходе 24, При этом многоканальный таймер 13 выдает на свои выходы значения признаков наличия переполнения в группах каналов, Каналы счетчика 10 увеличивант свое значение на единицу (тем самым подсчитывается коли 16581715 10 чество исполнения дуг, заходящих в вершину, номер которой соответствует номеру канала счетчика), Одновременно накапливающий узел логического сложения устанавливает в "1" значение того информационного разряда, для которого выбрано первое направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них кратчайшего пути). В том случае, если один или несколько каналов счетчика 10 переполняется (т. е. если...

Номер патента: 1658172

Опубликовано: 23.06.1991

Авторы: Балакирев, Карпенко, Луценко

МПК: G06F 15/419

Метки: графах, задач, решения

...логической единицы, При этом блок 3сравнения сформирует на своем выходе потенциал уровня логической единицы (признак отсутствия циклов), При наличиициклов в графе на одном или несколькихвыходах блока 2 сохранятся потенциалыуровня логического нуля и на выходе блока3 сравнения (он може быть выполнен в 10виде элемента И) сохранится потенциал логического нуля (приэнак наличия циклов вграфе),На фиг. 2 показан вариант исполненияустройства, который отличается тем, что, с 15целью сохранения первоначальной топологии графа, в него введен блок 6 удаленияисходящих дуг, причем выход значения (К,М) - го элемента блока 1 задания матрицысмежности подключен к входу признака наличия (К, М)-й дуги блока удаления исходящих дуг (К = 1, В, М = 1, , В, где В...