3.14 Graph theory: definitions and representationIB Maths: Applications and Interpretation HL: Revision notes

A graph is a set of vertices (points) joined by edges (lines). Two vertices joined by an edge are adjacent vertices; two edges that share a vertex are adjacent edges. The degree of a vertex is the number of edges meeting at it. Example: a network with edges $AB$, $AC$, $BC$, $CD$, $DE$ has $\deg C=3$ and $\deg E=1$. Because each edge has two ends, the sum of all the degrees is twice the number of edges: here $2+2+3+2+1=10=2\times5$. So the sum of the degrees is always even.

A simple graph has no loops (an edge from a vertex to itself) and no two edges joining the same pair of vertices. A complete graph on $n$ vertices has every pair of vertices joined, so it has $\frac{n(n-1)}{2}$ edges: 10 edges for 5 vertices, 15 for 6. A weighted graph gives each edge a number, the weight, such as a distance in km, a cost or a time; an unweighted graph does not. To model a real situation, make the objects vertices and the connections edges: computers and cables, towns and roads, sensors and links. If a question gives weights, add them to find the total length or cost of a set of edges.

A graph is connected if there is a path along edges between every pair of vertices. A subgraph is formed from some of the vertices and edges of a graph. A tree is a connected graph with no cycles. A tree with $n$ vertices has exactly $n-1$ edges. Example: in a network with edges $PQ$, $PR$, $QR$, $QS$, $RS$, $ST$, the edges $PQ$, $PR$, $QS$, $ST$ form a subgraph that is a tree (5 vertices, 4 edges). The whole graph is connected but not a tree, because $P$-$Q$-$R$ is a cycle. If vertex $S$ is deleted together with its edges, $T$ is left with no edge and the subgraph is not connected.

In a directed graph each edge has a direction, shown $X\to Y$, such as a one-way street. The out-degree of a vertex is the number of edges leaving it and the in-degree is the number of edges entering it. The sum of the in-degrees equals the sum of the out-degrees, which equals the number of edges. Example: one-way streets $W\to X$, $X\to Y$, $Y\to Z$, $Z\to W$, $X\to Z$ give out-degree 2 and in-degree 1 for $X$, and in-degree 2 for $Z$. A directed graph is strongly connected if, following the directions, you can get from any vertex to any other. The cycle $W\to X\to Y\to Z\to W$ passes through every vertex, so this graph is strongly connected.

A graph can be given as a list of edges, or as an adjacency matrix with a row and column for each vertex, where the entry is the number of edges joining them (AHL 1.14). For the sensor network with edges $PQ$, $PR$, $QR$, $QS$, $RS$, $ST$ (rows and columns in the order $P,Q,R,S,T$): $\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}$ The matrix of an undirected graph is symmetric about the leading diagonal, and each row sum is the degree of that vertex ($2,3,3,3,1$). For a simple graph every diagonal entry is 0 and every other entry is 0 or 1. For a directed graph the entry in row $i$, column $j$ counts edges from $i$ to $j$, so the matrix need not be symmetric.