Способ отб1скания замкнутб1х независимых контуров графа

Ш Я N ГЗ 4l 11 иатентно-технически библиотека МБМ

286354

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

Зависимое от авт. свидетельства М

Кл. 42тп, 3/10

Заявлено 28.IV.1969 (Ko 1326213/18-24) с присоединением заявки ЛЪ

МПК 6 06g 3/10

УДК 681.333 (088.8) Приоритет

Опубликовано 10.XI,1970. Бюллетень М 34

Дата опубликования описания 12.1.1971

Комитет па делам изобретений и открытий при Совете Министров

СССР

Авторы изобретения

С. Цой, Г. К. Рязанцев, О. Г. Кремер и Э, М. Бутин

Институт горного дела АН Казахской ССР

Заявитель

СПОСОБ ОТЫСКАНИЯ ЗАМКНУТЪ|Х НЕЗАВИСИМЫХ

КОНТУРОВ ГРАФА

Предложение относится к вычислительной технике, а именно к расчету сложных, распределительных сетей на ЭЦВМ, и может быть использовано на вычислительных центрах, а также при создании автоматической системы у правления сложными раппределительнымн сетями (вентиляционными, гидравлическими, газовыми, и т. п.).

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

Недостаток известнопо с пособа поиска продерева на правленного графа заключается в том, что он позволяет механизировать лишь операцию поиска, дерева, Отыскание же замкнутых независимых конту|роев графа на базе выя влен ого дерева необходимо производить вручную прежними методами, кодировать их топологию осуществляющими способами и в виде ци фровых массивов или матриц по-прежнему вводить в ЗУ ЭЦВМ.

Цель изобретения состоит в полной автоматиза ции процесса поиска неза висимых замкнутых контуров и передачи их топологии в ЭЦВМ в нужные моменты и освобождения

ЗУ ЭЦВМ от топологической информации.

Предложенный с пособ отличается тем, ITo независимые замкнутые конту ры графа выявляются сраBíåíèâì направлений токов в ветвях графа от общего питания с направлениями токов в них от источника питания обхода контура, их топологии в виде наборов единичных векторо в (+ 1, — 1, О) передаются в нужные моменты вычислений непосредственно в ЭЦВМ.

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

15 схемы «И», к которой подключается второй .полюс источника питания. Ветви цепи,разрываются в произвольном порядке при следующем условии: если после разрыва очередной ветви схема «И»,выдает сигнал, то разрыв

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

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

30 данного графа, поскольку при разрыве ветви

286354

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

Если присвоить разорванным и неразорBaiHHbIм ветвям какие-либо мет ки, например

« — » и «+» соответственно, то для 1-й ветви можно записать.

+ дерево — антидерево.

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

Как известно, каждая ветвь антидерева замыкает единственный и неза!висимый набор ветвей, составляющих замкнутый независимый контур.

Число ветвей, составляющих антидерево графа, сооъвет|ствует числу .всех независимых замкяутых контуров в данном lIpalge. Следовательно, перебор всех связей в о пределенном порядке соответствует полному перебору всех независимых за м кнутых контуlpoB .графа.

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

1 — ветвь входит в контур, и ее направление совпадет с на правле нием о б:хода контура, — 1 — то же, но направление ее против= воположно на правлению обхода контура.

Π— ветвь не входит в рассматри ваемый контур.

Отыскание независимых замкнутых контуploIB и выражение их то пологии единичными векторами производится следующим образом.

Отключается схема «И», и освободившийся полюс источника тока подсоединяется к последнему узлу цепи, моделирующей TQIIIoJIогии графа. Ток распределяется какиы-ли ба об1разом по ветвям цепи. Направления тоиов в ветвях цепи запоминаются на ферритовых кольцах или триггерах. После этого подключается схема «И», строиться дерево и выявляются ветви антид рева. Отключается схема «И» и общее питание цепи. Включается источник питания в разрыв первой ветви а нтидерева, Ток распределяется только по ветвям, составляющим соответствующий замкнутый неза висимый контур, причем на правле ние тока соответствует направлению о|бхода данного контура. Направление тока обхода сравнивают с запомненными ранее направлениями токов в

50 этих ветвях от oбшего питания и записыва|о в сл еду ющем в и де: совпадение -+ 1 и!ротиво положно — 1

< отсутствует ток обхода — О.

Полученный набор единичных векторов можно непосредственно вводить в ЭЦВМ по его команде.

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

Блок вепвей 1 по команде блока управления последовательно разрьпвает ветвями сети, набранной на плато, включая соответствующие сигнальные лам(почки на табло, блски рует и сохраняет разрыв в ветви, если со схемы

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

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

Схема сов падеHHH 3 (схема «И») стандартная. Осо беиностью схемы является то, что при от ключении сигнала на каком-либо входе схемы «И» в цепи этого входа до источника литания имеется разрыв. Поэтому из сущестьую щих стандартных схем соападе ния в дапчом случае применимы лишь те, у которых цепь подвода сигнала ко входу не является активным элементом схемы. Вследствие большого числа входов (узлов сети) схема «И» долвсна быть секционирована.

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

hf =n — N+1, пде М вЂ” число связей (ветвей антидерева)

rp а фа; и — число BeTIBeH в,графе;

Л вЂ” число узлов в гра фе.

Блок управления 5 о гключает схему «И», подключает к цепи, моделирующей на наборном плато топологию графа, полюсы источни ка об щего питания (к первому и последнему узлу графа), опрашивает все ветви графа и запоминает при помощи феррито вых колсц или IpHIIIIepoB напра|вления токо в:в них. При отыскании и за поминании ветвей антидерева

286 354

6 э ам

Составитель И. Н, Горелова

Редактор Л. А. Утехина Техред 3. H. Тараненко Корректор H. Л. Бронская

Заказ 3861/3 Тираж 480 Г1одписпое

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

Москва, jK-35, Раушская иаб., д. 4г5

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

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

Блок питания б обес печи вает необходимые режимы питания функциональных блоков.

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

Способ отыскания за мкнутых независимы.; контуров г1рафа, состоящий из процесса отыскания и запоминания ветвей антидерева графа посредством последовательных разрызов ь вет вях электрической цепи, моделирукзшей топологию графа, с анализом потенциа 108 узлов графа логической с: емой совпадения, oT,гичающийся тем, что, с целью упрогцения .п роцесса,поиска H ос вобождения оперативноЙ памяти вычислительной машины от топологической информации, отключают логическу10 схему совпадения, и к последнему узлу цепи, моделируюшей топологию графа, подсоединяют источник тока, направления токов в ветвях запоминают. затем подключают схему совпадения, строят дерево и выявляют ветви антидерева. после чего отключают схему совпадения и общее питание цепи, затем включают источник питания в разрыв первой вепви антидерева и сра,внивают направление тока обхода с запомненными ранее направлениями токов в этих ветвях от общего питания, формируют топологн|о независимых замкчутых контуров в виде дискретных сигналов.