A graph G consists of a finite set of vertices V(G), which cannot be empty and a finite set of edges, E(G), which connect pairs of vertices. The number of vertices of G is called the order of G. The number of edges in G is represented by |E| and the number of vertices by |V|.

The graph in Figure 19.2 has |V| = 6 and |E| = 9.

Incidence, adjacency, and neighbours

Two vertices are adjacent if they are joined by an edge. In Figure 19.2, v₃ is adjacent to v₄ and is also said to be a neighbour of v₄. The edge which joins the vertices is said to be incident to them. That is e₃ is incident to v₃ and v₄.

Multiple edges and loops, simple graphs

Two or more edges joining the same pair of vertices are multiple edges. An edge joining a vertex to itself is called a loop. In Figure 19.2 edges e₅ and e₉ are multiple edges and e₈ is a loop. A graph containing no multiple edges or loops is called a simple graph. There is an example of a simple graph in Figure 19.3.

Isomorphism

Graphs are isomorphic to each other if one can be obtained from a redrawing of the other one. Some isomorphic graphs are shown in Figure 19.4.

Weighted graph

A weighted graph has a number assigned to each of its edges, called its weight. The weight can be used to represent distances or capacities. A weighted graph is shown in Figure 19.5.

Digraphs

A digraph is a directed graph, that is, instead of edges in the definition of graphs we have arcs join pairs of vertices in a specified order. A digraph is shown in Figure 19.6(a).

Underlying graph

The underlying graph of a digraph D is the graph obtained by replacing each arc by an (undirected) edge as in Figure 19.6(b).

Degrees

The number of times edges are incident to a vertex, v, is called its degree, denoted by d(v). In Figure 19.2 vertex v₅ has degree 3 and vertex v₃ has degree 4.

A vertex of a digraph has an in-degree d_–(v) and an out-degree, d₊(v). In Figure 19.6(a) v₅ has in-degree of 1 and out-degree of 2. Vertex v₁ has in-degree 1 and out-degree 1.

The sum of the values of the degree, d(v), over all the vertices of a graph totals to twice the number of edges:

$\sum _{i}d({\text{v}}_i)=2\left|E\right|$

where |E| is the number of edges.

Checking this result for Figure 19.2, we find that the degrees are $d({\text{v}}_1)=2,d({\text{v}}_2)=5,d({\text{v}}_3)=4,d({\text{v}}_4)=2,d({\text{v}}_5)=3,\text{a}\text{n}\text{d?}d({\text{v}}_6)=2.$Summing these gives 18, which is the same as twice the number of edges.

For a digraph we get

$\begin{array}{ccc}\sum _i{d}_{-}({\text{v}}_i)=\left|A\right|& \text{and}& \sum _i{d}_{+}({\text{v}}_i)=\left|A\right|\end{array}$

where |A| is the number of arcs.

Subgraph

A subgraph of G is a graph, H, whose vertex set is a subset of G's vertex set, and similarly its edge set is a subset of the edge set of G.

$\begin{array}{l}V(\text{H})\subseteq V(\text{G})\\ E(\text{H})\subseteq E(\text{G})\end{array}$

If it spans all of the vertices of G, that is, V (H) == V (G) then H is called a spanning subgraph of G. A graph G, a subgraph, and a spanning subgraph are shown in Figure 19.7.

Complete graph

A simple graph in which every pair of two vertices is adjacent is called a complete graph. K_nis the complete graph with n vertices. K_nhas $\frac{1}{2}n(n-1)$edges. Some examples of complete graphs are shown in Figure 19.8.

Bipartite graph

This is a graph whose vertex set can be partitioned into two sets in such a way that each edge joins a vertex of the first set to a vertex of the second set. Some examples are given in Figure 19.9.

A complete bipartite graph is a bipartite simple graph in which every vertex in the first set is adjacent to every vertex in the second set. K_m,n is the complete bipartite graph with m vertices in the first set and n vertices in the second set. Some examples of complete bipartite graphs are given in Figure 19.9(b) and (c).

Walks, paths, and circuits

A sequence of edges of the form

${\text{v}}_{\text{s}}{\text{v}}_{\text{i}}{,\text{v}}_{\text{i}}{\text{v}}_{\text{j}}{,\text{v}}_{\text{j}}{\text{v}}_{\text{k}}{,\text{v}}_{\text{k}}{\text{v}}_{\text{l}}{,\text{v}}_{\text{1}}{\text{v}}_{\text{t}}$

