To apply a computer to graph-theoretic
computations, it is necessary to specify the underlying graph completely and
without ambiguity. Programming system designers use specifications that are
efficient for practical computation and that can be reused in additional
applications.
Definitions:
A specification of a graph is a list of its vertices, a list of its edges, and an
unambiguous description of the incidence rule for determining the endpoints of
every edge.
An endpoint table for a graph is a tabular description of the incidence rule,
that gives the endpoints of every edge. In a digraph or partially
directed graph, the tail and head of each directed edge are distinguished, for
instance, by marking the head, or by always giving the tail first.
An incident-edge table for a graph is a tabular description of the incidence rule,
that gives for each vertex v, a list of the edges having v
as an endpoint. If the graph is directed, this
list is partitioned into two sublists, according to
whether v is tail or head.
A representation of a graph G is a graph description, such as a drawing, from which a formal
specification could be constructed and labeled with
the vertex names and edge names from G, so as to obtain a graph that conforms to the
incidence rule for G.
The incidence matrix of a graph G with vertices v1, v2, . . . , vn and edges e1, e2, . . . , em is the n ×
m matrix B(G) with

The adjacency matrix of a graph G with vertices v1, v2, . . . , vn and edges e1, e2, . . . , em is the n ×
n matrix A(G) with
= the number of edges
between vi and vj if i ≠ j.
If there are self-loops, then
is usually defined to
be the number of loops at vi.
Examples:
1. The following normalized
drawing, endpoint table, incident-edge table, incidence matrix and adjacency
matrix all specify the same graph G.

|
endpoint table e1
e2 e3 e4 e5 e6 e7 v1
v2 v2 v3
v3 v3 v1 v2
v3 v4 v4 v4 v4 |
incident-edge table v1
e1 e7 v2
e1 e2 e3 v3
e2 e4 e5 e6 v4
e3 e4 e5 e6 v5 |