Networks & Matrices (Edexcel A Level Further Maths): Revision Note

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

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

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

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