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

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

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

Авторы: Васильев, Кузьмук, Лисицин, Шумов

МПК: G06F 15/173

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

...группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.Блок 10 инициации вершин мест(фиг. 6) содержит группу элементов 2 ОИ 34 и группу элементов ИЛИ 35.Блок 11 имитации зарезервированных меток состоит из группы узловимитации, каждый из которых содержитэлемент И 36, регистр 37 и счетчик 38,5содержащий группу элементов И-НЕ 39,группу триггеров 40, группу элементов И-ИЛИ 41, триггер 42 и элементИ 43.Устройство работает следующим образом.После включения питания переключателем 20 триггер 21 устанавливаетсяв состояние "1", и тем самым обеспечивается режим ввода исходных данныхдпя решения задачи по моделированиюсоставленного графа Петри. Данные(входные разметочные векторы, выходные разметочные векторы, начальнаяразметка графа Петри, длительности...

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

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

Авторы: Биков, Бороденко, Верияскин, Мельников, Назаренко, Подзубанов, Синица

МПК: G06F 15/173

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

...на прием сигналов от моделей ветвей, восстанавливается и усиливается усилителем-формирователем 19 импульсных сигналов, так как на электрический сигнал в моделях ветвей воздействуют переходные процессы, искажающие его форму. Поступая на вход останова второго генератора 11 линейно изменяющегося напряжения, который былзапущен в момент подачи зондирующего импульса, данный импульс останавливает его. На выходе второго генератора 11 линейно изменяющегося напряже" ния будет зафиксировано напряжение, эквивалентное полученному промежутку времени. Соответствующий ключ изпервой группы 15 ключей открываетсяпотенциалом логической единицы с со-. ответствующего выхода дешифратора 14 по управляющему входу, что обеспечивает поступление через его...

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

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

Авторы: Бороденко, Верияскин, Подзубанов, Синица

МПК: G06F 15/173

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

...ИЛИ 3 первой строки матрицы и через первый элеме г И 7 группы - на вторые входы элементов ИЛИ 3 первого столбца матрицы элементов ИЛИ и далее на вторые ,входы элементов И 2 первой строки и первого столбца матрицы элементов И. Если первая вершина слабо связана хотя бы с одной вершиной, то соответственно триггер 1, первой строки или гервого столбца находится в единччном состоянии, В противном случае все триггеры 1 первой строки и 15 первого столбца находятся в нулевом состоянии, граф является не связнью. на всех входах первого элемента ИЛИ 4 первой группы и первого элемента 1,11 И 6 третьей группы - нули, на 20 в:",одах первого элемента ИЛИ 19 четвертой группы - нули.Если К-й триггер 1 первой строки находится в единичном состнии, сигнал...

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

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

Автор: Костюк

МПК: G06F 15/173

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

...телям полученной компоненты сильной связности, на выходы 21 устройства через элементы ИЛИ 19 на входы регистра 20. Код пересечения также поступает к четвертой группе элементов И 18, в которых осуществляется его сравнение с кодами носителей компонент сильной связности, полученными на предыдущих тактах с целью исключения дублирования информации, Посколь- ЗО ку ни одна вершина графа не может одновременно принадлежать двум различным компонентам сильной связности, то при совпадении текущего кода с записанными в регистре 20 хотя бы в одном разряде на выходе элемента ИЛИ 22 появляется "1", поступающая на вход второго элемента НЕ 23 и запрещающая прохождение тактового импуль" са на выход 27 синхронизации вывода 40 и к второму счетчику 26. Тем...

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

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

Авторы: Волошаненко, Исаев, Рожкевич, Черняк

МПК: G06F 15/173

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

...уровень поступает на вход 0 элемента ИЛИ 5 проходит через него и поступает на первую строку, которая образована вторымн входами элементов И 4, . Поскольку ни на одном первом входе элементов И 4первый строки матрицы не при 1сутствует единичный уровень (в соответствии с топологией графа), а единичный уровень присутствует только на первом выходе счетчика 3, то на 15 выходе элемента И 10 - низкий уровень. Это означает, что первая вершина не является базой графа, При поступлении на счетный вход счетчика 3 второго положительного перепа да счетчик устанавливается в состояние 010. При этом с второго выхода счетчика 3 высокий уровень поступает на вход 0 элемента ИЛИ 5, проходит через него и далее поступает на вто" 25 рую строку, которая...

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

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

Авторы: Крылов, Романов, Славин

МПК: G06F 15/173

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

...одного из регистров 37,38 группы в момент прихода импуль"са Ц , задержанного на элементе52 задержки на время срабатываниядешифратора. После этого на выходе 20 только одной из групп 41, 42 элементов И будет находиться содержимое соответствующего регистра, ана выходах всех остальных групп41, 42 будут выставлены нулевые 25 слова, поэтому на выходе группы 46элементов ИЛИ будет выставлено слово, хранящееся в регистре, опреде-.ляемом адресным словом на адресномвходе 57. Таким образом, с помощьюимпульса 0 , на информационномвыходе 61 блока 1 памяти выставляется значение Р;.ТЯКТОВый импульс Б т.акт также поступает на синхронизирующий вход81 второго блока памяти (фиг.З). Через элемент ИЛИ 77 импульс Бтпоступает на синхронизирующий...

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

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

Авторы: Ефимов, Лебедев

МПК: G06F 15/173

Метки: графов, моделирования, сетевых

...и по 15Второму выходу на вход считываниярегистра 14, так что записанные врегистрах 14, 14 з коды 0001 и 0101Поступают на информационные входырегистров 13 и 13 соответственно, 20которые записывают эти коды при поступлении на их входы записи импульса с выхода элемента И 5. ЗаднимФронтом этого импульса перебрасывается в нулевое состояние триггер 2, 25закрывая элемент И 5 и открывая элемент И 4, а задним фронтом импульса,поступающего на вход счетчика 3, онсбрасывается из состояния переполнения в состояние с записанной 1, 30б-й, 7 - й и 8-й импульсы генератора 1проходят через элемент И 4 на тактирующие входы регистров 10 и 13, Свыходов регистров 10 , 1 О последовательно поступают сигналы "1","1", "О" (соответственно коду числа3, записанному...

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

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

Авторы: Волошаненко, Рожкевич, Фелер, Черняк

МПК: G06F 15/173

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

...на первых входах соответствующихэлементов И 4 - 0, Дпя графа с разорванными дугами анапогично описанному определяется совокупность параметров достижимости. При этомна К-м такте каждого рабочего цикла информация в разрядах адреса К блока 6 памяти параметров достижимости может меняться, т. е. в определенных разря дах может происходить замена записанных туда "1" на "0". Разряд М адреса К блока 6 памяти параметров достижимости соединен с пятым входом соответствующего блока 7 памяти ПТН, Ког да в разряде М адреса К блока 6 памяти параметров достижимости происходит замена "1" на "0", то при напичии разрешающего сигнала на четвер-, том входе соответствующего блока 7 б 0 памяти ПТН производится перезапись содержимого блрка 11 подсчета...

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

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

Авторы: Васильев, Кузьмук, Лисицин, Шумов

МПК: G06F 15/173

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

...блоке элементов ИСКЛЮЧАЮЩЕЕИЛИ 18 вычисляется новое значениевектора текущей разметки: ш 0 = (О,О,О, О, О, О, О, О), которое подается напервый информационный вход коммутатора. Одновременно сигнал с выходаблока 5 поступает на счетный входсоответствующего счетчика 10 и увеличивает его содержимое на 1, что чри водит к подключению к выходу соответствующего блока 13, первого из наборов значений переменных выходных разметочных векторов. Этот же сигнал,проходя через элементы ИЛИ 20, И 24, З 5 ИЛИ 22 (по приходу импульса Ф 1 сблока 1 синхронизации)подключает первый информационный вход коммутатора27 к его выходу и формирует сигналразрешения изменения содержимого,ре гистра 26Счетчики 9 работают следующим образом. После перевода врежим счет они...

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

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

Авторы: Васильев, Кузьмук, Купченко, Лисицин, Шумов

МПК: G06F 15/173

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

...определить пропускную способность транспортной сети,частоту возникновения конфликтов,длительности простоя и т.д,Для загрузки графа Петри в устройствоесоставляется таблица топологии графа Петри (см. фиг, 3), позволяющая отразить входные ь и выходок -ь20ные р разметочные вектора переходовприоритеты переходов Р, началькную разметку и длительности срабатывания переходовВ процессе загрузки:,исходных данных в устройстве значения" р заносятся в К-е регистры 1 первой группызначения" р в К-е регистры 2 второйгруппы, Значения 6 й к заносятся вК-е регистры 3 третьей группы, значе- ЗОние шр заносится в регистр 17.Режим моделирования графа Петриначинается по заднему фронту импульса на входе 32 пуска устройства.Разрешение на запуск К-го...

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

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

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

МПК: G06G 7/122

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

...15, ключи 23и переключатели 10 поочередно на всевершины графа, за исключением исходной (вершины А). Если Е равноили больше напряжения пробоя тиристоров 7 кратчайшего пути между текущей вершиной и вершиной А графа,то образуется цепь протекания токаот источника 16 через соответствующие модели 2 и резистор 19, напряжение с которого поступает через элемент ИЛИ 18 и открытый ключ 24 наинформационный вход соответствующегокоммутатора 20, с первого выхода которого сигнал поступает на вход соответствующего триггера 2 1 и перебрасывает его в единичное состояние.Например, импульс. с второго выходараспределителя 12 (Б -вторая вершина) открывает ключи 23 и 24 , и напряжение Е проходит через коммутатор 15 и открытый ключ 23 и переключатель 10...

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

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

Авторы: Бондарь, Бороденко, Верияскин, Назаренко

МПК: G06F 15/173

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

...комбинация 1011. При поступлении очередных тактоных импульсов происходит перемножениеоче" редных одноименных строк и столб510 15 20 25 35 40 45 50 55 5 15 цов матрицы достижимостей, что соответствует перемножению одноименных строк матриц достижимостей и контрдостижимостей К и Ч, При поступлении 5-го тактового импульса на 5-м выходе денифратора 23 появляется единичный потенциал 1 на всех остальных выходах - нулевой потенциал), который запрещает через элемент И 20 дальнейшее прохождение тактовых импульсов на счетчик 21. В регистрах 29 л -29 ц записана матрица КЩ (фиг.б). На этом заканчивается второй этап работы устройства.На третьем этапе производится разбиение графа на сильные компоненты. На первый вход элемента И 24, открытого по...

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

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

Авторы: Глушан, Ефремов, Резниченко

МПК: G06F 15/173

Метки: графов, раскраски

...одногодо В тактов, где В - количество вершин в графе.Блок 2 определения класса раскраски работает следующим образом.По сигналу начальной установкикоммутатор 14 замыкает каждую из своих В информационных цепей. По сигналу подготовки накапливающий узел логического сложения обнуляется. По сигналу пуска 13 синхронизации начинаетформировать сигналы, предусмотренныевременной диаграммой его работы. Сигнал уровня логической единицы появляется на первом выходе 9 узла 13 синхронизации, При этом узел 16 проверкисмежности проверяет отсутствие смежности вершин, накопленных на выходеузла 15. Через время, достаточноедля проверки, узел 13 синхронизацииформирует сигнал уровня логическойединицы на своем тактовом выходе 18,При этом блок 16 выдает значение...

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

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

Авторы: Глушан, Ермаков, Калмычек, Курейчик

МПК: G06F 15/173

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

...новое осчетдцце 111 О 00.После этого цдчццдето я и гй ци -цесс определения изом 1 рфи гмд ( цен и -морфизмд) полного пятинершцццого грд.фа и выбранного блоком 14 подгрдфд,состоящего в соответствии с сочетднием 1111010О из -й 2-й, З-й,4-й и 6-й вершин. Этот процесс цротгкает аналогично описанному с той липвразницей, что иэ-зд подачи единиц сныхода коммутатора 19 ца 1-й, 2-й,З-й, 4-й и 6-й входы узлов 20 и 21при последовательной поддче цд ихсинхровходы тактовых импульсов единицы появляются последовательно ца1-м, 2-м, З-м, 4-м и 6-м выходахт,е, именно нд тех выходах, которыеоднозначно соответствуют новому сформированному сочетанию 11110100.Предположим, что подгрдф, состоящий из указанных вершин (т.е.1,2,3,4,6) не изоморфен цолцому...

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

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

Авторы: Глушан, Карелин

МПК: G06F 15/173

Метки: графов, раскраски

...импульсный сигнал на выходе 9, что свидетельствует о полном переборе всех возможных комбинаций раскраски вершин графа в заданное количество цветов. В любом случае блок 1 синхронизации будет остановлен.Блок 2 формирования комбинаций работает следующим образом.Перед началом работы обнуляют все счетчики 13 группы, в младший разряд регистра 12 сдвига заносят единицу, остальные разряды обнуляют, по входу 18 задают коэффициенты пересчета всех счетчиков 1 3. При подаче на вход 22 тактовых импульсов один из счетчиков 13, на вход разрешения счета которого подан потенциал уровня логической единицы с выхода соответствующего разряда регистра 12 сдвига, начинает счет импульсов. Причем при наличии на входе 17 потенциала уровня логической единицы...

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

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

Авторы: Глушан, Ефремов, Карелин

МПК: G06F 15/419

Метки: графов, раскраски

...чтои в предыдущем цикле, т,е. окрашивается в следующий по порядку цвет таже вершина, что и в предыдущем цикле.Работа устройства продолжается аналогично, до тех пор, пока на входе 20не появится потенциал уровня " 1",что означает восстановление допустимой раскраски вершин, или до техпор, пока канал счетчика 11 не переполнится, если исчерпано допустимоеколичество цветов. При этом на еговыходе признака наличия переполненияпоявляется потенциал уровня "1", которыйразрешает сдвиг влево регистра 14,причем разрешение сдвига влево обладает большим приоритетом, чем сдвигвправо. Одновременно коммутатор 13подключает свой информационный входк второму информационному выходу ина вход разрешения работы одного иэканалов счетчика 12 поступает потенциал...

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

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

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

МПК: G06F 15/173

Метки: графов, моделирования

...1 Л, где и - количество разрядов представления весов ветвей, Из последовательности импульсов и-го разряда распределителя 34 импульсов распределитель 35 импульсов формирует а последовательностей импульсов длительно,стью иЛ, действующих с частотой 1/а и и сдвинутых одна относительно другой на время иВВ режиме ввода весов ветвей в регистры 1 и 22 сдвига коммутатором 39 (выполненным, например, в виде переключателя. на два положения) блока 21 управления под 1709346триггера 44 блока 21 управления к одномуиз входов элемента ИЛИ 15.Пуск устройства осуществляют комму 25 Я-триггера 44 и устанавливает его в единичное состояние. Триггер 44 единичным сигналом прямого выхода открывает элемент И 30 40 последовательность импульсов первогоразряда...

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

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

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

МПК: G06F 15/419

Метки: графов, раскраски

...11 синхронизации формирует им 50 пульс уровня логической единицы на своемвтором выходе, При этом при отсутствииединичного потенциала на его выходе блокировки и наличии потенциала уровня логической единицы на его входе разрешения55 сдвига вправо, узел 13 сдвигает значениехранимого им двоичного кода на один разряд вправо. При этом его крайние разряды слева заполняются нулями,В том случае, если единичные разрядыего кода выходят за разрядную сетку спра 1711189ва, регистр 13 сдвига формирует сигнал уровня логической единицы на своем выходе признака переноса вправо за разрядную сетку(это означает, что вершины графа раскрашены в заданное количество цветов). В том случае, если за разрядную сетку вправо выходят нулевые разряды кода,...

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

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

Авторы: Васильев, Зенкин, Кузьмук, Лисицин, Перепелица, Шумов

МПК: G06F 15/173

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

...элемент НЕ 55.Блок 12 анализа (фиг.9) содержит дваэлемента ИЛИ 58 и 59 и элемент 60 задержки.Блок 13 фиксации (фиг,5) содержит набор из ВЯЗ-триггеров 13. кБлок 14 просмотра выходных векторов(фиг.10) содержит ГПИ.56 и узел 57 управления.Устройство работает следующим образом.Пусть необходимо смоделировать графПетри, который содержит два типа вершин;вершины переходов (в дальнейшем переходов) и вершины мест Р (а дальнейшеммест). Примером может служить граф, приведенный нв фиг,11.Метки располагаются в вершинах местРе и их появление или удаление моделируетсоответственно окончание. или начало реальных действий а 1, имитируемых переходами 1. Местонахождение меток в графеПетри отображается вектором текущей разметки аР=...

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

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

Авторы: Борисов, Буслаев, Щербань, Ячкула

МПК: G06F 15/20

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

...единиц в соответствующихстроках матрицы смежности исследуемогографа, подаются на информационные входыблока 2 выбора минимального кода.Решение начинается подачей импульсана тактовый вход 12 устройства, При этом вблоке 2 осуществляется выбор минимального из входных сигналов и на соответствующем выходе блока появляется импульсуровня логической единицы, который поступает на единичный входтриггера соответст.вующей модели вершины, например на триггер 4 модели вершины. Триггер 4 модели вершины переходит в единичное состояние и сигнал с его единичного выхода поступает на объединенные входы всех моделей дуг -го столбца и -й строки блока 1, моделируя исключение -й вершины из множества вершин искомого подграфа. С выходов моделей дуг сигналы через...

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

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

Авторы: Бакуменко, Голованова, Ралдугин

МПК: G06F 15/419

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

..."Пуск" поступает на полюс 37(1) модели 2(1) вершины, который выбран в качестве начального и через элемент 16(1) ИЛИ поступает на вход 43(1), а также открывает блок 14 элементов И, с выходов которых на первые входы блока 29 элементов ИЛИ передается двоичный код номера выбранной модели. С выходов блока 29 элементов ИЛИ код номера узла поступает на информационные входы счетчика 19 импульсов, Под действием сигнала на стробирующем входе, поступающем с выхода элемента 27 ИЛИ, в счетчик 19 заносится двоичный код номера узла 1, Тактовые импульсы генератора 17 через элемент 23 И поступают на вход (4) блока формирования сигналов управления 18, под действием которых блок 18 начинает формировать сигналы управления, По сигналу на.выходе (2) этого...

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

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

Авторы: Гулиус, Калинин, Матейченко

МПК: G06F 15/20

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

...входы элемента ИЛИ из угла7, формирующего сигнал установки в "1"5 первого разряда регистра 9, должны бытьсвязаны с выходами 8- и 9-го каналов второйгруппы выходов блока 2. Аналогично, позиции рд соответствует четырехвходовой элемент ИЛИ, подключенный входами квыходам 10-го. 11-го, 12-го и 13-го каналоввторой группы выходов блока 2, э выходом -к входу установки в лог. "1" 9-го разрядарегистра 9 меток,Остальные сигналы установки в лог. "1"разрядов регистра 9 не требуют элементов 5ИЛИ, поскольку непосредственно снимаются с выходов соответствующих каналов второй группы выходов блока 2 согласнотопологии графа Петри.Узел 8 служит для удаления меток из тех 10позиций, которые связаны со входами возбужденного перехода, т.е, данный узел...

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

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

Авторы: Борисов, Буслаев, Щербань, Ячкула

МПК: G06F 15/20

Метки: анализа, графов

...14 снимается и появляется сигнал на управляющем выходе 13 и р выходах группы выходов 12 ь= 1, и в соответствии с первым сочетанием иэ и по р, сформированным в блоке 1, Сигнал с выхода 13 поступает через вход 24 на вход запуска времяинтегрирующего преобразователя 20, который при этом начинает генерировать линейно-возрастающий сигнал (напряжение или код), поступающий на информационные входы элементов памяти 21 ь= 1, и. Сигнал ы уровня логической единицы с р выходов 12 ь==1, п поступают на информационные входы 33 ь=1, и блока 7, а, через соответствующие разделительные диоды 8 ь= 1, и на объединенные полюса 16 ь 19 ь 22 ь= 1, и блоков 2, 3, 4 соответственно. При этом в блоке 2 моделируется достижение тех р вершин, которым соответствуют...

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

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

Авторы: Анисимов, Борисов, Зубачев, Ячкула

МПК: G06F 15/20, G06F 15/419

Метки: графов, компонент

...поступает на объединенные "входы моделей дуг -той строки матрицы смежности. С входов моделей дуг -той строки сигналы поступают на вход первого элемента И 9 этих моделей дуг, Кроме того, сигнал с выхода элемента ИЛИ 2 поступает на вход элемента И 4 ь это моделирует единичное значение элемента гц матрицы достижимости графа. Если в - той строке матрицы смежности исследуемого графа есть столбцы с единичными элементами, т,е. если триггер 8 модели дуги в соответствующем столбце находится в единичном состоянии, то на обоих входах элемента И 9 будут сигналы высокого уровня и сигнал с выхода первого элемента И 9 этих моделей дуг поступит через диод 11 на вход соответствующего данному столбцу 5 10 15 20 25 30 35 40 45 50 5.5 матрицы смежности...