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

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

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

Авторы: Кошель, Кривенко, Шаповалов

МПК: G06G 7/122

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

...преобразователя 1 О в регистр 13 памяти, соответствующий сработавшей ветви.Этот процесс продолжается до техпор, пока из блоков 5 индикации иконтактов 6 пороговых элементов 3 небудет создана электрическая цепь дляисточника 8 тока, В результате токисточника 8 протечет не по всем ветвям, отмеченным пороговыми элементами 3, а только по тем из них, которые создапи замкнутый путь для источника 8 тока.В момент протекания тока черезблоки 5 индикации, составляющие кратчайший .путь, они вырабатывают и выдают с второго выхода на первый входсоответствукицих элементов И-НЕ 11 постоянный единичный потенциал, Индикатор 9 тока в этот момент выдаетодиночный импульс, который, поступаяна вторые входы элементов И-НЕ 11,проходит только через те...

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

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

Авторы: Игнатьев, Петров, Сорокин

МПК: G06F 15/173

Метки: графе, путей

...код записывается в регистр 4 по начальному единичному импульсу генератора 23 импульсов. Затем в регистр 7 записывается код максимально возможного веса пути в данной графе для определения зацикливания или код максимального веса пути, приемлемого в данном случае. После этого обнуляются счетчики 18 и 19 и запускается генератор 23 импульсов.Генератор 23 импульсов выр,батывает синхрониэирующие импульсы, которые подаются ча входы записи регистра 4, регистра 6, блока 24 регистров и вход синхронизации сумматора 20. На каждом шаге работы устройства после записи в регистр 4 кода (очередной текущей вершины ) из блока 1 или 2 памяти осуществляется считывание новых данных. Если очередная текущая вершина имеет степень два, то иэ блока 2 памяти кода...

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

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

Авторы: Клишин, Лелис, Полищук

МПК: G06G 7/122

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

...19 и 20 и выходы 21, 22 модели ветви. Устройство работает следующим образом.С помощью блоков 4 устанавливают в управляющих цепях тиристоров 7 токи, соответствующие напряжениям переключения тир исторов, пропорциональным весам узлов ветвей. Полюса источника 1 подключают к моделям начального и конечного узлов графа.При увеличении напряжения источника 1 от нуля до некоторой определенной величины происходит переключение тиристоров, принадлежащих кратчайшему пути.В этой цепи потечет ток, создавая падение напряжения на резисторах блоков 10, в результате чего будут отмечены узлы и вершины кратчайшего пути (элементы индикации, обеспечивающие выдачу сигналов о протекании тока, на чертеже не показаны).Устройство позволяет задавая одинаковыми веса...

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

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

Автор: Колесник

МПК: G06F 15/173

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

...23 и останова устройства в единичном состоянии оказываются те триггеры 20 через соответствующие номерам которых вершины проходят максимальный путь иэ первой начальной вконечную тп-ю вершину графа,Для нахождения второго (по длине) 25максимального пути независимо повершинам от первого найденного пути подают единичный сигнал на вход исключения дуг устройства, при этом обнуляются регистры 6 (кроме щ-го) и 30 открываются элементы И 18, вследствие чего единичный сигнал с выходов тех триггеров 20, которые соответствуют вершинам первого максгпчального пути и находятся в единичном состоянии, поступает на входы установки в "0", триггеров 2 одноименных строк матрицы 1 и устанавливают их в "0", Этим из топологии графа исключаются дуги,...

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

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

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

МПК: G06F 15/173

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

...=Тр -(Т+Т), где Т - весданной дуги. Для этого устройствовновь приводят в исходное состояние,не обнуляя, счетчик 20, регистры 11и 12 и сохраняя записанную в матрице1 информацию о топологии инвертированного графа. Переключатель 22 переводят в другое положение, подключаясчетчик 18, в который заносят "1".Затем вновь подают сигнал пуска иимпульсы генератора 5 вновь поступают на вход распределителя 6, импульсс первого выхода которого открывает(М,М)-й блок 4 элементов И, и весдуги (1,2) между первой и второй вершинами графа через соответствующий5500 55 5 10 15 20 25 30 35 ао 45 50 блок 7 посту:ает на вход соответствующего сумматора 15, на другой входкоторого через (М,М)-й блок 18, открытый импульсом с первого выходараспределителя 6, и...

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

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

