A road network, friends on a social network, the dependencies between the packages of a software project, the links between web pages: very different objects, yet they share the same structure. There are things and relationships between pairs of things. Mathematics calls this structure a graph, and a huge part of practical computer science consists of spotting a graph inside a problem that at first glance looks like something else entirely.
The essential definition
A graph G is a pair (V, E):
- V is the set of vertices (or nodes): cities, people, files;
- E is the set of edges: each edge connects two vertices.
If the cities are Milan, Bologna and Florence and there are roads Milan–Bologna and Bologna–Florence, then V = {Milan, Bologna, Florence} and E = {{Milan, Bologna}, {Bologna, Florence}}. Nothing more: the graph knows nothing about coordinates, road lengths or scenery. It only knows who is connected to whom. Everything else, if needed, is added as extra information.
The number of vertices is usually written n and the number of edges m. These two quantities appear in every cost estimate for graph algorithms.
Degree, neighbours and paths
Two vertices joined by an edge are called adjacent, or neighbours. The degree of a vertex is the number of edges touching it. In the example, Bologna has degree 2, Milan and Florence degree 1.
A simple but very useful fact: the sum of the degrees of all vertices equals twice the number of edges, because each edge is counted once for each of its two endpoints. It follows that the number of vertices with odd degree is always even. This is a quick check for data errors: if an undirected network contains an odd number of nodes with odd degree, something went wrong while loading it.
A path is a sequence of vertices in which each consecutive pair is joined by an edge. A cycle is a path that returns to its starting point without repeating edges. A graph is connected if there is a path between every pair of vertices.
The graph types you will meet most often
Directed and undirected
In an undirected graph the edge {A, B} works both ways: if Anna is friends with Bruno, Bruno is friends with Anna. In a directed graph (or digraph) edges have a direction: (A, B) goes from A to B and not the other way round. «Follows» on a social network, «imports» between software modules and «links to» between web pages are directed relationships. In digraphs we distinguish in-degree and out-degree.
Weighted
Often each edge carries a number: the length of a road, a travel time, the cost of a link, the capacity of a pipe. We then speak of a weighted graph. Most optimisation problems on graphs, such as the shortest path or the minimum-cost spanning tree, only make sense with weights.
Simple graphs and multigraphs
A simple graph has no multiple edges between the same pair of vertices and no loops (edges from a vertex to itself). A multigraph allows them: two separate railway lines between the same two stations are a natural example.
Trees, DAGs and bipartite graphs
- A tree is a connected graph with no cycles; with n vertices it has exactly n − 1 edges. The folders of a file system are the classic example.
- A DAG (directed acyclic graph) is a digraph with no directed cycles. Build dependencies and spreadsheets with formulas must form a DAG, otherwise there is a circular reference.
- A bipartite graph has its vertices split into two groups, with edges only between different groups: workers and shifts, students and courses, users and purchased products.
Dense and sparse graphs
A simple undirected graph with n vertices can have at most n(n − 1)/2 edges. When m is close to this maximum the graph is dense; when m is of the same order as n the graph is sparse. Almost all real graphs are sparse: a person knows a few hundred other people, not billions; a road junction usually has three or four roads, not thousands. This observation drives the choice of how to store the graph in memory and which algorithm to use.
Recognising a graph in a problem
In my work the most useful step is often the first one: translating the problem. A few examples:
| Problem | Vertices | Edges |
|---|---|---|
| Package installation order | Packages | «A requires B» (directed) |
| Exam timetable without clashes | Exams | «share students» |
| Satellite navigator | Junctions | Road segments (weighted) |
| Analysing an intrusion in logs | Hosts and accounts | Observed connections and logins |
Once the translation is done, decades of well-studied algorithms become available, instead of inventing an ad hoc solution.
In short
- A graph is made of vertices and edges; it only describes who is connected to whom.
- Degree, path, cycle and connectivity are the basic concepts on which everything else is built.
- Directed, weighted, bipartite, tree and DAG are the most frequent variants in real problems.
- Most real graphs are sparse, and this shapes both representation and algorithms.
- Recognising the graph hidden in a problem is often half the solution.
