Базис циклов

---

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

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

В планарных графах множество циклов ограниченных граней (то есть циклы-границы ограниченных граней — одна, внешняя, грань бесконечна) вложенного в плоскость графа образуют базис циклов. Минимальный по весу базис циклов планарного графа соответствует дереву Гомори — Ху^[англ.] двойственного графа.

Остовное дерево заданного графа ${\displaystyle G}$ имеет тот же набор вершин, что и сам ${\displaystyle G}$, но, возможно, меньше рёбер. Говорят, что граф ${\displaystyle G}$, или один из его подграфов, является эйлеровым, если каждая его вершина имеет чётную степень (то есть число инцидентных вершине рёбер). Любой простой цикл в графе является эйлеровым подграфом, но могут существовать и другие эйлеровы подграфы. Пространство циклов графа — это набор его эйлеровых подграфов. Они образуют векторное пространство над конечным полем из двух элементов. Сложение векторов соответствует симметрической разности двух или более подграфов, которая образует другой подграф, состоящий из рёбер, входящих нечётное число раз в аргументы операции симметрической разности^[1].

Базис циклов — это базис векторного пространства и каждый базисный вектор соответствует простому циклу. Базис состоит из множества циклов, которые можно комбинировать, чтобы с помощью симметрической разности получить любой эйлеров подграф и этот набор циклов является минимальным набором, обладающих указанным свойством. Любой базис циклов заданного графа имеет то же самое число элементов базиса и это число равно размерности пространства циклов. Это число называется контурным рангом или 'цикломатическим числом графа и оно равно ${\displaystyle m-n+c}$, где ${\displaystyle m}$ — число рёбер графа, ${\displaystyle n}$ — число вершин, а ${\displaystyle c}$ — число компонент связности^[2].

Изучались некоторые специальные типы базисов циклов, среди них — фундаментальные базисы циклов, слабые фундаментальные базисы циклов, разреженные (или 2-) базисы циклов и целые базисы циклов^[3].

---