Фундаментальная система циклов

По этой ссылке вы найдёте полный курс лекций по математике:

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

Например, в полном графе Кп можно указать различных циклов8) длины к (к = 3 представляющих собой простые замкнутые цепи, а общее количество таких циклов имеет порядок (п - 1)!. Поэтому задача выражения всех циклов графа через некоторые фиксированные циклы достаточно интересна; о практическом приложении решения такой задачи будет упомянуто в конце параграфа. Поговорим сначала об операции, позволяющей по одним циклам получать другие. I 9.1.

Симметрическая разность множеств Симметрической разностью множеств А и В называют множество Фундаментальная система циклов Операция нахождения симметрической разности коммутативна: А Д В = В Д А (это очевидно) и ассоциативна: (попробуйте доказать это с помощью рис. 22). В силу ассоциативности при записи симметрической разности нескольких множеств скобки (указывающие порядок выполнения данной операции над множествами) можно не расставлять. А АВ Рис. 22.

Симметрическая разность двух и трех множеств Пусть А — произвольное множество. Множество всех подмножеств А с операцией симметрической разности (/3(Л), Д) образует коммутативную группу; в роли нейтрального элемента группы выступает пустое множество, каждый элемент группы является обратным самому себе. Лемма 3. При произвольном натуральном п симметрическая разность п множеств состоит в точности из тех элементов данных множеств, которые принадлежат нечетному их числу.

Доказательство проводится индукцией по числу множеств. База индукция очевидна. Индукционный шаг. Пусть доказываемое утверждение справедливо для всех п ^ к. Симметрическая разность к + 1 множеств имеет вид причем p,q ^ к, p + q = k+1. Множество В состоит из элементов, принадлежащих В\ (значит, по индуктивному предположению, принадлежащих нечетному числу множеств из) и не принадлежащих Bi (то есть входящих в четное число множеств из или, наоборот, не принадлежащие В\ и принадлежат** В2 (т. е. принадлежащих четному числу множеств из А\,...,АР и нечетному числу множеств из Ар+1,... yAp+q).

Возможно вам будут полезны данные страницы:

В любом случае множество В составляют те и только те элементы, которые входят в нечетное число множеств из данных к + 1 множеств: АAk+]. Лемма доказана. . Псевдоциклы Симметрическая разность двух циклов в графе в общем случае не является циклом. Множество ребер С С Е графа G = (V, Е) назовем псевдоциклом, если в графе (V, С) кажд ая вершина имеет четную степень. (Обычный) цшел графа и пустое множество — примеры псевдоциклов.

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

Лемма 4. Для любого натурального п сиюлетринеская разность п псевдоциклов есть псевдоцикл. м Доказательство ведется индукцией по п. База индукции (утверждение для п = 1) очевидна. Обоснование индукционного шага сводится к рассмотрению случая двух псевдоциклов. Пусть С\ и — псевдоциклы. Для произвольной вершины v графа обозначим через S,(tj) множество ребер цикла С,, инцидентных v (t = 1,2). Степени вершины v в графах ) равны мощностям множеств S\(v), соответственно.

Из определения симметрической разности и с помощью формулы мощности объединения двух множеств получаем: Из четности | вытекает четность Лемма доказана. Обсудив некоторые «технические» моменты, мы можем теперь заняться основным вопросом данного параграфа. Фундаментальная система циклов Пусть G = (V, Е) — связный граф, (— его стягивающее дерево. Если граф G содержит п вершин, то в Г — п - 1 ребер. Если к стягивающему дереву Рис.23. Фундаментальная система циклов добавить произвольное ребро е € Е \ Т, то (по теореме 12) образуется ровно один цикл, обозначим его Се.

Множество всех циклов такого вида {Се \ е е Е \ Г} будем называть фундаментмьной системой циклов графа G = (V, Е) относительно стягивающего дерева (V,T). Пример см. на рис.23. Теорема 14. Произвольный цикл С связного графа G = (V,E) представим в виде симметрической разности некоторых циклов из фундаментальной системы циклов G относительно любого стягивающего дерева (V, Т). Такое представление единственно и имеет вид: Мы докажем даже более сильное угверждение, считая С псевдоциклом. Пусть — связный граф, (V, Т) — некоторое фиксированное стягивающее дерево G. Ребра этого дерева будем называть ветвями, а остальные ребра графа G — хордами.

Заметим, что каждый цикл Се содержит ровно одну хорду, а именно — е. Поэтому в симметрической разности (различных) фундаментальных циклов, равной С, должны присутствовать все циклы, отвечающие хордам из С\Г, и только они. Таним образом, если представление псевдоцикла С в виде симметрической разности фундаментальных циклов существует, то оно единственно и имеет вид (1). Докажем теперь, что равенство (1) действительно имеет место.

Пусть По лемме 4 В — псевдоцикл; как уже показано, из хорд В содержит только хорды, принадлежащие С. Применяя леммы 3 и 4, получаем, что симметрическая разность ВАС — псевдоцикл, не содержащий хорд (так как каждая хорда одновременно либо принадлежит, либо не принадлежит В и С, т. е. число се вхождений в данные два множества четно); стало быть, В АС СТ. Осталось доказать, что в В Л С нет и ветвей.

не пуст, то согласно следствию 4 теоремы 9 он имеет не менее двух висячих вершин, в то же время — по определению псевдоцикла — он не содержит висячих вершин. Итак, мы выяснили: 2? Д С = 0, что равносильно совпадению множеств В = Д Се и С. Теорема доказана. На множестве всех псевдоциклов связного графа можно ввести структуру линейного пространства над полем GF{2), где в роли «сложения» выступает симметрическая разность, а умножение на скаляр определяется естественным образом — для произвольного псевдоцикла С имеем:

С - 0 = 0 (здесь через 0 и 1 обозначены элементы поля GF{2); напомним, что в этом поле . Как показано выше, базисом в данном линейном пространстве будет фундаментальная система циклов относительно любого стягивающего дерева. Выделение фундаментальной системы циклов находит применение при анализе электрических цепей.

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

Возможно эта страница вам будет полезна:

• Статические моменты площади сечения