Graph Theory

Graphs are used to show how things are connected. They can be used to help solve problems in train scheduling, traffic flow, bed usage in hospitals, and project management.
The theory of graphs was developed centuries ago, but the application of the theoretical ideas is relatively recent. Real progress was made during and after the Second World War as mathematicians, industrial technicians, and members of the armed services worked together to improve military operations.

Definitions

Definition Graph

A graph (or network) is a structure which shows the physical connections or relationships between things of interest.
The things of interest are represented by vertices (singular: vertex), also called nodes or points.
The connections or relationships are represented by edges, also called lines or arcs.

Example

This graph shows road connections between several towns. We can see that towns A and B are directly connected, but towns A and C are not.

Definition Degree of a Vertex

The degree of a vertex, denoted $\deg(v)$, is the number of edges connected to it.
If a loop exists (an edge connecting a vertex to itself), it contributes 2 to the degree of that vertex.

Example

For vertex A: It has one connection to B and one connection to D. $\deg(A) =2 $.

Definition Undirected Graph

In an undirected graph, movement is allowed in either direction along the edges. The relationship is symmetric.

Adjacent vertices are vertices connected by an edge.
Adjacent edges are edges which share a common vertex.

Example

In this graph, A is connected to B and B is connected to A.

Definition Directed Graph

A directed graph (or digraph) contains arrows indicating the direction we can move along the edges.

The in-degree is the number of edges coming into the vertex.
The out-degree is the number of edges going out from the vertex.

Example

In this graph, A is connected to B and B is not connected to A.

Definition Weighted Graph

A weighted graph has numbers assigned to its edges. These numbers may represent the cost, time, or distance.

Example

The weight of edge AD is 15.

Definition Walk$\virgule$ Trail$\virgule$ Path$\virgule$ circuit and Cycle

A walk is a sequence of vertices such that each successive pair is adjacent.
A trail is a walk in which no edge is repeated.
A path is a walk in which no vertex is repeated.
A circuit is a walk in which no edge is repeated that starts and ends at the same vertex.
A cycle is a walk in which no vertex is repeated except the first/last vertex that starts and ends at the same vertex.

Example

In this graph:

$A\rightarrow B\rightarrow C$ is a walk because there is an edge between $A$ and $B$ and an edge between $B$ and $C$.
$A\rightarrow B\rightarrow A$ is not a trail because the edge between $A$ and $B$ is repeated.
$A\rightarrow B\rightarrow C\rightarrow D\rightarrow A$ is not a path because the vertex $A$ is repeated.
$A\rightarrow B\rightarrow C\rightarrow D\rightarrow A$ is a circuit (and a cycle).

Properties of Graphs

Definition Connected Graph

A graph is called connected if it is possible to travel from any vertex to any other vertex via a sequence of edges.

Example

Connected	Disconnected

In the graph on the right, you cannot get from the left pair of vertices to the right pair. It has two disconnected components.

Definition Complete Graph

A complete graph is a simple undirected graph in which every vertex is connected by an edge to every other vertex.
The notation $K_n$ is used to describe the complete graph with $n$ vertices.

Example

This is $K_4$. It has 4 vertices and $\frac{4(3)}{2} = 6$ edges.

Adjacency Matrices

Definition Adjacency Matrix

For a graph with $n$ vertices, the adjacency matrix $\mathbf{M}$ is an $n \times n$ matrix where the element $m_{ij}$ represents the number of direct edges from vertex $i$ to vertex $j$.

Example

The table below shows the number of 1-step walks between the vertices:

The adjacency matrix for the graph is therefore:$$ \mathbf{M} = \begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix} $$Since we do not usually write the labels for the vertices on the adjacency matrix, it is important to remember what the rows and columns refer to. To make this easier, we put them in alphabetical order.

Proposition Multi-step Walks

If $\mathbf{M}$ is the adjacency matrix, then the element $(i,j)$ of $\mathbf{M}^k$ gives the number of walks of length $k$ from vertex $i$ to vertex $j$.

Example

To understand why the powers of $\mathbf{M}$ give the multi-step adjacency matrices, consider the 2-step matrix:

The element in row 2 column 4 of $\mathbf{M}^2$ shows there are two 2-step walks from B to D.
This value comes from the multiplication row 2 $\times$ column 4 as follows:

$1 \times 1 = 1$ walk from B to A $\times$ 1 walk from A to D
$0 \times 0 = 0$ walks from B to B $\times$ 0 walks from B to D
$1 \times 1 = 1$ walk from B to C $\times$ 1 walk from C to D
$0 \times 0 = 0$ walks from B to D $\times$ 0 walks from D to D
$0 \times 1 = 0$ walks from B to E $\times$ 1 walk from E to D

Adding these terms gives the two 2-step walks from B to D. The walks are $\text{B} \rightarrow \text{A} \rightarrow \text{D}$ and $\text{B} \rightarrow \text{C} \rightarrow \text{D}$.