Unweighted Graph Theory - Good Grade This Way

IB Maths AI HL Course (Early Bird Access; Continuous Updates) | 24-Month Access

Section Navigation

Section Overview

This section explores Graph Theory for Unweighted Graphs, transforming visual networks into numerical Adjacency Matrices. You will master the algebraic techniques used to calculate multi-step walks and apply the Google PageRank algorithm to determine importance within a network, providing a critical foundation for Paper 2 and Paper 3 modeling tasks.

Why This Matters for AIHL Exams

Network Analysis: Whether modeling social media connections or subway systems, adjacency matrices allow you to analyze complex relationships using simple matrix multiplication.
PageRank & Ranking: This is a definitive AI HL skill. You will learn how search engines identify “important” nodes by finding the steady state of a random walk on a directed graph.
Pathfinding Logic: Calculating $$M^n$$ provides a high-speed way to find the number of ways to travel between points in exactly $$n$$ steps, a frequent short-answer question pattern.

High-Score Focus (Level 6–7 Insight)

The “From-To” Convention Trap: Adjacency matrices usually use Row = From, Column = To. However, Transition matrices for random walks use Column = From, Row = To. Swapping these conventions is a common Level 5 error.
Undirected Loops ($$= 2$$):
In an undirected adjacency matrix, a loop is recorded as a $$2$$ because it can be traversed in two directions. In a directed graph, a loop is only a $$1$$. Getting this wrong will invalidate all multi-step walk calculations.
Convergence via GDC: To find a steady state (PageRank) quickly in Paper 2, raise your transition matrix to a high power like $$T^{50}$$. Level 7 students know to check that columns have converged to identical values before ranking.

By the End of This Section, You Should Be Able To:

Identify adjacent vertices and construct adjacency matrices for simple and multigraphs.

Apply matrix powers ($$M^n$$) to calculate the number of walks between specific vertices.

Interpret steady-state probabilities as a measure of a node’s relative importance (PageRank).

Model random walks by converting out-degrees into transition probabilities.

Analyze directed and undirected networks to rank vertices using iterative matrix algebra.

Suggested Study Path

Master Adjacency Matrix construction first; pay attention to loops and multiple edges.
Practice calculating Walks of Length $n$ using your GDC’s matrix power function.
Study the Transition Matrix rules—ensure columns sum to 1 every single time.
Work through the Web Page ranking example to see PageRank in action.
Review the TOK reflection on how abstract networks can distort or clarify reality.

Study Metrics

Core: 40–55 mins

Practice: 60–90 mins

Exam Priority: ★★★★☆

Graph Theory for Unweighted Graphs

Often, we are interested only in the connections between vertices and not in the weights of the edges. Examples of such situations might be a map of a metro system, connections on an electronic circuit board, a large file-storage system, or a network of friends on social media.

This information will normally be shown in an unweighted graph. To analyse these mathematically, we translate the visual network into a numerical format known as an adjacency matrix.

Definition: Adjacency and Adjacency Matrices

Two vertices are said to be adjacent if they are directly connected by an edge.
An element $ A_{ij} $ of an adjacency matrix $ A $ represents the number of direct connections between vertex $ i $ and vertex $ j $.

Unlike in a table, when giving information about connections in a matrix, if there is no connection, a $ 0 $ must be put in as a placeholder rather than leaving the entry empty.

TOK: Distorting Reality

Unweighted graphs simplify reality by ignoring distance and geography to focus purely on relationships. To what extent can shared knowledge be distorted and misleading when visual representations are heavily abstracted?

Worked Example

Find the adjacency matrices for the two graphs described below.

a. An undirected graph with four vertices ($ A, B, C, D $). There is an edge connecting $ A $ to $ B $, an edge connecting $ A $ to $ C $, an edge connecting $ B $ to $ C $, and an edge connecting $ C $ to $ D $.

b. A directed graph with four vertices ($ A, B, C, D $). Arrows indicate one-way paths: from $ A $ to $ B $, from $ A $ to $ C $, from $ C $ to $ A $, from $ C $ to $ B $, and from $ D $ to $ C $.

Solution

Part a: Undirected Graph

Since the graph is undirected, a connection between $ A $ and $ B $ counts for both row $ A $/column $ B $ and row $ B $/column $ A $. The matrix is symmetric in the diagonal from top left to bottom right (the leading diagonal).

$$ A = \begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0
\end{pmatrix} $$

Part b: Directed Graph