Авторы: Михайленко, Озирский, Федотов

МПК: G06G 7/122

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

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

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

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

Авторы: Клишин, Лелис, Полищук

МПК: G06G 7/122

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

...графа, модели 5 вершин графа. В состав каждой модели 3 входит пороговый элемент 6, элемент 7 индикации и обмотка 8 реле. Модель 5 содержит включенные последовательно контакты 9 реле моделей 3 тех ребер графа, которые выходят из данной вершины. Пороговый элемент 6 может быть. выполнен, например, на базе тиристора О, переменного резис тора 11 и источника 12 постоянного напряжения.Устройство работает следующим образом.В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помощью переменных резисторов 11 в моделях 3 и 4 ребер устанавливают токи в управляющих цепях тиристоров 10, соответству 1 ощие заданным напряжениям их переключения, пропорциональным весам ребер.При плавном увеличении выходного напряжения источника 1...

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

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

Авторы: Клишин, Лелис, Полищук

МПК: G06G 7/122

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

...13, отображающих ребра первого кратчайшего пути, во-вторых, протекание тока в обмотках 2 моделей 8 этих ребер и, в-третьих, протекание тока в обмотке 5 - 1. Протекание тока в обмотке 12 приводит к замыканию контактов 16 и блокировке моделей 8 до конца работы устройства. Это обеспечивает индикацию первого кратчайшего пути до конца работы устройства. Кроме того, протекание тока через обмотку 12 в каждой модели 8 приводит к размыканию контакта 11 - -1 в соответствующей модели 2. Тем самым после первого шага работы устройства благодаря размыканию контактов 11 - 1 из топологии графа будут исключены все ребра первого кратчайшего пути. Протекание тока через обмотку 5 - 1, с одной стороны, обуславливает замыкание контакта 7 -и подготовку к...

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

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

Авторы: Баженов, Одинцов, Титов

МПК: G06F 15/173

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

...2 к, отличается от обратного кода нуля, то единичным сигналом с выхода элемента И-НЕ 11 М открывается блок 13 к элементов И и код числа с выхода регистра 20 поступает на второй вход сумматора 15 к.Таким образом, на входы сумматора 15 могут поступить коды весов дуг графа (с регистра 2 к) и код числа (с регистра 20 к) только в том случае, если они оба отличны от обратного кода нуля. С выхода сумматора 15 полученная сумма поступает на к -й вход блока 16. Блок 16 производит поиск максимального кода и вырабатывает единичный сигнал на выходе, соответствующем номеру входа с максимальным кодом. Максимальный код поступает на блоки 18 элементов И-НЕ, а выходы, указываю 134164 щне его позиционный номер - на вход блока 17.Устройство работает...

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

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

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

МПК: G06F 15/173

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

...что обусловливает появление единичного сигнала на выходе элемента НЕ 4 и переход триггера 5 в состояние "1",На втором этапе вновь приводят20 устройство в исходное состояние, но регистры 1 О не обнуляются, а в матрицу 1 заносят информацию о топологии инвертированного графа, т.е. данные матрицы исходного графа, но транспортированные относительно неглавной диагонали.Затем пускают устройство и в счетчиках 8 повторно фиксируются наиболее ранние времена выполнения вершин ин 30 вертированного графа, которые в прямом графе соответствуют величинам максимальных путей из вершин графа в его конечную вершину. Однако в регистры 10 содержимое счетчиков 8 уже не ,записывается, так как единичный потенциал с первого разряда информационного счетчика 14...

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

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

Автор: Колесник

МПК: G06F 15/173

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

