Edge space
From Wikipedia, the free encyclopedia
In the mathematical discipline of graph theory, the edge space and vertex space of an undirected graph are vector spaces defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques of linear algebra in studying the graph.
[edit] Definition
Let G: = (V,E) be a finite undirected graph. The vertex space 
of G is the vector space over the finite field of two elements 
that is freely generated by the vertex set V. The edge space 
is the 
-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 is the power set of E
- vector addition is defined as the symmetric difference:
- scalar multiplication is defined by:
The singleton subsets of E form a basis for .
[edit] Properties
The incidence matrix H for a graph G defines a linear transformation
between the edge space and the vertex 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 + u
The cycle space and the cut space are linear subspaces of the edge space.
