Edge and vertex spaces explained
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.
Definition
Let
be a finite undirected graph. The
vertex space
of
G is the vector space over the
finite field of two elements
of all functions
. Every element of
naturally corresponds the subset of
V which assigns a 1 to its vertices. Also every subset of
V is uniquely represented in
by its characteristic function. 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:
, that is, as a set
is the
power set of
E
P+Q:=P\triangleQ P,Q\inl{E}(G)
0 ⋅ P:=\emptyset P\inl{E}(G)
The
singleton subsets of
E form a
basis for
.
One can also think of
as the power set of
V made into a vector space with similar vector addition and scalar multiplication as defined for
.
Properties
for a graph
defines one possible
linear transformation
between the edge space and the vertex space of
. The incidence matrix of
, as a linear transformation, maps each edge to its two
incident vertices. Let
be the edge between
and
then
The cycle space and the cut space are subspaces of the edge space.
References
- (the electronic 3rd edition is freely available on author's site).
See also
