Cycle matroid

Материал из WikiGrapp
Перейти к:навигация, поиск

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.