- Edge space
In the
mathematical discipline ofgraph theory , the edge space and vertex space of anundirected graph arevector space s defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques oflinear algebra in studying the graph.Definition
Let G:=(V,E) be a finite undirected graph. The vertex space mathcal{V}(G) of "G" is the vector space over the
finite field of two elements mathbb{Z}/2mathbb{Z}:=lbrace 0,1 brace that is freely generated by the vertex set "V". The edge space mathcal{E}(G) is the mathbb{Z}/2mathbb{Z}-vector space freely generated by the edge set "E". The dimension of the vertex space is thus the number of vertices of the graph, while the dimension of the edge space is the number of edges.These definitions can be made more explicit. For example, we can describe the edge space as follows:
* elements of the vector space are subsets of E, that is, as a set mathcal{E}(G) is thepower set of "E"
*vector addition is defined as thesymmetric difference : P+Q:=P riangle Q qquad P,Q in mathcal{E}(G)
*scalar multiplication is defined by:
**0 cdot P := emptyset qquad P in mathcal{E}(G)
** 1 cdot P := P qquad P in mathcal{E}(G)Thesingleton subsets of "E" form a basis for mathcal{E}(G).Properties
The
incidence matrix H for a graph G defines alinear transformation :H:mathcal{E}(G) o mathcal{V}(G)between the edge space and thevertex space of G. It maps each edge to its two incident vertices. Let vu be the edge between v and u then:H(vu) = v+uThe
cycle space and thecut space arelinear subspace s of the edge space.See also
*
cycle space
*cut space
Wikimedia Foundation. 2010.