Graph

Intuitively, a graph is a diagram composed of a set of points and a set of arrows, each linking two of those points. The points are called the nodes of the graph and the arrows are called the arcs of the graph.

In a more formalised way, Claude Berge defines a graph G as the datum of the (X, U) pair, where X and U respectively designate, a set of points x1, x2,…, xn called set of nodes, and a family u1, u2,…, umof elements of the Cartesian product :

X × X = (x, y) / x ∈ X, y ∈ X

The element u = (x, y) is called arc going from node x to node y.

All graphs are oriented, but it is possible to reason on not oriented arcs called edges when the problem to solve does not require any particular orientation. In this case, the concepts and properties of graphs remain valid, as it is always possible to consider the edges as two arcs oriented in opposite directions.

Nodes of networks may thus be represented by the nodes of a graph and links by the arcs.

With each graph is associated a square matrix (n × n) not necessarily symmetric. In each cell (x, y) the value 1 is indicated if an arc links x to y, and the value 0 in the converse case. This matrix is called adjacency (connectivity) matrix.

For the graphs theory the position of nodes and the shape of arcs do not matter. The only important thing is to know how nodes are linked. However, numerous applications of this theory in spatial analysis emphasise the importance of geographical coordinates associated to each of the nodes, and so doing, the importance of the distances that separate them. Hence, the position of nodes in resulting graphical representations is generally not chosen at random.

In the same way, the theory of graphs does not say anything about the nature of links represented by the arcs. At the very most, the number of arcs linking x to y may be indicated in the adjacency matrix instead of the value 1 mentioning only the possibility of a relation. Now, in spatial analysis and more generally in operational research, acquisition of numerous results requires taking into account information about the links represented by the graph.

With this end in view, it is possible to associate with each arc of the graph several specific values related to the represented phenomenon. It may be time – distance in the case of transport networks or a value characterising the importance of hierarchical relationships in the case of social networks. The corresponding graphs are called valued graphs.