3.14 Graph theory: definitions and representation

3.14 Graph theory: definitions and representation

IB Maths: Applications and Interpretation HL: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A graph has vertices joined by edges; the degree of a vertex is the number of edges at it.
  • The sum of all degrees is 2×2\times the number of edges, so it is always even.
  • A tree is a connected graph with no cycles; with nn vertices it has n−1n-1 edges.
  • A complete graph on nn vertices has n(n−1)2\frac{n(n-1)}{2} edges.
  • An adjacency matrix records edges; for an undirected graph it is symmetric.
PQRST
The sensor network: edges PQ, PR, QR, QS, RS and ST.

Vertices, edges and degree

A graph is a set of vertices joined by edges, and the degree counts the edges at each vertex.

Two vertices joined by an edge are adjacent vertices; two edges sharing a vertex are adjacent edges. The degree of a vertex is the number of edges meeting at it.

Each edge has two ends, so the sum of all degrees is twice the number of edges. It is always even.

For edges ABAB, ACAC, BCBC, CDCD, DEDE: degrees are 2,2,3,2,12,2,3,2,1 and 2+2+3+2+1=10=2×52+2+3+2+1=10=2\times5.

PQRST
The sensor network: edges PQ, PR, QR, QS, RS and ST.

A graph has 7 edges. What is the sum of the degrees?

Types of graph

Simple, complete and weighted graphs differ in which edges are allowed and whether edges carry numbers.

A simple graph has no loops and no repeated edges between the same pair of vertices. A complete graph on nn vertices joins every pair, so it has n(n−1)2\frac{n(n-1)}{2} edges: 10 for 5 vertices and 15 for 6.

A weighted graph gives each edge a number (a distance, cost or time); an unweighted graph does not.

To model a situation, make objects vertices and connections edges: computers and cables, towns and roads, sensors and links.

ABCDE
The complete graph on 5 vertices has 10 edges.

How many edges does a complete graph on 6 vertices have?

Connected graphs and trees

A tree is connected with no cycles, so nn vertices need exactly n−1n-1 edges.

A graph is connected if there is a path between every pair of vertices. A subgraph uses some of the vertices and edges of a graph.

A tree is a connected graph with no cycles. In the sensor network, PQPQ, PRPR, QSQS, STST form a subgraph that is a tree: 5 vertices, 4 edges. The whole network is connected but not a tree, because PP–QQ–RR is a cycle.

Deleting vertex SS leaves TT with no edge, so the rest is not connected.

PQRST
The edges PQ, PR, QS and ST form a tree on the 5 vertices.

A tree has 9 vertices. How many edges does it have?

Directed graphs

In a directed graph each edge goes one way, and vertices have an in-degree and an out-degree.

In a directed graph each edge has a direction X→YX\to Y, like a one-way street. The out-degree counts edges leaving a vertex and the in-degree counts edges entering. Both sums equal the number of edges.

One-way streets W→XW\to X, X→YX\to Y, Y→ZY\to Z, Z→WZ\to W, X→ZX\to Z give XX out-degree 2 and in-degree 1, and ZZ in-degree 2. The cycle W→X→Y→Z→WW\to X\to Y\to Z\to W reaches every vertex, so the graph is strongly connected.

WXYZ
One-way streets W→X, X→Y, Y→Z, Z→W and X→Z.

Which is true for the sums over all vertices of a directed graph?

Adjacency matrices

An adjacency matrix has a row and column per vertex, with entries counting the edges between them.

For the sensor network (order P,Q,R,S,TP,Q,R,S,T):

(0110010110110100110100010)\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}

An adjacency matrix of an undirected graph is symmetric, and each row sum is the degree of that vertex (2,3,3,3,12,3,3,3,1). In a simple graph the diagonal is 0 and other entries are 0 or 1. For a directed graph, entry (i,j)(i,j) counts edges from ii to jj, so the matrix need not be symmetric.

PQRST
The sensor network whose adjacency matrix is shown: edges PQ, PR, QR, QS, RS and ST.

Undirected

Matrix:
Symmetric
Feature:
Row sum = degree

Directed

Matrix:
Need not be symmetric
Feature:
Entry (i,j)(i,j): edges i→ji\to j

A row of an undirected adjacency matrix is (1,0,1,1,0)(1,0,1,1,0). What is the degree of that vertex?

Try an exam question

A graph has vertices A,B,C,D,EA, B, C, D, E and edges ABAB, ACAC, BCBC, CDCD, DEDE. (a) Write down the degree of each vertex. (b) Show that the sum of the degrees is twice the number of edges. (c) Explain why the graph is not a tree.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Write down the degree of vertex CC.

1 mark, marked against the mark scheme

Revision notes