Revision NotesPast Papers
International ASMaths: Decision 1EdexcelRevision NotesAlgorithms on GraphsMinimum Spanning TreesNetworks & Matrices

Networks & Matrices (Edexcel International AS Maths: Decision 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 edge 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
  • A matrix is typically set up with the following labelling system
    • Rows are labelled with the 'from' vertices
    • Columns are labelled with the 'to' vertices

Networks & Matrices

What is an adjacency matrix?

  • An adjacency matrix is a square matrix
    • All of the vertices in the graph are listed as the headings for both the rows and columns
    • The leading diagonal is the the line going from the top left cell to the bottom right cell
  • An adjacency matrix can be used to show the number of direct connections between two vertices
  • An entry of 1 in the matrix means that there is a direct connection (i.e. an edge) between that pair of 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 0 or 1
  • A loop is indicated in an adjacency matrix with a value in the leading diagonal
    • In an undirected matrix the value in the leading diagonal will be 2
      • 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 direction, the value in the leading diagonal will be 1
      • You can only travel along the loop out of and back into the vertex in one direction
      • An undirected loop in a directed matrix will still have a value of 2
    • For a graph with no loops every entry in the leading diagonal will be 0
  • An undirected graph is symmetrical about the leading diagonal
    • A directed graph is not symmetrical about the leading diagonal

What is a distance matrix?

  • A distance matrix is different to an adjacency matrix
    • 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 is used to indicate that there is no connection (i.e. no edge) between a pair of vertices
  • An undirected network is symmetrical about the leading diagonal
    • A directed network is not symmetrical about the leading diagonal
  • When drawing a network from its distance matrix be careful when labelling the edges
    • For an undirected graph the two cells between a pair of vertices will be the same
      • Connect the vertices with one edge labelled with the relevant weight
    • For a directed graph where two cells between a pair of vertices have different values
      • Draw two edges between the vertices
      • 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:

    Did this page help you?

    Previous:Hamiltonian GraphsNext: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.