Устройство для исследования графов Советский патент 1977 года по МПК G06F15/173 

Изобретение относится к цифровой вычислительной технике и может быть применено при расчетах транспортной сети, сетевых графиков, тестов контроля релейных структур, электрических сетей и т. п. Известно устройство тестового контроля релейных структур 1, содержащее двоичный счетчик, реле, соединенные с наборным полем, кольцевой счетчик, ключи, регистратор, логический элемент И и триггеры. Недостатком устройства является его относительная сложность и невозможность применения для анализа комбинаций по заданным признакам. Наиболее близким к изобретению по технической сущности является устройство для исследования графов 2, содержащее узел перебора сочетаний, узел управления выборОМ направления, генератор, элемент И, триггер, мультивибратор. Выходы узла управления выборам направления соединены с первыми входами наборного поля. Недостатком устройства является его относительная сложность, обусловленная жесткой и сложной логикой работы, которую нельзя приспособить для анализа перебираемых комбинаций. Использование этого устройства затрудняет также последовательность в соединении двух схем перебора сочетаний. Целью изобретения является упрощение устройства при выполнении сложных операций анализа перебираемых комбинаций и выявление комбинаций, обладающих признаками, соответствующими цикломатическим комбинациям ребер на связном графе. Поставленная цель достигается тем, что в предложенное устройство введены две группы элементов «Запрет и два пороговых элемента. Первый вход устройства соединен с первым входом триггера, выход которого соединен с первым входо.м элемента И, второй вход которого соединен с выходом генератора. Выход элемента И соединен через мультивибратор с первыми входами элементов «Запрет первой группы, а непосредственно с первыми входами элементов «Запрет второй группы и узла перебора сочетаний, второй вход которого соединен со вторым входом устройства. Выходы узла перебора сочетаний соединены со вторыми входами соответствующих элементов «Запрет второй группы, выходы которых соединены с соответствующими входами узла управления выбором направления и первого порогового элемента, выход которого через наборное поле соединен со вторыми входами соответствующих элементов «Запрет первой группы, выходы которых соединены с входами второго порогового элемента. Управляющие входы пороговых элементов соединены с третьим

управляющим входом устройства, а выход второго порогового элемента - со вторым входом триггера.

Блок-схема устройства приведена на чертеже.

Устройство содержит узел / перебора сочетаний, группы элементов «Запрет 2, 3, наборное поле 4, пороговые элементы 5, 6, узел 7 управления выбором направления, триггер 8, элемент И 9, генератор 10, мультивибратор //.

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

На наборном поле 4 набирается модель исходного графи.

По команде «Исходное триггер 8 устанавливается в единичное состояние, элемент И 9 закрывает выход генератора 10 и устанавливается iB исходное состояние узел 1. Пороговые элементы 5 н 6 устанавливаются соответственно на срабатывание iHO и /г единичным сигналам на их входах.

По команде «Пуск триггер 8 переводится в нулевое состояние, и импульсы с генератора 10 начинают проходить через элемент И 9. Первый импульс приводит к срабатыванию узла 1, закрывает элементы «Запрет 3 на время переходного процесса в узле / и через мультивибратор // закрывает элементы «Запрет 2 на время переходного процесса в узле / и наборном иоле 4. По заднему фронту первого импульса элементы «Запрет 3 открываются, и сигнал с выхода узла / в виде параллельного кода поступает на пороговый элемент 5 и узел 7.

Еслн параллельный код соответствует какой-либо комбинации из первого множества, то срабатывает пороговый элемент 5 и подает сигнал на любой один из узлов модели графа на наборном поле 4. Кроме того, узел S формирует сигнал и деформирует модель графа на наборном поле 4 в соответствии с испытуемой комбинацией из nepiBoro множества. Если при этом все я вершин модели графа на наборном поле 4 оказываются под напряжением, то при снятии со входов элементов «Запрет 2 сигнала с мультивибратора // они открываются, и по сигналу выхода набориого поля 4 срабатывает пороговый элемент 6. Последний переводит триггер 8 и единичное состояние, и элемент И 9 закрывает зыход генератора Ю. Схема прекращает работу, и на наборном поле 4 фиксируется со ответствующая цикломатическая комбинация ребер графа из второго множества и сигнализируется останов. По команде «Пуск триггер 8 снова переводится в нулевое состояние, н работа устройства продолжается.

По второму и следующим импульсам устройство работает аналогично. Однако если параллельный код с выхода узла 1 не соответствует комбинации из первого множества, тогда не все узлы модели графа на наборном поле 4 могут иметь проводимость между собой, и сигнал с выхода порогового элемента 5 не поступает. При этом на выходе наборного поля 4 сигнал будет нулевой, и пороговый элемент 6 при от1крытых элементах «Запрет 2 не срабатывает. Триггер 8 остается в нулевом состоянии, и работа устройства

продолжается.

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

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

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

Устройство для исследования графов, содержашее узел перебора сочеталий, узел управления выбором направления, генератор, элемент И, триггер, мультивибратор, причем

выход узла управления выбором направления соединен с первым входом наборного поля, отличающееся тем, что, с целью упрощения, в него введены две группы элементов «Запрет и два пороговых элемента; причем

первый вход устройства соединен с первым входом триггера, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора, а выход элемента PI соединен через мультивибратор с первыми входами элементов «Запрет первой группы и непосредственно с первыми входами элементов «Запрет второй группы и узла перебора сочетаний, второй вход которого соедннен со вторым входом устройства;

выходы узла перебора сочетаний соединены со вторыми входами соответствующих элементов «Запрет второй группы, выходы которых соединены с соответствующими входами узла управления выбором направления и первого порогового элемента, выход которого через наборное поле соединен со вторыми входами соответствующих элементов «Запрет первой группы, выходы которых соединены с входами второго порогового элемента; управляющие

входы пороговых элементов соединены с третьим управляющим входом устройства; выход второго порогового элемента соедииен со вторым входом триггера.

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

1.Авторское свидетельство СССР № 518872. кл. Н 04 L 1/10, 16.01.1975 г.

2.Авторское свидетельство СССР, кл. G 06 G 7/48, № 398976, 1971 г. (прототип).