Table 7‑1 provides a number of key definitions used within the discipline of network analysis. These terms are used within the various subsections of this chapter and widely within the cited references. The terms are all derived from abstract graph theory, itself part of the broader field of pure mathematics. Much work on graph theory bears little or no relation to the kind of spatial analysis discussed in this Guide, but nevertheless many of the results within this field are essential parts of the search for efficient (fast, high quality, compact, robust) solutions to many spatial problems.

Table 7‑1 Network analysis terminology

Term |
Description |

Vertex |
A point location considered as a network node. Vertices are typically either distinct points or the end points or intersection points of lines or polylines. Note that intermediate points along a polyline are not generally vertices |

Edge |
A (directed or undirected) link between two vertices that are directly connected is called an edge. An undirected edge is determined by an unordered sequence of vertices, e.g. (3,8), which is the same as (8,3) whereas for a directed edge the order of the sequence matters, with (3,8) being from 3 to 8. An indirect link (via one or more other vertices) is not an edge. Edges are sometimes referred to as links or arcs |

Degree (of a vertex) |
In an undirected graph the number of edges meeting at a vertex. In a directed graph the degree usually refers to number of edges directed to a vertex (the indegree) minus the number of edges directed from a vertex (the outdegree) |

Graph |
A collection of vertices and edges constitutes a graph. Directed graphs are graphs that include one or more directed edges. If all edges are directed such graphs are known as digraphs. The mathematical study of the properties of graphs and paths through graphs is known as graph theory |

Path |
A (network) path is a sequence of connected edges between vertices |

Connected graph |
If at least one path exists between every vertex and every other vertex in a graph it is described as connected. A fully connected graph is one in which every vertex is directly connected to every other vertex. In such a graph, if there are n vertices there are n(n‑1)/2 edges, assuming all edges are undirected |

Connectivity |
Network connectivity is the minimum number of nodes or links that must fail in order to partition the network (or sub-network) into two or more disjoint networks. The larger the connectivity for a network the better the network is able to cope with failures. In the real world network nodes and links do fail (e.g. roads require maintenance or an accident may block a link or junction). When nodes or links fail the network should continue to function with reduced capacity. Network connectivity is a measure of the resiliency of a network and its ability to continue to support traffic flows despite such problems. |

Planar graph |
If a graph can be drawn in the plane (embedded) in such a way as to ensure edges only intersect at points that are vertices then the graph is described as planar |

Network |
A collection of vertices and edges together with associated attribute data that may be represented and analyzed using graph theoretic methods. A network is often defined as a graph that has at least one real-valued attribute or weight (e.g. length) associated with every edge |

Diameter |
The maximum number of links that must be traversed to reach any node along a shortest path. Networks with small diameters are generally faster to traverse |

Cycle |
A path from a given vertex to itself that traverses other vertices is a cycle. A graph that has no cycles is called acyclic |

Tree |
An n-vertex acyclic network or subnetwork in which every vertex is connected, for which the number of edges is n-1. A unique path exists between every pair of vertices in a tree |

The disciplines that have focused the greatest attention on applications of graph theory in a geospatial context are those of operations research and combinatorial geometry. Within both areas an enormous range of results has been obtained and these provide the building blocks for the facilities seen increasingly in GIS and related software packages.

Figure 7‑1 illustrates a number of aspects of simple networks. Each network shown is comprised of seven nodes or vertices. In this example no information is provided on the values (e.g. length, cost) to be associated with links or edges, attention being focused instead simply on connectivity. From this perspective the first two diagrams are topologically equivalent, despite their apparent different arrangement in the plane. The third network is clearly different, with a number of one-way or ‘directed’ links, and a different pattern of connectivity. In each case these networks can be represented as a square binary connectivity matrix, where direct connections between nodes are indicated by 1, otherwise entries are set to 0. The first two networks in Figure 7‑1 have identical connectivity matrices, which are symmetric, whilst the third will be different and asymmetric.