Cycle matroid

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

Let [math]\displaystyle{ \,E(G) }[/math] be the edge-set of a graph [math]\displaystyle{ \,G }[/math] and [math]\displaystyle{ \,C }[/math] 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 [math]\displaystyle{ \,M(G) }[/math] and call it the cycle matroid of [math]\displaystyle{ \,G }[/math]. The bases of [math]\displaystyle{ \,M(G) }[/math] are the spanning trees.

The rank of [math]\displaystyle{ \,M(G) }[/math] is less by [math]\displaystyle{ \,1 }[/math] than the number of vertices.

Литература

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