Networks & Matrices

Introduction to Networks & Matrices

What is a network?

A network is a weighted graph
- A network is used to model real-world situations
- The weight of an arc usually represents a measure such as distance or time

What is a matrix?

A matrix can be used to represent a graph or network in the form of a table
The elements within the matrix give information about the connections between the different vertices

What is an adjacency matrix?

An adjacency matrix is a square matrix where all of the vertices in the graph are listed as the headings for both the rows and columns
An adjacency matrix can be used to show the number of direct connections between two vertices
An entry of 0 in the matrix means that there is no direct connection between that pair of vertices
In a simple graph the only entries are either 0 or 1
A loop is indicated in an adjacency matrix with a value in the leading diagonal (the line from top left to bottom right)

In an undirected matrix the value in the leading diagonal will be 2 because you can use the loop to travel out of and into the vertex in two different directions
In a directed matrix, if the loop has been given a direction, the value in the leading diagonal will be 1 as you can only travel along the loop out of and back into the vertex in one direction
For a graph with no loops every entry in the leading diagonal will be 0

An undirected graph will be symmetrical in the leading diagonal

What is a distance matrix?

A distance matrix is different to an adjacency matrix as the value in each cell is the weight of the edge connecting that pair of vertices

Weight could be cost, distance, time etc.

An empty cell can be used to indicate that there is no connection between a pair of vertices
A directed network is not symmetrical along the leading diagonal (the line from top left to bottom right)
When drawing a network from its distance matrix be careful when labelling the edges

For an un-directed graph the two cells between a specific pair of vertices will be the same so connect the vertices with one edge labelled with the relevant weight
For a directed graph if the two cells between a specific pair of vertices have different values draw two lines between the vertices and label each with the correct weight and direction

A distance matrix can be used to work out the weight of different walks in the network

Worked example

Write down the adjacency matrix for the graph shown below.

3-10-2-ib-hl-ai-walks--adjacency-matrices-we-1

$\begin{matrix} \begin{matrix} A & B & C & D & E \end{matrix} \\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & (\begin{matrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 2 & 1 & 1 & 1 & 2 \end{matrix}) \end{matrix}$

The table below shows the time taken in minutes to travel by car between 4 different towns.

	A	B	C	D
A		16	35
B	16		20	18
C	35	20		34
D		23	34

Draw the network described by this distance matrix.

qoHMRvSL_picture-1

Networks & Matrices (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Introduction to Networks & Matrices

What is a network?

What is a matrix?