Decision 4: Route Inspection

Question 1

What does the Chinese postman problem do?

Answer 1

Finds the shortest possible length of a journey that goes along every arc

Question 2

What is a Eulerian/traversable graph? (2)

Answer 2

A path can be made that returns to the starting point

The valency of every node is even

Question 3

What is a semi-Eulerian/semi-traversable graph? (2)

Answer 3

All arcs can be visited once, provided that the start and end vertices are different
Only two nodes have odd valency

Question 4

What is Königsberg? (5)

Answer 4

Two islands in a river and two riverbanks
One island connects to both sides with two bridges
The other island connects to both sides with one bridge
Both islands are connected
Is it possible to only cross each bridge once? (No)

Question 5

Prove that there must always be an even (or zero) number of vertices with odd valency in every graph (3)

Answer 5

Adding an arc adds two to the total valency of the graph - valency = 2 x number of arcs (handshaking lemma)
Therefore total valency is even
As total valency is even, every odd number must have a pair as odd + odd = even so there is an even number of odd valencies

Question 6

What is route inspection? (3)

Answer 6

Identify the odd nodes
Consider the minimum distance between all pairs of odd nodes
Repeat the minimum distance possible in order to make every valency even (graph is traversable)

Question 7

How does route inspection change if the start and end nodes can be different? (2)

Answer 7

There can be two nodes with odd valency (the start/end)

If there are four nodes with odd valency, repeat the shortest distance between any two odd nodes