Cycle matroid: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''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…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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.