Мультиграф — граф, где между двумя заданными вершинами может быть несколько дуг. Дуги, соединяющие одну и ту же пару вершин, принято называть параллельными. Мультиграф, у которого максимальное число параллельных дуг — s, называют s-графом.
Рассмотрим неориентированный мультиграф (s-граф) G, n — вершин, m — ребёр, p — связных компонент. ρ(G) = n − p — коцикломатическое число (число ребер в остовах всех p связных компонент графа). ν(G) = m − ρ(G) = m − n + p — цикломатическое число. Если граф отождествить с электрической цепью, то определенные числа приобретают физический смысл. ν(G) — наибольшее число независимых круговых токов в электрической цепи. ρ(G) — наибольшее число независимых разностей потенциалов в электрической цепи.
Далее в этом разделе разговор будет вестись о неориентированных графах. Напомним, что циклом в неориентированном графе называется цепь, у которой совпадают начало и конец. Цикл будем называть простым, если в нем нет одинаковых вершин (кроме первой и последней). Такие циклы можно представлять как множества ребёр. Рассмотрим операцию ⊕ сложения по модулю 2 или симметрической разности над множествами ребёр:
M1 ⊕ M2 = {e | (e ∈ M1 ∧ e ∉ M2) ∨ (e ∉ M1 ∧ e ∈ M2) }.
Рассмотрим ряд вспомогательных фактов:
0M = Ø
1M = M
M ⊕ Ø = M
M ⊕ M = Ø
M называется линейной комбинацией {Mi}, если M = ⊕ αiMi, где αi ∈ {0, 1}.
Таким образом множество подмножеств ребёр графа оказывается линейным пространством над полем {0, 1}.
Множество циклов {Zi} называется независимым, если ∀i Zi не является линейной комбинацией остальных.

Максимальное независимое множество циклов (или минимальное множество циклов, от которых зависят все остальные) называется фундаментальной системой циклов. Циклы системы называют фундаментальными. В приведенном на рисунке графе циклы: Φ1 = (1100100), Φ2 = (0010011), Φ3 = (1111000) — образуют фундаментальную систему циклов (разумеется, читатель знаком с формой представления подмножеств некоторого множества в виде битовых векторов). Отметим, что не любая линейная комбинация циклов является циклом (Φ1 ⊕ Φ2 = (1110111) циклом не является).
Теорема
Рассмотрим граф G = (V, E): неориентированный, связный (p = 1) и немультиграф (s = 1). Тогда количество фундаментальных циклов в точности равно ν(G) = m − n + 1.
Доказательство. Приведем конструктивное доказательство этого факта (оно одновременно содержит алгоритм построения фундаментальной системы циклов). Рассмотрим T(V, ET) — некоторый остов графа G, который существует ввиду связности. Этому остову соответствует кодерево T*(V, ET*), где ET* = E \ ET. Отметим, что кодерево разумеется не является деревом. Каждое ребро e ∈ T* из кодерева при добавлении его к остову T очевидно порождает ровно один простой цикл Ze. Эти циклы независимы, так как каждый из них содержит свое индивидуальное ребро e.
Покажем, что любой цикл графа G зависит от {Ze}, где e пробегает все множество ребер кодерева T*. Понятно, что любой элемент фундаментальной системы зависит от неё же самой, поэтому далее будем считать, что Z ≠ Ze.
Пусть теперь некоторый цикл Z содержит ребра e1, …, ek ∈ T*. Такие ребра в Z обязательно есть, в противном случае Z ⊂ T, что невозможно, так как T — дерево. Обозначим цикл, соответствующий ребруei, как Zi. Докажем индукцией по k, что Z = Z1 ⊕ … ⊕ Zk.
База: пусть k = 1, тогда e1 ∉ T, Z \ {e1} ⊂ T и Z = Z1, так как если бы Z ≠ Z1, то концы e1 были бы соединены в T двумя цепями, что невозможно.
Пусть (индукционное предположение) Z = Z1 ⊕ … ⊕ Zm для всех циклов Z, содержащих m < k ребер из кодерева. Далее ребра кодерева будем называть хордами. Рассмотрим цикл Z c k хордамиe1, …, ek ∈ T*. Рассмотрим Zk. Имеем Z′ := (Z \ {ek}) ∪ (Zk \ {ek}) — тоже цикл (возможно, не простой). Но Z′ содержит только k − 1 хорду e1, …, ek−1. По индукционному предположению Z′ = Z1⊕ … ⊕ Zk−1. Добавим к этому циклу Zk. Имеем:
Z′ ⊕ Zk = (Z \ {ek}) ∪ ((Zk \ {ek}) ⊕ Zk) = (Z \ {ek}) ∪ {ek} = Z.
Таким образом, {Ze}, где e ∈ T*, является фундаментальной системой циклов. Поскольку все фундаментальные системы содержат одинаковое число элементов (как базисы векторного пространства), достаточно ограничиться рассмотрением любой, например, той, которая определяется остовом T. Число ребер в ней равно числу ребер в кодереве.
|ET*| = |E| − |ET| = m − (n − 1) = m − n + 1.
Алгоритм построения фундаментальной системы циклов (для графа такого, как в условии теоремы):
Построим любое остовное дерево T исходного графа G.
Добавим к T некоторое ребро e, которое является ребром графа, но не принадлежит остову.
Очевидно, что после такого добавления образуется цикл Ze.
Все циклы {Ze} (соответствующие всем ребрам, взятым не из остова) образуют фундаментальную систему циклов.
|