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

Мультиграф — граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг — s, называют s-графом.

Рассмотрим неориентированный мультиграф (s-граф) G, n — вершин, m — ребёр, p — связных компонент. ρ(G) = n−p - коцикломатическое число (число ребер в остовах всех p связных компонент графа). ν(G) = m − ρ(G) = m − n + p — цикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. ν(G) — наибольшее число независимых круговых токов в электрической цепи. ρ(G) — наибольшее число независимых разностей потенциалов в электрической цепи.

Далее в этом разделе разговор будет вестись о неориентированных графах. Напомним, что циклом в неориентированном графе называется цепь, у которой совпадают начало и конец. Цикл будем называть простым, если в нем нет одинаковых вершин (кроме первой и последней). Такие циклы можно представлять как множества ребёр. Рассмотрим операцию ⊕ сложения по модулю 2 или симметрической разности над множествами ребёр:

Рассмотрим ряд вспомогательных фактов:

M называется линейной комбинацией {Mi}, если . Т.о. множество подмножеств ребёр графа оказывается линейным пространством над полем {0, 1}.

Множество циклов {Zi} называется независимым, если ∀i Zi не является линейной комбинацией остальных.

Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов.

Матрицей фундаментальных циклов графа G называется матрица Φ = [φij], состоящая из ν(G) строк и m столбцов, в которой равно 1, если ребро принадлежит циклу Φi, и равно 0 в противном случае. Предположим, что система фундаментальных циклов порождена некоторым остовом T графа G. Тогда, если ребра не принадлежащие дереву T, пронумеровать последовательно от 1 до ν(G), а ребра дерева T от ν(G) + 1 до m, то матрица циклов Φ будет иметь вид где I — единичная матрица.