Graph representation and computation

 

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