СПОСОБ ОТБ1СКАНИЯ ЗАМКНУТБ1Х НЕЗАВИСИМЫХ КОНТУРОВ ГРАФА Советский патент 1970 года по МПК G06G3/10 

II

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

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

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

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

независи|мые замкнутые контуры графа выявляются сравнением направлений токов в ветвях графа от общего питания с направлениями TOiKOB в них от источника 1питания обхода контура, и.х топологии в виде наборов единичных векторов (+1, - 1, 0) передаются в нужные моменты вычислений непосредственно в ЭЦВМ.

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

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

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

Проделав эту опе|рацию на каком-либо графе сети монсно убедиться, что в результате nepei6opa всех ветвей графа при соблюдении отмеченного выше условия разорван 1ы:ми ветвями окажутся ветви антидерева графа, а псразорванные ветви составят полное дерево антидврева графа все узлы сети остаются под напряжением (в силу свойств дерева), и схема «И .выдает сигнал, а при (разрыве ветви, входящей в дерево графа, какой-либо узел сети обязательно обесточивается (в силу свойсив дерева) и схема «И сигнала не выдает, так как отсутствует сипнал на однол из ее входов. Если трисвоить разорванны.м и шаразорва1нны;м ветйя-м какие-либо метки, например «- и «+ соот ветственно, то для i-й ветви можно записать. + дерево 1 -антидерево. Таким образом, на графе можно ащтоматически выделить и запомнить «ак ветви дарева, так и его связи. В данном случае удобно запомнить связи (юетви а,нтиде)рева), так как в дальнейшем необходимо отыскивать независимые замкнутые .контуры. Как известно, каждая ветвь антидерева замыкает единственный и независимый набор ветвей, ооставлятащих замкнутый независимы,й контур. Число ветвей, состав-ляюнцих антидерево графа, соОТ1вет1ствует числу .всех независимых замкнутых контуров в данно.м прафе. Следювательно, перебор Всех связей в опре деяен ном порядке соответствует полному перебору всех независимых за1М1Кнутых графа. Любой зам-кнутый коитур, образованный наиравленными вет1вя1М1И, можио представить в удобной ДЛЯ даенОГО случая дискретной форме в виде набора единичных векторов, «сли принять для ироишольйой f-й ветви следующие обоЗНачения: / - ветвь входит в контур, и ее направление совпадет с направле нием о1б:ход.а контура, - I - то же, но направление ее противоположно направлению О1бхода кантура. О - ветвь Ее входит в рассмат1ри1ваемый контур. Отыскание независимых замкнутых контуров и выражение их топологии едиии;чными векторами производится следующим образом. Отюлючается схема «И, и освободившийся полюс источника тока подсоединяется к последн-eiMy узлу цепи, моделирующей топологии фафа. Ток раодределяется каким-либо o6ipaзом по ветвяум цейи. На1пра1вления томав в ветвях цепи запоминаются на ферритовых кольцах или триггерах. Пооче этого ггодключается схема «И, строится дерево и выявляются антид:е|ре ва. Опключает1ся схема «PI и общее питание цепи. Включается источник .питания в разрыв первой 1вет1ви антидарева. Ток распределяется только по ветвям, составляюЩИ1М соответствующий за мкнутый независимый контур, причем наиравление тока соответствует направлению 01бхода данного контура. Направление тока обхода сравнивают с запомненными ранее направлениями токов в этих ветвях от общего питания и записывают в следующем вице: совнадеиие + 1 J I противошоложно - I(3) 1 отсутсивует ток обхода - 0. Полученный набор единичных векторов можно непосредственно вводить в ЭЦВМ по его команде. На чертеже приводится б,лок-схе|Ма, осуществляющая предложенный способ обработки топологической информации, содержащая шесть функциональных блоков. Б.ЛОК велвей У по команде блока управления после довательно разрывает ветви сети, набранной на плато, включая соответствующие сигнальные лампочки на табло, блокирует и сохраняет разрыв в ветви, если со схемы «И идет сигнал, в п.ротивном случае ликвидирует разрыв, гася соответствующую лампочку на табло. В процессе перебора ветвей переключают разорванные ветви на соответствующее устройство в блоке управления для того, чтобы в дальнейшем при форашравании наборов единичных векторов включать в ветви антидерева источник тока обхода замкнутых неза1виси1мых контуров. Наборное плато 2 представляет собой .группы штеккер:ных гнезд, интерпретирующих узлы сети. При помощи проводников рабочие ячейки блока ветвей соединяются между собой пооредст1вом групп штеккерных лнезд плато в (Геометрическом порядке, идентично-м топологии расаматриваемого лрафа. Пе.рвый узел наборного плато соединен с полюсом источника питания, остальные узлы выведены на входы схемы «И. Схема совпадения 3 (схема «И) стандартная. О:ообен1ностью схемы является то, что при от1клю1чении сигнала на KaiKOiM-либо входе схемы «И в цепи этого входа до источника питания имеется разрыв. Поэтому из существующих стандартных схем совпадения в данном случае применимы лишь те, у которых цепь подвода сигнала ко входу .не является активным элементом схамы. Вследствие большого числа входов (узлов сети) схема «И должна быть сещционирована. На табло 4 визуально фиксируются номера ветвей антиде|реВа графа. По числу фиксированных HOMeipoB ветвей можно судить о исправности аналога топологии сети. M n - N 1, дде М - число связей (ветвей антидерева) п - число ветвей в графе; N - число уз.лов в гра|фе. Блок управления 5 отключает схему «П, одключает к цепи, моделирующей на наборном плато топологию графа, полюсы источника общего питания (к первому и последнему Ззлу графа), опращивает все ветви прафа и запоминает при помощи ферритовых колец или триггеров направления токов в них. При отыскании и запоминании ветвей антидерева

прафа отключает полюс источ.ника общего питания от последнего узла, подключает ко всем узлам, KpoiMe первого, схему «И и последовательно возбуждает гаабочие ячейки блока ветвей. На это.м этапе (подготовка к работе с ЭЦВМ заканчи1вается. При формировании ,Hai6opOB единичных векторов по команде ЭЦВМ включает в очередную ветвь антидерева графа источник тока Обхода очередного заМкиутого независилюго кОНтура, опрашивает ветв.и графа, сравнивает направлвния токов в них с запомненными ра.нее, формирует для каждой i-й ветви сигнала и передает полученный набор сигналов, .характерИЗуЮ|Щ.ий Hai6op еди1ничных векторов, iB соответствую.и1ее уст ро«ст1ВО ЭЦВМ.

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

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

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

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