Cycle matroid

Cycle matroid — матроид циклов.

Let $\,E(G)$ be the edge-set of a graph $\,G$ and $\,C$ be the set of cycles. The cycles satisfy the circuit postulates. Thus, we obtain a matroid related to the graph. We denote this matroid by $\,M(G)$ and call it the cycle matroid of $\,G$. The bases of $\,M(G)$ are the spanning trees.

The rank of $\,M(G)$ is less by $\,1$ than the number of vertices.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.