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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Cycle space''' --- пространство циклов. Given a graph <math>G</math>, let <math>e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an ordering of its …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Cycle space''' --- пространство циклов.  
'''Cycle space''' — ''[[пространство циклов]].''


Given a graph <math>G</math>, let <math>e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an
Given a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, let <math>\,e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an ordering of its [[edge|edges]]. Then a subset <math>\,S</math> of <math>\,E(G)</math> corresponds to a <math>\,(0,1)</math>-vector <math>\,(b_{1}, \ldots, b_{|E(G)|})</math> in the usual way with <math>\,b_{i}= 1</math> if <math>\,e_{i} \in S</math>, and <math>\,b_{i} = 0</math> if <math>\,e_{i} \not \in S</math>. These vectors form an <math>|E(G)|</math>-dimensional vector space, denoted by
ordering of its edges. Then a subset <math>S</math> of <math>E(G)</math> corresponds to a
<math>(Z_{2})^{|E(G)|}</math>, over the field of integers modulo <math>\,2</math>. The vectors in <math>\,(Z_{2})^{|E(G)|}</math> which correspond to the [[cycle|cycles]] in <math>\,G</math> generate a subspace called the '''cycle space''' of <math>\,G</math> denoted by <math>\,{\mathcal C}(G)</math>. It is known that
(0,1)-vector <math>(b_{1}, \ldots, b_{|E(G)|})</math> in the usual way with <math>b_{i}
= 1</math> if <math>e_{i} \in S</math>, and <math>b_{i} = 0</math> if <math>e_{i} \not \in S</math>. These vectors form an <math>|E(G)|</math>-dimensional vector space, denoted by
<math>(Z_{2})^{|E(G)|}</math>, over the field of integers modulo 2. The vectors
in <math>(Z_{2})^{|E(G)|}</math> which
correspond to the cycles in <math>G</math> generate a subspace called the '''cycle space''' of <math>G</math> denoted by <math>{\mathcal C}(G)</math>. It is known that


<math>\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r</math>


where <math>r</math> is the number of connected components.
:::<math>\,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r</math>
 
 
where <math>\,r</math> is the number of connected components.
 
==See also==
==See also==
*''Basis number''.
 
* ''Basis number''.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

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

Cycle spaceпространство циклов.

Given a graph [math]\displaystyle{ \,G }[/math], let [math]\displaystyle{ \,e_{1}, e_{2}, \ldots, e_{|E(G)|} }[/math] be an ordering of its edges. Then a subset [math]\displaystyle{ \,S }[/math] of [math]\displaystyle{ \,E(G) }[/math] corresponds to a [math]\displaystyle{ \,(0,1) }[/math]-vector [math]\displaystyle{ \,(b_{1}, \ldots, b_{|E(G)|}) }[/math] in the usual way with [math]\displaystyle{ \,b_{i}= 1 }[/math] if [math]\displaystyle{ \,e_{i} \in S }[/math], and [math]\displaystyle{ \,b_{i} = 0 }[/math] if [math]\displaystyle{ \,e_{i} \not \in S }[/math]. These vectors form an [math]\displaystyle{ |E(G)| }[/math]-dimensional vector space, denoted by [math]\displaystyle{ (Z_{2})^{|E(G)|} }[/math], over the field of integers modulo [math]\displaystyle{ \,2 }[/math]. The vectors in [math]\displaystyle{ \,(Z_{2})^{|E(G)|} }[/math] which correspond to the cycles in [math]\displaystyle{ \,G }[/math] generate a subspace called the cycle space of [math]\displaystyle{ \,G }[/math] denoted by [math]\displaystyle{ \,{\mathcal C}(G) }[/math]. It is known that


[math]\displaystyle{ \,\dim{\mathcal C}(G) = |E(G)| - |V(G)| + r }[/math]


where [math]\displaystyle{ \,r }[/math] is the number of connected components.

See also

  • Basis number.

Литература

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