Networks and graphs

Networks and graphs

IB MYP Maths Extended: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A network has vertices joined by edges; the degree of a vertex is the number of edges meeting there.
  • The sum of the degrees is twice the number of edges.
  • In a weighted network the length of a path is the sum of its weights.
  • An adjacency matrix has a 1 where two vertices are joined.
  • Euler routes use every edge once; Hamiltonian routes visit every vertex once.

Vertices, edges and degree

A network is made of vertices joined by edges; the degree of a vertex is the number of edges that meet there.

Take edges ABAB, ACAC, ADAD and BCBC: AA has degree 33, BB and CC have degree 22, and DD has degree 11.

Every edge has two ends, so the sum of all the degrees is twice the number of edges: 3+2+2+1=8=2×43+2+2+1=8=2\times4. The number of odd-degree vertices is always even.

ABCD
Four vertices and four edges

A network has 7 edges. What is the sum of the degrees of its vertices?

Paths and connected networks

A path follows edges without visiting any vertex twice; a network is connected if there is a path between every pair of vertices.

In the road network there are 77 paths from PP to TT: PQRTPQRT, PQRSTPQRST, PQSTPQST, PQSRTPQSRT, PRTPRT, PRSTPRST and PRQSTPRQST.

Listing systematically stops you missing paths or repeating them.

PQRST
A road network with vertices P to T

In the road network, which of these is not a path from P to T?

Weighted networks and shortest paths

Add the weights along each path; the route with the fewest edges is not always the shortest.

In a weighted network each edge has a number, such as a distance in km. The length of a path is the sum of its weights.

PRTPRT has the fewest edges but is longer than PQRSTPQRST.

w=4w=7w=2w=6w=3w=9w=5PQRST
Weights (w) are distances in km

PQRST

Working:
4 + 2 + 3 + 5
Length:
14 km

PQRT

Working:
4 + 2 + 9
Length:
15 km

PRT

Working:
7 + 9
Length:
16 km

PRQST

Working:
7 + 2 + 6 + 5
Length:
20 km

In the network above, what is the length of the path PRQST?

Adjacency matrices

An adjacency matrix records which vertices are joined: 1 for an edge, 0 for none.

For edges AB,AC,AD,BCAB,AC,AD,BC in the order A,B,C,DA,B,C,D:

(0111101011001000)\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}

It is symmetric and each row total is the degree. Each entry of M2\mathbf M^2 counts journeys of exactly two edges.

ABCD
The ferry network: edges AB, AC, BC and CD

Worked example

The ferry network has edges AB,AC,BC,CDAB,AC,BC,CD. How many two-edge journeys are there from CC to CC?

What does the total of row B in an adjacency matrix tell you?

Euler and Hamiltonian routes

An Euler trail uses every edge once; a Hamiltonian path visits every vertex once.

An Euler circuit is an Euler trail that returns to its start. The degrees tell you which exists. A Hamiltonian cycle visits every vertex once and returns to the start; there is no simple degree test, so look by trying.

ABCD
Edges AB, AC, BC and CD

No odd vertices

  • Euler circuit exists

Exactly two odd vertices

  • Euler trail exists, odd vertex to odd vertex

More than two odd vertices

  • No Euler route

Worked example

For the network with edges AB,AC,BC,CDAB,AC,BC,CD, find an Euler trail and a Hamiltonian path, and say whether a Hamiltonian cycle exists.

A network has four vertices with degrees 2, 2, 4 and 2. What kind of Euler route does it have?

Try an exam question

A network has edges ABAB, ACAC, BCBC and CDCD. Find the degree of each vertex and decide whether an Euler trail exists.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the degree of vertex AA?

1 mark, marked against the mark scheme

Revision notes