An adjacency matrix indicates possible movement from row to column; this is the opposite to the convention for transition matrices. We place a $ 1 $ only if the arrow points from the row vertex to the column vertex.

$$ B = \begin{pmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{pmatrix} $$

Notice that row $ B $ is entirely zeros because there are no edges leaving vertex $ B $.

Loops, Multiple Edges, and Simple Graphs

Not all graphs consist of single connections between distinct points. Sometimes a path may double back on itself or there may be redundant connections between two nodes.

Definition: Complex Graph Features

An edge from a vertex back to itself is called a loop.
If there are multiple edges between two vertices, the graph is a multigraph.
A simple graph is one with no loops or multiple edges.

Worked Example

Find the adjacency matrices for the two graphs described below.

a. An undirected multigraph where $ A $ connects to $ B $, and $ A $ connects to $ C $ with two separate edges. $ B $ also connects to $ C $. Vertex $ D $ connects to $C$ and has a loop connecting back to itself.

b. A directed multigraph. $ A $ points to $ B $ and $ C $. $ C $ points to $ A $ via two separate arrows. $ D $ points to $ C $, and $ D $ also has a loop pointing back to itself.

Solution

Part a: Undirected Multigraph with a Loop

In an undirected graph, a loop is shown as a $ 2 $ in an adjacency matrix, as going both ways along it is possible. The multiple edges between $ A $ and $ C $ are recorded as $ 2 $.

$$ M_a = \begin{pmatrix}
0 & 1 & 2 & 0 \\
1 & 0 & 1 & 0 \\
2 & 1 & 0 & 0 \\
0 & 0 & 0 & 2
\end{pmatrix} $$

Part b: Directed Multigraph with a Loop

In this graph, the loop is shown as a $ 1 $ in the adjacency matrix as the edge is directed. The two arrows from $ C $ to $ A $ mean the entry for row $ C $, column $ A $ is $ 2 $.

$$ M_b = \begin{pmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 \\
2 & 0 & 0 & 0 \\
0 & 0 & 1 & 1
\end{pmatrix} $$

Powers of Adjacency Matrices

One of the most powerful applications of an adjacency matrix is using matrix algebra to determine the number of walks between vertices. By raising the matrix to a power, we calculate multi-step pathways.

Key Idea: Calculating Walks

Let $ M $ be the adjacency matrix of a graph. The number of walks of length $ n $ from vertex $ i $ to vertex $ j $ is the entry in the $ i \text{th} $ row and the $ j \text{th} $ column of $ M^n $.

The numbers of walks of length $ r $ or less between any two vertices are given by the matrix $ S_r $ where:

$$S_r = M + M^2 + \dots + M^r$$

Conceptual Prompt

How does the adjacency matrix allow you to analyse the paths between two points on a graph? Explain how you can use the powers of an adjacency matrix to find the minimum length of path between two vertices.

Exam Tip

When calculating $ M^n $ or $ S_r $, always use the matrix capabilities of your Graphic Display Calculator (GDC). Trying to multiply matrices manually, particularly for $ M^3 $ or higher, is highly prone to arithmetic errors and wastes valuable examination time.

Transition Matrices and Random Walks

In the study of networks, we often want to analyse how an entity (like a person, a data packet, or a web surfer) navigates through the connections. A random walk on a graph is a sequence of steps where the next vertex is chosen entirely at random from the available connected options.

Because the graph has a finite number of vertices, this random walk acts as a finite Markov chain. We can represent the probabilities of moving from one vertex to another using a transition matrix.

Constructing the Transition Matrix

To build a transition matrix, we must determine the probability of traveling along each edge. If a walk around a graph is equally likely to take any of the edges leading away from a vertex, it is a random walk.

Definition: The Transition Matrix

A transition matrix can be constructed for both directed and undirected graphs.

For an undirected graph, the probability of moving to an adjacent vertex is the reciprocal of the vertex’s degree.
For a directed graph, it is the reciprocal of the out-degree.

The probability of moving from vertex $ i $ to vertex $ j $ is recorded in the $ i \text{th} $ column and the $ j \text{th} $ row of the matrix.

Exam Tip

The direction of movement in a transition matrix is opposite to that in an adjacency matrix. Always remember: Columns represent “From”, and Rows represent “To”. Furthermore, IB syllabus questions will only feature graphs that are connected (or strongly connected, if directed).

Steady State and PageRank

If a random walk continues for a long period, the proportion of time spent at each vertex stabilizes. These are the steady state probabilities. In this model, the time taken to transition between vertices is ignored.

This concept is the foundation of the Google PageRank algorithm, developed by Larry Page and Sergey Brin in 1996. By treating hyperlinks as edges in a directed graph, the steady state probabilities identify which site would be visited most often by someone randomly clicking links.

Key Idea: Ranking Importance

Sites with the highest steady state probabilities are placed at the top of the search list. The justification is that a site is highly visited if it has many incoming links, or if it is linked to by other sites that themselves have many incoming links, reflecting its relative importance.

TOK: Real-Life Applications

Matrices are heavily utilized in computer graphics for three-dimensional modelling. How can this abstract mathematical structure be adapted to represent reality across completely different areas of knowledge?

Worked Example

Vertices $ A $ to $ F $ represent web pages in a closed network, and the directed edges indicate links between the pages. The connections are defined as follows:

Page $ A $ links to $ B, D $ and $ F $.
Page $ B $ links to $ D $.
Page $ C $ links to $ A $ and $ B $.
Page $ D $ links to $ B, C $ and $ F $.
Page $ E $ links only to $ D $.
Page $ F $ links to $ A $ and $ E $.

a. Construct the transition matrix for a random walk around this graph.

b. Find the steady state probabilities for the network.

c. Hence rank the vertices in order of importance.

Solution

Part a: Constructing the Matrix

We build the transition matrix column by column. The $ i \text{th} $ column represents the probabilities of leaving vertex $ i $.

For example, vertex $ A $ has an out-degree of $ 3 $ (linking to $ B, D, \text{ and } F $). The probability of randomly choosing any of these links is $ \displaystyle\frac{1}{3} $. These values are placed in the first column at rows 2, 4, and 6.

Page $ B $ only has one link (to $ D $), so its out-degree is $ 1 $. A value of $ 1 $ is placed in the second column at row 4.

Repeating this process for all vertices gives the transition matrix $ T $:

$$ T = \begin{pmatrix}
0 & 0 & \displaystyle\frac{1}{2} & 0 & 0 & \displaystyle\frac{1}{2} \\
\displaystyle\frac{1}{3} & 0 & \displaystyle\frac{1}{2} & \displaystyle\frac{1}{3} & 0 & 0 \\
0 & 0 & 0 & \displaystyle\frac{1}{3} & 0 & 0 \\
\displaystyle\frac{1}{3} & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & \displaystyle\frac{1}{2} \\
\displaystyle\frac{1}{3} & 0 & 0 & \displaystyle\frac{1}{3} & 0 & 0
\end{pmatrix} $$

Part b: Steady State Probabilities

Because the question does not specify an analytical method, you can use your GDC to evaluate the transition matrix to a sufficiently high power (e.g., $ T^{50} $) until the columns converge, showing no change in the third significant figure. Alternatively, you could solve the system of linear equations $ Tv = v $ where the sum of the probabilities equals $ 1 $.

The steady state probability vector is found to be:

$$\begin{pmatrix} A \\ B \\ C \\ D \\ E \\ F \end{pmatrix} = \begin{pmatrix} 0.130 \\ 0.207 \\ 0.109 \\ 0.326 \\ 0.0761 \\ 0.152 \end{pmatrix}$$

Part c: Ranking

To determine the importance of the web pages, the vertex with the highest steady state probability is placed at the top of the list.

Ordering the probabilities from highest to lowest: $ 0.326 > 0.207 > 0.152 > 0.130 > 0.109 > 0.0761 $.

The final ranking of importance is: D, B, F, A, C, E.

Conceptual Prompt

Why might a random walk indicate the most important sites on a graph? How do “dead ends” (vertices with an out-degree of 0) affect the standard PageRank algorithm, and how might you adjust the matrix to solve this?

🎯 Examiner’s Radar: Graph Theory & PageRank

📋 Paper Mapping

Paper 2 (Calculation): You will frequently be asked to find the number of “walks of length $$n$$.” Use the GDC to calculate $$M^n$$ instantly. Do not attempt this manually.
Paper 3 (Modeling): PageRank is a prime candidate for the 27-mark modeling question. You may be asked to “damp” the matrix or handle “dangling nodes” (nodes with no out-links).

💡 Scoring Secrets

The Convention Flip: This is the #1 error. Adjacency Matrices are “Row to Column,” but Transition Matrices are “Column to Row.” Mixing these up results in an immediate 0 for the entire question.
Loop Value: In an undirected graph, a loop counts as 2 in the adjacency matrix (one for each direction). In a directed graph, it counts as 1. Check the arrows carefully!