Устройство для исследования графов

5498 Ю ОЛ ИСАНИ ЕИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(51) М.Кл, С 06 Г 15/20 аявки-с присоединением 23) Приоритет Государственный комитет Совета Министров СССР 5.03,77, Бюллетень(43) Опубликова К 681,3 (088,8 по делам нзобретени н открытий) Дата опубликования описания 27.07.7. Е, Чистяков 1) Заявитель УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ Изооретение относится к цифровои вычислительной технике и может быть применено при расчетах транспортной сети, сетевых графиков, тестов контроля релейных структур, электрических сетей и т. п, 5Известно устройство тестового контроля релейных структур 1, содержащее двоичный счетчик, реле, соединенные с наборным полем, кольцевой счетчик, ключи, регистратор, логический элемент И и триггеры.10Недостатком устройства является его относительная сложность и невозможность применения для анализа комбинаций по заданным признакам.Наиболее близким к изобретению по тех нической сущности является устройство для исследования графов 2, содержащее узел перебора сочетаний, узел управления выбо ром направления, генератор, элемент И, триггер, мультивибратор. Выходы узла управления выборам направления соединены спервыми входами наборного поля.Недостатком устройства является его относительная сложность, обусловленная жесткой и сложной логикой работы, которую нель зя приспособить для анализа перебираемых комбинаций. Использование этого устройства затрудняет также последовательность в соединении двух схем перебора сочетаний.Целью изобретения является упрощение 30 устройства при выполнении сложных операций анализа перебираемых комбинаций и выявление комбинаций, обладающих признаками, соответствующими циклом атическим комбинациям ребер на связном графе.Поставленная цель достигается тем, что в предложенное устройство введены две группы элементов Запрет и два пороговых элемента. Первый вход устройства соединен с первым входом триггера, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора. Выход элемента И соединен через мультивибратор с первыми входами элементов Запрет первой группы, а непосредственно с первыми входами элементов Запрет второй группы и узла перебора сочетаний, второй вход которого соединен со вторым входом устройства. Выходы узла перебора сочетаний соединены со вторыми входами соответствующих элементов Запрет второй группы, выходы которых соединены с соответствующими входами узла управления выбором направления и первого порогового элемента, выход которого через наборное поле соединен со вторыми входами соответствующих элементов Запрет первой группы, вы. ходы которых соединены с входами второго порогового элемента. Управляющие входы пороговых элементов соединены с третьим20 25 ЗО 35 40 45 50 55 60 65 управляющим входом устройства, а выход второго порогового элемента - со вторым входом триггера.Блок-схема устройства приведена на чертеже,Устройство содержит узел 1 перебора сочетаний, группы элементов Запрет 2, 3, наборное поле 4, пороговые элементы 5, б, узел 7 управления выбором направления, триггер 8, элемент И 9, генератор 10, мультивибратор 11,Устройство работает следующим образом.На наборном поле 4 набирается модель исходного графа.По команде Исходное триггер 8 уста. навливается в единичное состояние, элемент И 9 закрывает выход генератора 10 и устанавливается в исходное состояние узел 1. Пороговые элементы 5 и б устанавливаются соответствечно на срабатьгвание по п=1 и а еди ничным сггггалам на их входах,По команде Пуск триггер 8 переводится в нулевое состояние, и импульсы с генератора 10 начинают проходить через элемент И 9, Первый импульс цриводит к срабатыванию узла 1, закрывает элементы Запрет 3 на время переходного процесса в узле 1 и через мультивибратор 11 закрывает элементы Запрет 2 на время переходного процесса в узле 1 и наборном поле 4. По заднему фронту первого импульса элементы Запрет 3 открываются, и сигнал с выхода узла 1 в виде параллельного кода поступает на пороговый элемент 5 и узел 7.Если параллельный код соответствует какой-либо комбинации из первого множества, то срабатывает пороговый элемент 5 и подает сигнал на любой один из узлов модели графа на наборном поле 4. Кроме того, узел 3 формирует сигнал и деформирует модель гра. фа на наборном поле 4 в соответствии с испытуемой комбинацией из перьвого множества. Если при этом все и вершин модели графа на наборном поле 4 оказываются под напряжением, то при снятии со входов элементов Запрет 2 сигнала с мультивибратора 11 они открываются, и по сигналу выхода наборного поля 4 срабатывает пороговый элемент б. Последний переводит триггер 8 и единичное состояние, и элемент И 9 закрывает выход генератора 10. Схема прекращает работу, и на наборном поле 4 фиксируется со ответствующая цикломатическая комбинаци ребер графа из второго множества и сигнализируется останов. По команде Пуск триггер 8 снова переводится в нулевое состояние, и работа устройства продолжается.По второму и следующим импульсам уст. ройство работает аналогично. Однако если параллельный код с выхода узла 1 не соответствует комбинации из первого множества, тогда не все узлы модели графа на наборном поле 4 могут иметь проводимость между собой, и сигнал с выхода порогового элемента 5 не поступает. При этом на выходе наборного поля 4 сигнал будет нулевой, и пороговый элемент б цри открытых элементах Запрет 2 не срабатывает. Триггер 8 остается в нулевом состоянии, и работа устройства продолжается,Устройство, благодаря наличию новых элементов и связей, существенно упрощает процесс определения полных множеств цикломатических комбинаций ребер на связных графах. Это достигается реализацией в устройстве автоматических операций, позволяющих выявлять комбинации с признаками, соответствующими цикломатическим комбинациям ребер на связном графе. Упрощение процесса вычисления тем эффективнее, чем сложнее граф. Устройство позволяет в десятки, а для сложных графов в сотни раз за счет упрощения вычислительгяого процесса и его автоматизации увеличить быстродействие и получать решения, исключая при этом субъективные ошибки. Формула изобретения Устройство для исследования графов, содержащее узел перебора сочетаний, узел управления выбором направления, генератор, элемент И, триггер, мультивибратор, причем выход узла управления выбором направления соединен с первым входом наборного поля, о т л и ч а ю щ е е с я тем, что, с целью упрощения, в него введены две группы элементов Запрет и два пороговых элемента; причем первый вход устройства соединен с первым входом триггера, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора, а вы. ход элемента И соединен через мультивибратор с первыми входами элементов Запрет первой группыинепосредственно с первыми входами элементов Запрет второй группы и узла перебора сочетаний, второй вход которого соединен со вторым входом устройства; выходы узла перебора сочетаний соединены со вторыми входами соответствующих элементов Запрет второй группы, выходы которых соединены с соответствующими входами узла уп равления выбором направления и первого порогового элемента, выход которого через наборное поле соединен со вторыми входами соответствующих элементов Запрет первой группы, выходы которых соединены с входами второго порогового элемента; управляющие входы пороговых элементов соединены с третьим управляющим входом устройства; вы. ход второго порогового элемента соединен со вторым входом триггера. Источники информации, принятые во внимание при экспертизе изобретения:1. Авторское свидетельство СССР Мо 518872, кл. Н 04 1. 1/10, 16.01,197 о г.2. Авторское свидетельство СССР, кл. (д 06 б 7/48, Мо 398976, 1971 г. (прототип).Редактор Л. Утехина Корректор В, Гутман Тип. Харьк, фил, пред. Патент Заказ 288/964 Изд. Мз 476 Тираж 899 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5