is a walk of from v_s to v_t. If these edges are all distinct then the walk is called a trail and if the vertices are also distinct then the walk is called a path. A walk or trail is closed if v_s = v_t. A closed walk in which all the vertices are distinct except v_s and v_t is called a cycle or circuit. Examples are given in Figure 19.10.

Connected graph

A graph G is connected if there is a path from any one of its vertices to any other vertex. A disconnected graph is said to be made up of components. All the graphs we have drawn so far have been connected. In Figure 19.11(a) there is a disconnected graph with two components and in Figure 19.11(b) a disconnected graph with three components.

Planar graphs

A planar graph is one which can be drawn in the plane without any edges intersecting except at vertices to which they are both incident. There is an example of a planar graph in Figure 19.12(a) and a non-planar graph in Figure 19.12(b).

The incidence matrix of a graph G is a |V| ×|E| matrix. The element a_ij= the number of times that vertex v_iis incident with the edge e_j.

The adjacency matrix of G is the |V| × |V| matrix. a_ij= the number of edges joining v_iand v_jThe incidence matrix for the graph in Figure 19.2 is given by

$\begin{array}{ll}\hfill & \begin{array}{lllllllll}{\text{e}}_1\hfill & {\text{e}}_2\hfill & {\text{e}}_3\hfill & {\text{e}}_4\hfill & {\text{e}}_5\hfill & {\text{e}}_6\hfill & {\text{e}}_7\hfill & {\text{e}}_8\hfill & {\text{e}}_9\hfill \end{array}\hfill \\ \begin{array}{l}{\text{v}}_1\hfill \\ {\text{v}}_2\hfill \\ \begin{array}{l}{\text{v}}_3\\ {\text{v}}_4\end{array}\hfill \\ {\text{v}}_5\hfill \\ {\text{v}}_6\hfill \\ \hfill \end{array}\hfill & \left(\begin{array}{lllllllll}1\hfill & 0??\hfill & 0??\hfill & 0??\hfill & 0??\hfill & 0??\hfill & 1??\hfill & 0??\hfill & 0??\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 1\hfill \\ 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 2\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \end{array}\right)\hfill \end{array}$

and the adjacency matrix by

$\begin{array}{l}\begin{array}{lllllll}\hfill & {\text{v}}_1\hfill & {\text{v}}_2\hfill & {\text{v}}_3\hfill & {\text{v}}_4\hfill & {\text{v}}_5\hfill & {\text{v}}_6\hfill \end{array}\\ \begin{array}{l}{\text{v}}_1\hfill \\ {\text{v}}_2\hfill \\ {\text{v}}_3\hfill \\ {\text{v}}_4\hfill \\ {\text{v}}_5\hfill \\ {\text{v}}_6\hfill \end{array}\left(\begin{array}{llllll}0??\hfill & 1??\hfill & 0???\hfill & 0???\hfill & 0??\hfill & 1??\hfill \\ 1\hfill & 0\hfill & 1\hfill & 0\hfill & 2\hfill & 1\hfill \\ 0\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 2\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right)\end{array}$

Spanning trees

A spanning tree of a graph G is a tree T which is a spanning subgraph of G. That is, T has the same vertex set as G. Examples of graphs with spanning trees marked are given in Figure 19.15.

How to grow a spanning tree

Take any vertex v of G as an initial partial tree. Add edges one by one so each new edge joins a new vertex to the partial tree. If there are n vertices in the graph G then the spanning tree will have n vertices and n – 1 edges.

Minimum spanning tree

Supposing we have a group of offices which need to be connected by a network of communication lines. The offices may communicate with each other directly or through another office. In order to decide on which offices to build links between we firstly work out the cost of all possible connections. This will then give us a weighted complete graph as shown in Figure 19.16.

The minimum spanning tree is then the spanning tree that represents the minimum cost.

The greedy algorithm for the minimum spanning tree

1 Choose any start vertex to form the initial partial tree (v_i).

2 Add the cheapest edge, e_i, to a new vertex to form a new partial tree.

3 Repeat Step 2 until all vertices have been included in the tree.

Example 19.1

