In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

discipline of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the edge space and vertex space of an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

are

vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...

s defined in terms of the

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

and vertex sets, respectively. These vector spaces make it possible to use techniques of

linear algebra Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathemat ...

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 In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...

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 In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...

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 In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...

of ''E'' *

vector addition Vector most often refers to: * Euclidean vector, a quantity with a magnitude and a direction * Disease vector, an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematics a ...

is defined as the

symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and ...

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

scalar multiplication In mathematics, scalar multiplication is one of the basic operations defining a vector space in linear algebra (or more generally, a module in abstract algebra). In common geometrical contexts, scalar multiplication of a real Euclidean vector ...

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 In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...

H

for a graph

G

defines one possible

linear transformation In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...

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

between the edge space and the vertex space of

G

. The incidence matrix of

G

, as a linear transformation, 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 subspaces of the edge space.

References

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

Definition

Properties

References

See also