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

G:=(V,E)

be a finite undirected graph. The vertex space

\mathcal(G)

of ''G'' is the vector space over the finite field of two elements

\mathbb/2\mathbb:=\lbrace 0,1 \rbrace

of all functions

V\rightarrow \mathbb/2\mathbb

. Every element of

\mathcal(G)

naturally corresponds the subset of ''V'' which assigns a 1 to its vertices. Also every subset of ''V'' is uniquely represented in

\mathcal(G)

by its characteristic function. The edge space

\mathcal(G)

is the

\mathbb/2\mathbb

-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 are subsets of

E

, that is, as a set

\mathcal(G)

is the power set of ''E'' * vector addition is defined as the symmetric difference:

P+Q:=P \triangle Q \qquad P,Q \in \mathcal(G)

* scalar multiplication is defined by: **

0 \cdot P := \emptyset \qquad P \in \mathcal(G)

1 \cdot P := P \qquad P \in \mathcal(G)

The singleton subsets of ''E'' form a basis for

\mathcal(G)

. One can also think of

\mathcal(G)

as the power set of ''V'' made into a vector space with similar vector addition and scalar multiplication as defined for

\mathcal(G)

Properties

The incidence matrix

H

for a graph

G

defines one possible linear transformation :

H:\mathcal(G) \to \mathcal(G)

between the edge space and the

vertex space Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

G

. The incidence matrix of

G

, as a linear transformation, maps each edge to its two

incident Incident may refer to: * A property of a graph in graph theory * ''Incident'' (film), a 1948 film noir * Incident (festival), a cultural festival of The National Institute of Technology in Surathkal, Karnataka, India * Incident (Scientology), a ...

vertices. Let

vu

be the edge between

v

and

u

then :

H(vu) = v+u

The cycle space and the

cut space In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connect ...

are

linear subspace In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, li ...

s of the edge space.

References

* (the electronic 3rd edition is freely available on author's site).

Definition

Properties

References

See also