Introduction

A graph is an abstraction representing some objects and connections between pairs of objects. In its simplest form, a graph has just two pieces:

• A set of vertices $V$, representing the objects we are interested in. These could represent, for instance, people, physical locations, webpages, or even other graphs.
• A set of edges $E$, consisting of pairs of the form $(v_i, v_j)$, representing a connection between vertices. These could represent, for instance, relationships between people, roads between physical locations, links between webpages, or isomorphisms between graphs.

More generally, a graph contains information about what pairs of objects are related to each other in some way.

Let us first define some terminology that will make talking about graphs less cumbersome. If $G$ has an edge $e = (u, v)$, we say $u$ and $v$ are adjacent. We also say $u$ is a neighbor of $v$ and $v$ is a neighbor of $u$. The edge $e$ is also referred to as being incident on $u$ (and $v$, as well).

The degree of a node $v$ (denoted $\text{deg}(v)$) is the number of other nodes adjacent to it, or in other words, the number of neighbors it has. Equivalently, $\text{deg}(v)$ is the number of edges incident on $v$.

We define a path as a sequence of nodes such that any two adjacent nodes in the sequence are adjacent in $G$. Two nodes $u$ and $v$ are then reachable from each other if there is a path that starts at $u$ and ends at $v$ (or vice versa).

As with most sufficiently complex mathematical notions, there is an infinite black hole of graph theory terminology, much of which we will see in the future. For now, however, these terms are sufficient for making basic claims about graphs. The following is one of the most important facts about graphs, especially for the purpose of runtime analysis.

The Handshaking Lemma. For any graph $G$, the sum of the degrees of every node is twice the number of edges. That is,

Intuition. It is more useful to consider the edge-incidence definition of degree here. First, observe that every edge is incident on exactly two vertices. Thus, in our sum of degrees, any given edge contributes to exactly two $\text{deg}(v)$ terms by 1. Therefore, we would expect this sum to be equal to twice the number of edges.

Proof. We can formalize this intuitive idea.

Representations

We have discussed the mathematical idea of a graph, but it remains to define the abstract data type for use in our code:

There are two common ways of implementing this data type.

Adjacency List

The most common way of representing a graph is by associating each vertex with a list of its neighbors, as shown in Figure 2.

Adjacency Matrix

One way to interpret a graph is that it is simply a binary relation on the vertices – that is, any two vertices are either adjacent or they aren’t adjacent. This leads to a natural programmatic representation – for every pair of vertices, keep track of whether they are adjacent or not. We can use any data type that acts as a two-place boolean predicate, but the most obvious choice is a two dimensional array. True to the relation interpretation, we could use a two-dimensional boolean array, but for reasons that will make sense later, it is more typical to use an integer array and store a $1$ for adjacency and $0$ for non-adjacency. This array is known as an adjacency matrix.

Adjacency matrices perform one operation very quickly: to detect whether two vertices are connected by an edge, we can simply test whether the adjacency matrix has a 1 in the corresponding position. This can be done with (approximately) two pointer deferences, so this operation takes $\Theta(1)$ time.

Unfortunately, unlike the case of the adjacency list, we can no longer quickly find neighbors. The adjacency matrix in Figure 3 demonstrates this. For a vertex $v_i$, we have no choice but to search the entire $i$-th row (or column) and check which entries have value 1. Neighbor iteration, thus, takes $\Theta(n)$. For the worst possible graphs, this is no worse than an adjacency list (since the degree of every vertex might be in $\Theta(n)$), but many graphs have much fewer edges than the worst case. A graph is called sparse if its number of edges is small compared to the maximum possible. It is dense if its number of edges is closer to the maximum. Graphs that are sparse typically benefit a lot from the adjacency list representation, since vertex degrees are small compared to the number of vertices.

Searching

So far, we have only answered local questions about graphs:

• What are the neighbors of $v$?
• Are $u$ and $v$ adjacent?

But not yet questions which answer higher level, global properties of graphs. Here is an example:

The reachability problem: Given a graph $G$ and two vertices $u$ and $v$, determine whether there is a path between $u$ and $v$ using edges in $G$.

It is easy to see why this is a practically useful problem to have a solution for.

• If your graph represents a set of locations and roadways between them, this problem asks whether there is a (literal, physical) path between two locations.
• If your graph represents a social network (with vertices as people and edges as personal connections), this problem asks whether there is a line of connections between two people – this would tell you, for instance, whether a rumor could spread between these two people just by word of mouth.
• If your graph represents states and transitions between them, this problem asks whether there is a way to get from one state to another only through transitions.

The most common way to solve the reachability problem is with a searching algorithm. There are many different ways to search a graph, but almost all of them are basic variations of the following high level algorithm.

We start with some specified vertex $v_s$ (for start). We maintain a partition of the vertices $V$ into two sets, which I will call $X$ (for explored) and $U$ for (unexplored). As the names imply, $X$ consists of vertices which we are sure are reachable from $v_s$, while $U$ consists of vertices for which this reachability is unknown. Call an edge $(x, u)$ a fringe edge if $x \in X$ and $u \in U$. Every iteration, we find a fringe edge and use it to increase the size of $X$, and repeat this until there are no more fringe edges. Algorithm 1 shows very high level psuedocode for such an algorithm.

• $X \gets \{ v_s \}$
• while there exists a fringe edge
  • $(x, u) \gets$ some fringe edge
  • $X \gets X \cup \{ u \}$

We have left out a lot of details here, but let’s first prove that this high-level algorithm accomplishes our goal before we try to flesh it out.

Theorem. After algorithm 1 terminates, $X$ contains exactly the vertices in $G$ which are reachable from $v_s$.

Intuition. The basic idea is that at all times, there is a path from $v_s$ to any $x \in X$. So, in order to add a new vertex to $X$, we need to find a path to it from $v_s$. If we have a fringe edge $(x, u)$, we can find the path from $v_s$ to $x$ and append $u$ to get a path from $v_s$ to $u$. Thus, it is safe to add $u$ to $X$. Every time we do this, we increase the size of $X$ by one, and as long as the graph is finite, we will eventually run out of nodes in $G$ to add.

Proof. We proceed by induction in the shortest path distance from $v_s$.

We can’t analyze the runtime of this algorithm yet as we have not specified all of its details. How do we actually find one of these fringe edges in the first place? It’s easy to check whether any particular edge is a fringe edge, so the most straightforward approach is checking all of the edges.

• $X \gets \{ v_s \}$
• while FindFringe(G, X) $\neq$ NIL
  • $(x, u) \gets$ FindFringe(G, X)
  • $X \gets X \cup \{ u \}$

There are at most $n$ iterations (in the case we add all vertices to $X$), and FindFringe takes $\Theta(m)$ time, so the entire algorithm takes $\Theta(nm)$ time.

But every iteration, we’re only adding one vertex to $X$, so the fringe is not changing dramatically. It seems like we’re wasting a lot of time by checking all of the edges every time when most of them haven’t changed to or from being fringe edges. Indeed, we can do much better than this.

Breadth-first Search

Depth-first Search

Path Reconstruction

Minimum Spanning Trees

Theorem (The Minimum Spanning Tree Lemma). Suppose $T$ is a minimum spanning tree of a graph $G$. Let $e$ be an edge in $G \setminus T$. Then the following are true:

• $T \cup \{e\}$ contains a unique cycle $C$.
• Let $e' \in C$. Then $T^\prime = T - \{e\} \cup \{e'\}$ is a spanning tree of $G$.
• If $w(e') \leq w(e)$, then $w(T') \leq w(T)$.