Revision NotesExam QuestionsPast Papers
A LevelFurther Maths: Decision Maths 1EdexcelRevision NotesAlgorithms on GraphsMinimum Spanning TreesNetworks & Matrices

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

Revision Note

Naomi C

Author

Naomi C

Last updated

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

Networks & Matrices

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

a)
Write down the adjacency matrix for the graph shown below.
 

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

table row blank cell table row bold A bold B bold C bold D bold E end table end cell row cell table row bold A row bold B row bold C row bold D row bold E end table end cell cell stretchy left parenthesis table row 0 1 1 0 1 row 1 0 0 0 0 row 1 0 1 1 1 row 0 0 0 0 1 row 2 1 1 1 2 end table stretchy right parenthesis end cell end table

 

b)
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

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:Planarity AlgorithmNext:Kruskal's Algorithm
    Naomi C

    Author: Naomi C

    Expertise: Maths

    Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.