10.3.1 Networks & Matrices

Introduction to Networks and Matrices

A network is a graph where edges can represent connections (e.g., roads, wires) and weights on edges often represent distances, costs, or capacities. Matrices provide a compact way to represent networks mathematically.

Adjacency Matrix

The adjacency matrix represents the connections between vertices in a network.

Rows and columns represent vertices.
Entries indicate connections:
- $a_{ij} = 1$ if there is an edge between vertices $i$ and $j$
- $a_{ij} = 0$ otherwise.

infoNote

Example: Adjacency Matrix for an Undirected Graph

For a graph with vertices $A, B, C, D$

Edges: $AB, BC, CD, DA$

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

Weighted Matrix

The weighted matrix includes weights (e.g., distances, costs) instead of simple binary values.

a_{ij} = \begin{cases} \text{weight of edge between } i \text{ and } j, & \text{if an edge exists between } i \text{ and } j, \\ \infty & \text{if no edge exists between } i \text{ and } j. \end{cases}

$a_{ij} = \infty$ if no edge exists.

infoNote

Example: Weighted Matrix

For a graph with $A, B, C$ :

$AB = 5, BC = 3, AC = \infty$

\mathbf{W} = \begin{pmatrix} 0 & 5 & \infty \\ 5 & 0 & 3 \\ \infty & 3 & 0 \end{pmatrix}

Drawing a Network from a Matrix

Steps:

Label vertices: Use rows/columns to determine vertices.
Add edges: Connect vertices based on non-zero entries in the matrix.
Include weights: Label edges with their corresponding values if using a weighted matrix.

infoNote

Example:

Given the matrix:

\mathbf{M} = \begin{pmatrix} 0 & 7 & 2 & 0 \\ 7 & 0 & 0 & 3 \\ 2 & 0 & 0 & 6 \\ 0 & 3 & 6 & 0 \end{pmatrix}

Steps to Draw the Network:

Vertices: $A, B, C, D$
Edges:
$AB$ (weight = 7), $AC$ (weight = $2$ ).
$BD$ (weight = 3), $CD$ (weight = $6$ ).

Writing a Matrix from a Network

Steps:

List vertices: Assign each vertex a row/column in the matrix.
Fill entries:

For adjacency matrices, use $1$ for connections, $0$ otherwise.
For weighted matrices, use weights for connections, $\infty$ or $0$ otherwise.

infoNote

Example:

For the graph with:

Vertices: $A, B, C, D$
Edges: $AB = 7, AC = 2, BD = 3, CD = 6$

The weighted matrix is:

\mathbf{W} = \begin{pmatrix} 0 & 7 & 2 & \infty \\ 7 & 0 & \infty & 3 \\ 2 & \infty & 0 & 6 \\ \infty & 3 & 6 & 0 \end{pmatrix}

Worked Examples

infoNote

Example 1: Drawing a Network from a Weighted Matrix

Given:

\mathbf{W} = \begin{pmatrix} 0 & 4 & \infty \\ 4 & 0 & 5 \\ \infty & 5 & 0 \end{pmatrix}

Steps:

Label vertices $A, B, C$
Add edges:

$AB$ with weight $4$ .
$BC$ with weight $5$

Network:

Vertices: $A, B, C$
Edges: $AB = 4, BC = 5$

infoNote

Example 2: Writing a Weighted Matrix from a Network

Given the graph:

Vertices: $A, B, C, D$
Edges: $AB = 3, AC = 6, AD = 4, BC = 5$

Steps:

Assign rows/columns for vertices.
Fill weights:

\mathbf{W} = \begin{pmatrix} 0 & 3 & 6 & 4 \\ 3 & 0 & 5 & \infty \\ 6 & 5 & 0 & \infty \\ 4 & \infty & \infty & 0 \end{pmatrix}

Note Summary

infoNote

Common Mistakes

Misinterpreting weights: Ensure weights in a matrix correspond to correct edges.
Ignoring symmetry: For undirected graphs, matrices must be symmetric ( $a_{ij} = a_{ji}$ ).
Confusing zero entries: A zero entry often means no edge, except on the diagonal where it means no self-loop.
Mislabeling vertices: Ensure consistency between vertex labels and matrix rows/columns.
Forgetting edge directions: For directed graphs, entries may not be symmetric.

infoNote

Key Formulas and Concepts

Adjacency Matrix:

a_{ij} = \begin{cases} 1 & \text{if an edge exists between } i \text{ and } j, \\ 0 & \text{otherwise.} \end{cases}

Weighted Matrix:

a_{ij} = \begin{cases} \text{weight of edge between } i \text{ and } j, & \text{if an edge exists}, \\ \infty & \text{otherwise.} \end{cases}

Networks & Matrices Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1

10.3.1 Networks & Matrices

Introduction to Networks and Matrices

Adjacency Matrix

Example: Adjacency Matrix for an Undirected Graph

Weighted Matrix

Example: Weighted Matrix

Drawing a Network from a Matrix

Steps:

Example:

Writing a Matrix from a Network

Steps:

Example:

Worked Examples

Example 1: Drawing a Network from a Weighted Matrix

Example 2: Writing a Weighted Matrix from a Network

Note Summary

Common Mistakes

Key Formulas and Concepts

500K+ Students Use These Powerful Tools to Master Networks & Matrices For their A-Level Exams.

Other Revision Notes related to Networks & Matrices you should explore