Аноним

Cycle matroid: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Cycle matroid''' --- матроид циклов. Let <math>E(G)</math> be the edge-set of a graph <math>G</math> and <math>C</math> be the set of cycles. The c…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cycle matroid''' --- матроид циклов.  
'''Cycle matroid''' — ''[[матроид циклов]].''


Let <math>E(G)</math> be the edge-set of a graph <math>G</math> and <math>C</math> be the set of
Let <math>\,E(G)</math> be the [[edge]]-set of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> and <math>\,C</math> be the set of [[cycle|cycles]]. The cycles satisfy the circuit postulates. Thus, we obtain a ''[[matroid]]'' related to the graph. We denote this matroid by <math>\,M(G)</math> and call it the '''cycle matroid''' of <math>\,G</math>. The bases of <math>\,M(G)</math> are the ''[[spanning tree|spanning trees]]''.
cycles. The cycles satisfy the circuit postulates. Thus, we obtain a
''matroid'' related to the graph. We denote this matroid by <math>M(G)</math>
and call it the '''cycle matroid''' of <math>G</math>. The bases of <math>M(G)</math> are
the ''spanning trees''.


The ''rank'' of <math>M(G)</math> is less by 1 than the
The ''[[rank of a matroid|rank]]'' of <math>\,M(G)</math> is less by <math>\,1</math> than the number of [[vertex|vertices]].
number of vertices.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.