Find the minimum spanning tree for the graph representing communication links between offices as shown in Figure 19.16.

Solution We start with any vertex and choose the one marked a. Add the edge ab which is the cheapest edge of those incident to a.

Add a new edge in order to form a partial tree and choose bc, which is one of the cheapest remaining edges incident either with a or b. Now we add edge ad which is the cheapest remaining edge of those incident with a or b or c. Continuing in this manner we find the minimum spanning tree, as shown in Figure 19.17. The total cost of the communication links in our solution is found to be 2 + 3 + 3 + 2 + 4 = 14.

Flow function

A valid flow function must be such that:

1 $f({\text{a}}_k)\le c({\text{a}}_k).$

2 The out-flow at any vertex equals the in-flow except at the source or the sink.

An arc is saturated if f(a_k) = c(a_k). The total flow is then the flow out of s (which equals the flow into t).

Finding a maximum flow

1 Assign an initial flow to each edge (this will probably be 0 flow on each arc).

2 Find a flow-augmenting path from s to t. Any arc along this flow-augmenting path may be either in the forward direction, that is, in the same direction as the path, or in the backward direction, that is, in the opposite direction to the path. If the arc along the path is in the forward direction, then it must have some ‘extra’ capacity $c({\text{a}}_k)\ge f({\text{a}}_k)$then the extra capacity is represented by ${\Delta }_k=c({\text{a}}_k)-f({\text{a}}_k).$If the arc along the path is in the backward direction, then f(a_k) must be greater than 0 and we assign the possible increase in flow Δ_k= f(a_k). We can then calculate the amount that this path can augment the flow by as Δ = minimum (Δ_k), where we consider all the values of along the path.

3 We can now change the value of the flow function along the flow-augmenting path to f(a_k) + Δ (for arcs in the forward direction along the path) and f (a_k) – Δ (for arcs in the backward direction along the path). We then repeat the second stage and look for another flow-augmenting path. If no more flow-augmenting paths exist, then we have found the maximum flow. This algorithm is due to Ford and Fulkerson. It can take a long while to terminate on complicated networks and better algorithms have been developed, for example, the Dinic algorithm which is not given here. We can check that we have in fact found the maximum flow in the network by finding the minimum cut. The max-flow, min-cut theorem states that the maximum value of a flow from s to t in a network is equal to the minimum capacity of a cut separating s and t.

Example 19.3

Find the maximum flow from s to t in the network shown in Figure 19.27(a). The weights on the arcs represent their capacities.

Solution We begin by identifying a flow-augmenting path s, e, t. As initially we consider the flow function to be zero then the spare capacities along the arcs are 12 and 14, the minimum of which is 12. We therefore assign a flow of 12 along the path to get Figure 19.27(b).

We spot another flow-augmenting path, s, c, d, t with a possible flow of 10 (the minimum of 14, 19, and 10). We add 10 to the flow function along this path to give Figure 19.27(c).

We identify the flow-augmenting path s, a, b, t with a possible flow of 8 (the minimum of the values of the spare capacities of 14, 8 and 15). We add 8 to the flow function along this path to give Figure 19.27(d).

Another flow-augmenting path is s, a, c, d, b, t with a possible flow of 6 (the minimum of the values of the spare capacities of 6, 14, 9, 6, 7). We add 6 to the flow function along this path to give Figure 19.27(e).

There are no more entirely forward paths but we can see one that involves an arc in the backward direction, that has a non-zero flow function. This path is s, c, a, e, t where ca is in the backward direction. We take the minimum of the spare capacity in the forward direction along with the value of the flow in the backward direction. This gives 2 as the minimum of 4, 6, 3, and 2. We add 2 to the flows on the arcs in the forward direction and subtract 2 from the flow on ca which is in the backward direction. Note that this process is equivalent to redirecting the flow. We have now reached Figure 19.27(f). We are unable to identify any more flow-augmenting paths. We can confirm that this is in fact a solution to the maximum flow problem by using the max-flow, min-cut theorem. If we look at the cut marked we see that this has a capacity of 38. To find this we add the capacities of all the arcs which cross the cut from the's end’ to the ‘t end’, that is, db, with a capacity of 6, dt with a capacity of 10 and et with a capacity of 14. This cut has a capacity of 38 in total which is the value of the flow we have found.