433504

р 433504 О П И С А Н И Е ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеслублик) Приорите осударственнмй квмитеСовета Министров СССРпв делам изобретениюи открытии Опубликовано 25.06.74. Бюллетень23Дата опубликования описания 18.11.74(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СВЯЗНОСТИ ВЕРОЯТНОСТНОГО ГРАФАИзобретение относится к вычислительной технике, а именно, к области электронного моделирования задач математического программирования и может быть использовано при создании автоматических систем управ ления сложными распределительными сетями (гидравлическими, газовыми, информационными и т. д.) для определения характеристик связности графа, у которого вероятность существования ребер и вершин отлична от еди ницы.Известны устройства для определения характеристик связности вероятностного графа, содержащие запоминающие триггеры, управляемые ключевые схемы, которые входами уп равления подсоединены к выходам запоминающих триггеров и соединены между собой в схему, отображающую граф, шину проверки проводимости, схему И, схемы ИЛИ и ключ съема результата. 20Однако при помощи этих устройств в результате анализа можно получить лишь ответ о связности или несвязности графа в целом, а в случае несвязности графа отсутствует информация о частичных подграфах данного 25 графа, внутри которых связность существует.Предложенное устройство отличается от известных тем, что в него включены генератор импульсных меток, линия задержки, дифференцирующая цепочка, стробируемые форми- ЗО рователи, управляемые ключевые схемы вершин, триггерная схема анализа связности и соединенные с входами электронных цифровых вычислительных машин (ЗЦВМ) кодовые шины, причем выходы генератора импульсных меток подключены на входы управляемых ключевых схем вершин, входы стробируемых формирователей, входы триггерной схемы анализа и вход ключа съема результата; выходы управляемых ключевых схем вершин соединены со входами вершинных логических схем ИЛИ и с входами логической схемы ИЛИ, выход которой соединен через дифференцирующую цепочку, линию задержки и инвертор уровня с одним из входов триггерной схемы анализа; выходы вершинных схем ИЛИ подключены к входам стробируемых формирователей, выходы которых соединены с входами управляемых ключевых схем ребер и с входами логических схем ИЛИ, остальные входы которых соединены с нулевыми выходами запоминающих триггеров вершин и входами триггерной схемы анализа, а выходы подключены к входам триггерной схемы анализа.В результате устройство выдает сигнал о связности вероятностного графа в целом, а при отсутствии таковои выдает информацию о частичных подграфах, получившихся в результате розыгрыша, т. е. может быть полу 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 10 15 20 25 30 35 40 45 50 55 60 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 соответствующих несвязаным вершинам, общие временные метки отсутствуют.Кодовые шины Зб - 39 соединены со входами логических схем ИЛИ 12, к которым подсоединены также шины 30 нулевых выходов триггеров вершин. При нулевом положении триггера вершин сигналы с соответствующей ему шины 44 исключаются из рассмотрения на входах схемы совпадения И 15.Схема, составленная из логических схем И 13 - 17, ИЛИ 18, 19 и инверторов 20 и 21 является триггером. Установка его в нулевое положение, которому соответствует запрещающий потенциал на шине 28, производится в начале работы сигналом с шины 31 на вход логической схемы И 13. Обратная связь триггерной схемы осуществляется сигналами с выходов инверторов 20 и 21 на входы логических схем И 14 - 16. На вход логической схемы И 14 поступают сигналы сшин 35, проходящие через логическую схему ИЛИ 22, дифференцирующую цепочку 23, линию задержки 24 и инвертор 25, причем эти сигналы разрывают обратную связь триггерной схемы, осуществляемую через логическую схему И 14. Однако, если на всех шинах 44, подсоединенных к входам логической схемы И 15 и подлежащих анализу в данном розыгрыше существуют одни и те же временные метки, обратная связь триггерной схемы будет осуществляться через логическую схему И, 15, разрыв цепи обратной связи через логическую схему И 14 не окажет влияния на состояние триггерной схемы в целом и к моменту опроса ключа 26 по шине опроса 34 на шине 28 остается разрешающий потенциал и на шине съема результата 45 появится сигнал, свидетельствующий о связности графа в целом,При одновременном разрыве цепи обратной связи, проходящей через логические схемы совпадения И 14 и 15, триггерная схема изменит состояние и к моменту опроса на шине 28 будет присутствовать потенциал, закрывающий ключ съема результата 26, что свидетельствует об отсутствии связности в анализируемом графе в целом. Информация о связности частичных подграфов записывается в ЗУ ЭЦВМ с кодовых шин 36 - 39 в моменты, синхронные с временными метками, и подлежит дальнейшему анализу на ЭЦВМ. 5 10 15 2 О 25 30 35 Предмет изобретения Устройство для определения характеристик связности вероятностного графа, содержащее запоминающие триггеры вершин и ребер, управляемые ключевые схемы ребер, схемы И, схемы ИЛИ, ключ съема результата и инвертор, отл ич а ю щеес я тем, что, с целью расширения функциональных возможностей устройства, в него включены генератор импульсных меток, линия задержки, дифференцируюгцая цепочка, стробируемые формирователи, управляемые ключевые схемы вершин, триггерная схема анализа и соединенные с выходами устройства кодовые шины, причем выходы генератора импульсных меток подключены к входам управляемых ключевых схем вершин, входам стробируемых формирователей, входам триггерной схемы анализа и входу ключа съема результата; выходы управляемых ключевых схем вершин соединены с входами вершинных логических схем ИЛИ и с входами логической схемы ИЛИ, выход которой соединен через дифференцирующую цепочку, линию задержки, инвертор с одним из входов триггерной схемы анализа; выходы вершинных схем ИЛИ подключены к входам стробируемых формирователей, выходы которых соединены с входами управляемых ключевых схем ребер и с входами логических схем ИЛИ, остальные входы которых соединеныснулевымп выходами запоминающих триггеров вершин и входами триггерной схемы анализа, а выходы подключены к входам триггерной схемы анализа.чз чз цю иг. г оставитель И. Перцев Техред Г. Васильева Корректор Н. Аук ктор Е, Гонча ПодписноСР Тираж 624Совета Минисоткрытийнаб., д. 4/5 каз 3106/6 Изд.64 ЦНИИПИ Государственного комитета по делам изобретений Москва, Ж, Раушска