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

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

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

M₁ ⊕ M₂ = {e | (e ∈ M₁ ∧ e ∉ M₂) ∨ (e ∉ M₁ ∧ e ∈ M₂) }.

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

0M = Ø

1M = M

M ⊕ Ø = M

M ⊕ M = Ø

M называется линейной комбинацией {M_i}, если M = ⊕ α_iM_i, где α_i ∈ {0, 1}.

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

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

Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы системы называют фундаментальными. В приведенном на рисунке графе циклы: Φ₁ = (1100100), Φ₂ = (0010011), Φ₃ = (1111000) — образуют фундаментальную систему циклов (разумеется, читатель знаком с формой представления подмножеств некоторого множества в виде битовых векторов). Отметим, что не любая линейная комбинация циклов является циклом (Φ₁ ⊕ Φ₂ = (1110111) циклом не является).

Теорема

Рассмотрим граф G = (V, E): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных циклов в точности равно ν(G) = m − n + 1.

Доказательство. Приведем конструктивное доказательство этого факта (оно одновременно содержит алгоритм построения фундаментальной системы циклов). Рассмотрим T(V, E_T) — некоторый остов графа G, который существует ввиду связности. Этому остову соответствует кодерево T*(V, E_T*), где E_T* = E \ E_T. Отметим, что кодерево разумеется не является деревом. Каждое ребро e ∈ T* из кодерева при добавлении его к остову T очевидно порождает ровно один простой цикл Z_e. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро e.

Покажем, что любой цикл графа G зависит от {Z_e}, где e пробегает все множество ребер кодерева T*. Понятно, что любой элемент фундаментальной системы зависит от неё же самой, поэтому далее будем считать, что Z ≠ Z_e.

Пусть теперь некоторый цикл Z содержит ребра e₁, …, e_k ∈ T*. Такие ребра в Z обязательно есть, в противном случае Z ⊂ T, что невозможно, так как T — дерево. Обозначим цикл, соответствующий ребруe_i, как Z_i. Докажем индукцией по k, что Z = Z₁ ⊕ … ⊕ Z_k.

База: пусть k = 1, тогда e₁ ∉ T, Z \ {e₁} ⊂ T и Z = Z₁, так как если бы Z ≠ Z₁, то концы e₁ были бы соединены в T двумя цепями, что невозможно.

Пусть (индукционное предположение) Z = Z₁ ⊕ … ⊕ Z_m для всех циклов Z, содержащих m < k ребер из кодерева. Далее ребра кодерева будем называть хордами. Рассмотрим цикл Z c k хордамиe₁, …, e_k ∈ T*. Рассмотрим Z_k. Имеем Z′ := (Z \ {e_k}) ∪ (Z_k \ {e_k}) — тоже цикл (возможно, не простой). Но Z′ содержит только k − 1 хорду e₁, …, e_k−1. По индукционному предположению Z′ = Z₁⊕ … ⊕ Z_k−1. Добавим к этому циклу Z_k. Имеем:

Z′ ⊕ Z_k = (Z \ {e_k}) ∪ ((Z_k \ {e_k}) ⊕ Z_k) = (Z \ {e_k}) ∪ {e_k} = Z.

Таким образом, {Z_e}, где e ∈ T*, является фундаментальной системой циклов. Поскольку все фундаментальные системы содержат одинаковое число элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом T. Число ребер в ней равно числу ребер в кодереве.

|E_T*| = |E| − |E_T| = m − (n − 1) = m − n + 1.

Алгоритм построения фундаментальной системы циклов (для графа такого, как в условии теоремы):

Построим любое остовное дерево T исходного графа G.

Добавим к T некоторое ребро e, которое является ребром графа, но не принадлежит остову.

Очевидно, что после такого добавления образуется цикл Z_e.

Все циклы {Z_e} (соответствующие всем ребрам, взятым не из остова) образуют фундаментальную систему циклов.