Графы электрических цепей

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

Опр Сопоставим каждому циклу -ку целых чисел

, где есть число прохо- дов -го ребра

при обходе цикла , совпадающих с ориентацией ребра, - число проходов -го

ребра с ориентацией, противопо- ложной заданной ориентации ребра. Вектор

называется вектор-циклом, соответствующим циклу .

Пример В предыдущем орграфе выберем несколько циклов и построим их вектор-циклы. , ,

.

ЗАМЕЧАНИЕ 1) тогда и только тогда, когда приобходе цикла каждое ребро или вообще не проходится или число его при обходов в прямом и противоположном направлениях совпадают.

2) Для любого цикла (в выше указанном смысле) на дереве .

3) . 4) . 5).

Опр Цикл называется линейной комбинацией циклов, если

.

Опр Последовательность циклов называется линейно независимой, если линейно независимы вектор-циклынад полем (или, что все равно, над кольцом ).

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

Пример В орграфе из предыдущего примера с параметрами мы построили остовное дерево .

Теперь выделим простые циклы, одна дуга в которых не входит в остовное дерево: , ,

Матрица, составленная из координат, имеет

вид .

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