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.

Текущая версия от 13:11, 22 декабря 2021

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.