Модель ветви графа

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. Союз Советских

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

Республик >714402 (61) Дополнительное к авт. саид-ву— р1)м. к .

G 06 F 15/20 (22) Заявлено 030677 (? 1) 2492575/18-24 с присоединением заявки ¹

Государственный комитет

СССР ио делам изобретений и открытий (23) Приоритет—

Опубликовано 0502.80. Бюллетень № 5 (53) УДК 681. 335 (088. 8) Дата опубликования описания 10. 02. 80 (72) Авторы изобретения

В. И. Волошин, А. Г. Додонов, А. М. Малярчук и В. В. Месяц (54) МОДЕЛЬ ВЕТВИ ГРАФА

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

Известна модель ветви сетевого графика, выполненная на логических элементах, с помощью которой можно решить задачу о минимальном потоке в сети (1). Недостатком известного устройства является недостаточное быстродействие., Наиболее близким по технической сущности к рассматриваемому является модель ветви графа, выполненная на элементах И, счетчиках, триггерах и инверторе (2) .

К основному недостатку этой моде- ли следует отнести невозможность моделирования графов, содержащих циклы.

Целью изобретения является расши» рение класса решаемых задач, за счет .моделирования циклических участков °

Это достигается тем, что в модель, содержащую счетчик импульсов, выход которого соединен с единичным входом первого триггера, .нулевой вход которого подключен к выходу первого элемента И, первый вход которого соединен со входом сброса модели, выходной полюс которой через элемент НЕ соединен со вторым входом первого элемента И и одним из входов блока индикации, соответствующие входы которого подключены к входному полюсу модели, единичным выходам первого и второго триггеров и к нулевому выходу третьего триггера, входной полюс модели соединен с первым входам второго элемента И, второй вход которого соединен со входом разрешающего потенциала модели, а третий вход под.ключен к нулевому выходу третьего триггера, единичный вход которого подключен к единичному выходу первого триггера, нулевой вход второго триггера подключен к выходу третьего элемента И, первый вход которого подключен ко входу синхронизации модели, второй вход — к единичному выходу третьего триггера, а третий— к выходу счетчика регенерации, вход которого объединен со входом счетчика импульсов и подключен к выходу четвертого элемента И, один вход которого подключен ко входу тактовых импульсов модели, второй вход — к единичному выходу второго триггера,. дополнительно введены счетчик циклов, 714402 пятый элемент И и элемент ИЛИ, выход которого соединен с единичным входом второго триггера, а входы подключены соответственно к выходу второго эле мента И и циклическому входу модели, который соединен с нулевым входом 5 третьего триггера, единичный выход которого соединен с (иклическим выходом модели, первым входом пятого элемента И и входом счетчика циклов, выход которого соединен со вторым вхо- g дом пятого элемента И, выход которого соединен с выходным полюсом модели.

Функциональная схема модели представлена на чертеже.

Модель ветви графа содержит счет- 15 чик 1 импульсов, счетчик 2 регенерации, триггеры 3-5, элементы 6-9 И, элемент 10 НЕ, блок 11 индикации, вх одной полюс 12 модели, выходной полюс 13 модели, вход 14 разрешающего 2() потенциала, вход 15 синхронизации, вход 16 сброса, вход 17 тактовых импульсов, циклический вход 18, элмент 19 ИЛИ, циклический выход 20, счетчик 21 циклов, элемент 22 И.

Работает устройство следующим образом.

Модели ветвей соединяются между собой полюсами 12 и 13 в соответствии с топологией сетевого графика. В счетчики 1 при записи исходной инфор- ЗО мации заносятся количества импульсов, дополняющие продолжительность работ до полной емкости счетчиков. Счетчики 2 и триггеры 3, 4, 5 первоначально находятся в нулевом состоянии. Сиг-З5 нал, поданный на циклический вход 18 устанавливает триг ер 3 в единичное состояние и производит повторный за пуск модели ветви, одновременно сигнал запуска по циклическому входу 40 сбрасывает триггер 5 в нулевое состояние, при этом появляется нулевой потенциал на выходном полюсе 13. Сигнал выхода инвертируется элементом 10 НЕ, поступает на элемент 8 И и после подачи импульса с генератора (на чертеже не показан) на вход 16 сброса модели происходит сброс триггера 4 в нулевое состояние. Таким образом, подавая сигнал на циклический вход .модели, можно каждый раз вызывать функционирование одной модели, не изменяя состояния других моделей ветвей, из,которых построена модель графа. Перед началом работы в счетчик циклов заносится число, дополнением к которому служит заданное число циклов, и каждый раз после появления сигнала на выходе триггера 5 и на выходе 20, содержимое счетчика 21 увеличивается на единицу и после отсче- gp та заданного числа циклов на выходе счетчика появится сигнал, который, попадая на вход элемента 22 И совместно с выходным сигналом триггера 5 вызывает появление сигнала на вйходном 6 полюсе 13, что означает окончание функционирования модели.

Таким образом модель ветви позволяет осуществить запуск заданное чис-, ло раз циклических участков моделиру-. емого графа и отделить циклический участок модели графа от нециклического.

Формула изобретения

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

Ист оч ник и ин формации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 394793; кл. G 06 F 15/20, 1971.

2. Васильев В. В. и Додонов A. Г.

Гибридные модели з апач оптимизации.

Киев, Наукова Думка, 1974, с. 114, рис. 67 (прототип) .

714402

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

Редактор М. Минаев Техред Н.Ковалева Корректор A.Ãðèöåíêî

Заказ 9290/47 Тираж . 751 Подписное

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

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

Филиал ППП Патент, r, Ужгород, ул. Проектная, 4