Networks and graphs
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 , , and : has degree , and have degree , and has degree .
Every edge has two ends, so the sum of all the degrees is twice the number of edges: . The number of odd-degree vertices is always even.
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 paths from to : , , , , , and .
Listing systematically stops you missing paths or repeating them.
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.
has the fewest edges but is longer than .
| PQRST | PQRT | PRT | PRQST | |
|---|---|---|---|---|
| Working | 4 + 2 + 3 + 5 | 4 + 2 + 9 | 7 + 9 | 7 + 2 + 6 + 5 |
| Length | 14 km | 15 km | 16 km | 20 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 in the order :
It is symmetric and each row total is the degree. Each entry of counts journeys of exactly two edges.
Worked example
The ferry network has edges . How many two-edge journeys are there from to ?
- 1
Write the matrix in the order . Row is and column is the same.
- 2
The to entry of is .
- 3
The three journeys are , and .
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.
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 , find an Euler trail and a Hamiltonian path, and say whether a Hamiltonian cycle exists.
- 1
Degrees: , , , . The odd vertices are and .
- 2
Exactly two odd vertices, so an Euler trail exists, starting at and ending at : .
- 3
A Hamiltonian path is , which visits every vertex once.
- 4
There is no Hamiltonian cycle, because has only one edge and cannot be left and re-entered.
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 , , and . Find the degree of each vertex and decide whether an Euler trail exists.
[3 marks]
- [1]Degrees: A = 2, B = 2, C = 3, D = 1.
- [1]Exactly two vertices (C and D) are odd.
- [1]So an Euler trail exists, from C to D.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the degree of vertex ?
1 mark, marked against the mark scheme
What is the degree of vertex ?
1 mark, marked against the mark scheme