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

 

<»i 5498IO

ОЛ ИСАНИ Е

ИЗОБРЕТЕН ИЯ

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

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

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

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 16.05.75 (21) 2134949, 24 с присоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 05.03.77. Бюллетень ¹ 9 (45) Дата опубликования описания 27.07.77 (51) М.Кл. С 06 F 15/20

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

Совета Министров СССР по делам изобретений н открытий (53) УДК 681.3 (088.8) (72) Автор изобретения (71) Заявитель

11. E. Чистяков (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ

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

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

l0

Недостатком устройства является его относительная сложность и невозможность применения для анализа комбинаций по заданным признакам.

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

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

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

Поставленная цель достигается тем, что в предложенное устройство введены две группы элементов «Запрет» и два пороговых элемента. Первый вход устройства соединен с первым входом триггера, выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора. Выход элемента И соединен через мультивибратор с первыми входами элементов

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

549810

20

ЗО

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

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

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

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

По команде «Исходное» триггер 8 устанавливается в единичное состояние, элемент

И 9 закрывает выход генератора 10 и устанавливается в исходное состояние узел 1. Пороговые элементы 5 и б устанавливаются соответствечно на срабатывание по п=1 и п еди ци!ío!ì сигналам на их входах.

По команде «Пуск» триггер 8 переводится в нулевое состояние, и импульсы с генератора 10 начинают проходить через элемент И

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

Если параллельный код соответствует какой-либо комбинации из первого множества, то срабатывает пороговый элемент 5 и подает сигнал на любой один из узлов модели графа на наборном поле 4. Кроме того, узел 8 формирует сигнал и деформирует модель графа на наборном поле 4 в соответствии с испытуемой комбинацией из первого множества.

Если при этом все и вершин модели графа на наборном поле 4 оказываются под напряжением, то при снятии со входов элементов

«Запрет» 2 сигнала с мультивибратора 11 они открываются, и по сигналу выхода наборного поля 4 срабатывает пороговый элемент б. Последний переводит триггер 8 и единичное состояние, и элемент И 9 закрывает выход генератора 10. Схема прекращает работу, и EIB наборном поле 4 фиксируется со ответствующая цикломатическая комбинаци» ребер графа из второго множества и сигнализируется останов. По команде «Пуск» триггер 8 снова переводится в нулевое состояние, и работа устройства продолжается.

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

5 не поступает. При этом на выходе наборного поля 4 сигнал будет нулевой, и пороговый элемент б цри открытых элементах «Запрет» 2 не срабатывает. Триггер 8 остается в нулевом состоянии, и работа устройства продолжается.

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

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

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

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

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

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

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

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

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

549810

Составитель П. Чистяков

Техред М. Семенов

Редактор Л. Утехина

Корректор В. Гутман

Тип. Харьк. фил. пред. «Патент»

Заказ 288/964 Изд. Мз 476 Тираж 899 Подписное

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

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