...записи указанноготриггера подается единичный потенциал.После установки К-го триггера любойстроки матрицы в "единицу" единичныйпотенциал с его несинхронизируемогоинформационного выхода, проходя черезэлемент НЕ Ь, запрещает установку вединичное состояние любого из оставшихся триггеров 2 К-го столбца матрицы и счет импульсов К-м счетчиком 8Единичный потенциал с выхода К-гоэлемента ИЛИ 3 поступает на входы раз"решения счета всех счетчиков 1 К-йстроки матрицы, которые начинают счеттактовых импульсов (исполнение ветвей, исходящих из К-й вершины графа),97534счетчиков, где Р " количество вершинв графе, матрицу из РхР триггеров,первую группу из Р элементов ИЛИ,группу из Р триггеров и элемент И, 5о т л и ч а ю щ е е с. я тем,что, сцелью...

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

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

Автор: Колесник

МПК: G06F 15/173

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

...8 определяет,что максимальным является поданный на второй вход код 1001, а потому выдает его обратный код на информационные 55 входы регистров 9, Когда с выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9, он запоминает число 6 как длину минимального пути из первой в четвертую вершину, Блок 8 вьщает такжепризнак максимального кода (потенциал "1"), который через вход 20 г проходит на вторые входы элементов 14 г,14 г, 14 г И. Единичный сигнал с второго выхода распределителя 4 поступает через вход 21 на первые входыэлементов 14, 14 14, И. Единичный сигнал появляется на выходе элемента 14 г И и перебрасывает в единичное состояние триггер 1 Зг.Третий импульс генератора 1 вновьпроходит на вход разрешения...

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

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

Авторы: Герасименко, Ильин, Квасницкий, Листровой, Певнев

МПК: G06F 15/173

Метки: графе, путей

...36 элементов И. Через сборку 37 элементов ИЛИ от сборки 35 или 36 сигнал поступает на вход распределителя 38 импульсов. Распределитель 38 импульсов подает на свой первый выход число, соответствующее но-.меру первой вершины, с которой естьсвязь у данной вершины. Этот сигнал,выдается в блок 4. При приходе второго импульса от генератора 1 импульсов схема работает аналогичным образом, только происходит передача чисра, соответствующего номеру второйвершины, с которой есть связь. Такимобразом схема работает до тех пор,пока содержимое счетчика 24 не сравняется с содержимым регистра 25. Вэтом случае на выходе схемы 26 сравнения появляется высокий потенщал,который закрывает элемент 27 "Запрет"и открывает элемент И 28. Новый имгистр 32 служит...

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

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

Авторы: Михайленко, Озирский, Федотов

МПК: G06G 7/122

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

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

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

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

Авторы: Глушан, Курейчик, Макеев, Рябец

МПК: G06F 15/419

Метки: гамильтоновых, графе, циклов

...И 16. Если на счетчик 6 не поступит двух сигналов, необходим принудительный сброс счетчика в исходное состояние, Это осуществляется каждым новым ТИ (независимо от состояния счетчика 6), который с выхода элемента И 16 поступает на вход сброса счетчика 6, Если сформированное ЭР в исследуемом графе существует, необходимо проверить, не входят ли в него уже рассмотренные вершины, Для сравнения сформированного ЭР с ранее записанными в БП 5 ЭР служит блок 4 сравнения ЭР (БСЭР 4, представляющий собой шесть схем сравнения, выходы которых объединены схемой ИЛИ).Формирователь импульсов 27 формирует импульсы 2-х видов: с периодом г 1, с периодомг.Первые импульсы поступают на первый вход элемента И 16,Вторые импульсы поступают на второй вход...

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

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

Авторы: Дробахин, Кудрявцев, Шевчик

МПК: G06F 15/20

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

...графа,составляющих кратчайший путь в графе.10 35 триггер, блок выбора максимального сигнала, аналого-цифровой преобразователь и блок формирования топологии графа, содержащий К узлов топологии графа, при этом, вход запуска устройства подключен к 40 45 50 15 20 25 ЗО Пришедший импульс поступает на вход поляризаторов 2 руппы, Гри этом на выходе К-го поляризатора группы появляется световой сигнал максимальной интенсивности, который преобразуется соответствующим фотоприемником 3-К группы в электрический. Этот сигнал через открытые ключи 5 группы поступает на входы блока 8 выбора максимального сигнала и проходит на входы аналого-цифрового преобразователя 9. Этот же сигнал, пройдя через элемент ИЛИ 6, обнуляет триггер 7, который закрывает...