4635
правок
Cycle space: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Cycle space''' --- пространство циклов. Given a graph <math>G</math>, let <math>e_{1}, e_{2}, \ldots, e_{|E(G)|}</math> be an ordering of its …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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 | |||
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. | |||
