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

286354 ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических РеспубликЗависимое от авт. свидетельства М Кл, 42 тп 4, ЗУО 326213/18-24) Заявлено 28.Ъ".1969с присоединением заПриоритет иХ 1 ПК Ст 06 о 3 1 Комитет по делам зобретеннй и открытийАвторыизобретения емер и Э, М, БуКазахской ССР ой, Г. К. Рязанцев, О, Институт горного дел аявитель ПОСОБ ОТЫСКАНИЯ ЗАМКНУТЪХ НЕЗАВИСИМЫХ КОНТУРОВ ГРАФАПредложение относится к вычислительной технике, а именно к расчету сложных, распределительных сетей на ЭЦВМ, и может быть использовано на вычислительных центрах, а также при создании автоматической системы управления сложными раопределительными сетями (вентиляционными, гидравлическими, газовыми, и т, п.).Известен способ для ,поиска продеревьев направленного графа, при котором используются последовательные разры 1 вы в ветвях, моделирующих граф с применением логической схемы соьпадения для анализа,потенциалов на вершинах трафа,Недостаток известнопо способа поиска продерева направленного графа заключается в том, что он позволяет механизировать лишь операцию поиска,дерева, Отыскание же замкнутых независимых контуроев графа на базе выявленного дерева необходимо производить вручную прежними методами, кодировать их топологию осуществляющими способами и в виде цифровых массивов или матриц по-прежнему вводить в ЗУ ЭЦВМ,Цель изобретения состоит в полной автоматизации процесса поиска независимых замкнутых контуров и передачи их топологии в ЭЦВМ в нлкные моменты и освобождения ЗУ ЭЦВМ от топологической информации,Предложенный способ отличается тем, что пезависимые замкнутые контуры графа выявляются сравненивм направлений токов в ветвях графа от общего питания с направлениями токов в них от источника питания обхода контура, их топологии в виде наборов единичных нектороев (+1, - 1, О) передаются в нужные моменты вычислений непосредственно в ЭЦВМ.Из электрических проводников произволь ного сопротивления собирается цепь, топология котстрой идентична топологии рассматриваемого графа. К однохту узлу цепи подк;по- чается, полюс источника питания, остальныс узлы коммутируются на входы логической 15 схемы И, к которой подключается второйполюс источника питания. Ветви цепи,разрываются в произвольном порядке при следующем условии: если после разрыва очередной ВЕТВИ СХЕМа И,ВЫдаЕт СнегНа, тО раЗрЫВ 20 ветви сохраняется до конца перебора, еслисигнала со схемы И нет, то разрыв этой ветви ликвидируется, и ветвь сохраняется до конца петр ебор а.Проделав эту операцию на каком-либо гра фе сети можно убедиться, что в результатсперебора всех ветвей графа прп соблюдении отьмеченнопо,выше условия разорванными ветвями окажутся ветви антидерева графа, а псразорванные ветви составят полное дерево 30 данного графа, поокольку при разрыве ветви55 60 65 антидерева графа все узлы сети остаются под напряжением (в силу свойств дерева), и схема И .выдает сигнал, а при разрыве ветви, входящей в дерево графа, какой-либо узел сети обязательно обесточивается (з силу свойств дерева) и схема И сигнала не выдает, так как отсутствует сипал на одном из ее входов.Если присвоить разорванным и неразорванным ветвям какие-либо метки, например-и + соответственно, то для 1-й ветви можно записать.+ дерево- антидерево,Таким образом, на графе можно автоматически выделить и запомнить как ветви дерева, так и его связи. В данном случае удобно запоынить связи (ветви антидерева), так как в дальнейшем необходимо отыскивать независимые замкнутые, контуры,Как известно, каждая ветвь антидерева замыкает единственный и независимый набор ветвей, составляющих замкнутый независимый контур.Число ветвей, составляющих антидерево графа, соответствует числу всех независимых замкнутых контуров в данном прафе, Следовательно, перебор всех связей в определенном порядке соответствует полному перебору всех независимых замкнутых контуров графа.Любой замкнутый контур, образованный наоравленными ветвями, можно представить в удобной .для данного случая дискретной форме в виде набора единичных векторов, если принять для проиэвольной -й ветви следующие обозначенная:1 - ветвь входит в контур, и ее направление совпадет с направлением обхода контура,- 1 - то же, ио направление ее противоположно направлению обхода ксннту р а. О - ветвь не входит в рассматриваемый контур.Отыскание независимых замкнутых контуров и выражение их топологии единичными векторами производится следующим образом.Отключается схема И, и освободившийся полюс источника тока подсоединяется к последнему узлу цепи, моделирующей топологии графа. Ток распределяется какиы-либа об 1 разом по ветвям цепи. Направления тоиов в ветвях цепи запоминаются на ферритовых кольцах или триггерах. После этого подключается схема И, строиться дерево и выявляются ветви антидерева, Отключается схема И и общее питание цепи. Включается источник питания в разрыв первой ветви антидорева, Ток распределяется только по ветвям, составляющим соответствующий замкнутый независимый контур, причем направление тока соответствует направлению обхода данного контура. Направление тока обхода сравнивают с запомненными ранее направлениями токов в 10 15 20 25 30 35 40 45 50 этих ветвях от общего питания и записываю в сл еду ющем в иде:совпадение + 1с =иротивоположно - 1отсутствует ток обхода - О.Полученный набор единичных векторов можно непосредственно вводить в ЭЦВМ по его команде.На чертеже приводится блок-схема, осуществляющая предложенный способ обработки топологической инфорыации, содержащая шесть функциональных блоков.Блок вепвей 1 по команде блока управления последовательно разрьпвает ветвями сети, набранной на плато, включая соответствующие сигнальные лам(почки на табло, блокирует и сохраняет разрыв в ветви, если со схемы И идет сигнал, в противном случае ликвидирует разрыв, гася соответствующую лампочку на табло. В процессе перебора ветвей переключают разорванные ветви на соответствующее устройство в блоке управления для того, чтобы в дальнейшем при формировании наборов единичных векторов включать в ветви антидерева источник тока обхода замкнутых не заяви симы х контуров.Наборпсе плато 2 представляет собой группы штеккерных гнезд, ингерпретирующих узлы сети. При помощи проводников рабочие ячейки блока ветвей соединяются между собой посредспвом групп штеккерных гнезд плато в геометрическом порядке, идентичном топологии рассматриваемого прафа, Первый узел наборного плато соединен с полюсом ис. точника питания, остальные узлы выведены на входы схемы И.Схема совпадения 3 (схема И) стандартная. Особеиностью схемы является то, что ири отключении сигнала на катком-либо входе схемы И в цепи этого входа до источника литания имеется разрыв. Поэтому из сущестьующих стандартных схем совпадения в дапчом случае применимы лишь те, у которых цепь подвода сигнала ко входу не является активным элементом схемы, Вследствие большого числа входов (узлов сети) схема И долина быть сеиционирована.На табло 4,визуально фиксируются номера ветвей антидерева графа. По числу фиксированных номеров ветвей можно судить о исправности аналога топологии сети.М=а - 1 Ч+1,пде М - число связей (ветвей антидерева)пр афа;п - число .ветвей в,гр а фе;Л - число узлов в графе.Блок управления Б огключает схему И, подключает к цепи, моделирующей на наборном плато топологию графа, полюсы источника общего питания (к первому и последнему узлу графа), опрашивает все ветви графа и запоминает при помощи ферритовых колсц или трипгеров направления токов:в них. При отыскании и запоминании ветвей антидереваЗаказ 3861/3 Тираж 480 Подписное1 ХНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, уК, Раушская иаб., д. 4/5 Типография, пр. Сапупова, 2 графа отключает полюс источника общего питания от последнего узла, подключает ко всем узлам, кроме первого, схему И и последовательно возбуждает рабочие ячейки блока ветвей. На этом этапе подготовка к раооте с ЭЦВМ заканчивается. При формировании наборов единичных векторов по команде ЭЦВМ включает в очередную ветвь антиде,рева графа источник тока обхода очередного замкнутого независимого контура, опрашивает ветви графа, сравнивает направления токов в них с запомненньви ранее, формирует для каждой г-й ветви сигнала и передает полученный набор сигналов, характеризующий набор единичных векторовв соответотвуюгцее устройспво ЭЦВМ.Блок питания б обеспечивает необходимые режимы питания функциональных блоков. П редмет изобретенияСпособ отыскания замкнутых независимых контуров г 1 рафа, состоящий из процесса отыскания и запоминания ветвей антидерева графа посредством последовательных разрызов ь ветвях электрической цепи, моделирукзщей топологию графа, с анализом потенциалов узлов графа логической схемой совпадения, от,гичаюи 1 ийся тем, что, с целью упротцення ,процесса,поска и освобождения оперативноЙ памяти вычислительной машины от топологической информации, отключают логическу 1 о схему совпадения, и к последнему узлу цепи, моделируюшей топологию графа, подсоединяют источник тока, направления токов в ветвях запоминают, затем подключают схему совпадения, строят дерево и выявляют ветви антидерева. после чего отключают схему совпадения и общее питание цепи, затем включают источник питания в разрыв первой вепвн антидерева и сравнивают направление тока обхода с запомненными ранее направлениями токов в этих ветвях от общего питания, формируют топологно независимых замкчутых контуров в виде дискретных сигналов,