Патент ссср 433504

О П И С А Н И Е (и) 433504

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

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

Реслублик (61) Зависимое от авт. свидетельства (22) Заявлено 06.03.72 (21) 1757236/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 25.06.74. Бюллетень № 23

Дата опубликования описания 18.11.74 (51) М. Кл. G 060 7/48

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

Совета Министров СССР по делам изобретению и открытии (53) УДК 681.3(088.8)

У (72) Автор изобретения

1

ФМ - P. В. Тверицкий (71) Заявитель (54() УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК

СВЯЗНОСТИ ВЕРОЯТНОСТНОГО ГРАФА

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

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

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

Предложенное устройство отличается от известных тем, что в него включены генератор импульсных меток, линия задержки, дифференцирующая цепочка, стробируемые формирователи, управляемые ключевые схемы вершин, триггерная схема анализа связности и соединенные с входами электронных цифровых вычислительных машин (ЗЦВМ) кодовые шины, причем выходы генератора импульсных меток подключены на входы управляемых ключевых схем вершин, входы стробируемых формирователей, входы триггерной схемы анализа и вход ключа съема результата; выходы управляемых ключевых схем вершин соединены со входами вершинных логических схем «ИЛИ» и с входами логической схемы «ИЛИ», выход которой соединен через дифференцирующую цепочку, линию задерж15 ки и инвертор уровня с одним из входов триггерной схемы анализа; выходы вершинных схем «ИЛИ» подключены к входам стробируемых формирователей, выходы которых соединены с входами управляемых ключевых

20 схем ребер и с входами логических схем

«ИЛИ», остальные входы которых соединены с нулевыми выходами запоминающих триггеров вершин и входами триггерной схемы анализа, а выходы подключены к входам триггер25 ной схемы анализа.

В результате устройство выдает сигнал о связности вероятностного графа в целом, а при отсутствии таковои выдает информацию о частичных подграфах, получившихся в ре30 зультате розыгрыша, т. е. может быть полу433504 чена информация о том, с чем связана каждая вершина и каких ребер не хватает для того, чтобы получить связность графа в целом.

На фиг. 1 изображена блок-схема предлагаемого устройства, соединенного с электронно-цифровой вычислительной машиной (ЭЦВМ); на фиг. 2 — функциональная схема того же устройства (в качестве примера приведена схема для числа вершин п(4).

Устройство, соединенное с ЭЦВМ 1, содержит блок возбуждения вершин 2, блок возбуждения кодовых шин 3, блок анализа 4 и генератор 5 импульсных меток.

Выходные шины ЭЦВМ соединены с входами блока возбуждения вершин, блока возбуждения кодовых шин и генератора импульсных меток. Выходы генератора импульсных меток соединены со входами блока возбуждения вершин, блока возбуждения кодовых шин и блока анализа. Выход блока анализа соединен с входом ЭЦВМ, выходы блока возбуждения вершин — с входами блоков возбуждения кодовых шин и блока анализа, а выходы блока возбуждения кодовых шин — с входами блока анализа и входами ЭЦВМ.

Генератор импульсных меток представляет собой пусковую схему, состоящую из ждущего генератора импульсов, линий задержки и формирователей импульсов. В ответ на запускающий импульс от ЭЦВМ генератор импульсных меток выдает серию импульсов, каждый из которых генерируется в момент времени, определяемый дискретной временной сеткой генератора и передается по отдельной шине.

Блок 2 возбуждения вершин содержит (см. фиг. 2) запоминающие триггеры 6 вершин и управляемые ключевые схемы 7 вершин.

Блок 3 возбуждения кодовых шин содержит запоминающие триггеры ребер 8, управляемые ключевые схемы ребер 9, вершинные логические схемы «ИЛИ» 10, стробируемые формирователи импульсов 11 и логические схемы

«ИЛИ» 12.

Блок 4 анализа содержит логические схемы

«И» 13 — 17, логические схемы «ИЛИ» 18, 19 и инверторы 20 и 21, составляющие триггерную схему анализа, а также логическую схему

«ИЛИ» 22, дифференцирующую цепочку 23, линию задержки 24, инвертор уровня 25 и ключ съема результата 26.

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

Для приведения устройства в исходное состояние от ЭЦВМ поступают по шинам 27 сигналы, устанавливающие все триггеры устройства в нулевое положение. При этом на шине 28, соединяющей инвертор 21 и ключ съема результата 26 устанавливается уровень, открывающий ключ съема результата, Результаты розыгрыша вершин и ребер поступают на запоминающие триггеры вершин 6 и ребер

8 по шинам 29 установки в положение «1».

Триггеры фиксируют результаты розыгрыша.

В случае полного отсутствия вершин в розыгрыше сигналы, снимаемые с нулевых выхо5

65 дов триггеров б, передаются по шинам 30 на схему совпадения «И» 17 и через логическую схему «ИЛИ» 19 и инвертор 21 удерживают на шине 28 в течение всего времени работы устройства потенциал, запрещающий открывание ключа опроса 26, что свидетельствует об отсутствии связности в графе.

Сигнал запуска устройства от ЭЦВМ, приходящий по шине 31 на генератор импульсных меток, вызывает на каждой из его выходных шин 32 появление сдвинутых во времени импульсов меток, причем в каждый дискретный момент времени присутствует импульсная метка только на одной шине 32. На шине 33 импульсные метки присутствуют во все дискретные моменты времени работы устройства.

Импульсная метка на шине 34 опроса результата является последней по времени. Сигнал запуска устройства с шины 31 передается также на логическую схему совпадения «И»

13 блока анализа и при наличии одного или большего количества триггеров вершин в положение «1» вызывает появление на шине 28 уровня, открывающего ключ съема результата 26.

Управляемые ключевые схемы вершин пропускают на шины 35 и соединенные с ним вершинные схемы «ИЛИ» 10, стробируемые формирователи 11 и кодовые шины Зб — 39 только те метки с шин 32, которые соответствуют триггерам вершин, установленным в результате розыгрыша в положение «1», Таким образом, на каждой из кодовых шин 36 — 39 обязательно присутствует собственная временная метка вершины, включенной в розыгрыш.

Кроме того, собственные импульсные метки с упомянутых шин, проходя через управляемые ключевые схемы ребер 9 и шины 40 — 43 при единичных состояниях всех или части триггеров ребер 8 передаются на шины, соответствующие другим вершинам. При наличии связности любых вершин на всех кодовых шинах

36 — 39, соответствующих этим вершинам, присутствуют одни и те же временные метки, На кодовых шинах 36 — 39 соответствующих несвязаным вершинам, общие временные метки отсутствуют.

Кодовые шины 36 — 39 соединены со входами логических схем «ИЛИ» 12, к которым подсоединены также шины 30 нулевых выходов триггеров вершин. При нулевом положении триггера вершин сигналы с соответствующей ему шины 44 исключаются из рассмотрения на входах схемы совпадения «И» 15.

Схема, составленная из логических схем

«И» 13 — 17, «ИЛИ» 18, 19 и инверторов 20 и

21 является триггером. Установка его в нулевое положение, которому соответствует запрещающий потенциал на шине 28, производится в начале работы сигналом с шины 31 на вход логической схемы «И» 13. Обратная связь триггерной схемы осуществляется сигналами с выходов инверторов 20 и 21 на входы логических схем «И» 14 — 16. На вход логической схемы «И» 14 поступают сигналы с

433504 шин 35, проходящие через логическую схему

«ИЛИ» 22, дифференцирующую цепочку 23, линию задержки 24 и инвертор 25, причем эти сигналы разрывают обратную связь триггерной схемы, осуществляемую через логическую схему «И» 14. Однако, если на всех шинах

44, подсоединенных к входам логической схемы «И» 15 и подлежащих анализу в данном розыгрыше существуют одни и те же временные метки, обратная связь триггерной схемы будет осуществляться через логическую схему

«И», 15, разрыв цепи обратной связи через логическую схему «И» 14 не окажет влияния на состояние триггерной схемы в целом и к моменту опроса ключа 26 по шине опроса 34 на шине 28 остается разрешающий потенциал и на шине съема результата 45 появится сигнал, свидетельствующий о связности графа в целом, При одновременном разрыве цепи обратной связи, проходящей через логические схемы совпадения «И» 14 и 15, триггерная схема изменит состояние и к моменту опроса на шине

28 будет присутствовать потенциал, закрывающий ключ съема результата 26, что свидетельствует об отсутствии связности в анализируемом графе в целом.

Информация о связности частичных подграфов записывается в ЗУ ЭЦВМ с кодовых шин

36 — 39 в моменты, синхронные с временными метками, и подлежит дальнейшему анализу на ЭЦВМ.

Предмет изобретения

Устройство для определения характеристик связности вероятностного графа, содержащее запоминающие триггеры вершин и ребер, управляемые ключевые схемы ребер, схемы

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

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

433504

Т 9 1- Д (г- ) Д 1-4 1г Я в Т и2 ср < ц) 2 се! 93 Ч1 иЗ 2

1 Ц11 И Z З ю г з

1 !

1 ! ! ! ! !

Фиг. 2

Составитель И. Перцев

Техред Г. Васильева

Корректор Н. Аук

Редактор Е. Гончар

Типография, пр. Сапунова, 2

Заказ 3106/6 Изд. № 64 Тираж 624 Подписное

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

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